Monadic second-order logic over rectangular pictures and recognizability by tiling systems
From MaRDI portal
Publication:1917078
DOI10.1006/inco.1996.0018zbMath0853.68131OpenAlexW1990618979MaRDI QIDQ1917078
Antonio Restivo, Dora Giammarresi, Wolfgang Thomas, Sebastian Seibert
Publication date: 3 July 1996
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.1996.0018
Related Items (38)
Reducing local alphabet size in recognizable picture languages ⋮ A logical approach to locality in pictures languages ⋮ Regular expressions and context-free grammars for picture languages ⋮ EXPLORING INSIDE TILING RECOGNIZABLE PICTURE LANGUAGES TO FIND DETERMINISTIC SUBCLASSES ⋮ Two-Dimensional Rational Automata: A Bridge Unifying One- and Two-Dimensional Language Theory ⋮ Context-sensitive string languages and recognizable picture languages ⋮ Star-free picture expressions are strictly weaker than first-order logic ⋮ Subshifts as models for MSO logic ⋮ Recognizable picture languages and domino tiling ⋮ Reducing the local alphabet size in tiling systems by means of 2D comma-free codes ⋮ Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages ⋮ A Nivat theorem for weighted picture automata and weighted MSO logics ⋮ Recognizable series on graphs and hypergraphs ⋮ An optimal construction of Hanf sentences ⋮ Weighted three directions OTA and weighted hexapolic picture automata ⋮ Weighted picture automata and weighted logics ⋮ Tiling Recognizable Two-Dimensional Languages ⋮ Recognizable vs. Regular Picture Languages ⋮ Unnamed Item ⋮ On the tiling system recognizability of various classes of convex polyominoes ⋮ Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages ⋮ A Büchi-like theorem for weighted tree automata over multioperator monoids ⋮ The monadic quantifier alternation hierarchy over grids and graphs ⋮ Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures ⋮ A Nivat Theorem for Weighted Picture Automata and Weighted MSO Logic ⋮ Perfectly quilted rectangular snake tilings ⋮ Weighted Automata and Logics on Infinite Graphs ⋮ Subshifts, Languages and Logic ⋮ Characterizations of recognizable picture series ⋮ Some notes on graph automata, tiling systems and partition logic ⋮ Logic for \(\omega\)-pushdown automata ⋮ Weighted automata ⋮ Two-dimensional models ⋮ A characterization of recognizable picture languages by tilings by finite sets ⋮ Communication complexity tools on recognizable picture languages ⋮ Two-dimensional Sgraffito automata ⋮ Unambiguous recognizable two-dimensional languages ⋮ Uniform and nonuniform recognizability.
This page was built for publication: Monadic second-order logic over rectangular pictures and recognizability by tiling systems
