Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Iterated GSMs and Co-CFL

Autor
Autebert, J.-M.; Gabarro, J.
Tipus d'activitat
Article en revista
Revista
Acta informatica
Data de publicació
1989-10
Volum
26
Número
8
Pàgina inicial
749
Pàgina final
769
DOI
https://doi.org/10.1007/BF00289160 Obrir en finestra nova
URL
https://link.springer.com/article/10.1007/BF00289160 Obrir en finestra nova
Resum
We study the infinite words generated by an iterated gsm. The motivation was two fold. The first one was given by the apparent similarity between the iterated gsm and the iterated morphism. However contrary to the appearences almost all questions become undecidable. The second one was to disprove the following conjecture of Berstel: The language of coprefixes of an infinite word w is context free iff w is generated by an iterated gsm. We use for that the infinite word: w = abca2ba2bca4ba4ba2ba4b...
Paraules clau
Ambiguity problem, Infinite words, Iterated GSMs, Iterated morphisms, Kleene hierarchy
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants