Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDecision problems for inverse monoids presented by a single sparse relator
156
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study a class of inverse monoids of the form M = Inv< X | w=1 >, where the single relator w has a combinatorial property that we call sparse. For a sparse word w, we prove that the word problem for M is decidable. We also show that the set of words in (X cup X^{-1})^* that represent the identity in M is a deterministic context free language, and that the set of geodesics in the Schutzenberger graph of the identity of M is a regular language.
rate research
Read More
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.
We show that groups presented by inverse-closed finite convergent length-reducing rewriting systems are characterised by a striking geometric property: their Cayley graphs are geodetic and side-lengths of non-degenerate triangles are uniformly bounded. This leads to a new algebraic result: the group is plain (isomorphic to the free product of finitely many finite groups and copies of $mathbb Z$) if and only if a certain relation on the set of non-trivial finite-order elements of the group is transitive on a bounded set. We use this to prove that deciding if a group presented by an inverse-closed finite convergent length-reducing rewriting system is not plain is in $mathsf{NP}$. A yes answer would disprove a longstanding conjecture of Madlener and Otto from 1987. We also prove that the isomorphism problem for plain groups presented by inverse-closed finite convergent length-reducing rewriting systems is in $mathsf{PSPACE}$.
Stalactic, taiga, sylvester and Baxter monoids arise from the combinatorics of tableaux by identifying words over a fixed ordered alphabet whenever they produce the same tableau via some insertion algorithm. In this paper, three sufficient conditions under which semigroups are finitely based are given. By applying these sufficient conditions, it is shown that all stalactic and taiga monoids of rank greater than or equal to $2$ are finitely based and satisfy the same identities, that all sylvester monoids of rank greater than or equal to $2$ are finitely based and satisfy the same identities and that all Baxter monoids of rank greater than or equal to $2$ are finitely based and satisfy the same identities.
We continue our programme of extending key techniques from geometric group theory to semigroup theory, by studying monoids acting by isometric embeddings on spaces equipped with asymmetric, partially-defined distance functions. The canonical example of such an action is a cancellative monoid acting by translation on its Cayley graph. Our main result is an extension of the Svarc-Milnor Lemma to this setting.
We prove a freeness theorem for low-rank subgroups of one-relator groups. Let $F$ be a free group, and let $win F$ be a non-primitive element. The primitivity rank of $w$, $pi(w)$, is the smallest rank of a subgroup of $F$ containing $w$ as an imprimitive element. Then any subgroup of the one-relator group $G=F/langlelangle wranglerangle$ generated by fewer than $pi(w)$ elements is free. In particular, if $pi(w)>2$ then $G$ doesnt contain any Baumslag--Solitar groups. The hypothesis that $pi(w)>2$ implies that the presentation complex $X$ of the one-relator group $G$ has negative immersions: if a compact, connected complex $Y$ immerses into $X$ and $chi(Y)geq 0$ then $Y$ is Nielsen equivalent to a graph. The freeness theorem is a consequence of a dependence theorem for free groups, which implies several classical facts about free and one-relator groups, including Magnus Freiheitssatz and theorems of Lyndon, Baumslag, Stallings and Duncan--Howie. The dependence theorem strengthens Wises $w$-cycles conjecture, proved independently by the authors and Helfer--Wise, which implies that the one-relator complex $X$ has non-positive immersions when $pi(w)>1$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
