Questions tagged [monoid]
The monoid tag has no usage guidance.
10 questions
7
votes
1
answer
166
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 ...
- 262
6
votes
1
answer
233
views
star height of star-free languages
I'm interested in the (restricted) star-height of star free-languages.
Recalling the definitions:
the star height $h(\mathtt{e})$ of a regular expression $\mathtt{e}$ is
$0$ if $\mathtt{e}= \...
- 193
5
votes
1
answer
233
views
Post correspondence problem for finite monoids
The Post correspondence problem has the following version for finite monoids:
Input: a finite monoid $M$ and a finite list $(m_1,m_1'),\ldots, (m_n,m_n')$ of pairs of elements of $M$
Question: is ...
- 51
3
votes
3
answers
177
views
Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$
Let $M$ be a monoid, the family of rational sets $\operatorname{RAT}(M)$ is defined as the smallest set containing the finite subsets, and closed under union, concatentaion and the star operation. The ...
- 2,057
9
votes
1
answer
319
views
Generalisation of the statement that a monoid recognizes language iff syntactic monoid divides monoid
Let $A$ be a finite alphabet. For a given language $L \subseteq A^{\ast}$ the syntactic monoid $M(L)$ is a well-known notion in formal language theory. Furthermore, a monoid $M$ recognizes a language $...
- 2,057
9
votes
1
answer
433
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 ...
- 1,365
15
votes
3
answers
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 ...
- 2,057
8
votes
0
answers
147
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 ...
- 181
9
votes
2
answers
849
views
Formal representation of an abstraction hierarchy
Introduction
I'm writing my PhD thesis on Abstract Delta Modeling (ADM), an abstract algebraic description of modifications (known as deltas) able to act on products (as in 'software products'). This ...
- 231
6
votes
0
answers
195
views
Complexity of Roman numeral evaluation
I came up with a result the other day that arbitrary length Roman numeral evaluation can be modeled as a monoid:
https://gist.github.com/4542999
1) Is this a known result?
2) If not, any ...
- 2,369