Context-sensitive string languages and recognizable picture languages

DOI10.1006/INCO.1997.2659zbMATH Open0895.68083OpenAlexW1988621416MaRDI QIDQ1376420FDOQ1376420

Authors: Michel Latteux, David Simplot 

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

Recommendations

• Families of automata characterizing context-sensitive languages
• Chomsky-Schützenberger-type characterization of multiple context-free languages
• Publication:3468622
• Classification of string languages via tiling recognizable picture languages
• On ``inherently context-sensitive languages -- an application of complexity cores

zbMATH Keywords

context-free languagesrecognizable tree languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Recognizable picture languages and domino tiling
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Title not available (Why is that?)
• Algebraic automata and context-free sets
• Some properties of two-dimensional on-line tessellation acceptors
• Picture languages with array rewriting rules

Cited In (13)

• Traces of term-automatic graphs
• Decision problems and projection languages for restricted variants of two-dimensional automata
• Title not available (Why is that?)
• Consensus game acceptors
• A logical approach to locality in pictures languages
• Picture codes
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures
• Iteration of rational transductions
• Title not available (Why is that?)
• Consensus game acceptors and iterated transductions
• From words to pictures: row-column combinations and Chomsky-Schützenberger theorem
• Recognizable vs. Regular Picture Languages
• Infinite games with finite knowledge gaps

This page was built for publication: Context-sensitive string languages and recognizable picture languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1376420)