Explicit left orders on free groups extending the lexicographic order on free monoids - 02/09/13
pages | 5 |
Iconographies | 2 |
Vidéos | 0 |
Autres | 0 |
Abstract |
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.
Le texte complet de cet article est disponible en PDF.Résumé |
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.
Le texte complet de cet article est disponible en PDF.Plan
Vol 351 - N° 13-14
P. 507-511 - juillet 2013 Retour au numéroBienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.
Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’achat d’article à l’unité est indisponible à l’heure actuelle.
Déjà abonné à cette revue ?