scientific article; zbMATH DE number 17554

DOI10.1007/3-540-51498-8_36MaRDI QIDQ3974879zbMATH OpenFDO

Authors Kai Salomaa

Publication date 26 June 1992

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-51498-8_36

zbMATH Keywords

alternating yield languagesalternationautomata on treesread-only finite-state automatarecursively enumerabletree automatontree structuresTuring computability

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10) Formal languages and automata (68Q45)

Review text

The paper sheds some new light on Turing computability, alternation and tree structures. Searching for an exact bound for the complexity of alternating yield languages, the author discovers that, surprisingly enough, any recursively enumerable (r.e.) set of words can be presented as the yield of a forest recognizable by a finite alternating frontier- to-root tree automaton. The interest of this new characterization of r.e. languages lies in the apparent simplicity of the computational models involved (read-only finite-state automata), as well as in the unexpected strength of alternation. The paper is a sequel to a series of articles by the author investigating alternating automata on trees. For the entire collection see [Zbl 0764.20028].

Recommendations

• Yield-languages recognized by alternating tree recognizers
• scientific article; zbMATH DE number 4083011
• scientific article; zbMATH DE number 3967934
• Morphic characterizations of languages in Chomsky hierarchy with insertion and locality
• scientific article; zbMATH DE number 3945364

Cited in

(4)

• A representation of recursively enumerable languages by two homomorphisms and a quotient
• Synchronized tree automata
• Representing recursively enumerable languages by iterated deletion
• Yield-languages recognized by alternating tree recognizers

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3974879)