Una categoría tiene biproductos cuando los mismos objetos son tanto productos como coproductos. ¿Alguien ha investigado la teoría de la prueba de categorías con biproductos? Quizás el ejemplo más conocido es la categoría de espacios vectoriales, en la que la suma directa y las construcciones de...
El problema de mantenimiento de la orden (o "mantener el orden en una lista") es apoyar las operaciones: singleton: crea una lista con un elemento, le devuelve un puntero insertAfter: dado un puntero a un elemento, inserta un nuevo elemento después de él, devolviendo un puntero al nuevo...
He estado buscando una formalización del teorema de compacidad para FOL, pero no he encontrado ninguna. ¿Alguien está al tanto de tal desarrollo o trabajo
El álgebra booleana se puede expresar en cálculo lambda sin tipo de (por ejemplo) de esta manera. true = \t. \f. t; false = \t. \f. t; not = \x. x false true; and = \x. \y. x y false; or = \x. \y. x true y; También el álgebra booleana se puede codificar en el Sistema F de esta manera : CBool =...
Los solucionadores SAT ofrecen una forma poderosa de verificar la validez de una fórmula booleana con un cuantificador. Por ejemplo, para verificar la validez de , podemos usar un solucionador SAT para determinar si φ ( x ) es satisfactoria. Para verificar la validez de ∀ x . φ ( x ) , podemos...
Recientemente me interesé bastante en la parametricidad después de ver el artículo LICS 2012 de Bernardy y Moulin ( https://dl.acm.org/citation.cfm?id=2359499 ). En este documento, internalizan la parametricidad unaria en un sistema de tipo puro con tipos dependientes y dan pistas sobre cómo puede...
Sabemos que los solucionadores de SAT basados en DPLL no responden correctamente en casos insatisfactorios de (principio del agujero de paloma), por ejemplo, "hay un mapeo inyectivo de n + 1 a n ":P H PPAGHPAG\mathrm{PHP}n + 1norte+1n+1nortenorten P H Pn + 1norte: = ⎛⎝⋀i ∈ [ n + 1 ] ⋁j ∈ [ n...
Si está familiarizado con la verificación del programa, es probable que prefiera leer la Pregunta antes que los Antecedentes . Si no está familiarizado con la verificación del programa, es posible que aún pueda responder esta pregunta, pero es probable que prefiera leer el Fondo...
En respuesta a otra pregunta, Extensiones de la teoría beta del cálculo lambda , Evgenij ofreció la respuesta: beta + la regla {s = t | syt son términos cerrados sin solución} donde un término M es soluble si podemos encontrar una sucesión de términos tales que M aplicación 's para ellos es igual...
Dos documentos que incluiría son: D. Kozen, "Indización de clases subrecursivas" , STOC, 1978. R. Ladner, "Sobre la estructura de la reducibilidad del tiempo polinomial" , JACM,
Las relaciones lógicas para lenguajes impredecibles como el Sistema F parecen depender críticamente de la impredicatividad de la lógica ambiental. Específicamente, la interpretación para el tipo forall se definirá en términos de todas las relaciones escritas. En un sistema impredecible (como CiC /...
¿Alguien me dirige a un artículo que detalla un teorema de eliminación de cortes para la lógica intuicionista proposicional, que incluye un tipo de datos inductivo como los números naturales (las listas o los árboles también estarían bien)? Un ejemplo del tipo de sistema que me interesa es la T de...
Mientras se discuten fuertes pruebas de normalización, este comentario contrasta el "modelo de formas normales" con los "métodos puramente sintácticos". Esto me lleva de vuelta a una pregunta más básica: ¿podemos distinguir estrictamente las construcciones sintácticas y semánticas, frente a los...
Incompleto de Chaitin teorema dice que no lo suficientemente fuerte como la teoría de la aritmética puede llegar K(s)>LK(s)>LK(s) > L , donde K(s)K(s)K(s) es la complejidad de Kolmogorov de cuerda sss y LLL es una constante suficientemente grande. LLL es suficientemente grande si es más...
Lema: Suponiendo equivalencia eta tenemos eso (\x -> ⊥) = ⊥ :: A -> B. Prueba: ⊥ = (\x -> ⊥ x)por equivalencia eta y (\x -> ⊥ x) = (\x -> ⊥)por reducción bajo la lambda. El informe Haskell 2010, sección 6.2 especifica la seqfunción mediante dos ecuaciones: seq :: a -> b ->...
Un lenguaje funcional puede verse como una categoría donde sus objetos son tipos y las funciones de morfismos entre ellos. ¿Cómo encajan las clases de tipos en este modelo? Supongo que solo deberíamos considerar aquellas implementaciones que satisfacen la restricción que tienen la mayoría de las...
Encontré que los sistemas de transición etiquetados son un buen modelo para mi aplicación, es decir, hay un documento sobre modelos de casos de uso con LTS. La pregunta es, ¿qué se puede probar fácilmente sobre los LTS? Me gustaría reutilizar las soluciones existentes para ver si son útiles para mi...
Según tengo entendido, una prueba de que P = NP o P ≠ NP debería ser no relativizable (como en los oráculos de la teoría de la recursión). Sin embargo, prácticamente todas las pruebas parecen ser relativizables. ¿Cuáles son buenos ejemplos de pruebas no relativizables, del tipo que una prueba P =...
En mi búsqueda continua para tratar de aprender el cálculo lambda, "Lambda-Calculus and Combinators an Introduction" de Hindley & Seldin menciona el siguiente artículo (por Bruce Lercher) que demuestra que la única expresión reducible que es la misma (conversión de módulo alfa) en sí misma es:...
Recordemos que la anchura de una resolución refutación de una fórmula CNF es el número máximo de literales en cualquier cláusula que ocurre en . Para cada , hay fórmulas insatisfactorias en 3-CNF st cada refutación de resolución de requiere un ancho de al menos .F R w F F...