7 results for Jackson, Marcel

On representing semigroups with subsemilattices
Jackson, Marcel; Stokes, Tim E. (2013)
Journal article
University of WaikatoWe examine the problem of representing semigroups as binary relations, partial maps and injective functions, with the constraint that certain predesignated idempotent elements must be represented as restrictions of the identity function. Appropriately formulated, the corresponding classes of representable structures is a quasivariety, but we show that they cannot be finitely axiomatised in first order logic. Quite a few algebraic structures have both a semigroup reduct and the ability to distinguish certain idempotent elements, and we use our construction to show that representability for these is also not finitely axiomatisable. Amongst the classes covered are subsemigroups of weakly left ample semigroups, various classes of ordered semigroups, semigroups of various kinds of binary relation with fixset operation. We also give new proofs of the nonfinite axiomatisability of the class of semigroups of binary relations endowed with domain and/or range operations, and of subsemigroups of inverse semigroups.
View record details 
Partial maps with domain and range: extending Schein's representation
Jackson, Marcel; Stokes, Tim E. (2009)
Journal article
University of WaikatoThe semigroup of all partial maps on a set under the operation of composition admits a number of operations relating to the domain and range of a partial map. Of particular interest are the operations R and L returning the identity on the domain of a map and on the range of a map respectively. Schein [25] gave an axiomatic characterisation of the semigroups with R and L representable as systems of partial maps; the class is a finitely axiomatisable quasivariety closely related to ample semigroups (which were introduced—as type A semigroups—by Fountain, [7]). We provide an account of Schein's result (which until now appears only in Russian) and extend Schein's method to include the binary operations of intersection, of greatest common range restriction, and some unary operations relating to the set of fixed points of a partial map. Unlike the case of semigroups with R and L, a number of the possibilities can be equationally axiomatised.
View record details 
Semigroups with ifthenelse and halting programs
Jackson, Marcel; Stokes, Tim E. (2009)
Journal article
University of WaikatoThe "if–then–else" construction is one of the most elementary programming commands, and its abstract laws have been widely studied, starting with McCarthy. Possibly, the most obvious extension of this is to include the operation of composition of programs, which gives a semigroup of functions (total, partial, or possibly general binary relations) that can be recombined using if–then–else. We show that this particular extension admits no finite complete axiomatization and instead focus on the case where composition of functions with predicates is also allowed (and we argue there is good reason to take this approach). In the case of total functions — modeling halting programs — we give a complete axiomatization for the theory in terms of a finite system of equations. We obtain a similar result when an operation of equality test and/or fixed point test is included.
View record details 
Modal restriction semigroups: towards an algebra of functions
Jackson, Marcel; Stokes, Tim E. (2011)
Journal article
University of WaikatoRestriction semigroups model algebras of partial maps under composition and domain. Here we consider restriction semigroups for which the usual Boolean operations on domains are modeled. Such algebras are capable of modeling the usual modal operators considered in dynamic logic. Indeed adding a natural functional variant of union to the signature gives a deterministic version of the modal semirings of Möller and Struth, but also a monoidal version of the classical restriction categories of Cockett and Manes. Other operations modeled are intersection and (in the finite case) functional iteration. In each case, axiomatizations of the concrete functional examples are given, leading to algebraic models of partial maps incorporating all the domainrelated and settheoretic operations previously considered. Our algebras furnish natural algebraic semantics for the logics of deterministic computer programs, leading to new results for some variants of propositional dynamic logic.
View record details 
Identities in the Algebra of Partial Maps
Jackson, Marcel; Stokes, Tim E. (2006)
Journal article
University of WaikatoWe consider the identities of a variety of semigrouprelated algebras modelling the algebra of partial maps. We show that the identities are intimately related to a weak semigroup deductive system and we show that the equational theory is decidable. We do this by giving a term rewriting system for the variety. We then show that this variety has many subvarieties whose equational theory interprets the full uniform word problem for semigroups and consequently are undecidable. As a corollary it is shown that the equational theory of Clifford semigroups whose natural order is a semilattice is undecidable.
View record details 
Agreeable semigroups
Jackson, Marcel; Stokes, Tim E. (2003)
Journal article
University of WaikatoThis paper concerns the theory of partial maps under composition and more generally, the RCsemigroups introduced by Jackson and Stokes [Semigroup Forum 62 (2001) 279–310] (semigroups with a unary operation called (right) closure). Many of the motivating examples have a natural meetsemilattice structure; the inverse semigroup of all injective partial transformations of a set and the semigroup of all binary operations under composition are two examples. We here view the semilattice meet as an additional operation, thereby obtaining a variety of algebras with one unary and two binary operations. The two nonsemigroup operations are then shown to be captured by a single binary operation, via the notion of an agreeable semigroup. We look at a number of properties of these structures including their congruences (which are uniquely determined by their restriction to certain idempotents), a relationship with socalled interior semigroups, and a natural category associated with a large variety of RCsemigroups (which includes all inverse semigroups). For example, we show that the existence of equalisers in this category is intimately connected with the existence of the natural meetsemilattice structure.
View record details 
Monoids with tests and the algebra of possibly nonhalting programs
Jackson, Marcel; Stokes, Tim E. (201503)
Journal article
University of WaikatoWe study the algebraic theory of computable functions, which can be viewed as arising from possibly nonhalting computer programs or algorithms, acting on some state space, equipped with operations of composition, ifthenelse and whiledo defined in terms of a Boolean algebra of conditions. It has previously been shown that there is no finite axiomatisation of algebras of partial functions under these operations alone, and this holds even if one restricts attention to transformations (representing halting programs) rather than partial functions, and omits whiledo from the signature. In the halting case, there is a natural “fix”, which is to allow composition of halting programs with conditions, and then the resulting algebras admit a finite axiomatisation. In the current setting such compositions are not possible, but by extending the notion of ifthenelse, we are able to give finite axiomatisations of the resulting algebras of (partial) functions, with whiledo in the signature if the state space is assumed finite. The axiomatisations are extended to consider the partial predicate of equality. All algebras considered turn out to be enrichments of the notion of a (onesided) restriction semigroup
View record details