On regular realizability problems for context-free languages

DOI10.1134/S0032946015040043zbMath1386.68098OpenAlexW2341616572MaRDI QIDQ327306

Mikhail N. 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)

Related Items (4)

Properties of graphs specified by a regular language ⋮ Properties of graphs specified by a regular language ⋮ 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

Cites Work

• On regular realizability problems
• Detecting palindromes, patterns and borders in regular languages
• Rational indexes of generators of the cone of context-free languages
• On expressive power of regular realizability problems
• Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $
• The Rational Index: A Complexity Measure for Languages
• One-Counter Verifiers for Decidable Languages
• Computational Complexity
• An Infinite Hierarchy of Context-Free Languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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