Deciding emptiness for stack automata on infinite trees (Q1333263)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Deciding emptiness for stack automata on infinite trees |
scientific article; zbMATH DE number 638556
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Deciding emptiness for stack automata on infinite trees |
scientific article; zbMATH DE number 638556 |
Statements
Deciding emptiness for stack automata on infinite trees (English)
0 references
13 September 1994
0 references
It is shown that the emptiness problem is decidable on stack automata on infinite trees. The authors give first an elementary proof for the corresponding problem on pushdown automata, and then they reduce the emptiness problem for stack automata to this special case. A computation of a stack automaton accepts an infinite tree if there are infinitely many accepting states on every path.
0 references
emptiness problem
0 references
stack automata
0 references
infinite trees
0 references
pushdown automata
0 references
0.789409875869751
0 references
0.77445387840271
0 references
0.7743175625801086
0 references
