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 nonempty regular words, equipped with these operations, are the free algebras in a variety which is axiomatizable by an infinite collection of some natural equations.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bloom, S.L., Choffrut, C.: Long words: the theory of concatenation and ω-power. Theoretical Computer Science 259, 533–548 (2001)
Bloom, S.L., Ésik, Z.: Deciding whether the frontier of a regular tree is scattered. Fundamenta Informaticae 55, 1–21 (2003)
Bloom, S.L., Ésik, Z.: Axiomatizing omega and omega-op powers on words (to appear)
Bloom, S.L., Ésik, Z.: Iteration Theories. Springer, Heidelberg (1993)
Courcelle, B.: Frontiers of infinite trees. RAIRO Informatique théorique/ Theoretical Computer Science 12, 319–337 (1978)
Eilenberg, S., Elgot, C.: Recursiveness. Academic Press, New York (1970)
Heilbrunner, S.: An algorithm for the solution of fixed-point equations for infinite words. Theoretical Informatics and Applications 14, 131–141 (1980)
Rosenstein, J.B.: Linear Orderings. Academic Press, New York (1982)
Thomas, W.: On frontiers of regular trees. Theoretical Informatics and Applications 20, 371–381 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bloom, S.L., Ésik, Z. (2003). Axioms for Regular Words. In: Pandya, P.K., Radhakrishnan, J. (eds) FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science. FSTTCS 2003. Lecture Notes in Computer Science, vol 2914. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24597-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-24597-1_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20680-4
Online ISBN: 978-3-540-24597-1
eBook Packages: Springer Book Archive