Ankündigung Vortrag

Im Rahmen des Kolloquiums des Instituts für Informatik hält

Herr Dr. Andreas Krebs (Eberhard Karls Universität Tübingen)
am Mittwoch, 05.12.12 um 16 c.t
in Raum 117 (Robert-Mayer-Str. 11-15, 1.OG)

einen Vortrag zum Thema
"Non-definability of languages by generalized first-order formulas over (N,+)"

Abstract:

We consider first-order logic with monoidal quantifiers over words. We show that all languages with a neutral letter, definable using the addition numerical predicate are also definable with the order predicate as the only numerical predicate. Let S be a subset of monoids.

Let LS be the logic closed under quantification over the monoids in S and N be the class of neutral letter languages. Then we show that:
LS[<,+] cap N = LS[<]
Our result can be interpreted as the Crane Beach conjecture to hold for the logic LS[<,+]. For cyclic groups, we answer an open question
of Roy and Straubing, proving that MOD[<,+] collapses to MOD[<].


Es lädt ein: Prof. Nicole Schweikardt

Zusätzliche Informationen