6
$\begingroup$

I'm reading Thomas Wilke's survey on the connections between Temporal Logic and finite automata, finite semigroups and first-order logic.

In Theorem 6 (by Kamp), the fragment $\mathrm{TL}[\mathsf{F},\mathsf{P}]$ (Temporal Logic with modalities $\mathsf{F}$ (eventually) and $\mathsf{P}$ (eventually in the past)) is said to be equivalent to first-order logic with two variables.

After the statement of the theorem, Wilke mentions another connection from TL to formal languages:

(...) the languages expressible in $\mathrm{TL}[\mathsf{F},\mathsf{P}]$ are exactly the unambiguous languages in the sense of Schützenberger [13]

where [13] cites Sur le produit de concatenation non ambigu. I can't pay for the paper and I can't find it anywhere else for download. What's more, I can't read French, even though I'd gladly try if I had the paper.

I've searched online for a while but I can't find a definition of "unambiguous in the sense of Schützenberger", and I guess it's not the same as in an "unambiguous context-free language", since $\mathrm{TL}[\mathsf{F},\mathsf{P}]$ is strictly less expressive than $\mathrm{TL}$, which is strictly less expressive than regular languages (unless it's the same definition, restricted to regular languages instead of context-free).

Does anybody have the definition, the paper, or know of a survey or book with this information?

An additional and related question: is there a (known) restriction to the syntax of regular expressions such that this class of unambiguous language is equivalent to the fragment of regular languages defined by those regular expressions? (as in the equivalence of star-free languages with first-order logic, for example).

Thanks in advance for your help!

$\endgroup$
14
$\begingroup$
  • Jean Berstel maintains a website with Schützenberger's collected papers. You can access the original paper (in French) here.

  • A definition of the unambiguous product you are referring to in English is given by Pin in Syntactic Semigroups, p.30: "The product $L = L_0a_1L_1 \cdots a_nL_n$ is unambiguous if every word $u$ of $L$ admits a unique factorization of the form $u_0a_1u_1 \cdots a_nu_n$ with $u_0 \in L_0, \cdots, u_n \in L_n$."

  • I recommend reading the following survey by Diekert, Gastin and Kufleitner for more background information. They refer to the concept of unambiguous product as "unambiguous monomial".

References:

  • J.-E. Pin, Syntactic semigroups, Chap. 10 in Handbook of language theory, Vol. I, G. Rozenberg and A. Salomaa (éd.), Springer Verlag, (1997), 679-746.

  • Volker Diekert, Paul Gastin, and Manfred Kufleitner. A survey on small fragments of first-order logic over finite words. International Journal of Foundations of Computer Science, 19(3):513-548, June 2008. Special issue DLT 2007.

$\endgroup$
  • 1
    $\begingroup$ Well, this is wonderful! Thanks a lot. I think the survey and the handbook are exactly what I need. I'm still looking for that restriction to regular expressions, not sure if it has been proven, though. $\endgroup$ – Janoma Aug 16 '11 at 23:19
  • $\begingroup$ Thanks for your comment. I am happy that you find my answer useful. $\endgroup$ – Hermann Gruber Aug 17 '11 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.