The syntactic concept lattice: Another algebraic theory of the context-free languages?

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)
291 Downloads (Pure)

Abstract

The syntactic concept lattice is a residuated lattice associated with a given formal language; it arises naturally as a generalization of the syntactic monoid in the analysis of the distributional structure of the language. In this article we define the syntactic concept lattice and present its basic properties, and its relationship to the universal automaton and the syntactic congruence; we consider several different equivalent definitions, as Galois connections, as maximal factorizations and finally using universal algebra to define it as an object that has a certain universal (terminal) property in the category of complete idempotent semirings that recognize a given language, applying techniques from automata theory to the theory of context-free grammars (CFGs). We conclude that grammars that are minimal, in a certain weak sense, will always have non-terminals that correspond to elements of this lattice, and claim that the syntactic concept lattice provides a natural system of categories for representing the denotations of CFGs.
Original languageEnglish
Article numberN/A
Pages (from-to)N/A
Number of pages27
JournalJournal of Logic and Computation
VolumeN/A
Issue numberN/A
Early online date30 Jul 2013
DOIs
Publication statusPublished - 2013

Fingerprint

Dive into the research topics of 'The syntactic concept lattice: Another algebraic theory of the context-free languages?'. Together they form a unique fingerprint.

Cite this