6533b7d2fe1ef96bd125dfee

RESEARCH PRODUCT

Monadic second-order logic over pictures and recognizability by tiling systems

Sebastian SeibertWolfgang ThomasAntonio RestivoDora Giammarresi

subject

Predicate logicDiscrete mathematicsTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESComputer Science::Logic in Computer ScienceSubstructural logicSecond-order logicMultimodal logicDynamic logic (modal logic)Intermediate logicHigher-order logicComputer Science::Formal Languages and Automata TheoryMonadic predicate calculusMathematics

description

We show that a set of pictures (rectangular arrays of symbols) is recognized by a finite tiling system if and only if it is definable in existential monadic second-order logic. As a consequence, finite tiling systems constitute a notion of recognizability over two-dimensional inputs which at the same time generalizes finite-state recognizability over strings and matches a natural logic. The proof is based on the Ehrenfeucht-FraIsse technique for first-order logic and an implementation of “threshold counting” within tiling systems.

yearjournalcountryeditionlanguage
1994-01-01
https://doi.org/10.1007/3-540-57785-8_155