6533b870fe1ef96bd12cf9a4

RESEARCH PRODUCT

Representation of Autonomous Automata

Janis BulsRoberts GlaudinsVaira Buza

subject

Krohn–Rhodes theoryDiscrete mathematicsNested wordFinite-state machineMathematics::Operator AlgebrasComputer scienceSemigroupTimed automatonω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesMobile automatonAutomatonNondeterministic finite automaton with ε-movesStochastic cellular automatonDeterministic finite automatonDFA minimizationDeterministic automatonContinuous spatial automatonSpecial classes of semigroupsQuantum finite automataAutomata theoryTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Formal Languages and Automata Theory

description

An autonomous automaton is a finite automaton with output in which the input alphabet has cardinality one when special reduced. We define the transition from automata to semigroups via a representation successful if given two incomparable automata (neither simulate the other), the semigroups representing the automata are distinct. We show that representation by the transition semigroup is not successful. We then consider a representation of automata by semigroups of partial transformations. We show that in general transition from automata to semigroups by this representation is not successful either. In fact, the only successful transition presented is the transiton to this semigroup of partial transformations together with its generating set, and in this case success occurs only with autonomous automata.

yearjournalcountryeditionlanguage
2001-01-01
https://doi.org/10.1007/3-540-44669-9_35