Regular Words
by
Stephen L. Bloom
Department of Computer Science, Stevens Institute of Technology
Coauthors: Zoltan Esik

Courcelle, in 1978, introduced the study of regular words, i.e., words isomorphic to frontiers of regular trees. In 1980, Heilbrunner showed that a nonempty word is regular iff it can be generated from the singletons by the operations of concatenation, omega power, omega-op power, and the infinite family of shuffle operations. He found certain equational axioms for these operations, but they are not complete. Thomas, in 1986, showed that the equational theory of regular words is decidable, but no complexity bound was found. In this talk, we outline a proof that the nonempty regular words on the set A, equipped with the above operations, is the A-generated free algebra in a variety which is axiomatizable by an infinite collection of some natural equations. We also show that this variety has no finite equational basis and that its equational theory is decidable in polynomial time.

Date received: June 24, 2004

Copyright © 2004 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caoc-07.