DPDA's in 'Atomic normal form' and applications to equivalence problems

DOI10.1016/0304-3975(81)90055-4zbMath0474.68065OpenAlexW2012313512MaRDI QIDQ1158965

Jean H. Gallier

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

zbMATH Keywords

deterministic pushdown automatarecursion schemesaddress languageencoding of trees

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (12)

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 ⋮ The tree equivalence problem for linear recursion schemes ⋮ 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