On expressive power of regular realizability problems

DOI10.1134/S0032946013030058zbMath1323.68348OpenAlexW2009902341MaRDI QIDQ2262977

Mikhail N. Vyalyi

Publication date: 17 March 2015

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

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

Cites Work

• Detecting palindromes, patterns and borders in regular languages
• Nondeterministic Space is Closed under Complementation
• Relativization of questions about log space computability
• Adaptive logspace reducibility and parallel time
• Relationships among $PL$, $\#L$, and the determinant
• Making Nondeterminism Unambiguous
• Computational Complexity
• On Context-Free Languages
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On expressive power of regular realizability problems