Membership Problem for Two-Dimensional General Row Jumping Finite Automata

DOI10.1142/S0129054120500239zbMath1458.68106OpenAlexW3039253014MaRDI QIDQ5859631

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

complexitymembership problempicture languagesjumping automata

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The method of forced enumeration for nondeterministic automata
• Turing machines with sublogarithmic space
• Simple picture processing based on finite automata and regular grammars
• Characterization and complexity results on jumping finite automata
• Jumping Finite Automata: Characterizations and Complexity
• A Survey on Picture-Walking Automata
• Nondeterministic Space is Closed under Complementation
• JUMPING FINITE AUTOMATA
• Two-dimensional jumping finite automata
• Regulated Grammars and Automata
• One-Way Jumping Finite Automata

This page was built for publication: Membership Problem for Two-Dimensional General Row Jumping Finite Automata