Unambiguous recognizable two-dimensional languages

DOI10.1051/ita:2006008zbMath1112.68085MaRDI 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

determinism; two-dimensional languages; automata and formal languages; unambiguity

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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