[Date Prev][Date Next][Date Index]

CORRECTION: Talk: "Learnability and definability in trees and similar structures"

Date: Wednesday, October 20th 2004, 16:00 s.t.
Place: Seminarroom of the Institute, Favoritenstraße 9-11/1842, 3rd floor (when you leave the elevator turn left, go through the corridor, the entrance is on the right side)

Learnability and definability in trees and similar structures

Gyorgy Turan

The relationship between the expressiveness of a logic and
the complexity of the associated computational problems is
a much studied topic in logic and computer science.
We discuss a related issue: the learnability aspect of the
different logic formalisms, motivated by the fact that
logic is a basic framework for machine learning
(e.g., inductive logic programming).

We study combinatorial parameters of the concept classes of
definable sets in finite structures, corresponding to PAC
and query learning: the Vapnik-Chervonenkis (VC) dimension and
the strong consistency dimension. For example,
positive results are given for the VC-dimension for
monadic second order (MSO) logic over structures of bounded clique-width,
resp., for the strong consistency dimension for MSO over trees.
The proofs are based on bounds for related definability problems
for tree automata.

This is joint work with Martin Grohe.