Decision problems and projection languages for restricted variants of two-dimensional automata

DOI10.1016/J.TCS.2020.12.028MaRDI QIDQ2029491zbMATH OpenOpenAlexFDO

Authors Taylor J. Smith, Kai Salomaa

Publication date 3 June 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2020.12.028

zbMATH Keywords

decision problemlanguage emptinesslanguage equivalenceprojection languagethree-way automatatwo-dimensional automatatwo-way automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Decision problems for restricted variants of two-dimensional automata
• Some results concerning two-dimensional turing machines and finite automata
• Three-way automata on rectangular types over a one-letter alphabet
• Some remarks on two-dimensional finite automata
• Complexity and decidability for restricted classes of picture languages

Cites work

• A note on decision problems for three-way two-dimensional finite automata
• A survey of two-dimensional automata theory
• A survey on picture-walking automata
• Accepting runs in a two-way finite automaton
• Checking automata and one-way stack languages
• Classification of string languages via tiling recognizable picture languages
• Context-sensitive string languages and recognizable picture languages
• Decision problems for restricted variants of two-dimensional automata
• Hierarchies of complete problems
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3738961 (Why is no real title available?)
• scientific article; zbMATH DE number 3557270 (Why is no real title available?)
• scientific article; zbMATH DE number 3302285 (Why is no real title available?)
• Matrix-based complexity functions and recognizable picture languages
• New operations and regular expressions for two-dimensional languages over one-letter alphabet
• Some results concerning two-dimensional turing machines and finite automata
• Theory Is Forever
• Three-way automata on rectangular types over a one-letter alphabet

Cited in

(6)

• Two-dimensional automata with rotated inputs (projection-type)
• Decision problems for restricted variants of two-dimensional automata
• Some results concerning two-dimensional turing machines and finite automata
• scientific article; zbMATH DE number 7770057 (Why is no real title available?)
• 2D oxide picture languages and their properties
• Relative approximate bisimulations for fuzzy picture automata

This page was built for publication: Decision problems and projection languages for restricted variants of two-dimensional automata

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