Nonelementary problem
In computational complexity theory, a nonelementary problem[1] is a problem that is not a member of the class ELEMENTARY.
Examples of nonelementary problems that are nevertheless decidable include:
- the problem of regular expression equivalence with complementation[2]
- decision problem for monadic second-order logic over trees[3]
- decision problem for term algebras[4]
References
- ↑ Vorobyov, Sergei; Voronkov, Andrie (1998), "Complexity of Nonrecursive Logic Programs with Complex Values", Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '98), New York, NY, USA: ACM, pp. 244–253, doi:10.1145/275487.275515, ISBN 0-89791-996-3.
- ↑ Stockmeyer, Larry J. (1974), The Complexity of Decision Problems in Automata Theory and Logic (PDF), Ph.D. dissertation, Massachusetts Institute of Technology
- ↑ Libkin, Leonid (2006), "Logics for unranked trees: an overview", Logical Methods in Computer Science 2 (3): 3:2, 31, arXiv:cs.LO/0606062, doi:10.2168/LMCS-2(3:2)2006, MR 2295773.
- ↑ Vorobyov, Sergei (1996), "An improved lower bound for the elementary theories of trees", Automated Deduction — Cade-13: 13th International Conference on Automated Deduction New Brunswick, NJ, USA, July 30 – August 3, 1996, Proceedings, Lecture Notes in Computer Science 1104, Springer, pp. 275–287, doi:10.1007/3-540-61511-3_91.
This article is issued from Wikipedia - version of the 10/12/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.