Regular Realizability Problems and Context-Free Languages

DOI10.1007/978-3-319-19225-3_22MaRDI QIDQ5500698zbMATH OpenOpenAlexFDO

Authors

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3909763 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 1142312 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• An Infinite Hierarchy of Context-Free Languages
• Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $
• Detecting palindromes, patterns and borders in regular languages
• On regular realizability problems
• One-counter verifiers for decidable languages
• Rational indexes of generators of the cone of context-free languages
• The Rational Index: A Complexity Measure for Languages
• Universality of Regular Realizability Problems

Cited in

(10)

• Rational index of languages defined by grammars with bounded dimension of parse trees
• scientific article; zbMATH DE number 1822166 (Why is no real title available?)
• scientific article; zbMATH DE number 1134630 (Why is no real title available?)
• 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)