Geodesic
D0L sequence equivalence is in P for fixed alphabets
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 2, pp. 361-374

Voir la notice de l'article provenant de la source Numdam

A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in time polynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and certain well-known properties of ℤ-rational sequences.

DOI : 10.1051/ita:2007037
Classification : 68Q45
Keywords: D0L system, equivalence problem, polynomial-time algorithm 
@article{ITA_2008__42_2_361_0,
     author = {Ruohonen, Keijo},
     title = {D0L sequence equivalence is in $P$ for fixed alphabets},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {361--374},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {2},
     year = {2008},
     doi = {10.1051/ita:2007037},
     mrnumber = {2401267},
     zbl = {1144.68037},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2007037/}
}
TY  - JOUR
AU  - Ruohonen, Keijo
TI  - D0L sequence equivalence is in $P$ for fixed alphabets
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
SP  - 361
EP  - 374
VL  - 42
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2007037/
DO  - 10.1051/ita:2007037
LA  - en
ID  - ITA_2008__42_2_361_0
ER  - 
%0 Journal Article
%A Ruohonen, Keijo
%T D0L sequence equivalence is in $P$ for fixed alphabets
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 361-374
%V 42
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2007037/
%R 10.1051/ita:2007037
%G en
%F ITA_2008__42_2_361_0
Ruohonen, Keijo. D0L sequence equivalence is in $P$ for fixed alphabets. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 2, pp. 361-374. doi: 10.1051/ita:2007037

Cité par Sources :