Skip to Main content Skip to Navigation
Conference papers

A context-free linear ordering with an undecidable first-order theory

Abstract : The words of a context-free language, ordered by the lexicographic ordering, form a context-free linear ordering. It is well-known that the linear orderings associated with deterministic context-free languages have a decidable monadic second-order theory. In stark contrast, we give an example of a context-free language whose lexicographic ordering has an undecidable first-order theory.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00733458
Contributor : Arnaud Carayol <>
Submitted on : Tuesday, July 4, 2017 - 5:59:43 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:07 PM
Long-term archiving on: : Friday, December 15, 2017 - 2:39:52 AM

File

978-3-642-33475-7_8_Chapter.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Arnaud Carayol, Zoltan Esik. A context-free linear ordering with an undecidable first-order theory. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. pp.104-118, ⟨10.1007/978-3-642-33475-7_8⟩. ⟨hal-00733458⟩

Share

Metrics

Record views

363

Files downloads

359