7 results for Jackson, Marcel

  • On representing semigroups with subsemilattices

    Jackson, Marcel; Stokes, Tim E. (2013)

    Journal article
    University of Waikato

    We examine the problem of representing semigroups as binary relations, partial maps and injective functions, with the constraint that certain pre-designated 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 Waikato

    The 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 if-then-else and halting programs

    Jackson, Marcel; Stokes, Tim E. (2009)

    Journal article
    University of Waikato

    The "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 Waikato

    Restriction 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 domain-related and set-theoretic 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 Waikato

    We consider the identities of a variety of semigroup-related 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 Waikato

    This paper concerns the theory of partial maps under composition and more generally, the RC-semigroups 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 meet-semilattice 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 non-semigroup 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 so-called interior semigroups, and a natural category associated with a large variety of RC-semigroups (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 meet-semilattice structure.

    View record details
  • Monoids with tests and the algebra of possibly non-halting programs

    Jackson, Marcel; Stokes, Tim E. (2015-03)

    Journal article
    University of Waikato

    We study the algebraic theory of computable functions, which can be viewed as arising from possibly non-halting computer programs or algorithms, acting on some state space, equipped with operations of composition, if-then-else and while-do 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 while-do 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 if-then-else, we are able to give finite axiomatisations of the resulting algebras of (partial) functions, with while-do 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 (one-sided) restriction semigroup

    View record details