3 papers
cs.LO2026
A finer reparameterisation theorem for MSO and FO queries on strings
Lê Thà nh Dũng Nguyên, PaweŠParys
We show a theorem on monadic second-order k-ary queries on finite words. It may be illustrated by the following example: if the number of results of a query on binary strings is O(…
cs.FL2024
Two or three things I know about tree transducers
Lê Thà nh Dũng Nguyên
You might know that the name "tree transducers" refers to various kinds of automata that compute functions on ranked trees, i.e. terms over a first-order signature. But have you ev…
cs.LO2024
Simply typed convertibility is TOWER-complete even for safe lambda-terms
Lê Thà nh Dũng Nguyên
We consider the following decision problem: given two simply typed -terms, are they -convertible? Equivalently, do they have the same normal form? It is famously non-elemen…