Search

We introduce a new measure on regular languages: their nondeterministic syntactic complexity. It is the least degree of any extension of the ‘canonical boolean representation’ of the syntactic monoid. Equivalently, it is the least number of states of any subatomic nondeterministic acceptor. It turns out that essentially all previous structural work on nondeterministic state-minimality computes this measure. Our approach rests on an algebraic interpretation of nondeterministic finite automata as deterministic finite automata endowed with semilattice structure. Crucially, the latter form a self-dual category.

Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property \(\varPhi \). What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question is if there exists one graph satisfying \(\varPhi \)? We approach this question by using formal languages for specifying families of graphs. In particular, we show that certain graph properties can be decided by studying the syntactic monoid of the specification language.

A fundamental result about formal languages states: Theorem 1 A regular language is first-order definable if and only if its syntactic monoid contains no nontrivial groups. Rest assured, we will explain in the next section exactly what the various terms in the statement mean!

We establish necessary and sufficient conditions for a semigroup identity to hold in the monoid of $n\times n$ upper triangular tropical matrices, in terms of equivalence of certain tropical polynomials. This leads to an algorithm for checking whether such an identity holds, in time polynomial in the length of the identity and size of the alphabet. It also allows us to answer a question of Izhakian and Margolis, by showing that the identities which hold in the monoid of $2\times 2$ upper triangular tropical matrices are exactly the same as those which hold in the bicyclic monoid. Our results extend to a broader class of "chain structured tropical matrix semigroups"; we exhibit a faithful representation of the free monogenic inverse semigroup within such a semigroup, which leads also to a representation by $3\times 3$ upper triangular matrix semigroups, and a new proof of the fact that this semigroup satisfies the same identities as the bicyclic monoid., Comment: 21 pages. This amended version of the author accepted manuscript contains a corrected proof of Proposition 7.1. The new proof establishes the proposition exactly as originally published, all other results are unaffected and the manuscript is otherwise unamended

In this paper the concept of Parikh-reducing Church–Rosser systems is studied. It is shown that for two classes of regular languages there exist such systems which describe the languages using finitely many equivalence classes of the rewriting system. The two classes are: 1.) the class of all regular languages such that the syntactic monoid contains only abelian groups and 2.) the class of all group languages over a two-letter alphabet. The construction of the systems yield a monoid representation such that all subgroups are abelian. Additionally, the complexity of those representations is studied.

We relate the old and new cohomology monoids of an arbitrary monoid $M$ with coefficients in semimodules over $M$, introduced in the author's previous papers, to monoid and group extensions. More precisely, the old and new second cohomology monoids describe Schreier extensions of semimodules by monoids, and the new third cohomology monoid is related to a certain group extension problem.

In this paper, completely regular endomorphisms of the join of split graphs are investigated. We give conditions under which all completely regular endomorphisms of the join of two split graphs form a monoid.

In this paper we determine the $$G\times G$$ orbits of both an even orthogonal monoid and an even special orthogonal monoid, where G is the unit group of the even special orthogonal monoid. We then use the orbit decompositions to compute the orders of these monoids over a finite field.

In this paper, we investigate the basis graph of the monoid algebra of a submonoid of the monoid of mappings from N = {1,…,n} to itself, defined by a nested sequence of compositions of N. Each such monoid is a left regular band (LRB), that is, a semigroup S satisfying x2 = x and xyx = xy for all x,y∈S. This class is sufficiently rich that every path algebra of an acyclic quiver can be embedded in such a monoid algebra. The multiplication in the monoid algebra has a particularly simple quasi-multiplicative form, allowing definition over the integers. Combining this with a formula for Ext-groups for LRBs due to Margolis et al. [6], we get a simple criterion for the nested composition algebras to be hereditary.

A semigroup S is called permutable if $$ \rho $$ ◦ σ = σ ◦ $$ \rho $$ for any pair of congruences $$ \rho $$ , σ on S. A local automorphism of the semigroup S is defined as an isomorphism between two subsemigroups of this semigroup. The set of all local automorphisms of a semigroup S with respect to an ordinary operation of composition of binary relations forms an inverse monoid of local automorphisms. We present a classification of all finite nilsemigroups for which the inverse monoid of local automorphisms is permutable.

We show that every semigroup with an RE word problem can be pointwise represented in the lambda calculus. In addition, we show that the free monoid generated by an arbitrary RE subset of combinators can be represented as the monoid of all terms which fix a finite set of points.

