Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAutomaton semigroup free products revisited
70
0
0.0
(
0
)
Added by
Tara Brough
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Tara Brough
Ask ChatGPT about the research
No Arabic abstract
An improvement on earlier results on free products of automaton semigroups; showing that a free product of two automaton semigroups is again an automaton semigroup providing there exists a homomorphism from one of the base semigroups to the other. The result is extended by induction to give a condition for a free product of finitely many automaton semigroups to be an automaton semigroup.
rate research
Read More
The aim of this paper is to investigate whether the class of automaton semigroups is closed under certain semigroup constructions. We prove that the free product of two automaton semigroups that contain left identities is again an automaton semigroup. We also show that the class of automaton semigroups is closed under the combined operation of free product followed by adjoining an identity. We present an example of a free product of finite semigroups that we conjecture is not an automaton semigroup. Turning to wreath products, we consider two slight generalizations of the concept of an automaton semigroup, and show that a wreath product of an automaton monoid and a finite monoid arises as a generalized automaton semigroup in both senses. We also suggest a potential counterexample that would show that a wreath product of an automaton monoid and a finite monoid is not a necessarily an automaton monoid in the usual sense.
Tetris is a popular puzzle video game, invented in 1984. We formulate tw
This paper studies the classes of semigoups and monoids with context-free and deterministic context-free word problem. First, some examples are exhibited to clarify the relationship between these classes and their connection with the notions of word-hyperbolicity and automaticity. Second, a study is made of whether these classes are closed under applying certain semigroup constructions, including direct products and free products, or under regressing from the results of such constructions to the original semigroup(s) or monoid(s).
We consider the class of groups whose word problem is poly-context-free; that is, an intersection of finitely many context-free languages. We show that any group which is virtually a finitely generated subgroup of a direct product of free groups has poly-context-free word problem, and conjecture that the converse also holds. We prove our conjecture for several classes of soluble groups, including metabelian groups and torsion-free soluble groups, and present progress towards resolving the conjecture for soluble groups in general. Some of the techniques introduced for proving languages not to be poly-context-free may be of independent interest.
This paper considers the word problem for free inverse monoids of finite rank from a language theory perspective. It is shown that no free inverse monoid has context-free word problem; that the word problem of the free inverse monoid of rank $1$ is both $2$-context-free (an intersection of two context-free languages) and ET0L; that the co-word problem of the free inverse monoid of rank $1$ is context-free; and that the word problem of a free inverse monoid of rank greater than $1$ is not poly-context-free.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
