[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #41 (Solved !)

Originator: Participants at Unif Val d’Ajol
Date: April 1991

Summary: What is the complexity of the first-order theory of trees?

The complexity of the theory of finite trees when there are finitely many symbols is known to be PSPACE-hard [Mah88]. Is it in PSPACE? The same question applies to infinite trees.

Remark

The problem is non-elementary [Vor96].

References

[Mah88]

Michael J. Maher. Complete axiomatizations of the algebras of the finite, rational and infinite trees. In Yuri Gurevich, editor, Third Symposium on Logic in Computer Science, pages 348–357, Edinburgh, Scotland, July 1988. IEEE.

[Vor96]

Sergei Vorobyov. An improved lower bound for the elementary theories of trees. In M. A. McRobbie and J. K. Slaney, editors, 13th International Conference on Automated Deduction, Lecture Notes in Computer Science, pages 275–287, New Brunswick, NJ, July/August 1996. Springer-Verlag.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]