[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |
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.
The problem is non-elementary [Vor96].
[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |