Problèmes P-complets sur les arbres

Cette question est liée à l'une de mes questions précédentes, les problèmes NP-difficiles sur les arbres .

Je recherche des problèmes P-complets sur les arbres.

Une récente, présentée à l'ICALP, est

Markus Lohrey, Christian Mathissen: Isomorphism of Regular Trees and Words. ICALP (2) 2011: 210-221

Vous trouverez l'article sur arxiv et ici .

Un autre exemple est l'épimorphisme de Mostowski (voir l'exhaustivité de P et la parallélisation efficace par Satoru Miyano et l'article de Dahlhaus ):

Dahlhaus E, est SETL un langage approprié pour la programmation parallèle - une approche théorique, la logique informatique, 1er atelier, CSL '87, Karlsruhe / FRG 1987, Lect. Notes Comput. Sci. 329, 56-63, 1988)

Instance: un graphe acyclique dirigé satisfaisant l'axiome d'extensionnalité et deux sommets x 1 , x 2 ∈ $D = (V, A)$$x_1, x_2 \in V$

Problème: Déterminer si , où M D est la epimorphisme Mostowski pour D .$M_D(x_1) = M_D(x_2)$$M_D$$D$

Cela dépend un peu du type de problèmes que vous regardez, mais le problème des systèmes de chemin peut être un candidat.

Étant donné: un ensemble fini de propositions , un ensemble A ⊆ P d'axiomes, un ensemble R ⊆ P × P × P de règles d'inférence et une cible p ∈ P .$P$$A \subseteq P$$R \subseteq P \times P \times P$$p \in P$

Question: est-il prouvable de A en utilisant R ?$p$$A$$R$

Ici, chaque proposition dans est prouvable à partir de A en utilisant R et, s'il y a une règle ( p 1 , p 2 , p 3 ) dans R et p 1 et p 2 sont prouvables à partir de A en utilisant R , alors p 3 est également prouvable à partir de A l' aide de R .$A$$A$$R$$(p_1,p_2,p_3)$$R$$p_1$$p_2$$A$$R$$p_3$$A$$R$

Le fait est que la structure d'une telle preuve est un arbre.

Un problème étroitement lié est le problème de vide de langage pour une grammaire sans contexte: étant donné une grammaire sans contexte, a-t-elle au moins un arbre de dérivation? (La réduction des systèmes de chemin est presque immédiate.) Par conséquent, la vacuité du langage des grammaires hors contexte est P-complète. Pour une raison très similaire, le problème de vide pour les automates d'arbre est également P-complet.

Une référence sur les systèmes de chemin est: Stephen Cook: An Observation on Time-Space storage trade-off. JCSS, 1974.

Je voudrais suggérer quelques candidats possibles pour P-complétude:

• le jeu de galets généralisés pour les arbres (voir "Une application du galet d'arbres généralisé à la factorisation à matrice clairsemée" par JWH Liu)
• Le problème Accord Supertree en phylogénétique (voir "Algorithmes à paramètres fixes pour Accord Supertrees" par D. Fernandez-Baca et al).

Le P-exhaustivité n'est pas clair pour moi cependant, une réduction de HornSAT semble possible mais délicate; peut-être que le problème de sélection de l'ensemble cible serait un point de départ plus naturel?

Voici le troisième problème que j'ai mentionné, appelé Quad Tree Recoloring. On nous donne:

• une matrice de couleurs ,$\Gamma = (\gamma_{i,j})$
• $T$$\Gamma$

$T$$T$$\Gamma$

Une autre fonction de coût possible serait de compter la surface des nœuds recolorés au lieu de leur nombre. Je suppose que ce problème est P-complet, mais même l'appartenance à P n'est pas immédiate.