The idempotent-separating degree of a block-group

Semigroup Forum, nº76 (2008), pg.579-583

The cardinal and the idempotent number of various monoids of transformations on a finite chain

Bulletin of the Malaysian Mathematical Sciences Society, 2, 34 (1),(2011), p. 79–85

The cardinal of various monoids of transformations that preserve a uniform partition

In this paper we give formulas for the number of elements of the monoids ORm x n of all full transformations on it finite chain with tun elements that preserve it uniform m-partition and preserve or reverse the orientation and for its submonoids ODm x n of all order-preserving or order-reversing elements, OPm x n of all orientation-preserving elements, O-m x n of all order-preserving elements, O-m x n(+) of all extensive order-preserving elements and O-m x n(-) of all co-extensive order-preserving elements.

Solvable monoids with commuting idempotents

International Journal of Algebra and Computation, 15, nº 3 (2005), p. 547-570

Normally ordered semigroups

Glasgow Mathematical Journal, nº 50 (2008), p. 325-333

The orthogonal subcategory problem in homotopy theory

It is known that, in a locally presentable category, localization exists with respect to every set of morphisms, while the statement that localization with respect to every (possibly proper) class of morphisms exists in locally presentable categories is equivalent to a large-cardinal axiom from set theory. One proves similarly, on one hand, that homotopy localization exists with respect to sets of maps in every cofibrantly generated, left proper, simplicial model category M whose underlying category is locally presentable. On the other hand, as we show in this article, the existence of localization with respect to possibly proper classes of maps in a model category M satisfying the above assumptions is implied by a large-cardinal axiom called Vopënka's principle, although we do not know if the reverse implication holds. We also show that, under the same assumptions on M, every endofunctor of M that is idempotent up to homotopy is equivalent to localization with respect to some class S of maps, and if Vopënka's principle holds then S can be chosen to be a set. There are examples showing that the latter need not be true if M is not cofibrantly generated. The above assumptions on M are satisfied by simplicial sets and symmetric spectra over simplicial sets, among many other model categories.

Generating finite integral relation algebras

Relation algebras and categories of relations in particular have proven to be extremely useful as a fundamental tool in mathematics and computer science. Since relation algebras are Boolean algebras with some well-behaved operations, every such algebra provides an atom structure, i.e., a relational structure on its set of atoms. In the case of complete and atomic structure (e.g. finite algebras), the original algebra can be recovered from its atom structure by using the complex algebra construction. This gives a representation of relation algebras as the complex algebra of a certain relational structure. This property is of particular interest because storing the atom structure requires less space than the entire algebra. In this thesis I want to introduce and implement three structures representing atom structures of integral heterogeneous relation algebras, i.e., categorical versions of relation algebras. The first structure will simply embed a homogeneous atom structure of a relation algebra into the heterogeneous context. The second structure is obtained by splitting all symmetric idempotent relations. This new algebra is in almost all cases an heterogeneous structure having more objects than the original one. Finally, I will define two different union operations to combine two algebras into a single one.

A study on semigroup action on fuzzy subsets, inverse fuzzy automata and related topics

This thesis comprises five chapters including the introductory chapter. This includes a brief introduction and basic definitions of fuzzy set theory and its applications, semigroup action on sets, finite semigroup theory, its application in automata theory along with references which are used in this thesis. In the second chapter we defined an S-fuzzy subset of X with the extension of the notion of semigroup action of S on X to semigroup action of S on to a fuzzy subset of X using Zadeh's maximal extension principal and proved some results based on this. We also defined an S-fuzzy morphism between two S-fuzzy subsets of X and they together form a category S FSETX. Some general properties and special objects in this category are studied and finally proved that S SET and S FSET are categorically equivalent. Further we tried to generalize this concept to the action of a fuzzy semigroup on fuzzy subsets. As an application, using the above idea, we convert a _nite state automaton to a finite fuzzy state automaton. A classical automata determine whether a word is accepted by the automaton where as a _nite fuzzy state automaton determine the degree of acceptance of the word by the automaton. 1.5. Summary of the Thesis 17 In the third chapter we de_ne regular and inverse fuzzy automata, its construction, and prove that the corresponding transition monoids are regular and inverse monoids respectively. The languages accepted by an inverse fuzzy automata is an inverse fuzzy language and we give a characterization of an inverse fuzzy language. We study some of its algebraic properties and prove that the collection IFL on an alphabet does not form a variety since it is not closed under inverse homomorphic images. We also prove some results based on the fact that a semigroup is inverse if and only if idempotents commute and every L-class or R-class contains a unique idempotent. Fourth chapter includes a study of the structure of the automorphism group of a deterministic faithful inverse fuzzy automaton and prove that it is equal to a subgroup of the inverse monoid of all one-one partial fuzzy transformations on the state set. In the fifth chapter we define min-weighted and max-weighted power automata study some of its algebraic properties and prove that a fuzzy automaton and the fuzzy power automata associated with it have the same transition monoids. The thesis ends with a conclusion of the work done and the scope of further study.

Sheaves, local homeomorphisms and local sets as Hilbert locale modules

