An unsolvable algorithmic problem for deterministic real-time pushdown automata (Q2563381)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An unsolvable algorithmic problem for deterministic real-time pushdown automata |
scientific article |
Statements
An unsolvable algorithmic problem for deterministic real-time pushdown automata (English)
0 references
11 December 1996
0 references
The results of \textit{L. I. Stanevichene} [Sb. Nauch. Tr. Ross. Assots. ''Zhenshchiny-matematiki'', Nizhnii Novgorod, 112-117 (1993) (in Russian)] are extended to real time applications. The author proves the algorithmic unsolvency of the modified conjugacy graph problem. Then it follows that the idea to solve the problem of equivalence of deterministic pushdown store acceptors in real time can not be applied.
0 references
deterministic pushdown store acceptor
0 references
conjugation graph
0 references
