En la teoría de la complejidad computacional , un problema no elemental [1] es un problema que no pertenece a la clase ELEMENTARY . Como clase, a veces se denota como NO ELEMENTAL.
Ejemplos de problemas no elementales que, sin embargo, son decidibles incluyen:
- el problema de la equivalencia de expresiones regulares con complementación [2]
- el problema de decisión para la lógica monádica de segundo orden sobre árboles [3]
- el problema de decisión para álgebras de términos [4]
- satisfacibilidad del fragmento acanalado de WVO Quine de lógica de primer orden [5]
- decidir la β-convertibilidad de dos términos cerrados en el cálculo lambda tipificado [6]
Referencias
- ^ Vorobyov, Sergei; Voronkov, Andrei (1998), "Complejidad de programas lógicos no recursivos con valores complejos", Actas del decimoséptimo Simposio ACM SIGACT-SIGMOD-SIGART sobre principios de sistemas de bases de datos (PODS '98) , Nueva York, NY, EE. UU .: ACM, págs. . 244–253, CiteSeerX 10.1.1.39.8822 , doi : 10.1145 / 275487.275515 , ISBN 978-0-89791-996-8.
- ^ Stockmeyer, Larry J. (1974), La complejidad de los problemas de decisión en la teoría y la lógica de los autómatas (PDF) , Ph.D. disertación, Instituto de Tecnología de Massachusetts
- ^ 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), "Un límite inferior mejorado para las teorías elementales de los árboles", Deducción automatizada - CADE-13: 13th International Conference on Automated Deduction New Brunswick, NJ, USA, 30 de julio - 3 de agosto de 1996, Actas , Lecture Notes in Computer Science, 1104 , Springer, págs. 275–287, CiteSeerX 10.1.1.39.1499 , doi : 10.1007 / 3-540-61511-3_91 , ISBN 978-3-540-61511-8.
- ^ Pratt-Hartmann, Ian; Szwast, Wieslaw; Tendera, Lidia (2016), "El fragmento estriado de Quine no es elemental", en Talbot, Jean-Marc; Regnier, Laurent (eds.), 25th EACSL Annual Conference on Computer Science Logic, CSL 2016, 29 de agosto - 1 de septiembre de 2016, Marsella, Francia , LIPIcs, 62 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, págs.39: 1 –39: 21, doi : 10.4230 / LIPIcs.CSL.2016.39
- ^ Statman, Richard (1979), "The typed λ-calculus is not elementary recursive", Theoretical Computer Science , 9 : 73–81, doi : 10.1016 / 0304-3975 (79) 90007-0 , hdl : 2027.42 / 23535.