All Questions
Tagged with algebra fl.formal-languages
11 questions
6
votes
0
answers
240
views
Satisfiability and a Galois Theory Analog
Let $v(a, b)$ be a binary predicate, and define $\phi$ as follows:
$$\phi: v(a_1, b_1) \land v(a_1, b_2) \land (a_1, b_3)$$
where our universe consists of two sorts $A: \{a_1, a_2, a_3\}$ and $B: \{...
- 101
5
votes
2
answers
228
views
Reference request: An algebraic characterisation of LTL[XF]-definable word languages
I'm looking for a reference to the fact that LTL[XF]-definable languages (LTL where only the (strict) finally/future modality is allowed) correspond to the variety $\mathbf{R}$ (see: 1).
A similar ...
- 1,422
11
votes
0
answers
200
views
Are there cascade decompositions of machines that are more general than finite automata?
The idea of decomposing automata and their associated semi-groups into irreducible sub-components is due to Krohn & Rhodes and has been explored relatively thoroughly. Krohn & Rhodes gave an ...
- 361
1
vote
0
answers
67
views
Rational power series over $\mathbb N \cup \{\infty\}$, rationality of singular part
Let $\Sigma$ be a finite alphabet, and consider the formel power series over $\Sigma$ considered as non-commuting variables with coefficients in the semiring $\mathcal N := \mathbb N \cup \{\infty\}$ ...
- 2,057
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
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
4
votes
1
answer
447
views
The polynomial languages and ordered syntactic monoids
A polynomial language is a languge which could be represented as the finite union of languages of the form:
$$
A_0^* a_1 A_1^* a_2 \cdots a_k A_k^* \quad a_i \in X, A_i \subseteq X
$$
Such an ...
- 2,057
13
votes
4
answers
2k
views
(N)DFA with same initial/accepting state(s)
What is known about the class of languages recognized by finite automata having the same initial and accepting state? This is a proper subset of the regular languages (since every such language ...
- 4,831
7
votes
2
answers
322
views
Smallest representatives of a quotient by an equivalence relation
Background
Let $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ be a minimal DFA for a regular language $L$ such that $|Q|=n$, and let $\equiv_L$ be the relation given by $$x\equiv_Ly\text{ iff for all $u$: }xu\...
- 1,406
7
votes
1
answer
658
views
On the relation for the Myhill-Nerode theorem/syntactic monoid of a language
In order to characterize regular languages one finds the following definition useful:
Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\equiv_L$-related, and ...
- 1,406