Skip to Main content Skip to Navigation
Conference papers

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

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01633953
Contributor : Hal Ifip <>
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

File

416473_1_En_7_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

258

Files downloads

149