CONTRIBUTIONS A LA THEORIE DES MODELES FINIS ET A LA COMPLEXITE DESCRIPTIVE / YASSINE HACHAICHI ; SOUS LA DIR. DE PATRICK CEGIELSKI

Date : 2001

Editeur / Publisher : [S.l.] : [s.n.] , 2001

Type : Livre / Book

Langue / Language : français / French

Cegielski, Patrick (1954-....) (Directeur de thèse / thesis advisor)

Université Paris Diderot - Paris 7 (1970-2019) (Organisme de soutenance / degree-grantor)

Relation : CONTRIBUTIONS A LA THEORIE DES MODELES FINIS ET A LA COMPLEXITE DESCRIPTIVE / YASSINE HACHAICHI / Villeurbanne : [CCSD] , 2016

Résumé / Abstract : CE TRAVAIL A COMME AMBITION DE CONTRIBUER A LA CARACTERISATION LOGIQUE DE CERTAINES CLASSES DE LANGAGES, C'EST-A-DIRE A LA DISCIPLINE APPELEE COMPLEXITE DESCRIPTIVE. DANS CETTE THESE, ON DONNE UNE CARACTERISATION LOGIQUE DE LA CLASSE DES LANGAGES ALGEBRIQUES NON-AMBIGUS, ET DES CARACTERISATIONS LOGIQUES DES LANGAGES RUDIMENTAIRES. UN DES INTERETS DE CES DERNIERES CARACTERISATIONS EST LE JEU, INTRODUIT DANS LE CHAPITRE 6, QU'ELLES INSPIRENT. ON DONNERA AUSSI UN RESULTAT UTILISANT LA PARTIE EXISTENTIELLE DE CE JEU SUR LA DEFINISSABILITE DE LA CONNEXITE DES GRAPHES FINIS DANS LA CONTINUITE DES TRAVAUX DE FAGIN, DE ROUGEMONT ET SCHWENTICK. DANS LE CHAPITRE 4, ON PROUVE, PAR UNE COMPARAISON DE POUVOIR D'EXPRESSION DES LOGIQUES, QUE LES LANGAGES RECONNUS PAR DES RESEAUX DE PETRI SONT STRICTEMENT INCLUS DANS NTIMEN (LA CLASSE DES LANGAGES RECONNAISSABLES PAR UNE MACHINE DE TURING NON-DETERMINISTE EN TEMPS LINEAIRE). ON UTILISERA LA CARACTERISATION LOGIQUE DES LANGAGES DES RESEAUX DE PETRI DONNEE PAR PARIGOT ET PELZ ET UNE CARACTERISATION DE NTIMEN ENONCEE PAR LAUTEMANN, SCHWENTICK ET SCHWEIKHARDT.