Deciding emptiness for stack automata on infinite trees (Q1333263)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Deciding emptiness for stack automata on infinite trees |
scientific article |
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
