Date of Award
1989
Degree Type
Dissertation
Degree Name
Doctor of Philosophy
Abstract
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.
Recommended Citation
Sulis, William Herbert, "Order Automata" (1989). Digitized Theses. 1855.
https://ir.lib.uwo.ca/digitizedtheses/1855