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.
Type de document :
Communication dans un congrès
Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.104-118, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_8〉
https://hal-upec-upem.archives-ouvertes.fr/hal-00733458
Contributeur : Arnaud Carayol
<>
Soumis le : mardi 4 juillet 2017 - 17:59:43
Dernière modification le : mercredi 11 avril 2018 - 12:12:03
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 02:39:52
Arnaud Carayol, Zoltan Esik. A context-free linear ordering with an undecidable first-order theory. Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.104-118, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_8〉. 〈hal-00733458〉
