6533b85efe1ef96bd12c07f0
RESEARCH PRODUCT
Monadic Second-Order Logic over Rectangular Pictures and Recognizability by Tiling Systems
Sebastian SeibertDora GiammarresiAntonio RestivoWolfgang Thomassubject
Predicate logicMonadic second-order logicDiscrete mathematicsNatural logicIntermediate logicHigher-order logicMonadic predicate calculusComputer Science ApplicationsTheoretical Computer ScienceMathematics::LogicTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESComputational Theory and MathematicsComputer Science::Logic in Computer ScienceMany-valued logicDynamic logic (modal logic)Computer Science::Formal Languages and Automata TheoryInformation SystemsMathematicsdescription
Abstract It is shown that a set of pictures (rectangular arrays of symbols) is recognized by a finite tiling system iff 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 also 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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1996-02-01 | Information and Computation |