Lexicographic orderings

Sala Javier Pinto, DCC, Campus San Joaquín, PUC

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.