From Wikipedia, the free encyclopedia
(Redirected from NONELEMENTARY)
Examples of nonelementary problems that are nevertheless decidable include:
- the problem of regular expression equivalence with complementation
- decision problem for monadic second-order logic over trees
- decision problem for term algebras
- 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: , 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.
|P ≟ NP||This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.|