Membership problem for two-dimensional general row jumping finite automata

DOI10.1142/S0129054120500239zbMATH Open1458.68106OpenAlexW3039253014MaRDI QIDQ5859631FDOQ5859631

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

complexitypicture languagesmembership problemjumping automata

Mathematics Subject Classification ID

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

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

• 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?)
• A survey on picture-walking automata
• Characterization and complexity results on jumping finite automata
• 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)