1 citations · 1 across the 5 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…