Regular Realizability Problems and Context-Free Languages
From MaRDI portal
Publication:5500698
DOI10.1007/978-3-319-19225-3_22zbMATH Open1432.68244arXiv1503.00295OpenAlexW2284602210MaRDI QIDQ5500698FDOQ5500698
Authors:
Publication date: 7 August 2015
Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)
Abstract: We investigate regular realizability (RR) problems, which are the problems of verifying whether intersection of a regular language -- the input of the problem -- and fixed language called filter is non-empty. In this paper we focus on the case of context-free filters. Algorithmic complexity of the RR problem is a very coarse measure of context-free languages complexity. This characteristic is compatible with rational dominance. We present examples of P-complete RR problems as well as examples of RR problems in the class NL. Also we discuss RR problems with context-free filters that might have intermediate complexity. Possible candidates are the languages with polynomially bounded rational indices.
Full work available at URL: https://arxiv.org/abs/1503.00295
Recommendations
- On regular realizability problems for context-free languages
- On regularity of context-free languages
- Regularity Problems for Visibly Pushdown Languages
- On decidability of regular languages theories
- On decidability of theories of regular languages
- Towards a theory of complexity of regular languages
- scientific article; zbMATH DE number 1134630
- On the complexity of realization of finite languages by formulas
- Regularity and context-freeness over word rewriting systems
- On the boundary of regular languages
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- On regular realizability problems
- Title not available (Why is that?)
- 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 $
- Title not available (Why is that?)
- The Rational Index: A Complexity Measure for Languages
- Title not available (Why is that?)
- One-counter verifiers for decidable languages
- Title not available (Why is that?)
- An Infinite Hierarchy of Context-Free Languages
- Universality of Regular Realizability Problems
Cited In (10)
- Rational index of languages defined by grammars with bounded dimension of parse trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- On computational complexity of set automata
- On regular realizability problems for context-free languages
- 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
- On universality of regular realizability problems
- On expressive power of regular realizability problems
- Automata equipped with auxiliary data structures and regular realizability problems
This page was built for publication: Regular Realizability Problems and Context-Free Languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5500698)
