Abstract | ||
---|---|---|
Asynchronous two-dimensional iterative arrays of automata will be introduced where the underlying automata are not of Moore-type but of Mealy-type. We will prove that there exists a Mealy automaton, $$\\mathfrak{U}_{ 0} $$, with only two states and one input and output for each of its four distinguished directions, such that any given Mealy-automaton can be realized by an iterative array with only $$\\mathfrak{U}_{ 0} $$ for its component-machines. It is known that loop-free nets cannot be as powerful as Mealy automata; however, we will show that any Mealy automaton can be realized by a network, N, with very restrictive component machines, where no signal may pass a loop in N. Using this fact asynchronous iterative arrays can be built up with one component machine, $$\\mathfrak{U}_{ 1} $$ such that any given Mealy automaton can be realized under the restriction that no signal passes a loop more than once. $$\\mathfrak{U}_{ 1} $$ contains only four states and one input and output for each direction. |
Year | DOI | Venue |
---|---|---|
1980 | 10.1007/BF00288646 | Acta Inf. |
Keywords | Field | DocType |
Information System,Operating System,Data Structure,Communication Network,Information Theory | Information theory,Discrete mathematics,Asynchronous communication,Data structure,Combinatorics,Telecommunications network,Existential quantification,Automaton,Input/output,Mathematics | Journal |
Volume | Issue | ISSN |
13 | 3 | 0001-5903 |
Citations | PageRank | References |
2 | 0.39 | 5 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hans Kleine Brining | 1 | 5 | 0.76 |
Lutz Priese | 2 | 240 | 31.41 |