17 May 2012
San Micheletto - Via S. Micheletto 3 (Classroom 2 )
Each countable linear ordering may be represented as the
lexicographic ordering of a language over some alphabet.
But which linear orderings can be represented by regular,
context-free, or deterministic context-free
languages? Can we decide whether the lexicographic ordering
of a regular or (deterministic) context-free language is a
well-ordering, or a scattered linear ordering, or a dense ordering?
Do these linear orderings have decidable first-order or monadic
second-order theories? Is it decidable whether the lexicographic
orderings of two given regular or context-free languages are
isomorphic?
In the talk I will present answers to the above questions.
Units:
SysMA