# Questions tagged [monoid]

The tag has no usage guidance.

10 questions
Filter by
Sorted by
Tagged with
151 views

### Complexity of the inevitability problem over monoids

I am interested in the complexity of following problem: Inevitability problem in monoids Input: two regular languages $K$, $L$ specified by finite monoids $M_K$ and $M_L$ (+ morphisms and accepting ...
203 views

414 views

### Transition monoid membership for DFAs

Given a complete DFA $A=(Q, \Gamma, \delta, F)$, we can define a collection of functions $f_a$ for each $a\in \Gamma$and with $f_a:Q\rightarrow Q$, $f_a(q)=\delta(q, a)$. We can generalize this notion ...
2k views

### On the realisation of monoids as syntactic monoids of languages

Let $L \subseteq X^{\ast}$ be some language, then we define the syntactic congruence as $$u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L$$ and the quotient ...
144 views

### What is the optimal binary encoding of the elements of a monoid?

The Question Let $M$ be a finite monoid. Let $S$ be a generating set of $M$. Say we have a binary encoding of $S$ represented by $\phi:S \rightarrow A^*$ where $A = \{0, 1\}$. This encoding should ...