Decidable subcases of the equivalence problem for recursive program schemes

DOI10.1051/ita/1987210302451zbMath0634.68017OpenAlexW120038171MaRDI QIDQ3773319

Jean H. Gallier, Bruno Courcelle

Publication date: 1987

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92287

zbMATH Keywords

decidabilityequivalence problemprogram schemesdeterministic push-down automatapolyadic recursive schemes

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Abstract data types; algebraic specification (68Q65)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamental properties of infinite trees
• A representation of trees by languages. II
• The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine
• Algebraic semantics
• DPDA's in 'Atomic normal form' and applications to equivalence problems
• Completeness results for the equivalence of recursive schemas
• 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. I
• A representation of trees by languages. I
• Strict deterministic grammars
• The equivalence problem for real-time DPDAs
• On the Parsing of Deterministic Languages
• Initial Algebra Semantics and Continuous Algebras
• On jump-deterministic pushdown automata
• The decidability of equivalence for deterministic stateless pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata
• Finite-Turn Pushdown Automata
• Real-Time Strict Deterministic Languages

This page was built for publication: Decidable subcases of the equivalence problem for recursive program schemes