Quantitative Monadic Second-Order Logic
Cristian Riveros
Info
|
Date |
11th June 2013 (week , Trinity Term 2013) |
|
Time |
11:30 |
|
Place |
051 |
Abstract
While monadic second-order logic is a prominent logic for specifying languages of finite words, it lacks the power to
compute quantitative properties, e.g. to count.
An automaton model capable of computing such properties are weighted automata, but logics equivalent to these automata
have only recently emerged.
In this talk, I will propose a new framework for adding quantitative properties to logics specifying Boolean properties
of words. I will use this to define Quantitative Monadic Second-Order Logic (QMSO) and
show a simple logic which is equally expressive to weighted automata. Furthermore, by refining the analysis of this logic
one can obtain fragments that characterise exactly subclasses of weighted
automata defined by the level of ambiguity allowed in the automata. In this way, I will present a quantitative logic
which has good decidability properties while being reasonably expressive and
enjoying a simple syntactic definition.
This is joint work with Stephan Kreutzer of TU Berlin, to be presented at LICS 2013.
Further info
|
Related series |
|
