On regular realizability problems for context-free languages

DOI10.1134/S0032946015040043MaRDI QIDQ327306zbMATHOpenAlexFDO

Authors Mikhail Vyalyi, Alexander A. Rubtsov

Publication date 19 October 2016

Published in Problems of Information Transmission (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0032946015040043

Mathematics Subject Classification ID

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

Recommendations

• Regular Realizability Problems and Context-Free Languages
• On regular realizability problems
• On expressive power of regular realizability problems
• Universality of Regular Realizability Problems
• Rational index of context-free languages in exp \(\Theta(^ p\sqrt{n})\) and \(n^{\Theta((\ln n)^{1/p})}\)

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• 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 3677223 (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
• Computational Complexity
• Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $
• Detecting palindromes, patterns and borders in regular languages
• On expressive power of regular realizability problems
• 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

Cited in

(8)

• From decidability to undecidability by considering regular sets of instances
• On expressive power of regular realizability problems
• Properties of graphs specified by a regular language
• Properties of graphs specified by a regular language
• Regular Realizability Problems and Context-Free Languages
• Rational index of context-free languages in exp \(\Theta(^ p\sqrt{n})\) and \(n^{\Theta((\ln n)^{1/p})}\)
• On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
• On universality of regular realizability problems

This page was built for publication: On regular realizability problems for context-free languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q327306)