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

DOI10.1016/j.tcs.2020.12.028zbMath1504.68116OpenAlexW3116363031MaRDI QIDQ2029491

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

language equivalencedecision problemtwo-way automatathree-way automatatwo-dimensional automatalanguage emptinessprojection language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

2D oxide picture languages and their properties ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Three-way automata on rectangular types over a one-letter alphabet
• A note on decision problems for three-way two-dimensional finite automata
• Hierarchies of complete problems
• Context-sensitive string languages and recognizable picture languages
• Accepting runs in a two-way finite automaton
• Decision problems for restricted variants of two-dimensional automata
• New operations and regular expressions for two-dimensional languages over one-letter alphabet
• Checking automata and one-way stack languages
• A survey of two-dimensional automata theory
• Classification of String Languages via Tiling Recognizable Picture Languages
• A Survey on Picture-Walking Automata
• Some results concerning two-dimensional turing machines and finite automata
• Theory Is Forever

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