Search

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.

A variety of ordered algebras is a class K of ordered algebras satisfying satisfying a set of inequalities [email protected]?t'. It is shown that a class K of ordered algebras is a variety if K is closed under subalgebras, products, and certain homomorphic images. The process of obtaining a ''canonical'' @w-completion of an ordered algebra is analyzed and it is shown that varieties of ordered algebras are closed with respect to @w-completion. The concluding sections concern (i) a connection between ordered algebras and ordered algebraic theories, and (ii) a logic of inequalities, analogous to equational logic. A completeness theorem for this logic is proved.

Iteration semi-rings are Conway semi-rings satisfying Conway's group identities. We show that the semi-rings N^r^a^t > of rational power series with coefficients in the semi-ring N of natural numbers are the free partial iteration semi-rings. Moreover, we characterize the semi-rings N"~"^"r"^"a"^"t > as the free semi-rings in the variety of iteration semi-rings defined by three additional simple identities, where N"~ is the completion of N obtained by adding a point of infinity. We also show that this latter variety coincides with the variety generated by the complete, or continuous semirings. As a consequence of these results, we obtain that the semi-rings N"~^r^a^t >, equipped with the sum order, are free in the class of symmetric inductive ^*-semi-rings. This characterization corresponds to Kozen's axiomatization of regular languages.