We give a thorough account of the various equivalent notions for \sheaf" on a locale, namely the separated and complete presheaves, the local home- omorphisms, and the local sets, and to provide a new approach based on quantale modules whereby we see that sheaves can be identi¯ed with certain Hilbert modules in the sense of Paseka. This formulation provides us with an interesting category that has immediate meaningful relations to those of sheaves, local homeomorphisms and local sets. The concept of B-set (local set over the locale B) present in [3] is seen as a simetric idempotent matrix with entries on B, and a map of B-sets as de¯ned in [8] is shown to be also a matrix satisfying some conditions. This gives us useful tools that permit the algebraic manipulation of B-sets. The main result is to show that the existing notions of \sheaf" on a locale B are also equivalent to a new concept what we call a Hilbert module with an Hilbert base. These modules are the projective modules since they are the image of a free module by a idempotent automorphism On the ¯rst chapter, we recall some well known results about partially ordered sets and lattices. On chapter two we introduce the category of Sup-lattices, and the cate- gory of locales, Loc. We describe the adjunction between this category and the category Top of topological spaces whose restriction to spacial locales give us a duality between this category and the category of sober spaces. We ¯nish this chapter with the de¯nitions of module over a quantale and Hilbert Module. Chapter three concerns with various equivalent notions namely: sheaves of sets, local homeomorphisms and local sets (projection matrices with entries on a locale). We ¯nish giving a direct algebraic proof that each local set is isomorphic to a complete local set, whose rows correspond to the singletons. On chapter four we de¯ne B-locale, study open maps and local homeo- morphims. The main new result is on the ¯fth chapter where we de¯ne the Hilbert modules and Hilbert modules with an Hilbert and show this latter concept is equivalent to the previous notions of sheaf over a locale.

Exact Unification and Admissibility

A new hierarchy of "exact" unification types is introduced, motivated by the study of admissible rules for equational classes and non-classical logics. In this setting, unifiers of identities in an equational class are preordered, not by instantiation, but rather by inclusion over the corresponding sets of unified identities. Minimal complete sets of unifiers under this new preordering always have a smaller or equal cardinality than those provided by the standard instantiation preordering, and in significant cases a dramatic reduction may be observed. In particular, the classes of distributive lattices, idempotent semigroups, and MV-algebras, which all have nullary unification type, have unitary or finitary exact type. These results are obtained via an algebraic interpretation of exact unification, inspired by Ghilardi's algebraic approach to equational unification.

On the completion of Latin rectangles to symmetric Latin squares

We find necessary and sufficient conditions for completing an arbitrary 2 by n latin rectangle to an n by n symmetric latin square, for completing an arbitrary 2 by n latin rectangle to an n by n unipotent symmetric latin square, and for completing an arbitrary 1 by n latin rectangle to an n by n idempotent symmetric latin square. Equivalently, we prove necessary and sufficient conditions for the existence of an (n - 1)-edge colouring of K-n (n even), and for an n-edge colouring of K-n (n odd) in which the colours assigned to the edges incident with two vertices are specified in advance.

On the Semigroup of all Increasing Full Transformations

Илинка А. Димитрова - Полугрупата Tn от всички пълни преобразувания върху едно n-елементно множество е изучавана в различни аспекти ог редица автори. Обект на разглеждане в настоящата работа е полугрупата Incn състояща се от всички нарастващи пълни преобразувания. Очевидно Incn е подполугрупа на Tn. Доказано е, че всеки елемент на полугрупата Incn от ранг r може да се представи като произведение на идемпотенти от същия ранг и всеки идемпотент от ранг по-малък или равен на r може да се представи като произведение на идемпотенти от ранг r. С помощта на тези твърдения е показано, че полугрупата Incn се поражда от множеството на всички идемпотенти от ранг n − 1 и тъждественото преобразувание. Освен това е доказано, че идемпотентите от ранг n − 1 са неразложими в полугрупата Incn. В резултат на това е получено, че рангът и идемпотичниат ранг на разглежданата полугрупа са равни. Като са използвани тези твърдения е направена пълна класификация на маскималните подполугрупи на полугрупата Incn.

Splitting monoidal stable model categories

If C is a stable model category with a monoidal product then the set of homotopy classes of self-maps of the unit forms a commutative ring, [S,S]C. An idempotent e of this ring will split the homotopy category: [X,Y]C≅e[X,Y]C⊕(1−e)[X,Y]C. We prove that provided the localised model structures exist, this splitting of the homotopy category comes from a splitting of the model category, that is, C is Quillen equivalent to LeSC×L(1−e)SC and [X,Y]LeSC≅e[X,Y]C. This Quillen equivalence is strong monoidal and is symmetric when the monoidal product of C is.

On Reasonable Space and Time Cost Models for the λ-Calculus

Slot and van Emde Boas Invariance Thesis states that a time (respectively, space) cost model is reasonable for a computational model C if there are mutual simulations between Turing machines and C such that the overhead is polynomial in time (respectively, linear in space). The rationale is that under the Invariance Thesis, complexity classes such as LOGSPACE, P, PSPACE, become robust, i.e. machine independent. In this dissertation, we want to find out if it possible to define a reasonable space cost model for the lambda-calculus, the paradigmatic model for functional programming languages. We start by considering an unusual evaluation mechanism for the lambda-calculus, based on Girard's Geometry of Interaction, that was conjectured to be the key ingredient to obtain a space reasonable cost model. By a fine complexity analysis of this schema, based on new variants of non-idempotent intersection types, we disprove this conjecture. Then, we change the target of our analysis. We consider a variant over Krivine's abstract machine, a standard evaluation mechanism for the call-by-name lambda-calculus, optimized for space complexity, and implemented without any pointer. A fine analysis of the execution of (a refined version of) the encoding of Turing machines into the lambda-calculus allows us to conclude that the space consumed by this machine is indeed a reasonable space cost model. In particular, for the first time we are able to measure also sub-linear space complexities. Moreover, we transfer this result to the call-by-value case. Finally, we provide also an intersection type system that characterizes compositionally this new reasonable space measure. This is done through a minimal, yet non trivial, modification of the original de Carvalho type system.