Grid structures and undecidable constraint theories

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

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1016/S0304-3975(00)00032-3

Titre :

Grid structures and undecidable constraint theories

Auteur(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]

Titre de la revue :

Theoretical Computer Science

Pagination :

453-490

Éditeur :

Elsevier

Date de publication :

2001-05

ISSN :

0304-3975

Mot(s)-clé(s) en anglais :

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

Discipline(s) HAL :

Informatique [cs]

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

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

Source :

Harvested from HAL

Fichiers

https://api.istex.fr/ark:/67375/6H6-47NL8ZTJ-4/fulltext.pdf?sid=hal
Accès libre
Accéder au document

https://api.istex.fr/ark:/67375/6H6-47NL8ZTJ-4/fulltext.pdf?sid=hal
Accès libre
Accéder au document

https://doi.org/10.1016/s0304-3975(00)00032-3
Accès libre
Accéder au document

https://doi.org/10.1016/s0304-3975(00)00032-3
Accès libre
Accéder au document

https://doi.org/10.1016/s0304-3975(00)00032-3
Accès libre
Accéder au document

https://doi.org/10.1016/s0304-3975(00)00032-3
Accès libre
Accéder au document

s0304-3975(00)00032-3
Accès libre
Accéder au document

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

Fichiers

Grid structures and undecidable constraint ...

BibTeX

CSV

Excel

RIS