Technical Report TR-2011-03

BibliographyKufleitner, Manfred; Lauser, Alexander: Around Dot-depth One.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Technical Report Computer Science No. 2011/03.
15 pages, german.
CR-SchemaF.4.1 (Mathematical Logic)
F.4.3 (Formal Languages)
Keywordsfinite semigroups; dot-depth; regular languages; first-order logic
Abstract

The dot-depth hierarchy is a classification of star-free languages. It is related to the quantifier alternation hierarchy of first-order logic over finite words. We consider fragments of languages with dot-depth 1/2 and dot-depth 1 obtained by prohibiting the specification of prefixes or suffixes. As it turns out, these language classes are in one-to-one correspondence with fragments of existential first-order logic without min- or max-predicate. For all fragments, we obtain effective algebraic characterizations. Moreover, we give new combinatorial proofs for the decidability of the membership problem for dot-depth 1/2 and dot-depth 1.

Full text and
other links
PDF (494995 Bytes)
PostScript (924488 Bytes)
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Entry dateMarch 8, 2011
   Publ. Computer Science