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

Talkback

Downloads

Information
category of automata (Topic)
Definition 0.1   A classical automaton $\mathcal A$, (or simply automaton, 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),$

with $\delta$ being called the transition function and $\lambda$ being called the output function.

Definition 0.2   A categorical automaton $\mathcal A_C$ or discrete and finite/countable, categorical dynamic system is defined by a commutative square diagram containing all of the above components and assuming that $S_A$ is either a countable or finite set of discrete states:

$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ {I \times S }\ar[r]^{\delta}\ar[d]_{t}&{S}\ar[d]^{o}\ {S \times S}\ar[r]_{\lambda}&{O} } } \end{xy}$

With the above definition one can now define morphisms between automata and their composition. If the automata are defined by square diagrams such as the one shown above, and diagrams are defined by their associated functors, then automata homomorphisms are in fact defined as natural transformations between diagram functors. One also has a consistent, simpler definition as follows.

Definition 0.3   A homomorphism of automata 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 now we have sufficient data to define the category of automata and automaton homomorphisms.

Definition 0.4   The category of automata is a category of automata quintuples $(I_X, O_X, X, {\delta}_X: I_X \times X \rightarrow X; {\lambda}_X: X \times X \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 $\mathcal{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 (UT) 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 when all its transitions are reversible; then its state space is a groupoid. The category of reversible automata is then a 2-category, and also a subcategory of the 2-category of groupoids, or the groupoid category.

Remarks:

Other definitions of automata, sequential machines, semigroup automata or cellular automata lead to subcategories of the category of automata defined above. On the other hand, the category of quantum automata is not a subcategory of the automata category defined here.



"category of automata" is owned by bci1.

View style:

See Also: category of quantum automata, computer, supercomputer, automaton, categories of quantum automata and quantum computers, supercomputers

Other names:  Universal Turing (UT) machines, UTs
Also defines:  automaton, sequential machine, categorical automaton, automata homomorphism, automaton configuration, sequential machine, fuzzy automaton, computer simulations, Universal Turing (UT) machines, UT, abstract automata theory (AAT), AAT, abstract computer programming theory (ACPT), automaton square diagram, automata homomorphism as natural transformation
Keywords:  categories of automata and their transformations, algebraic theories, structure and semantics, universal Turing machines, variable automata, fuzzy automata, semigroups, semigroup homomorphisms, automata homomorphisms, Cartesian closed category

Cross-references: category of quantum automata, groupoid category, 2-category, groupoid, category, supercomputers, robots, state space, semigroup, commute, commutativity, homomorphism, natural transformations, functors, diagrams, square diagrams, composition, morphisms, commutative square diagram, dynamic system, output function, transition function, classical automaton
There are 17 references to this object.

This is version 33 of category of automata, born on 2009-01-25, modified 2010-06-09.
Object id is 430, canonical name is CategoryOfAutomata.
Accessed 4403 times total.

Classification:
Physics Classification: 00. (GENERAL)
 02. (Mathematical methods in physics)
 03. (Quantum mechanics, field theories, and special relativity )
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 "