The equational theory of regular words |
| |
Authors: | Stephen L Bloom Zoltn sik |
| |
Affiliation: | aDepartment of Computer Science, Stevens Institute of Technology, Hoboken, NJ 07030, USA;bInstitute for Informatics, University of Szeged, Szeged, Hungary |
| |
Abstract: | Courcelle introduced the study of regular words, i.e., words isomorphic to frontiers of regular trees. 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. We prove that the algebra of nonempty regular words on the set A, equipped with these operations, is freely generated by A 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. |
| |
Keywords: | Word Arrangement Regular Linear order Equational theory |
本文献已被 ScienceDirect 等数据库收录! |
|