3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What morphisms are you considering between grammars? and between languages? $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Jun 5, 2013 at 3:13
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jun 5, 2013 at 4:21

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .