1,720,980 research outputs found
Bicyclic subsemigroups in amalgams of finite inverse semigroups
No full textIt is well known that an inverse semigroup is completely semisimple if and only if it does not contain a copy of the bicyclic semigroup. We characterize the amalgams [S1, S2; U] of two finite inverse semigroups S1, S2 whose free product with amalgamation is completely semisimple and we show that checking whether the amalgamated free product of finite inverse semigroups contains a bicyclic subsemigroup is decidable by means of a polynomial time algorithm with respect to max{|S1|,|S 2|}. Moreover we consider amalgams of finite inverse semigroups respecting the J-order proving that the free product with amalgamation is completely semisimple and we also provide necessary and sufficient conditions for the R-classes to be finite. © 2010 World Scientific Publishing Company
Regular ideal languages and synchronizing automata
No full textWe introduce the notion of reset left regular decomposition of an ideal regular language and we prove that there is a one-to-one correspondence between these decompositions and strongly connected synchronizing automata. We show that each ideal regular language has at least a reset left regular decomposition. As a consequence each ideal regular language is the set of synchronizing words of some strongly connected synchronizing automaton. Furthermore, this one-to-one correspondence allows us to formulate Černý's conjecture in a pure language theoretic framework. © 2013 Springer-Verlag Berlin Heidelberg
Missing factors of ideals and synchronizing automata
No full textRecently, a series of papers have started to look at Cerný‘s conjecture, and in general at synchronizing automata, from the point of view of the theory of ideals of free monoids. The starting point of such an approach is a simple observation: the set of reset words of an automaton is a two-sided ideal of the free monoid on its alphabet that is also a regular language. We study the relationship between a synchronizing automaton and the sets of (minimal) generators of its reset words. We show that if such set does not contain a word of a certain length, then Cerný‘s conjecture holds
Amalgams of inverse semigroups and reversible two-counter machines
No full textWe show that the word problem for an amalgam [S 1, S 2;U, ω 1, ω 2] of inverse semigroups may be undecidable even if we assume S 1 and S 2 (and therefore U) to have finite R-classes and ω 1, ω 2 to be computable functions, interrupting a series of positive decidability results on the subject. This is achieved by encoding into an appropriate amalgam of inverse semigroups 2-counter machines with sufficient universality, and relating the nature of certain Schützenbergergraphs to sequences of computations in the machine. © 2012 Elsevier B.V
On periodic points of free inverse monoid homomorphisms
No full textIt is proved that the periodic point submonoid of a free inverse monoid endomorphism is always finitely generated. Using Chomsky's hierarchy of languages, we prove that the fixed point submonoid of an endomorphism of a free inverse monoid can be represented by a context-sensitive language but, in general, it cannot be represented by a context-free language. © 2013 World Scientific Publishing Company
Semisimple synchronizing automata and the wedderburn-artin theory
No full textWe approach Černý's conjecture using the Wedderburn- Artin theory. We first introduce the radical ideal of a synchronizing automaton, and then the natural notion of semisimple synchronizing automata. This is a rather broad class since it contains simple synchronizing automata like those in Černý's series. Furthermore, semisimplicity gives the advantage of "factorizing" the problem of finding a synchronizing word into the sub-problems of finding words that are zeros in the projections into the simple components in the Wedderburn-Artin decomposition. This situation is applied to prove that Černý's conjecture holds for the class of strongly semisimple synchronizing automata. These are automata whose sets of synchronizing words are cyclic ideals, or equivalently are ideal regular languages which are closed by takings roots. © 2014 Springer International Publishing Switzerland
Fixed points of endomorphisms of graph groups
No full textIt is shown, for a given graph group G, that the fixed point subgroup Fix φ is finitely generated for every endomorphism φ of G if and only if G is a free product of free abelian groups. The same conditions hold for the subgroup of periodic points. Similar results are obtained for automorphisms if the dependence graph of G is a transitive forest. © de Gruyter 2013
Catalan fragile words
Full text linkFragile words have been already considered in the context of automata groups. Here we focus our attention on a special class of strongly fragile words that we call Catalan fragile words. Among other properties, we show that there exists a one-to-one correspondence between the set of Catalan fragile words and the set of full binary trees
Automaton semigroups and groups: On the undecidability of problems related to freeness and finiteness
Full text linkIn this paper, we study algorithmic problems for automaton semigroups and automaton groups related to freeness and finiteness. In the course of this study, we also exhibit some connections between the algebraic structure of automaton (semi)groups and their dynamics on the boundary. First, we show that it is undecidable to check whether the group generated by a given invertible automaton has a positive relation, i.e., a relation p = 1 such that p only contains positive generators. Besides its obvious relation to the freeness of the group, the absence of positive relations has previously been studied by the first two authors and is connected to the triviality of some stabilizers of the boundary. We show that the emptiness of the set of positive relations is equivalent to the dynamical property that all (directed positive) orbital graphs centered at non-singular points are acyclic. Our approach also works to show undecidability of the freeness problem for automaton semigroups, which negatively solves an open problem by Grigorchuk, Nekrashevych and Sushchansky. In fact, we show undecidability of a strengthened version where the input automaton is complete and invertible. Gillibert showed that the finiteness problem for automaton semigroups is undecidable. In the second part of the paper, we show that this undecidability result also holds if the input is restricted to be bi-reversible and invertible (but, in general, not complete). As an immediate consequence, we obtain that the finiteness problem for automaton subsemigroups of semigroups generated by invertible, yet partial automata, so called automaton-inverse semigroups, is also undecidable
State complexity of code operators
No full textWe consider five operators on a regular language. Each of them is a tool for constructing a code (respectively prefix, suffix, bifix, infix) and a hypercode out of a given regular language. We give the precise values of the (deterministic) state complexity of these operators: over a constant-size alphabet for the first four of them and over a quadratic-size alphabet for the hypercode operator. © 2011 World Scientific Publishing Company
- …
