Questions tagged [monoid]
The monoid tag has no usage guidance.
8
questions
5
votes
1answer
188 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 ...
3
votes
3answers
119 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 ...
9
votes
1answer
169 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 $...
9
votes
1answer
318 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 ...
14
votes
3answers
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 ...
7
votes
0answers
108 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 ...
9
votes
2answers
802 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 ...
6
votes
0answers
187 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 ...
