Degrees of asynchronously automaton transformations
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.
- Some Algebraic Properties of Machine Poset of Infinite Words
- Semigroups arising from asynchronous automata.
- scientific article; zbMATH DE number 4078815
- Finite-state automata on infinite inputs
- Transducer degrees: atoms, infima and suprema
- scientific article; zbMATH DE number 3976377
- scientific article; zbMATH DE number 1948506
- Automata on infinite words. Ecole de Printemps d'Informatique Théorique, Le Mont Dore, May 14-18, 1984
- Algorithmic solvability of comparison problems for finitely ambiguous sequence transducers on superwords
- Automata transformations of prefix decidable and decidable by Buchi superwords
- The degree of squares is an atom
- scientific article; zbMATH DE number 3904569 (Why is no real title available?)
- scientific article; zbMATH DE number 4078815 (Why is no real title available?)
- scientific article; zbMATH DE number 8116 (Why is no real title available?)
- Degrees of infinite words, polynomials and atoms
- Automaton transformations and monadic theories of infinite sequences
This page was built for publication: Degrees of asynchronously automaton transformations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q647840)
