Please Enter a Search Term
Departmental Seminar Mar 20th: Dr. Zoltan Esik
Antonina Kolokolova

                                         Dr. Zoltan Esik

                           Department of Computer Science

                             University of Szeged, Hungary

                               Lexicographic orderings

                      Department of Computer Science
          Tuesday, March 20th, 2012, 1:00 p.m., Room EN-2022 (note unusual day)


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

In the talk I will present answers to the above questions.


Mar 5th, 2012

Bookmark and Share