MSO-definable Properties of Muller Context-Free Languages Are Decidable - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

MSO-definable Properties of Muller Context-Free Languages Are Decidable

Zoltán Ésik
  • Fonction : Auteur
University of Szeged [Szeged]
Szabolcs Iván
  • Fonction : Auteur
  • PersonId : 1022733
University of Szeged [Szeged]

Résumé

We show that it is decidable given an MSO-definable property P of countable words and a Muller context-free grammar G, whether every word in the language generated by G satisfies P.

Domaines

Informatique [cs]
Fichier principal
Vignette du fichier
416473_1_En_7_Chapter.pdf (149.08 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Hal Ifip  : Connectez-vous pour contacter le contributeur

https://inria.hal.science/hal-01633953

Soumis le : lundi 13 novembre 2017-15:32:45

Dernière modification le : lundi 13 novembre 2017-15:35:34

Archivage à long terme le : mercredi 14 février 2018-15:44:57

Télécharger pour visualiser

Dates et versions

hal-01633953 , version 1 (13-11-2017)

Licence

Paternité

Identifiants

Citer

Zoltán Ésik, Szabolcs Iván. MSO-definable Properties of Muller Context-Free Languages Are Decidable. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. pp.87-97, ⟨10.1007/978-3-319-41114-9_7⟩. ⟨hal-01633953⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

IFIP-LNCS IFIP IFIP-TC IFIP-TC1 IFIP-WG IFIP-DCFS IFIP-LNCS-9777 IFIP-WG1-2
129 Consultations
110 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More