Unambiguous recognizable two-dimensional languages

DOI10.1051/ita:2006008zbMath1112.68085OpenAlexW2135939135MaRDI QIDQ3431439

Marcella Anselmo, Marina Madonia, Dora Giammarresi, Antonio Restivo

Publication date: 10 April 2007

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2006__40_2_277_0

zbMATH Keywords

determinismtwo-dimensional languagesautomata and formal languagesunambiguity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items

A computational model for tiling recognizable two-dimensional languages, Snake-Deterministic Tiling Systems, Unbordered Pictures: Properties and Construction, Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages, A Nivat theorem for weighted picture automata and weighted MSO logics, Weighted picture automata and weighted logics, Characterization and measure of infinite two-dimensional strong prefix codes, Structure and properties of strong prefix codes of pictures, Tiling Recognizable Two-Dimensional Languages, Recognizable vs. Regular Picture Languages, Deterministic Two-Dimensional Languages over One-Letter Alphabet, Classes of two-dimensional languages and recognizability conditions, Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages, Picture codes and deciphering delay, Framed Versus Unframed Two-Dimensional Languages, On Complexity of Two Dimensional Languages Generated by Transducers, Two-dimensional comma-free and cylindric codes, Transducer generated arrays of robotic nano-arms, A Nivat Theorem for Weighted Picture Automata and Weighted MSO Logic, Sets of Pictures Avoiding Overlaps, Deterministic and unambiguous two-dimensional languages over one-letter alphabet, Characterizations of recognizable picture series, Two-dimensional models, Communication complexity tools on recognizable picture languages, PREFIX PICTURE CODES: A DECIDABLE CLASS OF TWO-DIMENSIONAL CODES, Two-dimensional codes

Cites Work

• Some properties of two-dimensional on-line tessellation acceptors
• Nondeterminism versus determinism of finite automata over directed acyclic graphs
• Communication complexity method for measuring nondeterminism in finite automata
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Tile rewriting grammars and picture languages
• Collage of two-dimensional words
• New operations and regular expressions for two-dimensional languages over one-letter alphabet
• Weighted Picture Automata and Weighted Logics
• Theory Is Forever
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item