<ul>
<li><p>Jean Berstel maintains a website with Schützenberger's collected papers. You can access the original paper (in French) <a href="http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1976ProduitConcatenationNonAmbiguSF.pdf" rel="noreferrer">here</a>.</p></li>
<li><p>A definition of the unambiguous product you are referring to in English is given by Pin in <a href="http://liafa.jussieu.fr/~jep/PDF/HandBook.pdf" rel="noreferrer">Syntactic Semigroups</a>, 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$." </p></li>
<li><p>I recommend reading the following <a href="http://www2.informatik.uni-stuttgart.de/fmi/ti/veroeffentlichungen/pdffiles/DiekertGastinKufleitner2008ijfcs.pdf" rel="noreferrer">survey by Diekert, Gastin and Kufleitner</a> for more background information. They refer to the concept of unambiguous product as "unambiguous monomial".</p></li>
</ul>

<p>References:</p>

<ul>
<li><p>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.</p></li>
<li><p>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.</p></li>
</ul>

CC BY-SA 3.0
2011-08-16T23:19:45.730Z
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.
Janoma
CC BY-SA 3.0
2011-08-17T18:14:52.637Z
Thanks for your comment. I am happy that you find my answer useful.
Hermann Gruber
CC BY-SA 3.0
2011-08-16T21:44:04.547Z
2015-06-16T22:03:29.947Z
2015-06-16T22:03:29.947Z
Hermann Gruber
<p>I'm reading <a href="https://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8942" rel="nofollow noreferrer" title="Classifying Discrete Temporal Properties">Thomas Wilke's survey</a> on the connections between Temporal Logic and finite automata, finite semigroups and first-order logic.</p>
<p>In Theorem 6 (by Kamp), the fragment <span class="math-container">$\mathrm{TL}[\mathsf{F},\mathsf{P}]$</span> (Temporal Logic with  modalities <span class="math-container">$\mathsf{F}$</span> (eventually) and <span class="math-container">$\mathsf{P}$</span> (eventually in the past)) is said to be equivalent to first-order logic with two variables.</p>
<p>After the statement of the theorem, Wilke mentions another connection from TL to formal languages:</p>
<blockquote>
<p>(...) the languages expressible in <span class="math-container">$\mathrm{TL}[\mathsf{F},\mathsf{P}]$</span> are exactly the unambiguous languages in the sense of Schützenberger [13]</p>
</blockquote>
<p>where [13] cites <a href="https://doi.org/10.1007/BF02194921" rel="nofollow noreferrer" title="SpringerLink: pay for this article...">Sur le produit de concatenation non ambigu</a>. 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.</p>
<p>I've searched online for a while but I can't find a definition of &quot;unambiguous in the sense of Schützenberger&quot;, and I guess it's not the same as in an &quot;unambiguous context-free language&quot;, since <span class="math-container">$\mathrm{TL}[\mathsf{F},\mathsf{P}]$</span> is strictly less expressive than <span class="math-container">$\mathrm{TL}$</span>, which is strictly less expressive than regular languages (unless it's the same definition, restricted to regular languages instead of context-free).</p>
<p>Does anybody have the definition, the paper, or know of a survey or book with this information?</p>
<p>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).</p>
<p>Thanks in advance for your help!</p>

<lo.logic><algebra><regular-language><nondeterminism><linear-temporal-logic>
What is an unambiguous language in the sense of Schützenberger?
Janoma
# What is an unambiguous language in the sense of Schützenberger?

(Asked by: username_0 on 2011-08-16)

I'm reading [Thomas Wilke's survey](https://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8942 "Classifying Discrete Temporal Properties") 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](https://doi.org/10.1007/BF02194921 "SpringerLink: pay for this article..."). 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!

**Tags:** lo.logic, algebra, regular-language, nondeterminism, linear-temporal-logic


---

## 1 answers

### Answer by username_1 on 2011-08-16. Score: 16 | Accepted answer

* Jean Berstel maintains a website with Schützenberger's collected papers. You can access the original paper (in French) [here](http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1976ProduitConcatenationNonAmbiguSF.pdf).
* A definition of the unambiguous product you are referring to in English is given by Pin in [Syntactic Semigroups](http://liafa.jussieu.fr/~jep/PDF/HandBook.pdf), 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](http://www2.informatik.uni-stuttgart.de/fmi/ti/veroeffentlichungen/pdffiles/DiekertGastinKufleitner2008ijfcs.pdf) 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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: Thanks for your comment. I am happy that you find my answer useful.  

---

