Computer Science – Formal Languages and Automata Theory
Scientific paper
2012-04-19
Computer Science
Formal Languages and Automata Theory
37 pages
Scientific paper
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.
No associations
LandOfFree
First-Order Quantifiers and the Syntactic Monoid of Height Fragments of Picture Languages 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 First-Order Quantifiers and the Syntactic Monoid of Height Fragments of Picture Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and First-Order Quantifiers and the Syntactic Monoid of Height Fragments of Picture Languages will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-35625