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

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