Automata equipped with auxiliary data structures and regular realizability problems

DOI10.1142/S0129054124420073MaRDI QIDQ7316811zbMATH OpenFDO

Authors Alexander A. Rubtsov, Mikhail Vyalyi

Publication date 20 August 2026

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054124420073

Mathematics Subject Classification ID

Data structures (68P05) Classical models of computation (Turing machines, etc.) (68Q04) Formal languages and automata (68Q45)

Cites work

• Detecting palindromes, patterns and borders in regular languages
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 1222108 (Why is no real title available?)
• Interconvertibility of a class of set constraints and context-free-language reachability
• On computational complexity of set automata
• On computational complexity of set automata
• On emptiness and membership problems for set automata
• On expressive power of regular realizability problems
• 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
• On the security of ping-pong protocols
• Reachability analysis of pushdown automata: Application to model-checking
• Regular Realizability Problems and Context-Free Languages
• Set automata
• The bag automaton: a model of nondeterministic storage

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 Q7316811)