@InProceedings{	  KufleitnerL12icalp,
  author	= "Manfred Kufleitner and Alexander Lauser",
  title		= "Lattices of Logical Fragments over Words",
  booktitle	= "Automata, Languages and Programming, International
		  Colloquium (ICALP) 2012, Conference Proceedings Part II",
  publisher	= "Springer-Verlag",
  series	= "Lecture Notes in Computer Science",
  year		= "2012",
  volume	= "7392",
  pages		= "275--286",
  abstract	= "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 formulae. 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
		  $\mathrm{FO}^{ 2}$.",
  doi		= "10.1007/978-3-642-31585-5_27"
}