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.
Abstract
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
Germany
frank@sfs.nphil.uni-tuebingen.de