Date of Award


Degree Type


Degree Name

Doctor of Philosophy


We define an order automaton to be a 4-tuple (M,X,R, {dollar}\eta{dollar}) where ({dollar}X,\eta{dollar}) is a {dollar}M{dollar}-automaton and {dollar}R{dollar} a partial ordering on {dollar}X{dollar} such that {dollar}x \leq y{dollar} if and only if there exists an {dollar}a \in M{dollar} such that {dollar}\eta(x,a) = y{dollar}. The monoid {dollar}M{dollar} is said to generate the order {dollar}R{dollar} on {dollar}X{dollar}. Some relationships between the algebraic properties of {dollar}M{dollar} and the order {dollar}R{dollar} are determined. A monoid {dollar}M{dollar} is shown to be the monoid for some order automaton if and only if it has a homomorphic image {dollar}M\sp\prime{dollar} which is ordering, i.e. for all {dollar}x,a,b \in M\sp\prime{dollar} if {dollar}xab = x{dollar}, then {dollar}xa = xb = x{dollar}. It is shown that every ordered set has a regular monoid generating it and every upper semilattice has an inverse monoid generating it. If {dollar}M{dollar} generates {dollar}X\sb{lcub}R{rcub}{dollar} in an order preserving manner, then {dollar}X\sb{lcub}R{rcub}{dollar} has the lbub property: every pair of elements having a lower bound has an upper bound. A partial converse is obtained. It is shown that the order automata form a complete and cocomplete category. Every ordered set {dollar}X\sb{lcub}R{rcub}{dollar} has a free monoid {dollar}M{dollar} of minimal dimension such that ({dollar}M,X,R,\eta{dollar}) is an order automaton for some action {dollar}\eta{dollar}. The dimension of {dollar}M{dollar} is termed the free dimension of {dollar}X\sb{lcub}R{rcub}{dollar}. The one dimensional orders are characterized completely. Various bounds on the dimension are determined. The free dimenision is calculated explicitly for all finite orders, all linear orders and those of infinite free dimension. A tight bound is obtained for finite free dimensional orders. An analogue of the finite condensation defined for linear orders is developed and used to explore the properties of finite free abelian dimensional orders.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.