Physics Library
 An open source physics library
Encyclopedia | Forums | Docs | Random | Template Test |  
Login
create new user
Username:
Password:
forget your password?
Main Menu
Sections

Meta

Talkback

Downloads

Information
automaton (Definition)
Definition 0.1   A (classical) automaton, s-automaton $\mathcal A$, or sequential machine, is defined as a quintuple of sets, $I$,$O$ and $S$, and set-theoretical mappings,

$\displaystyle (I, O, S, \delta: I \times S \rightarrow S; \lambda: S \times S \rightarrow O),$

where $I$ is the set of s-automaton inputs, $S$ is the set of states (or the state space of the s-automaton), $O$ is the set of s-automaton outputs, $\delta$ is the transition function that maps an s-automaton state $s_i$ onto its next state $s_{i+1}$ in response to a specific s-automaton input $i \in I$, and $\lambda$ is the output function that maps couples of consecutive (or sequential) s-automaton states $(s_i, s_{i+1})$ onto s-automaton outputs $o_{i+1}$:

$\displaystyle (s_i, s_{i+1}) \mapsto o_{i+1}$

(hence the older name of sequential machine for an s-automaton).

Definition 0.2   A categorical automaton can also be defined by a commutative square diagram containing all of the above components.

With the above automaton definition(s) one can now also define morphisms between automata and their composition.

Definition 0.3   A homomorphism of automata or automata homomorphism is a morphism of automata quintuples that preserves commutativity of the set-theoretical mapping compositions of both the transition function $\delta$ and the output function $\lambda$.

With the above two definitions one now has sufficient data to define the category of automata and automata homomorphisms.

Definition 0.4   A category of automata is defined as a category of quintuples $(I, O, X, \delta: I \times X \rightarrow X; \lambda: X \times S \rightarrow O)$ and automata homomorphisms $h:{\mathcal A}_i \rightarrow {\mathcal A}_j$, such that these homomorphisms commute with both the transition and the output functions of any automata ${\mathcal A}_i$ and ${\mathcal A}_j$.

Remarks:

  1. Automata homomorphisms can be considered also as automata transformations or as semigroup homomorphisms, when the state space, $X$, of the automaton is defined as a semigroup $S$.
  2. Abstract automata have numerous realizations in the real world as : machines, robots, devices, computers, supercomputers, always considered as discrete state space sequential machines.
  3. Fuzzy or analog devices are not included as standard automata.
  4. Similarly, variable (transition function) automata are not included, but Universal Turing machines are.
Definition 0.5   An alternative definition of an automaton is also in use: as a five-tuple $(S, \Sigma, \delta, I, F)$, where $\Sigma$ is a non-empty set of symbols $\alpha$ such that one can define a configuration of the automaton as a couple $(s,\alpha)$ of a state $s \in S $ and a symbol $\alpha \in \Sigma $. Then $\delta$ defines a “next-state relation, or a transition relation” which associates to each configuration $(s, \alpha)$ a subset $\delta (s,\alpha)$ of S- the state space of the automaton. With this formal automaton definition, the category of abstract automata can be defined by specifying automata homomorphisms in terms of the morphisms between five-tuples representing such abstract automata.
Example 0.1   A special case of automaton is that of a stable automaton when all its state transitions are reversible; then its state space can be seen to possess a groupoid (algebraic) structure. The category of reversible automata is then a 2-category, and also a subcategory of the 2-category of groupoids, or the groupoid category.
Definition 0.6   An alternative definition of an automaton is also in use: as a five-tuple $(S, \Sigma, \delta, I, F)$, where $\Sigma$ is a non-empty set of symbols $\alpha$ such that one can define a configuration of the automaton as a couple $(s,\alpha)$ of a state $s \in S $ and a symbol $\alpha \in \Sigma $. Then $\delta$ defines a “next-state relation, or a transition relation” which associates to each configuration $(s, \alpha)$ a subset $\delta (s,\alpha)$ of S- the state space of the automaton. With this formal automaton definition, the category of abstract automata can be defined by specifying automata homomorphisms in terms of the morphisms between five-tuples representing such abstract automata.
Example 0.2  

A special case of automaton is that of a stable automaton when all its state transitions are reversible; then its state space can be seen to possess a groupoid (algebraic) structure. The category of reversible automata is then a 2-category, and also a subcategory of the 2-category of groupoids, or the groupoid category.



"automaton" is owned by bci1.
View style:
See Also: category of automata, general dynamic systems

Other names:  classical automaton, sequential machine, abstract automaton
Also defines:  s-automaton, categorical automaton, sequential machine, stable automaton, state space, transition function, classical automaton, sequential machine, state space, set of automaton states, output function, automata homomorphism, \delta~, \lambda~
Keywords:  s-automaton, state space, sequential machine, stable automaton, transition function, clasical automaton, sequential machine, set of automaton states, output function, automata homomorphism

Cross-references: groupoid category, 2-category, algebraic, groupoid, supercomputers, robots, semigroup, commute, category, category of automata, commutativity, homomorphism, composition, morphisms, commutative square diagram
There are 18 references to this object.

This is version 11 of automaton, born on 2009-01-27, modified 2009-02-26.
Object id is 442, canonical name is Automaton2.
Accessed 4268 times total.

Classification:
Physics Classification: 00. (GENERAL)
 02. (Mathematical methods in physics)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:

No messages.

Testing some escape charachters for html category with a generator has an injective cogenerator" now escape ” with "