Advertisement
Published in:
2010 | OriginalPaper | Chapter
Rankers over Infinite Words
(Extended Abstract)
Authors : Luc Dartois, Manfred Kufleitner, Alexander Lauser
Published in: Developments in Language Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the fragments FO
2
,
$\Sigma_2\cap FO^2$
,
$\Pi_2 \cap FO^2$
, and Δ
2
of first-order logic FO[ < ] over finite and infinite words. For all four fragments, we give characterizations in terms of rankers. In particular, we generalize the notion of a ranker to infinite words in two possible ways. Both extensions are natural in the sense that over finite words they coincide with classical rankers, and over infinite words they both have the full expressive power of FO
2
. Moreover, the first extension of rankers admits a characterization of
$\Sigma_2 \cap FO^2$
while the other leads to a characterization of
$\Pi_2 \cap FO^2$
. Both versions of rankers yield characterizations of the fragment Δ
2
= Σ
2
∩ Π
2
. As a byproduct, we also obtain characterizations based on unambiguous temporal logic and unambiguous interval temporal logic.