2 Iconography
Access to the text (HTML) Access to the text (HTML)
PDF Access to the PDF text

Access to the full text of this article requires a subscription.
  • If you are a subscriber, please sign in 'My Account' at the top right of the screen.

  • If you want to subscribe to this journal, see our rates

  • You can purchase this item in Pay Per ViewPay per View - FAQ : 30,00 € Taxes included to order
    Pages Iconography Videos Other
    5 2 0 0

Comptes Rendus Mathématique
Volume 351, n° 13-14
pages 507-511 (juillet 2013)
Doi : 10.1016/j.crma.2013.07.001
Received : 2 April 2013 ;  accepted : 1 July 2013
Explicit left orders on free groups extending the lexicographic order on free monoids
Ordres à gauche explicites sur les groupes libres étendant lʼordre lexicographique sur les monoïdes libres

Zoran Šunić 1
 Dept. of Mathematics, Texas A&M University, MS-3368, College Station, TX 77843-3368, USA 


For every finitely generated free group, we construct an explicit left order extending the lexicographic order on the free monoid generated by the positive letters. The order is defined by a left, free action on the orbit of 0 of a free group of piecewise linear homeomorphisms of the line. The membership in the positive cone is decidable in linear time in the length of the input word. The positive cone forms a context-free language closed under word reversal.

The full text of this article is available in PDF format.

Pour tout groupe libre fini engendré, nous construisons explicitement un ordre à gauche qui étend lʼordre lexicographique sur le monoïde libre engendré par les lettres positives. Cet ordre est défini par une action à gauche, libre, sur lʼorbite de 0 dʼun groupe libre dʼhoméomorphismes de la droite linéaires par morceaux. Lʼappartenance au cône positif est décidable en temps linéaire par rapport à la longueur du mot. Le cône positif forme un langage non contextuel fermé par image miroir.

The full text of this article is available in PDF format.
1  This material is based upon work supported by the National Science Foundation under Grant No. DMS-1105520.

© 2013  Académie des sciences@@#104156@@
EM-CONSULTE.COM is registrered at the CNIL, déclaration n° 1286925.
As per the Law relating to information storage and personal integrity, you have the right to oppose (art 26 of that law), access (art 34 of that law) and rectify (art 36 of that law) your personal data. You may thus request that your data, should it be inaccurate, incomplete, unclear, outdated, not be used or stored, be corrected, clarified, updated or deleted.
Personal information regarding our website's visitors, including their identity, is confidential.
The owners of this website hereby guarantee to respect the legal confidentiality conditions, applicable in France, and not to disclose this data to third parties.
Article Outline