2012/02/15 by Manfred Kufleitner, Kufleitner, Manfred, Alexander Lauser +1
Computer Science · #Advanced Algebra and Logic #F.4.0 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #cs.FL #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1202.3355
openalex publication_date 2012/02/15 · arxiv created 2012/03/09 · arxiv updated 2015/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Sigma2. As it turns out, the latter has the same expressive power as two-variable first-order logic FO2.