DPDA's in 'Atomic normal form' and applications to equivalence problems
From MaRDI portal
Publication:1158965
DOI10.1016/0304-3975(81)90055-4zbMath0474.68065OpenAlexW2012313512MaRDI QIDQ1158965
Publication date: 1981
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(81)90055-4
Related Items
Decidable subcases of the equivalence problem for recursive program schemes ⋮ Recursion-closed algebraic theories ⋮ On second-order iterative monads ⋮ Tree equivalence of linear recursive schemata is polynomial-time decidable ⋮ Pushdown tree automata ⋮ Deterministic finite automata with recursive calls and DPDAs ⋮ The tree equivalence of linear recursion schemes ⋮ A NOTE ON LIMITED PUSHDOWN ALPHABETS IN STATELESS DETERMINISTIC PUSHDOWN AUTOMATA ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ Fundamental properties of infinite trees ⋮ Tree pushdown automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Superdeterministic DPDAs: The method of accepting does affect decision problems
- A representation of trees by languages. II
- Recursion-closed algebraic theories
- Regular trees and the free iterative theory
- Deterministic one-counter automata
- Program equivalence and context-free grammars
- A result on the equivalence problem for deterministic pushdown automata
- Completeness results for the equivalence of recursive schemas
- The inclusion problem for simple languages
- Equivalence problems for deterministic context-free languages and monadic recursion schemes
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- IO and OI. II
- Simple program schemes and formal languages
- Strict deterministic grammars
- Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
- The equivalence problem for real-time strict deterministic languages
- On the Parsing of Deterministic Languages
- Initial Algebra Semantics and Continuous Algebras
- Simple context-free languages and free monadic recursion schemes
- On jump-deterministic pushdown automata
- The decidability of equivalence for deterministic stateless pushdown automata
- The equivalence problem for deterministic finite-turn pushdown automata
- Tree-Manipulating Systems and Church-Rosser Theorems
This page was built for publication: DPDA's in 'Atomic normal form' and applications to equivalence problems
