Decidable subcases of the equivalence problem for recursive program schemes

DOI10.1051/ITA/1987210302451MaRDI QIDQ3773319zbMATH OpenOpenAlexFDO

Authors Jean 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

decidabilitydeterministic push-down automataequivalence problempolyadic recursive schemesprogram schemes

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2086674
• scientific article; zbMATH DE number 1670473
• scientific article; zbMATH DE number 2081092
• Decidability of the equivalence problem for deterministic pushdown automata
• scientific article; zbMATH DE number 1738657

Cites work

• A representation of trees by languages. I
• A representation of trees by languages. II
• Algebraic semantics
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• Completeness results for the equivalence of recursive schemas
• DPDA's in 'Atomic normal form' and applications to equivalence problems
• Equivalence problems for deterministic context-free languages and monadic recursion schemes
• Finite-Turn Pushdown Automata
• Fundamental properties of infinite trees
• scientific article; zbMATH DE number 3958760 (Why is no real title available?)
• scientific article; zbMATH DE number 3540387 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• Initial Algebra Semantics and Continuous Algebras
• IO and OI. I
• On jump-deterministic pushdown automata
• On the Parsing of Deterministic Languages
• Real-Time Strict Deterministic Languages
• Strict deterministic grammars
• The decidability of equivalence for deterministic stateless pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata
• The equivalence problem for real-time DPDAs
• The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine

Cited in

(14)

• The undecidability of some equivalence problems concerning ngsm's and finite substitutions
• The tree equivalence of linear recursion schemes
• On the decidability of the equivalence problem for orthogonal sequential programs
• scientific article; zbMATH DE number 1670473 (Why is no real title available?)
• A note on the decidability of subword inequalities
• scientific article; zbMATH DE number 5572668 (Why is no real title available?)
• Regular algebra of functionals of labeled trees
• Decidable problems for powerful programs
• On the Decidability of the Equivalence Problem for Monadic Recursive Programs
• The decidable properties of subrecursive functions
• scientific article; zbMATH DE number 1456960 (Why is no real title available?)
• A short proof of the decidability of normalization in recursive program schemes
• Automata, Languages and Programming
• Equivalent transformations of recursive schemes with finite deconvolution

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3773319)