One-Dimensional Tiling Semigroups and Factorial Languages

Abstract

In this article, we investigate some further properties of one-dimensional tiling semigroups as a particular case of the inverse semigroup associated with a factorial language. Namely, a presentation for the semigroup and its description as a P*-semigroup are obtained. Since both cons-truc-tions rely on the language, these properties highlight the deep connection between the semigroup and the language associated with a one-dimensional tiling semigroup.

Key Words:

• Bi-infinite words
• Factorial languages
• Locally testable languages
• Minimal forbidden words
• Presentation of an inverse semigroup
• P*-Semigroup
• (Strongly) E*-Unitary inverse semigroups
• Tiling semigroups

2000 Mathematics Subject Classification:

• 20M18
• 20M05
• 68Q45

ACKNOWLEDGMENTS

The second author wishes to thank Professor Mário Branco for several fruitful discussions and for drawing her attention to Perrin (1997).

This work was developed within the project POCTI/0143/2003 “Fundamental and Applied Algebra” of Centro de Álgebra da Universidade de Lisboa, financed by FCT and FEDER. The authors would also like to thank the referee for careful reading of the manuscript and helpful comments.

Notes

Communicated by V. Gould.