Problemas P-completos em árvores

Esta pergunta está relacionada a uma das minhas perguntas anteriores, problemas difíceis de NP em árvores .

Estou procurando problemas que sejam P completos nas árvores.

Um recente, apresentado na ICALP, é

Markus Lohrey, Christian Mathissen: Isomorfismo de árvores e palavras regulares. ICALP (2) 2011: 210-221

Você encontrará o artigo no arxiv e aqui .

Outro exemplo é o epimorfismo de Mostowski (veja P-completude e paralelização eficiente de Satoru Miyano e o artigo de Dahlhaus ):

Dahlhaus E, é SETL uma linguagem adequada para programação paralela - uma abordagem teórica, lógica da ciência da computação, 1º Workshop, CSL '87, Karlsruhe / FRG 1987, Lect. Notas Comput. Sci. 329, 56-63, 1988)

Instância: um gráfico acíclico direcionado satisfaz o axioma da extensionalidade e dois vértices x 1 , x 2 ∈ $D = (V, A)$$x_1, x_2 \in V$

Problema: Decidir se , em que M D é o epimorfismo Mostowski para D .$M_D(x_1) = M_D(x_2)$$M_D$$D$

Depende um pouco do tipo de problema que você está procurando, mas o problema dos sistemas de caminho pode ser um candidato.

Dado: um conjunto finito de proposições , um conjunto Um ⊆ P de axiomas, um conjunto R ⊆ P × P × P de regras de inferência e alguns alvo p ∈ P .$P$$A \subseteq P$$R \subseteq P \times P \times P$$p \in P$

Pergunta: dedutível de A usando R ?$p$$A$$R$

Aqui, cada proposição em é dedutível de A usando R e, se há uma regra ( p 1 , p 2 , p 3 ) em R e p 1 e p 2 é dedutível de A usando R , então também p 3 é dedutível de Um usando R .$A$$A$$R$$(p_1,p_2,p_3)$$R$$p_1$$p_2$$A$$R$$p_3$$A$$R$

O ponto é que a estrutura dessa prova é uma árvore.

Um problema intimamente relacionado é o problema de vazio de linguagem para uma gramática livre de contexto: dada uma gramática livre de contexto, ela possui pelo menos uma árvore de derivação? (A redução dos sistemas de caminho é quase imediata.) Portanto, o vazio da linguagem das gramáticas sem contexto é P-completo. Devido a uma razão muito semelhante, o problema de vazio para autômatos em árvore também é P-complete.

Uma referência em sistemas de caminho é: Stephen Cook: Uma Observação sobre o trade-off de armazenamento Time-Space. JCSS, 1974.

Gostaria de sugerir alguns possíveis candidatos para o preenchimento P:

• o jogo de seixos generalizados para árvores (consulte "Uma aplicação de seixos de árvores generalizadas na fatoração de matriz esparsa" por JWH Liu)
• O problema de acordo com Supertree em filogenética (consulte "Algoritmos de parâmetros fixos para contratos com árvores" por D. Fernandez-Baca et al).

A completude P não está clara para mim, porém, uma redução do HornSAT parece possível, mas complicada; talvez o problema de seleção do conjunto de alvos seja um ponto de partida mais natural?

Aqui está o terceiro problema que eu mencionei, chamado Quad Tree Recoloring. Nos é dado:

• uma matriz de cores ,$\Gamma = (\gamma_{i,j})$
• um quad-tree cujas folhas são rotuladas por elementos de Γ ,$T$$\Gamma$

e o objetivo é recolorir o número mínimo de nós de modo que dois nós adjacentes de T não sejam rotulados por cores adjacentes em Γ .$T$$T$$\Gamma$

Outra função de custo possível seria contar a superfície dos nós recoloridos em vez do número. Suponho que esse problema seja P-completo, mas mesmo a participação em P não é imediata.