An automata-theoretic approach to the word problem for omega-terms over R

• Type: Article in International Scientific Journal
• Date: 2007

Authors

Jorge Almeida (Author) FCUP; Marc Zeitoun (Author) Other

Journal

Title: Theoretical Computer Science

Vol. 370

Pages: 131-169

ISSN: 0304-3975

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 17 Citations

Scopus - 18 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-004-BTP

DOI: 10.1016/j.tcs.2006.10.019

Abstract (EN): This paper studies the pseudovariety R of all finite R-trivial semigroups. We give a representation of pseudowords over R by infinite trees, called R-trees. Then we show that a pseudoword is an omega-term if and only if its associated tree is regular (i.e. it can be folded into a finite graph), or equivalently, if the w-term has a finite number of tails. We give a linear algorithm to compute a compact representation of the R-tree for omega-terms, which yields a linear solution of the word problem for omega-terms over R. We finally exhibit a basis for the omega-variety generated by R and we show that there is no finite basis. Several results can be compared to recent work of Bloom and Choffrut on long words.

Language: English

Type (Professor's evaluation): Scientific