On computational complexity of set automata

DOI10.1016/J.IC.2021.104797OpenAlexW3198182215MaRDI QIDQ5918383

Mikhail N. Vyalyi, Alexander A. Rubtsov

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 complexitymembership problemformal languageemptiness problemrational coneset automaton

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• QRT FIFO automata, breadth-first grammars and their relations
• On emptiness and membership problems for set automata
• Set Automata
• Deterministic Set Automata
• On certain formal properties of grammars
• Efficient string matching
• Fast Pattern Matching in Strings
• The emptiness problem for intersections of regular languages
• Computational Complexity
• Regularity and Size of Set Automata
• Regular Realizability Problems and Context-Free Languages
• An Approach to a Unified Theory of Automata
• One-way stack automata
• On computational complexity of set automata

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