Regular Realizability Problems and Context-Free Languages
From MaRDI portal
Publication:5500698
DOI10.1007/978-3-319-19225-3_22zbMath1432.68244arXiv1503.00295OpenAlexW2284602210MaRDI QIDQ5500698
No author found.
Publication date: 7 August 2015
Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1503.00295
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
On computational complexity of set automata ⋮ On the decidability of finding a positive ILP-instance in a regular set of ILP-instances ⋮ From decidability to undecidability by considering regular sets of instances ⋮ Automata equipped with auxiliary data structures and regular realizability problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On regular realizability problems
- Detecting palindromes, patterns and borders in regular languages
- Rational indexes of generators of the cone of context-free languages
- Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $
- The Rational Index: A Complexity Measure for Languages
- Universality of Regular Realizability Problems
- One-Counter Verifiers for Decidable Languages
- An Infinite Hierarchy of Context-Free Languages
This page was built for publication: Regular Realizability Problems and Context-Free Languages