Automata equipped with auxiliary data structures and regular realizability problems

DOI10.1007/978-3-030-93489-7_13MaRDI QIDQ2096592zbMATH OpenOpenAlexFDO

Authors Alexander A. Rubtsov, Mikhail Vyalyi

Publication date 9 November 2022

Full work available at URL https://arxiv.org/abs/2210.03934

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• An Approach to a Unified Theory of Automata
• Detecting palindromes, patterns and borders in regular languages
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 1222108 (Why is no real title available?)
• On computational complexity of set automata
• On emptiness and membership problems for set automata
• On Models of a Nondeterministic Computation
• On regular realizability problems
• On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
• Regular Realizability Problems and Context-Free Languages
• Set automata
• The bag automaton: a model of nondeterministic storage

Cited in

(3)

• Properties of graphs specified by a regular language
• On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
• New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines

This page was built for publication: Automata equipped with auxiliary data structures and regular realizability problems

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