Boundary sets of regular and context-free languages
From MaRDI portal
Publication:896680
DOI10.1016/j.tcs.2015.07.032zbMath1332.68114OpenAlexW1955289261MaRDI QIDQ896680
Markus Holzer, Sebastian Jakobi
Publication date: 10 December 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.07.032
computational complexitydecidabilitycontext-free languagesregular languagesboundary setsvalid computations
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Space-bounded reducibility among combinatorial problems
- On Minimising Automata with Errors
- From Equivalence to Almost-Equivalence, and Beyond—Minimizing Automata with Errors
- Hyper-minimizing minimized deterministic finite state automata
- Nondeterministic Space is Closed under Complementation
- Minimal NFA Problems are Hard
- On the State Complexity of Combined Operations
This page was built for publication: Boundary sets of regular and context-free languages