Poster (Scientific congresses and symposiums)
Free Group and Recognizability
Raskin, Julien
2013Fourth PhD-Day of the Belgian Mathematical Society
 

Files


Full Text
poster.pdf
Author preprint (183.17 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
recognizable languages; free group; automata
Abstract :
[en] It is well known that recognizability has many algebraic properties. For example, a subset $L$ of the free monoid $\Sigma^*$ is recognizable if and only if there exists a finite monoid $M$, a subset $P$ of $M$ and a morphism $f : \Sigma^* \to M$ such that $L = f^{-1}(P)$. These properties allow us to easily define a concept of recognizability in non-free monoids or even in other algebraic structures, such as groups. Our aim is to study the recognizable subsets of the free group $F_X$ generated by $X$. A classical construction of the latter shows that it can be seen as a subset of the free monoid $(X \cup X')^*$, where $X'$ is a set of formal inverses of elements of $X$, endowed with an ad hoc operation. When $X$ is finite, it appears that $F_X$ is a recognizable language of this monoid. It is then natural to wonder if there is a link between recognizability in $F_X$ and recognizability in $(X \cup X')^*$. We show that every recognizable language of $F_X$ is recognizable in $(X \cup X')^*$, and that we can define a class of automata that recognize the recognizable languages of $F_X$.
Disciplines :
Mathematics
Author, co-author :
Raskin, Julien ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Free Group and Recognizability
Publication date :
09 September 2013
Number of pages :
A1
Event name :
Fourth PhD-Day of the Belgian Mathematical Society
Event organizer :
Belgian Mathematical Society
Event place :
Bruxelles, Belgium
Event date :
09 septembre 2013
Available on ORBi :
since 06 June 2014

Statistics


Number of views
83 (32 by ULiège)
Number of downloads
67 (16 by ULiège)

Bibliography


Similar publications



Contact ORBi