Descriptive complexity for pictures languages

DOI10.4230/LIPICS.CSL.2012.274zbMATH Open1252.68147arXiv1201.5853MaRDI QIDQ4649552FDOQ4649552

Authors: Etienne Grandjean, Frédéric Olive 

Publication date: 22 November 2012

Full work available at URL: https://arxiv.org/abs/1201.5853

Recommendations

• A logical approach to locality in pictures languages
• Definability by Horn formulas and linear time on cellular automata
• Recognizable vs. Regular Picture Languages
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Restarting automata for picture languages: a survey on recent developments

zbMATH Keywords

cellular automatarecognizabilitylinear timelocality and tilinglogical characterizationspicture languagessecond-order logic

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Cellular automata (computational aspects) (68Q80) Descriptive complexity and finite models (68Q19)

Cited In (6)

• Definability by Horn formulas and linear time on cellular automata
• A logical approach to locality in pictures languages
• A language-theoretical approach to descriptive complexity
• Complexity and decidability for restricted classes of picture languages
• Title not available (Why is that?)
• Descriptive complexity for minimal time of cellular automata

This page was built for publication: Descriptive complexity for pictures languages

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