Logic and Rational Languages of Words Indexed by Linear Orderings

Copyright informations

This paper has been published in Lecture Notes in Computer Sciences, Vol. 5010, 2008, and the copyright is owned by Springer.

A journal version of this work has also been published in Theory of Computing Systems


We prove that every rational language of words indexed by linear orderings is definable in monadic second-order logic. We also show that the converse is true for the class of languages indexed by countable scattered linear orderings, but false in the general case. As a corollary we prove that the inclusion problem for rational languages of words indexed by countable linear orderings is decidable.



PDF file (145 Ko)

Valid HTML 4.01!