0000000000171885

AUTHOR

Wolfgang Thomas

showing 3 related works from this author

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

1994

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.

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
researchProduct

The Monadic Quantifier Alternation Hierarchy over Grids and Graphs

2002

AbstractThe monadic second-order quantifier alternation hierarchy over the class of finite graphs is shown to be strict. The proof is based on automata theoretic ideas and starts from a restricted class of graph-like structures, namely finite two-dimensional grids. Considering grids where the width is a function of the height, we prove that the difference between the levels k+1 and k of the monadic hierarchy is witnessed by a set of grids where this function is (k+1)-fold exponential. We then transfer the hierarchy result to the class of directed (or undirected) graphs, using an encoding technique called strong reduction. It is notable that one can obtain sets of graphs which occur arbitrar…

Discrete mathematicsPolynomial hierarchyDirected graphMonadic predicate calculusAutomatonTheoretical Computer ScienceComputer Science ApplicationsCombinatoricsTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESComputational Theory and MathematicsAnalytical hierarchyComplexity classAutomata theoryGraph propertyMathematicsInformation SystemsInformation and Computation
researchProduct

Monadic Second-Order Logic over Rectangular Pictures and Recognizability by Tiling Systems

1996

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.

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 SystemsMathematicsInformation and Computation
researchProduct