Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Jean-Eric Pin

LFCS Seminar: Jean-Eric Pin

— filed under:

Equational descriptions of logic fragments

What
  • LFCS Seminar
When Nov 18, 2011
from 03:00 PM to 04:00 PM
Where Appleton Tower, AT2.12
Contact Name
Add event to calendar vCal
iCal

Title (Friday's LFCS seminar, AT 2.12, 3pm):

Equational descriptions of logic fragments

 

Abstract:

A famous theorem states that a regular language is first-order definable

if and only if its syntactic monoid satisfies an identity of the form $x^n =

x^{n+1}$. This theorem was the first of a series of results aiming at

characterising logic fragments by equations. I will survey old and new results

on this topic, including Eilenberg's varieties theorem and its extensions, Reiterman's result on profinite equations, and more recent results related

to duality theory.

 

 

Title (Monday's MAXIMALS seminar, ICMS, 3pm):

 

The abstract notion of recognition: algebra, logic and topology

(Joint work with M. Gehrke and S. Grigorieff)

 

Abstract:

We propose a new approach to the notion of recognition, which departs from the classical definitions by three specific features. First, it does not rely on automata. Secondly, it applies to any Boolean algebra (BA) of subsets rather than to individual subsets. Thirdly, topology is the key ingredient. We prove the existence of a minimum recognizer in a very general setting which applies in particular to any BA of subsets of a discrete space. Our main results show that this minimum recognizer is a uniform space whose completion is the dual of the original BA in Stone-Priestley duality; in the case of a BA of languages closed under quotients, this completion, called the syntactic space of the BA, is a compact monoid if and only if all the languages of the BA are regular. For regular languages, one recovers the notions of a syntactic monoid and of a free profinite monoid. For nonregular languages, the syntactic space is no longer a monoid but is still a compact space. Further, we give an equational characterization of BA of languages closed under quotients, which extends the known results on regular languages to nonregular languages. Finally, we generalize all these results from BAs to lattices, in which case the appropriate structures are partially ordered.

 

Document Actions