MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've just beginning to learn logic and proof theory - and the following rather vague and perhaps ill-formed question occurred to me.

Given an alphabet it's straightforward to construct the Language, that is the monoid of all sentences (by concatanation as the operation and using the empty sentence as the unit).

A particular grammar for that alphabet will select a sublanguage.

Is it possible to turn into a Galois connection? So a morphism between Grammars would give one between Languages etc. Of course this would mean we must a robust description as to what is meant by a Grammar.

Has anyone done work in this direction, or is this angle simply not formalisble in any sensible or useful way or is it actually a re-capitulation of Lawveres Galois connection in Model theory between Theories and Models?

share|cite|improve this question
What morphisms are you considering between grammars? and between languages? – Mariano Suárez-Alvarez Jun 5 '13 at 3:13
Rather than answer your question, I recommend you look at Rudolf Wille's work on Concept Lattices, and Denecke's work on M-hyperidentities (using a submonoid of all possible hypersubstitutions rather than the full set). They are examples of applied Galois connections, and are the closest I can imagine to your attempt at defining a Galois connection between languages and grammars. To extend Mariano's question: what subclasses of grammars do you find useful that you want to map to subclasses of languages? Gerhard "Indirect Reference Questions And Answers" Paseman, 2013.06.04 – Gerhard Paseman Jun 5 '13 at 4:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.