Regular Realizability Problems and Context-Free Languages

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

Mathematics Subject Classification ID

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