Logic and Rational Languages of Words Indexed by Linear Orderings

Copyright informations

This paper has been published in Theory of Computing Systems (special issue of CSR'08). Volume 46, Issue 4 (2010), and the copyright is owned by Springer. The final publication is available at www.springerlink.com.

This paper is the journal version of a work presented at CSR'08.


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 (267 Ko)

Valid HTML 4.01!