2 citations · 3 across the 9 of their papers we have counts for
9 papers
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(…
Generalised Kauffman Clock Theorems
Nguyen Thanh Tung Le, Daniel V. Mathews
Kauffman's clock theorem provides a distributive lattice structure on the set of states of a four-valent graph in the plane. We prove two distinct generalisations of this theorem,…
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…
Refutations of pebble minimization via output languages
Sandra Kiefer, Lê Thành Dũng Nguyên, Cécilia Pradic
Polyregular functions are the class of string-to-string functions definable by pebble transducers, an extension of finite-state automata with outputs and multiple two-way reading h…
Comparison-free polyregular functions
Lê Thành Dũng Tito Nguyên, Camille Noûs, Cécilia Pradic
This paper introduces a new automata-theoretic class of string-to-string functions with polynomial growth. Several equivalent definitions are provided: a machine model which is a r…
Implicit automata in typed -calculi II: streaming transducers vs categorical semantics
Lê Thành Dũng Nguyên, Camille Noûs, Cécilia Pradic
We characterize regular string transductions as programs in a linear -calculus with additives. One direction of this equivalence is proved by encoding copyless streaming string…
When lattice cubes meet affine subspaces: a short note
Lê Thành Dũng Nguyên
We give short and simple proofs of what seem to be folklore results: * the maximum cardinality of the intersection of a lattice cube with an affine subspace; * the minimum number o…
On the Elementary Affine Lambda-Calculus with and Without Fixed Points
Lê Thành Dũng Nguyen
The elementary affine lambda-calculus was introduced as a polyvalent setting for implicit computational complexity, allowing for characterizations of polynomial time and hyperexpon…
Typed lambda-calculi and superclasses of regular functions
Lê Thành Dũng Nguyên
We propose to use Church encodings in typed lambda-calculi as the basis for an automata-theoretic counterpart of implicit computational complexity, in the same way that monadic sec…