P-complete problems on trees This question is related to one of my previous questions, NP-hard problems on trees.


  I am looking for problems that are P-complete on trees.
A recent one, presented at ICALP is

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

You will find the paper both on arxiv
and here.

Another example is  Mostowski epimorphism (see P-completeness and efficient parallelization by Satoru Miyano, and the paper by Dahlhaus): 

Dahlhaus E, Is SETL a suitable language for parallel programming - a theoretical approach, Computer science logic, 1st Workshop, CSL ’87, Karlsruhe/FRG 1987, Lect. Notes Comput. Sci. 329, 56-63, 1988)

Instance: a directed acyclic graph $D = (V, A)$ satisfying the axiom of extensionality and two vertices $x_1, x_2 \in V$ 

Problem: Decide whether $M_D(x_1) = M_D(x_2)$, where $M_D$ is the Mostowski epimorphism for $D$.