Using the theory of monoids and monoid actions, we give a unified framework that handles three common pointer manipulation tasks, namely, data serialisation, deserialisation, and memory allocation. Our main theoretical contribution is the formulation of the notion of a twisted functor , a generalisation of the semi-direct product construction for monoids. We show that semi-direct products and twisted functors are particularly well suited as an abstraction for many pointer manipulation tasks. We describe the implementation of these abstractions in the context of a cryptographic library for Haskell. Twisted functors allow us to abstract all pointer arithmetic and size calculations into a few lines of code, significantly reducing the opportunities for buffer overflows.

We describe all endomorphisms of a free trioid of rank 1 and construct a semigroup which is isomorphic to the endomorphism monoid of such free trioid. Also, we give an abstract characteristic for the endomorphism monoid of a free trioid of rank 1 and prove that free trioids are determined by their endomorphism monoids.

We study congruences on the semigroup (ℤ lex ) of monotone injective partial self-maps of the set of L n × lexℤ with cofinite domains and images, where L n × lexℤ is the lexicographic product of an n -element chain and a set of integers with ordinary linear order. The structure of the sublattice of congruences on (ℤ lex ) contained in the least group congruence is described.

Let $m,n\in \mathbb{N}$, and $V$ be a $m$-dimensional vector space over a field $F$ of characteristic $0$. Let $U=F\oplus V$ and $R_n$ be the rook monoid. In this paper, we construct a certain quasi-idempotent in the annihilator of $U^{\otimes n}$ in $FR_n$, which comes from some one-dimensional two-sided ideal of rook monoid algebra. We show that the two-sided ideal generated by this element is indeed the whole annihilator of $U^{\otimes n}$ in $FR_n$., 14 pages, 1 figure

We consider the pseudovariety generated by all finite monoids on which Green’s relations ℛ and ℋ coincide. It is shown that any finite monoid S belonging to this pseudovariety divides the monoid of all upper triangular row-monomial matrices over a finite group with zero adjoined. The proof is constructive; given a monoid S, the corresponding group and the order of matrices can be effectively found.

We construct the syntactic nondeterministic monoid associated with a subset L of a nondeterministic monoid M. It is the quotient of M by the greatest nondeterministic congruence∼L on M saturating L and is characterized by the classical universal property.

A zero-one language L is a regular language whose asymptotic probability converges to either zero or one. In this case, we say that L obeys the zero-one law. We prove that a regular language obeys the zero-one law if and only if its syntactic monoid has a zero element, by means of Eilenberg's variety theoretic approach. Our proof gives an effective automata characterisation of the zero-one law for regular languages, and it leads to a linear time algorithm for testing whether a given regular language is zero-one. In addition, we discuss the logical aspects of the zero-one law for regular languages., In Proceedings GandALF 2015, arXiv:1509.06858

Let denote the class of aperiodic monoids with central idempotents. A subvariety of that is not contained in any finitely generated subvariety of is said to be inherently non-finitely generated. A characterization of inherently non-finitely generated subvarieties of , based on identities that they cannot satisfy and monoids that they must contain, is given. It turns out that there exists a unique minimal inherently non-finitely generated subvariety of , the inclusion of which is both necessary and sufficient for a subvariety of to be inherently non-finitely generated. Further, it is decidable in polynomial time if a finite set of identities defines an inherently nonfinitely generated subvariety of .

Weighted tree languages over semirings lack the expressive power to model computations like taking the average or the discounting of weights in a straightforward manner. This limitation was overcome by weighted tree automata and logics using (a) tree valuation monoids and (b) multioperator monoids. We compare the expressive power of these two solutions and show that a weighted tree language recognizable (resp. definable) over a tree valuation monoid is also recognizable (resp. definable) using a multioperator monoid. For this, we provide direct, semantic-preserving transformations between the automata models and between the respective logics. We research the relationship between two classes of weighted tree languages.We give a construction from one automaton model to the other preserving the language.An analogous result is shown for the corresponding weighted tree logics.A direct transformation between the logics avoids nonelementary blow-up.

