Frank Morawietz

Monadic Second Order Logic, Tree Automata and Constraint Logic Programming

Arbeitspapiere des SFB 340, Bericht Nr. 86 (1997), 40pp.
DVI (155kb); Postscript (434kb)1-up; Postscript gzip-komprimiert (117kb) 1-up , 2-up.


In this paper we present a first step toward the development of a constraint logic programming (clp) language R(MSO) based on monadic second order (mso) logic. We apply the scheme proposed by Höhfeld und Smolka (1988) to obtain a relational extension of mso logic with a corresponding sound and complete operational semantics. The solutions to constraints expressed in monadic second order logic are represented by tree automata recognizing the assignment trees satisfying the formulas. Since this allows a compact and efficient representation of constraints, we can use mso theorem provers as constraint solvers for the clp interpreter. Building on the detailed investigation of mso logic in Rogers (1994) as a tree description language in the Principles and Parameter (P&P) paradigm, we present as motivation and applications details from the realm of P&P-based parsing.

Seminar für Sprachwissenschaft
Eberhard-Karls-Universität Tübingen
Wilhelmstraße 113
72074 Tübingen