ON CONFLUENCE OF ONE-RULE TRACE-REWRITING SYSTEMS

Authors
WRATHALL C DIEKERT V
Citation
C. Wrathall et V. Diekert, ON CONFLUENCE OF ONE-RULE TRACE-REWRITING SYSTEMS, Mathematical systems theory, 28(4), 1995, pp. 341-361
Citations number
26
Categorie Soggetti
System Science","Mathematics, Pure","Computer Science Theory & Methods",Mathematics
Journal title
Mathematical systems theory → ACNP
ISSN journal
00255661
Volume
28
Issue
4
Year of publication
1995
Pages
341 - 361
Database
ISI
SICI code
0025-5661(1995)28:4<341:OCOOTS>2.0.ZU;2-N
Abstract
The paper presents combinatorial criteria for confluence of one-rule t race-rewriting systems. The criteria are based on self-overlaps of tra ces, which are closely related to the notion of conjugacy of traces, a nd can be tested in linear time. As a special case, we reobtain the co rresponding results for strings.