2012/04/19 by Oliver Matz, Matz, Oliver
Computer Science · #03C13 #03C85 #20M35 #Advanced Algebra and Logic #F.4.1 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Natural Language Processing Techniques #acm:03C13 #acm:03C85 #acm:20M35 #cs.FL #msc:03C13 #msc:03C85 #msc:20M35 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1204.4443
37 pages
openalex publication_date 2012/04/19 · arxiv created 2012/04/22 · arxiv updated 2012/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the expressive power of first-order quantifications in the context of monadic second-order logic over pictures. We show that k+1 set quantifier alternations allow to define a picture language that cannot be defined using k set quantifier alternations preceded by arbitrarily many first-order quantifier alternations. The approach uses, for a given picture language L and an integer m > 0 the height-m fragment of L, which is defined as the word language obtained by considering each picture p of height m in L as a word, where the letters of that word are the columns of p. A key idea is to measure the complexity of a regular word language by the group complexity of its syntactic monoid. Given a picture language L, such a word language measure may be applied to each of its height fragments, so that the complexity of the picture language is a function that maps each m to the complexity of the height-m fragment of L. The asymptotic growth rate of that function may be bounded based on the structure of a monadic second-order formula that defines L. The core argument for that lower bound proof is based on Straubing's algebraic characterization of the effect of first-order quantifiers on the syntactic monoid of word languages by means of Rhodes' and Tilson's block product.