My question refers to the draft of Mathematical Foundations of Automata Theory, IV.2.1 (pages 89ff in the pdf). I will repeat everything necessary nevertheless:

Let $M,N$ be monoids and $\varphi: M \rightarrow N $ a monoid morphism. We say that a subset $L$ of $M$ is recognizable by $\varphi$ if there is a subset $P$ of $N$ such that $L = \varphi^{-1}(P)$. As is known, the rational languages are precisely the recognizable subsets of $\Sigma^\ast$.

Furthermore, we define an equivalence relation $R_\varphi$ by $u R_\varphi v :\Leftrightarrow \varphi(u)=\varphi(v)$. This relation is a congruence relation, that is $\forall s,t,u,v \in M:s R_\varphi t \Rightarrow usv~R_\varphi~utv$.

We say that a congruence relation $R$ saturates $L$ if for all $u \in L$, $uRv$ implies $v \in L$. Then in the above document, the following proposition (IV.2.2, page 90) is stated:

Let $\varphi : M \rightarrow N$ be a monoid morphism and let $L$ be a subset of $M$. The following conditions are equivalent:

(1) $L$ is recognised by $\varphi$

(2) $L$ is saturated by $R_\varphi$

(3) $\varphi^{-1}(\varphi(L))=L$

Proof. (1) implies (2). If $L$ is recognised by $\varphi$, then $L=\varphi^{-1}(P)$ for some subset $P$ of $N$. Thus if $x \in L$ and $x R_\varphi y$, one has $\varphi(x) \in P$ and since $\varphi(x)=\varphi(y), y \in \varphi^{-1}(P)=L$.

(2) implies (3). If $x \in \varphi^{-1}(\varphi(L))$, there is $y \in L$ such that $\varphi(x) = \varphi(y)$, that is $x R_\varphi y$. Thus, $x \in L$, and $\varphi^{-1}(\varphi(L)) \subseteq L$ follows. "$\supseteq$" is trivial.

(3) implies (1). Let $P:=\varphi(L)$, then $\varphi^{-1}(P)=L$.

I want to weaken the assumptions made in the proposition. Namely, assume tgat the $N$ in the above definitions is a proper groupoid (in fact, I need to deal with loops), that is, associativity and identity are lost. Further, $\varphi$ need not be a morphism (the relation $R_\varphi$, defined in the same way as above, a priori need not be a congruence anymore) and we restate (1) accordingly (as formally, the notion of a "recognable subset" is not defined for groupoids). Then my questions are

(1) Is $R_\varphi$ still a congruence if we demand $\varphi$ to be a morphism of groupoids (loops)?

(2) Does the proposition still hold? Does it if we assume that $R_\varphi$ is not a congruence?

(3) What other sources (preferably monographs) are there that you recommend as comprehensive introductions to algebraic automata theory, esp. concerned with the role of monoids, semigroups (and maybe more general structures as groupoids) and their connection with automata and languages?

Personally, I think they are both true, as for (2), neither the morphism properties, nor associativity nor congruences seem to be used in the proof. And for (1), I don't see where one would need associativity to prove it. But it may well be that I overlooked something (which is why I ask...).

  • 2
    $\begingroup$ Perhaps I am mistaken, but the free groupoid, isn't that the same as the set of binary trees (with leaves on a certain alphabet)? Then your morphism $\varphi$ looks like a bottom-up tree evaluation, and the result seems to be equivalent to a tree automaton? $\endgroup$ Jun 7 '13 at 22:38
  • 1
    $\begingroup$ Do you mean like in Algebraic recognizability of languages by Pascal Weil, Section 3? $\endgroup$ Jun 7 '13 at 22:59
  • $\begingroup$ @HendrikJan: My question is not restricted to the free structures, that is, I want to consider general monoids / groupoids (at least as codomain of $\varphi$). My question arises from the following context: I have a language $L$ (that is known to be regular) and a mapping $\varphi$ from the free monoid generated by $\Sigma$ to a loop $N$, and I know that $R_\varphi$ saturates $L$. So, does this mapping "recognize" $L$? $\endgroup$ Jun 8 '13 at 10:02
  • $\begingroup$ My first comment was on free structures, to see whether the notions matched. The reference by Weil (my second comment) is much broader, and I think it is relevant. But I am not an algebraist by training... Please have a look? $\endgroup$ Jun 8 '13 at 11:52
  • $\begingroup$ The reference you gave is indeed relevant for my third question (skimming over it quickly, I don't see direct answers for (1) or (2)), however only the introduction to section 3 seems directly related, so I will have a look at the references [17] and [60] given there. $\endgroup$ Jun 8 '13 at 14:14

(1) for any function $\varphi:E\to F$, the relation $R_\varphi$ as you define it is always an equivalence relation on elements of $E$. But the notion of congruence depends of the laws you have on your sets, and $R_\varphi$ will be a congruence for the operations that are preserved by $\varphi$. Notice that your formulation with $usv$ is not anymore well-defined without associativity: you have to state it separately for $us$ and $sv$.

(2) Let us weaken even more the hypotheseses. Let $\varphi:E\to F$ be any function, without any structure assumed on $E$ and $F$. Then if we take the definitions you wrote for "recognised" and "saturated", the 3 propositions are still equivalent, as your proofs still work.

The thing you will lose by considering arbitrary sets (or groupoids or loops) is that you won't carry out the nice monoid structure of $\Sigma^*$, so you lose almost all the tools of regular languages theory, like Myhill-Nerode equivalence, Green relations, and so on...

For (3), I think Jean-Eric Pin's webpage (including the document you mention) contains good surveys of this field.

  • $\begingroup$ As far as (1) is concerned: So, if the domain of our function is a monoid and the codomain is a loop, and $\varphi$ is a morphism of loops, the formulation becomes well-defined again and $R_\varphi$ is a congruence according to my definition? $\endgroup$ Jun 9 '13 at 12:01
  • 1
    $\begingroup$ $\varphi$ cannot be a morphism of loop, because there is no inverse in monoids. But if it preserves multiplication, then associativity will be lifted by $\varphi$, and the image of $\varphi$ will indeed be a monoid. $\endgroup$
    – Denis
    Jun 9 '13 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.