Descriptive complexity for pictures languages

DOI10.4230/LIPICS.CSL.2012.274MaRDI QIDQ4649552zbMATH OpenFDO

Authors Etienne Grandjean, Frédéric Olive

Publication date 22 November 2012

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

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)

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

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
• scientific article; zbMATH DE number 1543317 (Why is no real title available?)
• 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)