Computer Science – Formal Languages and Automata Theory
Scientific paper
2012-02-15
Computer Science
Formal Languages and Automata Theory
Scientific paper
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.
Kufleitner Manfred
Lauser Alexander
No associations
LandOfFree
Lattices of Logical Fragments over Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Lattices of Logical Fragments over Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lattices of Logical Fragments over Words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-558103