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: theory: category theory

Topic: Chomsky hierarchy and Categories

Alexander Gietelink Oldenziel (Sep 09 2023 at 18:10):

Is there a way to thinkg about regular grammars, context-free grammars and context-sensitive grammars in terms of categories?

A regular grammar is representered by a finite (weighted) automata which is ~= a group representation of the free monoid on a finite alphabet I think?
So it might make sense taht context-sensitive grammars might be related to representations of categories maybe?
Thankful for any pointers

Bryce Clarke (Sep 09 2023 at 18:47):

This may not answer your question exactly, but this paper may contain some related ideas which interest you:
Parsing as a lifting problem and the Chomsky-Schützenberger representation theorem - Paul-André Melliès, Noam Zeilberger

John Baez (Sep 09 2023 at 18:51):

Eilenberg's work on category theory, grammars and automata, and subsequent followups, seem relevant. David Lewis wrote:

In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised a Volume C dealing with "a hierarchy (called the rational hierarchy) of the nonrational phenomena... using rational relations as a tool for comparison. Rational sets are at the bottom of this hierarchy. Moving upward one encounters 'algebraic phenomena,'" which lead to "to the context-free grammars and context-free languages of Chomsky, and to several related topics."

But Eilenberg never published volume C. He did leave preliminary handwritten notes for the first few chapters (http://www-igm.univ-mlv.fr/~berstel/EilenbergVolumeC.html) complete with scratchouts, question marks, side notes and gaps.

Finally, the question -- does anyone know of work along the same lines to possibly reconstruct what Eilenberg had in mind? If not, what material is likely closest to his ideas?

J.-E. Pin replied:

It would be hazardous to guess what Eilenberg had in mind, but a reasonable answer to your question

What material is likely closest to his ideas?

might be the theory of cones (also called full trios). An excellent reference on the part of this theory related to context-free languages is Berstel's book Transductions and Context-Free Languages, Teuber 1979.

An alternative answer (still for context-free languages) can be found in the little known but very inspiring article by J. Berstel and L. Boasson, Towards an algebraic theory of context-free languages, 1996, Fundamenta Informaticae, 25(3):217-239, 1996.

To quote your introduction, the first reference is using "rational relations as a tool for comparison" and the second one really "encounters algebraic phenomena which lead to the context-free grammars and context-free languages".

John Baez (Sep 09 2023 at 18:54):

Michaël Cadilhac provided another reference:

I recommend Behle, Krebs, and Reifferscheid's recent work on extending Eilenberg's fundamental theorem (that is, the correspondence between pseudovarieties of monoids and varieties of languages) to non-regular languages (link). They point out previous works in this line (in particular, Sakarovitch's on CFL).

John Baez (Sep 09 2023 at 18:55):

I would like to study this stuff sometime.

Spencer Breiner (Sep 10 2023 at 00:47):

Also possibly relevant is this paper on generalizations of regular grammars by @Matt Earnshaw and @Pawel Sobocinski:
https://arxiv.org/abs/2207.00526

dusko (Sep 11 2023 at 03:52):

Alexander Gietelink Oldenziel said:

Is there a way to thinkg about regular grammars, context-free grammars and context-sensitive grammars in terms of categories?

there is more than one way to present the chomsky hierarchy in any cartesian category. i think the simplest way is in terms of state machines. (if we want to start from grammars, each of the 4 families of grammars is equivalent to a natural family of state machines along its version of the myhill-nerode-type of theorem.)

a state machine is of course a coalgebra in the form $X\times A\to X\times B$. (ok, the official coalgebra $X\to (X\times B)^A$ requires the closed structure. but when a slightl relaxed definition hugely expands the scope of applications, then most people relax the definition. both coalgebra books think of coalgebras as stateful functions, not state destructors.) the correspondence is then:

3) regular languages are recognized by finite-state automata (machines with $B=2$)
2) context-free languages are recognized by pushdown automata
1) context-sensitive languages are recognized by linearly bounded TMs and
0) recursively enumerable languages are recognized (and generated) by general TMs.

the TMs in a cartesian categories were written down in many papers. my mmory goes to my monoidal computer III, and in my "testing equivalences" with mike mislove from 2006 (my son was born!). getting from state machines to the corresponding language is also described in that paper. both are on dusko.org and on arxiv. [PS the published version of the testing paper cut off the appendix wit the TMs, but the version on dusko.org has it.] a TM in a cartesian category is just a state machine with the tape modeled as an external state space. the linearly bounded TMs are the TMs where the tape lenght is linearly bounded. (this goes back to kuroda in the early 60s, before space complexity was defined.)

