Membership problem for two-dimensional general row jumping finite automata

DOI10.1142/S0129054120500239MaRDI QIDQ5859631zbMATH OpenOpenAlexFDO

Authors Grzegorz Madejski, Andrzej Szepietowski

Publication date 19 April 2021

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

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

zbMATH Keywords

complexityjumping automatamembership problempicture languages

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Two-dimensional jumping finite automata
• Decidability of right one-way jumping finite automata
• Decision problems for restricted variants of two-dimensional automata
• Decidability of right one-way jumping finite automata
• Two-way deterministic automata with jumping mode

Cites work

• A survey on picture-walking automata
• Characterization and complexity results on jumping finite automata
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Jumping finite automata
• Jumping finite automata: characterizations and complexity
• Nondeterministic Space is Closed under Complementation
• One-way jumping finite automata
• Regulated grammars and automata
• Simple picture processing based on finite automata and regular grammars
• The method of forced enumeration for nondeterministic automata
• Turing machines with sublogarithmic space
• Two-dimensional jumping finite automata

Cited in

(1)

• Decision problems for restricted variants of two-dimensional automata

This page was built for publication: Membership problem for two-dimensional general row jumping finite automata

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