On computational complexity of set automata

DOI10.1016/J.IC.2021.104797MaRDI QIDQ5918383zbMATH OpenOpenAlexFDO

Authors Alexander A. Rubtsov, Mikhail Vyalyi

Publication date 25 November 2021

Published in Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityformal languagemembership problememptiness problemrational coneset automaton

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On computational complexity of set automata
• On emptiness and membership problems for set automata
• Deterministic set automata
• Set automata
• Regularity and size of set automata

Cites work

• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1222108 (Why is no real title available?)
• An Approach to a Unified Theory of Automata
• Computational Complexity
• Deterministic set automata
• Efficient string matching
• Fast Pattern Matching in Strings
• On certain formal properties of grammars
• On computational complexity of set automata
• On emptiness and membership problems for set automata
• One-way stack automata
• QRT FIFO automata, breadth-first grammars and their relations
• Regular Realizability Problems and Context-Free Languages
• Regularity and size of set automata
• Set automata
• The bag automaton: a model of nondeterministic storage
• The emptiness problem for intersections of regular languages

Cited in

(6)

• Set automata
• On emptiness and membership problems for set automata
• On the computational complexity of P automata
• Descriptive set theoretic methods in automata theory. Decidability and topological complexity
• On computational complexity of set automata
• Deterministic set automata

This page was built for publication: On computational complexity of set automata

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