The aim of this paper is to study the cohomology theory of monoid schemes in general and apply it to vector and line bundles. We will prove that over separated monoid schemes, any vector bundle is a coproduct of line bundles and that the Pic functor respects finite products. Next we will introduce the notion of s-cancellative monoids and show that if X is locally of that type, O X ⁎ can be embed injectively in a constant sheaf. We develop the theory of s-divisors, which generalise the Cartier divisors, and we prove that for s-cancellative monoid schemes, s-divisors describe the group Pic ( X ) . We then generalise smooth monoid schemes with s-smooth monoid schemes, and prove that for them H i ( X , O X ⁎ ) = 0 for all i ≥ 2 . Furthermore we show that it is a local property and respects finite products. Finally we investigate the relationship between line bundles over a monoid scheme X and over its geometric realisation X k , where k is a commutative ring. We prove that if k is an integral domain (resp. PID) and X is a cancellative and torsion-free (resp. seminormal and torsion-free) monoid scheme, then the induced map Pic ( X ) → Pic ( X k ) is a monomorphism (resp. isomorphism).

An endomorphism of the free monoid $${A}^*$$ is invertible if it is injective and extends to an automorphism of the free group generated by $${A}$$ . A simple example: the endomorphism that leaves all generators $${A}$$ invariant except one, say a, which is mapped to ba for some other generator b. We give a monoid presentation for the submonoid generated by all such endomorphisms when a and b are taken arbitrarily. These left translations are a special case of Nielsen positive transformations: “left” because the mutiplicative constant acts on the left and “positive” because this constant belongs to the free monoid, not the free group.

Autonomic computing (AC) is characterized by self-* such as self-configuration, self-healing, self-optimization, self-protection and more which run simultaneously in autonomic systems (ASs). Hence, self-* is a set of self-_'s. Each self-_ in self-* is called self-* action. Our way to interpret self-* is to say that self-* actions are running on ASs. In this paper, algebraic objects called monoids are tasked with encoding the self-* action's perspective in all this, i.e. what the self-* action can do, and what happens when different self-* actions are done in succession.

The half-factorial, locally right Garside monoid of cofinite monotone sequences on $${\mathbb {N}}^{*}$$ is considered in this paper. This is a right cancellative, left rigid Mobius monoid, and this monoid directs us to the inverse monoid of cofinite monotone partial bijections on $${\mathbb {N}}^{*}$$ . In a certain sense, the polycyclic inverse monoid is a 0-analogue of this derived inverse monoid. Similarities and differences between these two inverse monoids are presented involving Mobius categories, Leech’s construction, breaking processes, gauge inverse submonoids, etc.

We study monoids S over which the class of injective S-acts is axiomatizable, complete, and model complete. We prove that, for a countable commutative monoid or a countable group S, the class of injective S-acts is axiomatizable if and only if S is a finitely generated monoid. We show that there is no nontrivial monoid nor a group the class of injective acts over which is complete, model complete, or categorical.

Let $$W$$ be a finite set of words over an alphabet $$X$$ . The discrete syntactic monoid $$S(W)$$ of $$W$$ is a monoid whose elements are $$0, 1$$ and all subwords of words in $$W$$ with the multiplication: for $$\mathbf {w}_1, \mathbf {w}_2 \in W$$ , $$\mathbf {w}_1\cdot \mathbf {w}_2=\mathbf {w}_1\mathbf {w}_2$$ if $$\mathbf {w}_1\mathbf {w}_2$$ is a subword of a word in $$W$$ and $$0$$ otherwise. The set of words $$W$$ is called finitely based if the monoid $$S(W)$$ is finitely based. A single word $$\mathbf {w}$$ is called finitely based if $$\{\mathbf {w}\}$$ is finitely based. In this paper, we classify all finitely based words in a class of words over the alphabet $$\{x,y,z\}$$ without subwords of the form $$xz$$ , $$yx$$ or $$zy$$ .

For \(X\) a pointed simplicial set with a simplicial monoid action, we construct a simplicial monoid and give a sufficient condition for its classifying space to be the homotopy cofiber of the inclusion of \(X\) into its reduced Borel construction. The known formulae for the respective classifying spaces of the four classical constructions of James, Milnor, Carlsson and Wu are special cases of this result. Thus, we unify categorially the four above-mentioned constructions. We also give the classical constructions and an example as the applications of the main result.

We give two explicit (quadratic) presentations of the plactic monoid in row and column generators correspondingly. Then we give direct independent proofs that these presentations are Grobner–Shirshov bases of the plactic algebra in deg-lex orderings of generators. From Composition-Diamond lemma for associative algebras it follows that the set of Young tableaux is the Knuth normal form for plactic monoid ( [30] , see also Ch. 5 in [32] ).