Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: deprecated: show and tell

Topic: Syntactic monoid for decidable languages

Sam Tenka (Apr 06 2020 at 22:04):

While I was trying to learn about Turing Decidable languages (considered as functions $\Sigma^* \to 2$), I found out that they are precisely the maps that factor as $\Sigma^* \xrightarrow{\alpha} (\Sigma \sqcup \{\star\})^* \xrightarrow{\tau} P \xleftarrow{\supseteq} 2$, where $\tau$ is a monoid map and $P$ is a finitely presented monoid. Here, $\alpha$ bookends strings with the fresh symbol $\star$ ("alpha" for "affine"!) and we consider $2$ as a subset of $P$.

This framework describes other language classes, too. For example, if we replace finitely presented by finite, then we get the Regular Languages. I wonder what happens for other types of monoids?

Nathanael Arkor (Apr 06 2020 at 22:06):

this sounds very much like the topic of A Categorical Approach to Syntactic Monoids (https://arxiv.org/abs/1804.03011)

Sam Tenka (Apr 06 2020 at 22:07):

Nathanael Arkor said:

this sounds very much like the topic of A Categorical Approach to Syntactic Monoids (https://arxiv.org/abs/1804.03011)

Ooh! I should learn what a syntactic monoid is, then. Sounds useful!

Lê Thành Dũng (Tito) Nguyễn (Apr 07 2020 at 00:33):

Hm, I can't parse the theorem statement here. What does the inverted arrow $P \leftarrow 2$ mean?

Lê Thành Dũng (Tito) Nguyễn (Apr 07 2020 at 00:36):

The characterization of regular languages that I know of is that every regular $\Sigma^* \to 2$ factorizes as $\Sigma^* \to M \to 2$ where $M$ is a finite monoid. But if you replace $M$ by $\Sigma^*$, which is finitely presented (it's the free monoid generated by a finite alphabet), then you can obtain all languages, not just decidable ones. So clearly I'm missing something…

Lê Thành Dũng (Tito) Nguyễn (Apr 07 2020 at 00:38):

@Sam Tenka (naive student) BTW, I replied in the "commutative semigroups" thread with an intuitive statement for Krohn-Rhodes (you seemed to be interested in this topic)

Sam Tenka (Apr 07 2020 at 01:20):

@Nguyễn Lê Thành Dũng , yep, if the arrow had gone into 2, then we wouldn't have gotten just decidable langauges!

I drew the arrow out of 2 because I wanted to say that a certain triangle commutes wihout typing a lot. I should have said more! I meant: the language L:Sigma*->2 is decidable iff participates in a relation

i○L=tau○alpha

where i is some embedding of 2 into P.

Sam Tenka (Apr 07 2020 at 01:20):

Does that make sense?

Lê Thành Dũng (Tito) Nguyễn (Apr 07 2020 at 01:23):

OK, I see what the theorem statement means, thanks! (But I'm still trying to figure out the proof…)

Sam Tenka (Apr 07 2020 at 01:32):

Great! Here's a proof sketch. I never wrote out a proof, so there's a chance I'm wrong:

We will show that if a language is decidable by a Turing Machine, then it is decidable in our algebraic sense; the converse is routine to check.

The idea is to have each element of P represent the state of a Turing tape. The tape symbols (marked with whether or not the tape head is on them) generate P, so we only need to find appropriate relations. The transition dynamics of the TM determines several relations of the form $x\hat{y}z\sim xy'\hat{z}$, where x,y,z are tape symbols, hat denotes that the head is on y's cell, and y′ is the new value written onto that cell before the head moves to z's cell. Two tapes are equivalent (under the equivalence relation generated by these string relations) if and only if they lead to some shared future tape under the Turing dynamics. We have a finitely presented monoid that captures the dynamics, so we are almost there!

Actually, we must deal with initialization and termination, too. We use the symbol 0 concatenated by α to initialize the head location and introduce bookending blank tape cells. We require the TM to clear its tape before halting, hence ensuring that every accepting trajectory has a unique terminal tape (and likewise for rejecting trajectories).

Lê Thành Dũng (Tito) Nguyễn (Apr 07 2020 at 01:34):

Hm, I was actually stumped by the converse which you claim is routine.

Lê Thành Dũng (Tito) Nguyễn (Apr 07 2020 at 01:34):

Can't you encode the word problem for monoids using this?

Lê Thành Dũng (Tito) Nguyễn (Apr 07 2020 at 01:34):

(The word problem is undecidable in general…)

Lê Thành Dũng (Tito) Nguyễn (Apr 07 2020 at 01:35):

Actually it's not that clear, I don't know

Sam Tenka (Apr 07 2020 at 01:36):

Nguyễn Lê Thành Dũng said:

Hm, I was actually stumped by the converse which you claim is routine.

For the converse, we just search over all possible rewrite histories to see whether we get to a canonical form for Yes or for No. The general word problem is undecidable, but here, due to the commuting square, we have the extra condition that the words we get will be rewritable to one of a finite set (of 2 possibilities), so we are good! Intuitively, the word problen is undecidable but in a one sided sense (i.e. is a recognizable lang). So we beat the one sidedness by reformulating our question as two positives (is it Yes? us it No?) instead of a pos and a neg (is it Yes? isn't it Yes?).

Lê Thành Dũng (Tito) Nguyễn (Apr 07 2020 at 01:39):

Oh right (you're saying if a language is recursively enumerable and the complement is also RE then it's decidable, right?)

Sam Tenka (Apr 07 2020 at 01:43):

Nguyễn Lê Thành Dũng said:

Oh right (you're saying if a language is recursively enumerable and the complement is also RE then it's decidable, right?)

Yep! Sorry for my nonstandard way of saying that.

Lê Thành Dũng (Tito) Nguyễn (Apr 07 2020 at 01:45):

OK, I'm pretty much convinced "morally" by our theorem! Just a nitpick: a TM doesn't just have a tape and head position, it also has a control state; but I suppose you can encode that by using letters $y^q$ for $q \in \mathrm{states}$ instead of $\hat{y}$

Sam Tenka (Apr 07 2020 at 01:46):

Good point! Ha, I forgot about that this whole time. Yep, that's a good way to encode it and rescue the result!

Lê Thành Dũng (Tito) Nguyễn (Apr 07 2020 at 01:47):

Wait, there is still a detail: how do you ensure that the terminal tape is reached only by rewriting steps that go "forward in time" instead of zigzags? Do you have some confluence lemma?

Sam Tenka (Apr 07 2020 at 01:48):

Confluence is ensured by TMs being deterministic in forward tine.

Sam Tenka (Apr 07 2020 at 01:49):

So, like, the lemma to show is that "wellformed tapes x and y are equivalent iff they share some common future tape" and that "only wellformed tapes are reachable by the relations from wellformed input"

Lê Thành Dũng (Tito) Nguyễn (Apr 07 2020 at 01:49):

Oh, of course…

zigzag (Apr 07 2020 at 01:50):

Yep; normally this kind of constructions are known for showing that the word problem for monoids is undecidable in general (I think that this is usually attributed to Davis, also for the "directed version" which are called Thue-Morse systems iirc)

Sam Tenka (Apr 07 2020 at 01:58):

Cool! Is there a paper title by Davis i should look into?

Something I'm curious about is what happens when we replace the "finitely presented" condition by other conditions. For instance, how about, abelian ? @Nathanael Arkor pointed me to the concept of syntactic monoids, which for the most part have seemed to be finite, but I bet there's work on the general case if I keep looking.

zigzag (Apr 07 2020 at 02:03):

Thing is, the arrow is in the direction $P \to 2$ afaik in those applications (and no diagram involved to define a "recognizer"), so I do not know if this is the right keyword. I know that there are tons of work on syntactic monoids for subclasses of regular languages (so you consider subclasses of finite monoids as classifiers; the flagship example is the correspondence star-free languages/FO/finite aperiodic monoids which is Schützenberger's theorem https://www.mimuw.edu.pl/~bojan/20142015-2/alg/3-the-schutzenberger-theorem), but I do not know about superclasses/infinite monoids.

Lê Thành Dũng (Tito) Nguyễn (Apr 07 2020 at 02:03):

AFAIK syntactic monoids are meant to fit the $\Sigma^* \to M \to 2$ pattern that I mentioned earlier (the syntactic monoid of a language is the "minimal" M through which it factorizes)

zigzag (Apr 07 2020 at 02:04):

(I also have not looked at the paper mentioned by @Nathanael Arkor , but it was my understanding that it attempt to relate to those situations)

John Baez (Apr 07 2020 at 02:06):

Sam Tenka (naive student) said:

While I was trying to learn about Turing Decidable languages (considered as functions $\Sigma^* \to 2$), I found out that they are precisely the maps that factor as $\Sigma^* \xrightarrow{\alpha} (\Sigma \sqcup \{\star\})^* \xrightarrow{\tau} P \xleftarrow{\supseteq} 2$, where $\tau$ is a monoid map and $P$ is a finitely presented monoid. Here, $\alpha$ bookends strings with the fresh symbol $\star$ ("alpha" for "affine"!) and we consider $2$ as a subset of $P$.

This framework describes other language classes, too. For example, if we replace finitely presented by finite, then we get the Regular Languages.

Is there a good place to read about these theorems?

Sam Tenka (Apr 07 2020 at 02:08):

@John Baez i figured that theorem out myself, but @zigzag pointed me toward Davis's work and related work on "Thue-Morse systems". Probably this is discussed there!

Also, @Nathanael Arkor points us to the concept of "syntactic monoid", which seems very similar though with a different polarity of 2.

zigzag (Apr 07 2020 at 02:09):

Ah, and about Davis' paper, I have chased a citation to a 58 paper "Computability and Unsolvability"

John Baez (Apr 07 2020 at 02:10):

@Sam Tenka (naive student): these results vaguely remind me of Eilenberg's book Automata, Languages, and Machines.

Sam Tenka (Apr 07 2020 at 02:10):

Thanks!

zigzag (Apr 07 2020 at 02:11):

Now, I am afraid I do not have any better than this to offer; it was the case that I reproved that bit of folklore sometime last year towards another result, before realizing that it was the word problem for monoids and chased down a ref; I do not think I have actually read that paper.

John Baez (Apr 07 2020 at 02:11):

Everyone thought Eilenberg was nuts when he switched from algebraic topology to applying category theory to automata, back then... but he was just ahead of his time.

zigzag (Apr 07 2020 at 02:31):

Wrt syntactic monoids, as I was hinting, there are lots of work on correspondence between varieties of finite monoids and subclasses of regular languages in the automata theory community. The easiest thing for me is to point at lecture notes of a course I was attending during my Msc to try to give a flavor of what I am vaguely aware of https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf

John Baez (Apr 07 2020 at 02:42):

Thanks for that reference, @zigzag! So it seems Eilenberg played a role in recognizing this correspondence - it says:

These successes settled the power of the algebraic approach, which was axiomatized by Eilenberg in 1976 [42]. A variety of finite monoids is a class of monoids closed under taking submonoids, quotients and finite direct products. Eilenberg’s theorem states that varieties of finite monoids are in one-to-one correspondence with certain classes of recognisable languages, the varieties of languages.

John Baez (Apr 07 2020 at 19:18):

@zigzag - can you (or someone else here) explain in a simple way how profinite stuff shows up when we try to classify varieties of finite monoids, as explained in that reference you gave? I understand the basic idea of profinite objects, like profinite groups, but I think I need a simple example to understand what's going on here.

zigzag (Apr 07 2020 at 22:22):

I am definitely not an authority on this, but for me the first "use" of the profinite monoids in those notes is Reiterman's theorem (3.13) which states that a variety of semigroup is in one-to-one correspondence with a set of profinite identities. One rationale for liking this I believe is that you may like to have different descriptions of varieties of language (by logic/automata/algebraic property on the relevant class of monoids), and this result tells you that in principle, you can always describe a variety of languages by a bunch of profinite identities. The table under 4.4 p208 describes a bunch of those matches variety/equations.

zigzag (Apr 07 2020 at 22:30):

The actual profinite words showing up in those examples are not very complicated, and that the most basic examples (aperiodic monoids $x^\omega x = x^\omega$, groups $x^\omega = e$, commutative monoids $xy = yx$) are essentially paraphrasing their official definition. What the profinite brings to the table here is the ability to speak about $a^\omega$, which should be thought of as "taking the idempotent value associated to $a$ when evaluating to a finite monoid" (incidentally, this operation of "exponentiating to the idempotent" does a lot of work in the Green theory of finite monoids).

zigzag (Apr 07 2020 at 22:36):

The next chapter has some characterization of lattices of languages in terms of "profinite equations", but this seems to be a different application (here equations are meant to characterize a set of language over a given alphabet rather than a class of finite monoids), so I suppose the two should not be confused.

John Baez (Apr 08 2020 at 00:09):

I'll look at the table. I get the statement of the theorem in the sense of what's supposed to correspond to what... I just don't have an intuition for why it's true: why "profinite identities" specify a language.

John Baez (Apr 08 2020 at 01:03):

Oh, I didn't read all your comments until now. I think I see why $x^\omega = e$ is connected to finite groups; for those listening in this is kind of a way of saying "for all $x$, $x$ to some power is the identity", which is true in any finite group.

John Baez (Apr 08 2020 at 01:31):

And I guess conversely any monoid in which "for all $x$, $x$ to some power is the identity" holds must be a group, since this says every $x$ has an inverse.

zigzag (Apr 08 2020 at 01:33):

Yes; you usually write that inverse as $x^{\omega-1}$ as a profinite word.

zigzag (Apr 08 2020 at 01:41):

For the correspondence varieties/set of identities, I don't have the energy to reread that proof so close to bedtime, but iirc the proof itself is rather simple and actually considers arbitrary sets of identities (i.e. possibly infinite), so I don't know if this is extremely enlightening. In particular, it does not really imply that any given variety will have a nice finite set of identities iiuc. But I think that to a lot of people, profinite words may be mostly valuable to give concrete and short algebraic definitions like those in that table.

zigzag (Apr 08 2020 at 01:48):

(As a clarification for onlookers: one set of profinite identities classify a whole class of finite monoids, and in turn, one finite monoid plus some additional data classify a regular language; so really this theorem speaks about characterizing "well-behaved" subclasses of regular languages)