Grid structures and undecidable constraint theories

Seynhaeve, Franck; Tison, Sophie; Tommasi, Marc; Treinen, Ralf

Document type :

Article dans une revue scientifique: Article original

DOI :

10.1016/S0304-3975(00)00032-3

Title :

Grid structures and undecidable constraint theories

Author(s) :

Seynhaeve, Franck [Auteur]

Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Tison, Sophie [Auteur]

Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Tommasi, Marc [Auteur]

Machine Learning in Information Networks [MAGNET]
Treinen, Ralf [Auteur]
Preuves, Programmes et Systèmes [PPS]

Journal title :

Theoretical Computer Science

Pages :

453-490

Publisher :

Elsevier

Publication date :

2001-05

ISSN :

0304-3975

English keyword(s) :

Term rewriting
Tree automata
Decidable and undecidable theories
Grid structure
Set constraints

HAL domain(s) :

Informatique [cs]

English abstract : [en]

We 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 ...
Show more >We 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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Files

https://api.istex.fr/ark:/67375/6H6-47NL8ZTJ-4/fulltext.pdf?sid=hal
Open access
Access the document

https://api.istex.fr/ark:/67375/6H6-47NL8ZTJ-4/fulltext.pdf?sid=hal
Open access
Access the document

https://doi.org/10.1016/s0304-3975(00)00032-3
Open access
Access the document

https://doi.org/10.1016/s0304-3975(00)00032-3
Open access
Access the document

https://doi.org/10.1016/s0304-3975(00)00032-3
Open access
Access the document

https://doi.org/10.1016/s0304-3975(00)00032-3
Open access
Access the document

s0304-3975(00)00032-3
Open access
Access the document

Grid structures and undecidable constraint ... BibTeX CSV Excel RIS

Files

Grid structures and undecidable constraint ...

BibTeX

CSV

Excel

RIS