Model Checking Secondary Relations

Stephan Kepser, Uwe Mönnich, Frank Morawietz

Model Checking Secondary Relations

11pp., PS (609kB), PDF (194kB).

also: 5pp., Extended Abstract, PS (175kB), PDF (87kB).

Abstract

In this paper we present an approach to model checking of mildly context-sensitive relations with purely regular means. The approach is based on a generalisation of the classical result that the intersection of a context-free language and a regular one is a context-free language which consists in defining context-freeness in terms of least fixed points of sets of equations over union and concatenation operators. When formalising (linguistic) trees using projection and composition as operators it is possible to characterise structures that are definable by linear context-free tree grammars and can hence be mildly context-sensitive. Since the translation of tree algebras using projection and composition operators into tree algebras familiar to linguists can be defined by monadic second-order transductions, the corresponding automaton theory can be put to use to query mildly context-sensitive secondary relations with purely regular means.

In case of problems or for comments, please contact: frank@sfs.uni-tuebingen.de
Last updated: 23-May-2002