IMPORTANT
i think that segregating category theory from the rest of math by asking "does the basic concept X have a categorical version" works against both sides. the tacit assumption that a state machine someone wrote down must be a set and that it is worth a bunch of papers to spell out a "categorical version" hides the fact that, more often than not, the original structural definition was a diagram in some category, and that defining what it does with the elements of some sets required additional work, leading away from the original structure. everything has a categorical version!! if the "categorical version" is not obvious, it is because people added some convenient theology (like when zermelo replaced cantor's wellorderings, which arise by counting, by the axiom of choice, which arises from nothing...)

dusko (Sep 11 2023 at 04:00):

note that the cartesian structure suffices for the machien definitions, but that running them causes computational effects, which take us outside the cartesian structure. most computational effects induce commutative monads, and then the types become free algebras in the cartesian category form a monoidal category with data services (a commutative comonoid) ie a choice of a basis of copiable and deletable data over each type.

dusko (Sep 11 2023 at 04:01):

(what i call "monoidal categories with data services" was called GS-monoidal categories in fabio gaducci's thesis from i think 96, and people seem to continue to use this name. i forgot that and started calling the comonoids that copy and delete data the data services in the lectures in the late 90s. i don't like to rename things and woudn't if i remembered. but still, calling things by acronyms is probably better avoided (WHO-monoids, USSR-naturality, KZ-monads?) the nice part is that (fabio tells me) the GS-Monoidal categories got their name in reference to the GSM protocol for mobile phones, that was emerging at the time. old people like history, so i will totally try switch to that :)))

dusko (Sep 11 2023 at 04:23):

Alexander Gietelink Oldenziel said:

A regular grammar is representered by a finite (weighted) automata which is ~= a group representation of the free monoid on a finite alphabet I think?
So it might make sense taht context-sensitive grammars might be related to representations of categories maybe?

can you explain this a little more?
on one hand, the view of an automaton monoid action doesn't seem to be particularly informative. if we form the free algebra over states by applying any strong monad whatsoever, the automaton induces the action of the alphabet on that free algebra.
on the other hand, category representations usually go into presheaves, and lots of people have used presheaves to analyze computational behaviors. so your intuition could be leading to something useful...

Patrick Nicodemus (Sep 11 2023 at 04:24):

dusko said:

IMPORTANT
i think that segregating category theory from the rest of math by asking "does the basic concept X have a categorical version" works against both sides. the tacit assumption that a state machine someone wrote down must be a set and that it is worth a bunch of papers to spell out a "categorical version" hides the fact that, more often than not, the original structural definition was a diagram in some category, and that defining what it does with the elements of some sets required additional work, leading away from the original structure. everything has a categorical version!! if the "categorical version" is not obvious, it is because people added some convenient theology (like when zermelo replaced cantor's wellorderings, which arise by counting, by the axiom of choice, which arises from nothing...)

Category theory is to a large extent a tool for abstraction, and often "the categorical version of something" is in particular a category-theoretic abstraction of it. It's much more common in science (and pedagogy) to go from the concrete to the abstract than to go from the abstract to the concrete. So criticizing mathematicians for studying and understanding set-theoretic models and then translating this into categorical language sounds like "Oh you should have done it the abstract way from the beginning." In my experience this is usually not how people learn or think or reason.

Patrick Nicodemus (Sep 11 2023 at 04:36):

The stuff about "theology" and "leading away from the original structure" is too strong of a claim. I worry that this kind of polemic has the side effect of being dismissive of the work done by these mathematicians.

I remember that in the Pacific Journal of Mathematics controversy, Paul Halmos said about the model theorists' work (paraphrasing) "Well this is all very well and good but you have deliberately obscured things by insisting for unexplainable reasons on phrasing it in your own idiosyncratic language, which adds no value at all but only distracts from the real mathematical content" and this was his excuse for translating their proof from a model-theoretic proof into a more purely analytical proof and publishing it independently at the same time. The obvious problem there is that it's much easier to come up with a second proof once the first proof is known.

Accusing set theoretic reasoning of leading us astray from the real mathematical structure contradicts mathematical history. Taking point-set topology for example as a central branch of set-theoretical mathematics, without Brouwer's work on point-set topology, there is no modern differential geometry, there is no solution to Hilbert's fifth problem, no proof of the invariance of domain.

dusko (Sep 11 2023 at 04:37):

Patrick Nicodemus said:

Category theory is to a large extent a tool for abstraction, and often "the categorical version of something" is in particular a category-theoretic abstraction of it. It's much more common in science (and pedagogy) to go from the concrete to the abstract than to go from the abstract to the concrete.

the idea that thinking goes from concrete to abstract is common, but not espoused either in cognitive science or in theory of science. e.g., the cognitive apparatus in children definitely goes from abstract to concrete: from "hungry", or "happy" to "spoon" and "toy".

in fact, the two directions are thought to present the difference between the human and the animal lexicons. dogs generalize from leash to walk, and from bowl to eating. people apparently go the other way around. people as different as chomsky and wittgenstein agree about this.

dusko (Sep 11 2023 at 04:38):

(sorry, dinner time :)

David Michael Roberts (Sep 11 2023 at 05:52):

I guess the PJM controversy is the one described in this paper https://arxiv.org/abs/1607.00149 ?

Patrick Nicodemus (Sep 11 2023 at 06:05):

Yes, that is the controversy I am referring to. My paraphrase was in turn of the paraphrase given by the authors of this paper in section 3.2

dusko (Sep 11 2023 at 06:38):

Patrick Nicodemus said:

Accusing set theoretic reasoning of leading us astray from the real mathematical structure contradicts mathematical history. Taking point-set topology for example as a central branch of set-theoretical mathematics, without Brouwer's work on point-set topology, there is no modern differential geometry, there is no solution to Hilbert's fifth problem, no proof of the invariance of domain.

your general point that i shouldn't accuse people is well taken. i didn't mean to.

but history is not a story of progress, and going astray from history is sometimes useful.

you mention point set topology. euclid begins the story about space by defining points, which occupy no space. we could observe points as line intersections --- if we could observe lines, which have no breadth or depth. they also occupy no space. so we observe lines as intersections of planes... so our studies of space the first couple of thousand years were based on points. so much for your impression that abstract concepts come about by generalizing concrete concepts. a potato is concrete, but it was easier to develop the theory of space in terms of things that occupy no space, and to even keep drawing these things in sand, on perchment, and on blackboards, imagining that they are infinitely small and invisible. point set topology helped us understand surfaces that we can see in terms of simpler things that we cannot. then came grothendieck and spaces where points are not distinguishable by any observable neighborhoods were in the way. so he realized that we actually don't really need the points. they are a "vanishing point" of what we can observe: the perfect ideals of neighborhoods. but it was easier to reason with the vanishing points than with the neighborhoods that we observe in the concrete world. so we now went astray from history, and know that the point set topology can be replaced by the point-free topology... but most people still like their points.

i read cantor's correspondence with dedekind (edited by emmy noether). that makes me talk about theology that the community tends to impose its members. theology of points. theology of choice. cantor didn't think of sets as sets of points. he thought of sets up to bijections. specified by various forms of recursion. so sets ended up well-ordered. dedekind convinced him that the order types should be abandoned, and used recursion in his Zahlbericht, where goedel got it from. then zermelo edited cantor's collected work, said that the well-ordering assumption was unfounded, and published a couple of papers how to found it on the axiom of choice. discovering that sets should really be considered up to bijection, like cantor did, waited for eilenberg and maclane, who needed natural equivalences...

i was really astonished that history could be so wasteful. but then i remembered it's driven by wars. wastefulness is the whole point of it. we just need to remember to always go astray.

dusko (Sep 11 2023 at 06:44):

this is surely more than anyone wanted to hear about this but in case anyone wants to see how cantor's constructions, criticized by dedekind and zermelo, give us a useful family of program-closed categories, check ch 8 of my book (type "programs as diagrams" in amazon). i also gave a talk about it in the CUNY seminar (type "program-closed" in youtube).

James Deikun (Sep 11 2023 at 08:49):

I think you both have good points about respecting the original mathematical work, dusko that usually the original work has an abstract and categorical core before it gets situated in set theory, Patrick that often a lot of the important mathematical work around this core concept happens after the thing has been situated firmly in the category of sets and freely uses the assumptions thereof so it takes real intellectual work to untangle it from this context.

GhaS Shee (Oct 02 2023 at 10:03):

@Alexander Gietelink Oldenziel

I have just been introduced to Automata Theory by the recent EMS's handbook. (It's a great book!)
In my thought, it is very natural that we regard nodes in automata as objects in category and transitions as morphisms.
In this setting, a brief thinking make us clear that a category can be made into an automata but not the vice versa (an automata is not a category since there is automata which does not contain identities).

Category theory is kind of linear algebra. (imagine e.g. morphisms in category of chain complexes)
And, Automata theory too. For each automata (word automata), there is a matrix ( over semiring ).
The transition matrix is very simple. If there is a transition from Node i to Node j labelled by Alphabet 'a', the matrix is just defined by

$M_{ij} = a$ .

This is very natural if we know graph representation matrices.

In the setting, if we take a preorder of generalization;
$Categories < Automata$

In the same sense, there is a tree automata version, i.e.
$Multi categories < Tree \ Automata$

Given a category, we always do not know where to start computation. Whereas, automata give the way of the computation and using infinity more precisely or formally. Given an equivalence between sSet and Top
in categories, where to start the computation ?

In the sense of computation, automata seems more precise and general.
And, it's just a beginner's thought.

fosco (Oct 02 2023 at 10:13):

it's always a pleasure for the eye to read dusko's answers