Grid structures and undecidable constraint theories

International audienceWe prove three new undecidability results for computational mechanisms over 3nite trees:There is a linear, ultra-shallow, noetherian and strongly con6uent rewrite systemRsuch thatthe∃∗∀∗-fragment of the 3rst-order theory of one-step-rewriting byRis undecidable; the empti-ness problem for tree automata with equality tests between cousins is undecidable; and the∃∗∀∗-fragment of the 3rst-order theory of set constraints with the union operator is undecidable.The common feature of these three computational mechanisms is that they allow us to describethe set of 3rst-order terms that represent grids. We extend our representation of grids by terms toa representation of linear two-dimensional patterns by linear terms, which allows us to transferclassical techniques on the grid to terms and thus to obtain our undecidability results.c©2001Elsevier Science B.V. All rights reserved