On the equivalence, containment, and covering problems for the regular and context-free languages
From MaRDI portal
Publication:1229100
DOI10.1016/S0022-0000(76)80038-4zbMath0334.68044OpenAlexW1982206794MaRDI QIDQ1229100
Thomas G. Szymanski, Daniel J. Rosenkrantz, Harry B. III Hunt
Publication date: 1976
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(76)80038-4
Related Items (42)
Testing for grammatical coverings ⋮ Process Algebra and Model Checking ⋮ Rewriting regular inequalities ⋮ A theoretical framework for cardinality-based feature models: the semantics and computational aspects ⋮ Decidable sentences of Church-Rosser congruences ⋮ Boundedness testing for unambiguous context-free grammars ⋮ The language intersection problem for non-recursive context-free grammars ⋮ A survey of normal form covers for context-free grammars ⋮ Uniform data encodings ⋮ Algebraic rewritings for optimizing regular path queries. ⋮ Well-abstracted transition systems: Application to FIFO automata. ⋮ Regular languages with variables on graphs ⋮ Regular expression simplification ⋮ Words-to-Letters Valuations for Language Kleene Algebras with Variable Complements ⋮ Classifying the computational complexity of problems ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ Unnamed Item ⋮ A new proof technique to establish equivalence of the original and the generated lambda-free CFG with linear increase in size ⋮ NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES ⋮ The inclusion problem for some subclasses of context-free languages ⋮ On the complexity of finite, pushdown, and stack automata ⋮ Verifying polymer reaction networks using bisimulation ⋮ NFA reduction algorithms by means of regular inequalities ⋮ On the computational complexity of bisimulation, redux ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ The covering problem for linear context-free grammars ⋮ Regular path queries under approximate semantics ⋮ Bounded regular path queries in view-based data integration ⋮ Normal form algorithms for extended context-free grammars ⋮ ON THE EXISTENCE OF LOOKAHEAD DELEGATORS FOR NFA ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Minimal NFA and biRFSA Languages ⋮ From left-regular to Greibach normal form grammars ⋮ Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete ⋮ Efficient implementation of regular languages using reversed alternating finite automata ⋮ Counting problems for parikh images ⋮ Note on the complexity of Las Vegas automata problems ⋮ Implementing automata. Selected papers from the 2nd international workshop, WIA '97, Univ. of Western Ontario, London, Ontario, Canada, September 18--20, 1997 ⋮ On derivation preservation ⋮ Learning residual alternating automata ⋮ More on Minimizing Finite Automata with Errors — Nondeterministic Machines ⋮ Decidability of EDT0L structural equivalence
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Structural equivalence of context-free grammars
- Relationships between nondeterministic and deterministic tape complexities
- Computational Parallels between the Regular and Context-Free Languages
- Bounded Regular Sets
- A note on undecidable properties of formal languages
- Parenthesis Grammars
- On the equivalence and containment problems for context-free languages
- A characterization of parenthesis languages
- Properties of deterministic top-down grammars
- A Note Concerning Nondeterministic Tape Complexities
- On Languages Accepted in Polynomial Time
- On the Covering and Reduction Problems for Context-Free Grammars
This page was built for publication: On the equivalence, containment, and covering problems for the regular and context-free languages
