Two-Dimensional Rational Automata: A Bridge Unifying One- and Two-Dimensional Language Theory

DOI10.1007/978-3-642-35843-2_13zbMath1302.68147OpenAlexW207971140MaRDI QIDQ2927640

Marcella Anselmo, Dora Giammarresi, Marina Madonia

Publication date: 4 November 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-35843-2_13

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

A 2D non-overlapping code over a \(q\)-ary alphabet ⋮ Cross-bifix-free sets in two dimensions ⋮ Non-overlapping matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A computational model for tiling recognizable two-dimensional languages
• Deterministic and unambiguous two-dimensional languages over one-letter alphabet
• Some properties of two-dimensional on-line tessellation acceptors
• Recognizable picture languages and domino tiling
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Finite transducers and rational transductions
• Two-dimensional models
• Strategies to scan pictures with automata based on Wang tiles
• Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages
• On Complexity of Two Dimensional Languages Generated by Transducers
• An aperiodic set of Wang cubes
• Context-Sensitive Languages, Rational Graphs and Determinism
• On Relations Defined by Generalized Finite Automata