6533b861fe1ef96bd12c4242
RESEARCH PRODUCT
The monadic quantifier alternation hierarchy over grids and pictures
Nicole Schweikardtsubject
Discrete mathematicsTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESFinite-state machineComputational complexity theoryHierarchy (mathematics)Proof theoryComputer Science::Logic in Computer ScienceQuantifier (linguistics)Subject (grammar)Alternation (formal language theory)Monadic predicate calculusMathematicsdescription
The subject of this paper is the expressive power of monadic second-order logic over two-dimensional grids. We give a new, self-contained game-theoretical proof of the nonexpressibility results of Matz and Thomas. As we show, this implies the strictness of the monadic second-order quantifier alternation hierarchy over grids.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1998-01-01 |