Results 1 to 10 of about 20,804 (234)
Generalized Results on Monoids as Memory [PDF]
Electronic Proceedings in Theoretical Computer Science, 2017 We show that some results from the theory of group automata and monoid automata still hold for more general classes of monoids and models. Extending previous work for finite automata over commutative groups, we demonstrate a context-free language that ...
Özlem Salehi +2 more
doaj +3 more sources
On a factorisation of free monoids [PDF]
Proceedings of the American Mathematical Society, 1965 A property is given which relates two results of Spitzer [6]; it also relates two results of Chen, Fox and Lyndon [1]; the same remark applies to work of Meyer-Wunderli [5] and M. Hall [3] and to its generalisation by Lazard [4]. These connections are indicated more fully below.
M. P. Schützenberger
openalex +3 more sources
Congruence Preserving Functions on Free Monoids [PDF]
Algebra universalis, 2016 A function on an algebra is congruence preserving if, for any congruence, it maps congruent elements to congruent elements. We show that, on a free monoid generated by at least 3 letters, a function from the free monoid into itself is congruence preserving %nonmonogenic if and only if it is of the form $x \mapsto w_0 x w_1 \cdots w_{n-1} x w_n$ for ...
Patrick Cégielski +2 more
openalex +5 more sources
Walking automata in free inverse monoids [PDF]
, 2016 Walking automata, be they running over words, trees or even graphs, possibly extended with pebbles that can be dropped and lifted on vertices, have long been defined and studied in Computer Science. However, questions concerning walking automata are surprisingly complex to solve.
David Janin
openalex +4 more sources
On a complete lattice of retracts of a free monoid generated by three elements [PDF]
Opuscula Mathematica, 2008 We prove that the family of retracts of a free monoid generated by three elements, partially ordered with respect to the inclusion, is a complete lattice.
Wit Foryś
doaj +2 more sources
Generalizations of free monoids [PDF]
Semigroup ForumWe generalize free monoids by defining $k$-monoids. These are nothing other than the one-vertex higher-rank graphs used in $C^{\ast}$-algebra theory with the cardinality requirement waived. The $1$-monoids are precisely the free monoids. We then take the next step and generalize $k$-monoids in such a way that self-similar group actions yield monoids of
Mark V. Lawson, Alina Vdovina
openalex +4 more sources
Free submonoids of hyperbolic monoids [PDF]
In this paper, we prove that infinite cancellative finitely generated hyperbolic monoids never contain $\mathbb N\times\mathbb N$ as a submonoid but that they contain an element of infinite order and, if they are elementary, then they also contain a free monoid of rank at least 2. As a corollary we obtain that the latter have exponential growth.
Matthias Hamann
openalex +3 more sources
Prefix monoids of groups and right units of special inverse monoids
Forum of Mathematics, Sigma, 2023 A prefix monoid is a finitely generated submonoid of a finitely presented group generated by the prefixes of its defining relators. Important results of Guba (1997), and of Ivanov, Margolis and Meakin (2001), show how the word problem for certain one ...
Igor Dolinka, Robert D. Gray
doaj +1 more source
On morphisms preserving infinite Lyndon words [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 In a previous paper, we characterized free monoid morphisms preserving finite Lyndon words. In particular, we proved that such a morphism preserves the order on finite words.
Gwenael Richomme
doaj +3 more sources