Piecewise testable tree languages

Mikołaj Bojańczyk 1 Luc Segoufin 2 Howard Straubing 3
2 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Σ1 sentences. This is a tree extension of the Simon theorem, which says that a string language can be defined by a boolean combination of Σ1 sentences if and only if its syntactic monoid is J-trivial.
Type de document :
Article dans une revue
Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2012, 8 (3), pp.29
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01160458
Contributeur : Luc Segoufin <>
Soumis le : vendredi 5 juin 2015 - 14:38:53
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : mardi 15 septembre 2015 - 11:35:40

Fichier

simon.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01160458, version 1

Collections

Citation

Mikołaj Bojańczyk, Luc Segoufin, Howard Straubing. Piecewise testable tree languages. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2012, 8 (3), pp.29. 〈hal-01160458〉

Partager

Métriques

Consultations de la notice

471

Téléchargements de fichiers

75