Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Probevortrag - Promotion: Lucas Heimberg

  • Wann 13.02.2017 von 09:30 bis 11:30
  • Wo 12489 Berlin, Rudower Chaussee 25, Humboldt-Kabinett
  • iCal

Herr Dipl.-Inf. Lucas Heimberg wird einen Vortrag zum Thema

"Complexity of Normal Forms on Structures of Bounded Degree"

halten. Mit diesem Vortrag möchte er Ihnen sein Promotionsthema vorstellen.

Alle Interesseneten sind herzlich eingeladen!


 

Abstract:

Normal forms express semantic properties of logics by means of
syntactical restrictions. For a logic, they are a link between its
expressive power and its algorithmic properties. In particular,
Gaifman normal form expresses the locality of first-order logic. It
serves as an intermediate step in fixed-parameter tractable
model-checking algorithms, parameterised by the size of the input
formula, for sparse graph classes.  However, in most cases, a
non-elementary blow-up of the Gaifman normal form is unavoidable and
leads to an enormous parameter-dependency.

We consider classes of structures of bounded degree, where this
non-elementary blow-up can be avoided, and focus on extensions of
first-order logic by unary counting quantifiers.  We generalise a
local normal form by Hanf and show that formulae permit Hanf normal
form only if all quantifiers are ultimately periodic. Furthermore we
show that, in this case, Hanf normal form can be computed in
elementary time. This leads to elementary algorithms for
model-checking, Feferman-Vaught decompositions, and (for the
restricted case of first-order logic) Gaifman normal form. For all
these algorithms we provide matching lower bounds. In another
direction, we use a locality theorem in the manner of Hanf's theorem
to show that for formulae that are preserved under extensions
(homomorphisms), existential (existential-positive) formulae can be
computed in elementary time.