INFINITE WORDS AND CONFLUENT REWRITING SYSTEMS: ENDOMORPHISM EXTENSIONS

被引：13

作者：

Cassaigne, Julien ^{[1
]}

Silva, Pedro V. ^{[2
]}

机构：

[1] Inst Math Luminy, F-13288 Marseille 9, France

[2] Univ Porto, Fac Ciencias, Ctr Matemat, P-4169007 Oporto, Portugal

来源：

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION | 2009年 / 19卷 / 04期

关键词：

Confluent rewriting systems; endomorphisms; topological completion; continuous extensions; decidability; RATIONAL SUBSETS; MONOIDS;

D O I：

10.1142/S0218196709005111

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Infinite words over a finite special confluent rewriting system R are considered and endowed with natural algebraic and topological structures. Their geometric significance is explored in the context of Gromov hyperbolic spaces. Given an endomorphism. of the monoid generated by R, existence and uniqueness of several types of extensions of. to infinite words (endomorphism extensions, weak endomorphism extensions, continuous extensions) are discussed. Characterization theorems and positive decidability results are proved for most cases.

引用

页码：443 / 490

页数：48

共 17 条

[1]

[Anonymous], 1993, Texts and Monographs in Computer Science

[2]

[Anonymous], 1966, Allyn and Bacon Series in Advanced Mathematics

[3]

[Anonymous], 1979, Transductions and context-free languages

[4]

BENOIS M, 1987, LECT NOTES COMPUT SC, V256, P121

[5] INFINITE PERIODIC POINTS OF ENDOMORPHISMS OVER SPECIAL CONFLUENT REWRITING SYSTEMS [J].

Cassaigne, Julien ;

Silva, Pedro V. .

ANNALES DE L INSTITUT FOURIER, 2009, 59 (02) :769-810

[6]

Chottin L., 1982, RAIRO INFORM TEOR, V16, P1

[7]

Cohen D. E., 1989, COMBINATORIAL GROUP, V14

[8] Word hyperbolic semigroups [J].

Duncan, A ;

Gilman, RH .

MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 2004, 136 :513-524

[9]

Ghys E., 1990, Sur les groupes hyperboliques daprs Mikhael Gromov

[10]

Hopcroft J., 1979, Introduction to automata theory, languages, and computation

← 1 2 →