A word reconstruction problem for polynomial regular languages

The reconstruction problem concerns the ability to uniquely determine an unknown word from querying information on the number of occurrences of chosen subwords. In this work, we focus on the reconstruction problem when the unknown word belongs to a known polynomial regular language, i.e., its growth function is bounded by a polynomial. Exploiting the combinatorial and structural properties of these languages, we are able to translate queries into polynomial equations and transfer the problem of unique reconstruction to finding those sets of queries such that their polynomial equations have a unique integer solution. Alongside combinatorial properties of the equations and polynomials we completely characterize which queries are necessary to uniquely reconstruct the word in the case of two loops. Further, we integrate techniques from real algebraic geometry and Tarski--Seidenberg Theorem on quantifier elimination to show that we can decide for a constant number of queries whether they suffice for a unique reconstruction.