Decidability of the equivalence problem for synchronous deterministic pushdown-store automata (Q1062450)
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: Decidability of the equivalence problem for synchronous deterministic pushdown-store automata |
scientific article; zbMATH DE number 3913681
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Decidability of the equivalence problem for synchronous deterministic pushdown-store automata |
scientific article; zbMATH DE number 3913681 |
Statements
Decidability of the equivalence problem for synchronous deterministic pushdown-store automata (English)
0 references
1984
0 references
A new subclass of deterministic pushdown automata (DPDA's) is determined and identified as ''synchronous''. The decidability of the equivalence problem is proved for synchronous DPDA's. An example is given of a context-free language that is accepted by a synchronous DPDA and is not accepted by any real-time DPDA.
0 references
deterministic pushdown automata
0 references
context-free language
0 references
synchronous DPDA
0 references
