P-полные задачи на деревьях

Этот вопрос связан с одним из моих предыдущих вопросов, NP-трудными задачами на деревьях .

Я ищу проблемы, которые являются P-полными на деревьях.

Недавний, представленный на ICALP

Маркус Лорей, Кристиан Матиссен: Изоморфизм правильных деревьев и слов. ICALP (2) 2011: 210-221

Вы найдете статью как на arxiv, так и здесь .

Другой пример - эпиморфизм Мостовского (см. P-полноту и эффективное распараллеливание Сатору Мияно и статью Дальхауса ):

Dahlhaus E, является ли SETL подходящим языком для параллельного программирования - теоретический подход, логика информатики, 1-я мастерская, CSL '87, Karlsruhe / FRG 1987, Lect. Примечания Comput. Sci. 329, 56-63, 1988)

Экземпляр: ориентированный ациклический граф удовлетворяющий аксиоме экстенсиональности, и две вершины x 1 , x 2 ∈ $D = (V, A)$$x_1, x_2 \in V$

Проблема: Решите ли , где М Д является Мостовский эпиморфизмом для D .$M_D(x_1) = M_D(x_2)$$M_D$$D$

Это немного зависит от того, на какие проблемы вы смотрите, но проблема систем путей может быть подходящей.

Дано: конечный набор предложений , набор аксиом A ⊆ P , набор правил вывода R ⊆ P × P × P и некоторая цель$P$$A \subseteq P$$R \subseteq P \times P \times P$ .$p \in P$

Вопрос: Является ли доказуемо от $p$$A$ с использованием ?$R$

Здесь, каждое положение в выводимо из A с использованием R , и, если есть правило ( р 1 , р 2 , р 3 ) в R и р 1 и р 2 доказуемы от А с помощью R , то и р 3 выводим из$A$$A$$R$$(p_1,p_2,p_3)$$R$$p_1$$p_2$$A$$R$$p_3$$A$ с помощью .$R$

Дело в том, что структура такого доказательства - дерево.

Тесно связанной проблемой является проблема пустоты языка для грамматики без контекста. Имеет ли грамматика без контекста хотя бы одно дерево деривации? (Сокращение от систем путей почти мгновенно.) Следовательно, пустота языка контекстно-свободных грамматик является P-полной. По очень схожей причине проблема пустоты для автоматов деревьев также P-полна.

Ссылка на системы маршрутов: Стивен Кук: Наблюдение за компромисс между хранением в пространстве и времени. ССПС, 1974.

Я хотел бы предложить несколько возможных кандидатов на P-полноту:

• Обобщенная игра Pebbling для деревьев (см. «Применение обобщенного Pebbling дерева к разреженной матричной факторизации», автор JWH Liu)
• Проблема Супердерева Соглашения в филогенетике (см. «Алгоритмы с фиксированным параметром для Супердерева Соглашения» Д. Фернандес-Бака и др.).

П-полнота мне не ясна, хотя сокращение от HornSAT кажется возможным, но сложным; может быть, проблема выбора набора целей будет более естественной отправной точкой?

Вот третья проблема, которую я упомянул, она называется Перекрашивание Quad Tree. Нам дают:

• матрица цветов ,$\Gamma = (\gamma_{i,j})$
• $T$$\Gamma$

$T$$T$$\Gamma$ .

Другой возможной функцией стоимости будет подсчет поверхности перекрашенных узлов вместо их количества. Я предполагаю, что эта проблема является P-полной, но даже членство в P не является немедленным.