MSO-definable Properties of Muller Context-Free Languages Are Decidable - Descriptional Complexity of Formal Systems (DCFS 2016)
Conference Papers Year : 2016

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

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

Abstract

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.

Domains

Computer Science [cs]
Fichier principal
Vignette du fichier
416473_1_En_7_Chapter.pdf (149.08 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Hal Ifip  : Connect in order to contact the contributor

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

Submitted on : Monday, November 13, 2017-3:32:45 PM

Last modification on : Monday, November 13, 2017-3:35:34 PM

Long-term archiving on : Wednesday, February 14, 2018-3:44:57 PM

Download

Dates and versions

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

Licence

Attribution

Identifiers

Cite

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⟩

Export

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
147 View
131 Download

Altmetric

Share

More