Star-free picture expressions are strictly weaker than first-order logic

DOI10.1007/3-540-63165-8_191zbMath1401.03068OpenAlexW1535331541MaRDI QIDQ4571966

Thomas Wilke

Publication date: 4 July 2018

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63165-8_191

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items (7)

A Nivat theorem for weighted picture automata and weighted MSO logics ⋮ Weighted picture automata and weighted logics ⋮ New operations and regular expressions for two-dimensional languages over one-letter alphabet ⋮ Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures ⋮ A Nivat Theorem for Weighted Picture Automata and Weighted MSO Logic ⋮ Characterizations of recognizable picture series ⋮ Picture codes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Definability with bounded number of bound variables
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Weak Second‐Order Arithmetic and Finite Automata
• Using string languages to describe picture languages

This page was built for publication: Star-free picture expressions are strictly weaker than first-order logic