Context-sensitive string languages and recognizable picture languages

DOI10.1006/inco.1997.2659zbMath0895.68083OpenAlexW1988621416MaRDI QIDQ1376420

David Simplot, Michel Latteux

Publication date: 17 December 1997

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/4e17bf6cb389b417395cc307e797d8ab2606df0d

zbMATH Keywords

context-free languagesrecognizable tree languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

A logical approach to locality in pictures languages ⋮ Consensus Game Acceptors ⋮ Unnamed Item ⋮ Recognizable vs. Regular Picture Languages ⋮ Traces of term-automatic graphs ⋮ Unnamed Item ⋮ Consensus Game Acceptors and Iterated Transductions ⋮ Infinite games with finite knowledge gaps ⋮ Decision problems and projection languages for restricted variants of two-dimensional automata ⋮ Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures ⋮ Picture codes ⋮ Iteration of rational transductions

Cites Work

• 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
• Algebraic automata and context-free sets
• Picture languages with array rewriting rules
• Unnamed Item
• Unnamed Item