On regular realizability problems

DOI10.1134/S003294601104003XzbMath1276.68083MaRDI QIDQ375967

Mikhail N. Vyalyi

Publication date: 1 November 2013

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

Mathematics Subject Classification ID

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

Related Items

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 ⋮ Regular Realizability Problems and Context-Free Languages ⋮ Automata equipped with auxiliary data structures and regular realizability problems

Cites Work

• Unnamed Item
• Unnamed Item
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• On Models of a Nondeterministic Computation
• A note on succinct representations of graphs
• Computational Complexity