Technischer Bericht TR-2012-03

Bibliograph.
Daten
Kufleitner, Manfred; Lauser, Alexander: Lattices of Logical Fragments over Words.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Technischer Bericht Informatik Nr. 2012/03.
32 Seiten, englisch.
CR-Klassif.F.4.0 (Mathematical Logic and Formal Languages General)
F.4.3 (Formal Languages)
Keywordsfragments; first-order logic; monadic second-order logic; C-varieties of languages; formal language theory
Kurzfassung

This paper introduces an abstract notion of fragments of monadic second-order logic. This concept is based on purely syntactic closure properties. We show that over finite words, every logical fragment defines a lattice of languages with certain closure properties. Among these closure properties are residuals and inverse C-morphisms. Here, depending on certain closure properties of the fragment, C is the family of arbitrary, non-erasing, length-preserving, length-multiplying, or length-reducing morphisms. In particular, definability in a certain fragment can often be characterized in terms of the syntactic morphism. This work extends a result of Straubing in which he investigated certain restrictions of first-order logic formulae. In contrast to Straubing's model-theoretic approach, our notion of a logical fragment is purely syntactic and it does not rely on Ehrenfeucht-Fraisse games.

As motivating examples, we present (1) a fragment which captures the stutter-invariant part of piecewise-testable languages and (2) an acyclic fragment of Sigma_2. As it turns out, the latter has the same expressive power as two-variable first-order logic FO^2.

Volltext und
andere Links
PDF (443347 Bytes)
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
Eingabedatum13. März 2012
   Publ. Institut   Publ. Informatik