Inclusion between the frontier language of a non-deterministic recursive program scheme and the Dyck language is undecidable
From MaRDI portal
Publication:2422040
DOI10.1016/j.tcs.2018.09.035zbMath1429.68120OpenAlexW2909807115MaRDI QIDQ2422040
Publication date: 18 June 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2018.09.035
Formal languages and automata (68Q45) Decidability (number-theoretic aspects) (11U05) Grammars and rewriting systems (68Q42) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)
Related Items
General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond ⋮ Unboundedness problems for machines with reversal-bounded counters ⋮ General decidability results for asynchronous shared-memory programs: higher-order and beyond ⋮ Unnamed Item
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The IO- and OI-hierarchies
- The IO and OI hierarchies revisited
- Monoid-Based Approach to the Inclusion Problem on Superdeterministic Pushdown Automata
- THE INCLUSION PROBLEM OF CONTEXT-FREE LANGUAGES: SOME TRACTABLE CASES
- Superdeterministic PDAs
- On word and frontier languages of unsafe higher-order grammars
- Types and higher-order recursion schemes for verification of higher-order programs
- An automata-theoretic approach to branching-time model checking
- Model Checking Higher-Order Programs
- Verifying higher-order functional programs with pattern-matching algebraic data types
- Foundations of Software Science and Computational Structures
- Complexity Results on Balanced Context-Free Languages
This page was built for publication: Inclusion between the frontier language of a non-deterministic recursive program scheme and the Dyck language is undecidable
