The inclusion problem for simple languages
From MaRDI portal
Publication:1235014
DOI10.1016/0304-3975(76)90074-8zbMath0349.68032OpenAlexW2078050093MaRDI QIDQ1235014
Publication date: 1976
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(76)90074-8
Related Items (31)
From Security Protocols to Pushdown Automata ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ Bisimulation equivalence and regularity for real-time one-counter automata ⋮ A generic framework for checking semantic equivalences between pushdown automata and finite-state automata ⋮ Decision problems for pushdown threads ⋮ Superdeterministic DPDAs: The method of accepting does affect decision problems ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Unnamed Item ⋮ A representation of trees by languages. II ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ The different shades of infinite session types ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ DPDA's in 'Atomic normal form' and applications to equivalence problems ⋮ New techniques for proving the decidability of equivalence problem ⋮ Unnamed Item ⋮ On deciding some equivalences for concurrent processes ⋮ Nested session types ⋮ The inclusion problem for some subclasses of context-free languages ⋮ Unnamed Item ⋮ Infinite trees in normal form and recursive equations having a unique solution ⋮ Complexity of universality and related problems for partially ordered NFAs ⋮ Unnamed Item ⋮ On the complexity of checking semantic equivalences between pushdown processes and finite-state processes ⋮ A representation of trees by languages. I ⋮ Two decidability results for deterministic pushdown automata ⋮ String Analysis as an Abstract Interpretation ⋮ On equivalence of grammars through transformation trees ⋮ Monadic recursion schemes: The effect of constants ⋮ Monoid-Based Approach to the Inclusion Problem on Superdeterministic Pushdown Automata ⋮ Constructing a realtime deterministic pushdown automaton from a grammar ⋮ A NOTE ON LIMITED PUSHDOWN ALPHABETS IN STATELESS DETERMINISTIC PUSHDOWN AUTOMATA
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The equivalence problem for deterministic two-tape automata
- Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
- Decidable Properties of Monadic Functional Schemas
- Decidable and Undecidable Questions About Automata
- The theory of languages
- Properties of deterministic top-down grammars
- Real-Time Strict Deterministic Languages
This page was built for publication: The inclusion problem for simple languages
