Degrees of asynchronously automaton transformations (Q647840): Difference between revisions

This paper considers finite asynchronous automata, which are quintuples \((S,\Sigma,\Sigma',\delta,\omega)\), where \(S\) is a finite set of states, \(\Sigma,\Sigma'\) are finite sets of input and output symbols, respectively, \(\delta:S\times \Sigma\to S\) is a next-state function and \(\omega:S\times \Sigma\to (\Sigma')^*\) is an output function. An asynchronous automaton is hence a finite machine taking a word over \(\Sigma\) as input and producing a word over \(\Sigma'\) as output. This paper considers only infinite inputs; the output is hence also an infinite word. An infinite word \(y\) is said to be reduced to another infinite word \(x\) if there is some finite asynchronous automaton producing \(y\) as output from input \(x\). Two infinite words \(x\), \(y\) are said to be equivalent if they both reduce to each other. This is clearly an equivalence relation. Furthermore the reduction relation induces a partial order on the set of equivalence classes of this equivalence relation. The paper studies this partial order. The author shows that there are continuum many atoms in this partial order. Furthermore she also shows that it embeds any finite order as an initial segment. Finally, a nonextensibility of embeddings of partial order is proved, which shows that the methods of [\textit{M. Lerman}, Degrees of unsolvability. Local and global theory. Berlin etc.: Springer-Verlag (1983; Zbl 0542.03023), Chapter II] cannot be used on this structure. These results generalize corresponding results of [\textit{G. Rayna}, Kibern. Sb., Nov. Ser. 14, 95--106 (1977; Zbl 0408.03038); \textit{V. R. Bairasheva}, Izv. Vyssh. Uchebn. Zaved., Mat. 1988, No. 7 (314), 34--39 (1988; Zbl 0659.68077)] for Mealy automata. A Mealy automaton is defined as a finite asynchronous automaton, but in this case the function \(\omega:S\times \Sigma\to \Sigma'\) produces a single character instead of a finite string.