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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nondeterministic Space is Closed under Complementation
• The method of forced enumeration for nondeterministic automata
• Turing machines with sublogarithmic space
• A survey on picture-walking automata
• Regulated Grammars and Automata
• Two-dimensional jumping finite automata
• Characterization and complexity results on jumping finite automata
• JUMPING FINITE AUTOMATA
• Simple picture processing based on finite automata and regular grammars
• Jumping Finite Automata: Characterizations and Complexity
• One-Way Jumping Finite 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)