Boundary sets of regular and context-free languages

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

zbMATH Keywords

computational complexitydecidabilitycontext-free languagesregular languagesboundary setsvalid computations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Problems on finite automata and the exponential time hypothesis

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