On regular realizability problems

DOI10.1134/S003294601104003XMaRDI QIDQ375967zbMATHFDO

Authors Mikhail 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)

Recommendations

• On expressive power of regular realizability problems
• Universality of Regular Realizability Problems
• On regular realizability problems for context-free languages
• Regular Realizability Problems and Context-Free Languages
• On the complexity of realization of finite languages by formulas

Cites work

• scientific article; zbMATH DE number 3271692 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• A note on succinct representations of graphs
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Computational Complexity
• On Models of a Nondeterministic Computation

Cited in

(14)

• Automata equipped with auxiliary data structures and regular realizability problems
• From decidability to undecidability by considering regular sets of instances
• Universality of Regular Realizability Problems
• The realizability problem for Golovach-type functions
• On expressive power of regular realizability problems
• scientific article; zbMATH DE number 1415124 (Why is no real title available?)
• On excluded minors for real-representability
• Regular Realizability Problems and Context-Free Languages
• Deciding regular intersection emptiness of complete problems for PSPACE and the polynomial hierarchy
• Orbits of linear maps and regular languages
• Orbits of linear maps and properties of regular languages
• On regular realizability problems for context-free languages
• 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

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