[Up]
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
Abstract
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.
Download
PDF file (145 Ko)
