Technischer Bericht TR-2011-03

Bibliograph.
Daten
Kufleitner, Manfred; Lauser, Alexander: Around Dot-depth One.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Technischer Bericht Informatik Nr. 2011/03.
15 Seiten, deutsch.
CR-Klassif.F.4.1 (Mathematical Logic)
F.4.3 (Formal Languages)
Keywordsfinite semigroups; dot-depth; regular languages; first-order logic
Kurzfassung

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.

Volltext und
andere Links
PDF (494995 Bytes)
PostScript (924488 Bytes)
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
Eingabedatum8. März 2011
   Publ. Abteilung   Publ. Institut   Publ. Informatik