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
cellular automatarecognizabilitylinear timelocality and tilinglogical characterizationspicture languagessecond-order logic
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)