No label defined (Q3974879)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 17554
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 17554 |
Statements
26 June 1992
0 references
read-only finite-state automata
0 references
Turing computability
0 references
alternation
0 references
tree structures
0 references
alternating yield languages
0 references
recursively enumerable
0 references
tree automaton
0 references
automata on trees
0 references
0.7459049224853516
0 references
0.7111694812774658
0 references
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].
0 references
