Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2018.14
URN: urn:nbn:de:0030-drops-99138
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9913/
Asada, Kazuyuki ; Kobayashi, Naoki
Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered
| pdf-format: |
|
Abstract
Asada and Kobayashi [ICALP 2017] conjectured a higher-order version of Kruskal's tree theorem, and proved a pumping lemma for higher-order languages modulo the conjecture. The conjecture has been proved up to order-2, which implies that Asada and Kobayashi's pumping lemma holds for order-2 tree languages, but remains open for order-3 or higher. In this paper, we prove a variation of the conjecture for order-3. This is sufficient for proving that a variation of the pumping lemma holds for order-3 tree languages (equivalently, for order-4 word languages).
BibTeX - Entry
@InProceedings{asada_et_al:LIPIcs:2018:9913,
author = {Kazuyuki Asada and Naoki Kobayashi},
title = {{Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered}},
booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
pages = {14:1--14:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-093-4},
ISSN = {1868-8969},
year = {2018},
volume = {122},
editor = {Sumit Ganguly and Paritosh Pandya},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9913},
URN = {urn:nbn:de:0030-drops-99138},
doi = {10.4230/LIPIcs.FSTTCS.2018.14},
annote = {Keywords: higher-order grammar, pumping lemma, Kruskal's tree theorem, well-quasi-ordering, simply-typed lambda calculus}
}
| Keywords: | higher-order grammar, pumping lemma, Kruskal's tree theorem, well-quasi-ordering, simply-typed lambda calculus | |
| Seminar: | 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 05.12.2018 |
