A continuación, MSO denota la lógica monádica de segundo orden de los gráficos con cuantificaciones de conjuntos de vértices y conjuntos de bordes. Sea una familia cerrada menor de gráficos. Se deduce de Robertson y de Seymour gráfico teoría menor que F se caracteriza por una lista finita H 1 , H...
Recientemente, Dana Scott propuso el cálculo lambda estocástico, un intento de introducir elementos probabilísticos en el cálculo lambda (sin tipo) basado en una semántica llamada modelo gráfico. Puede encontrar sus diapositivas en línea, por ejemplo, aquí y su artículo en Journal of Applied Logic...
¿Hay alguna encuesta de algoritmos para calcular interpolantes? ¿Qué pasa con los documentos en un solo algoritmo? El caso que más me interesa es y , más la restricción de que el interpolante es lo más pequeño posible. (Conozco el artículo de McMillan de 2005 , que describe cómo obtener...
Creo que no lo entiendo, pero la conversión me parece una conversión que no hace nada, un caso especial de conversión donde el resultado es solo el término en la abstracción lambda porque no hay nada hacer, una especie de conversión sentido.β β βηη\etaββ\betaββ\betaββ\beta Entonces, tal vez...
Este artículo sugiere que hay combinadores (que representan cálculos simbólicos) que no pueden ser representados por el cálculo Lambda (si entiendo las cosas
En un hilo reciente en la lista de correo de Agda, surgió la cuestión de las leyes , en la que Peter Hancock hizo un comentario estimulante .ηη\eta Tengo entendido que las leyes ηη\eta vienen con tipos negativos, es decir. conectivos cuyas reglas de introducción son invertibles. Para deshabilitar...
El problema de la satisfacción es, por supuesto, un problema fundamental en la CS teórica. Estaba jugando con una versión del problema con infinitas variables. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Configuración básica. Sea un conjunto de variables no vacío y...
¿Alguien puede explicar brevemente (si es posible!) O referirme a una referencia, resumiendo las diferencias entre el cálculo lambda sin tipo y los cálculos lambda con tipo más comunes? Estoy buscando particularmente declaraciones de su poder expresivo, equivalencias a sistemas lógicos /...
En los sistemas de prueba para la lógica proposicional clásica, si se quiere mostrar que una determinada fórmula no es derivable, simplemente se muestra que se puede derivar (aunque ciertamente son posibles otras técnicas). La no derivabilidad se deriva esencialmente de la solidez y la integridad...
¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...
¿La prueba automática de teoremas y la búsqueda de pruebas son más fáciles en lógicas subestructurales lineales y otras proposicionales que carecen de contracción? ¿Dónde puedo leer más sobre la demostración automática de teoremas en estas lógicas y el papel de la contracción en la búsqueda de...
Sé que es imposible decidir la equivalencia para el cálculo lambda sin tipo. Citando a Barendregt, HP El cálculo Lambda: su sintaxis y semántica. Holanda Septentrional, Amsterdam (1984). :ββ\beta Si A y B son disjuntos, conjuntos no vacíos de términos lambda que están cerrados en igualdad,...
¿Hay alguna manera de probar el siguiente teorema en Coq? Theorem bool_pirrel : forall (b : bool) (p1 p2 : b = true), p1 = p2. EDITAR : un intento de dar una breve explicación de "qué prueba es irrelevante" (corríjame a alguien si estoy equivocado o es inexacto) La idea básica es que en el mundo...
En la teoría de los autómatas (autómatas finitos, autómatas pushdown, ...) y en la complejidad, existe una noción de "ambigüedad". Un autómata es ambiguo si hay una palabra www con al menos dos ejecuciones de aceptación distintas. Una máquina es kkk ambigua si por cada palabra www aceptada por la...
A partir de Curry-Howard-Lambek, ha habido una buena trinidad de teorías de tipos, lógicas y categorías. Tengo curiosidad por saber qué semántica categórica obtienes al agregar subtipos (coercitivos) a una teoría de tipos; parece que esto no se ha explorado mucho, si es que lo ha hecho. En...
Estoy buscando un ejemplo sencillo de dos sistemas de transición que sean equivalentes a LTL, pero que no sean equivalentes de rastreo. He leído la prueba de que Trace Equivalence es más fina que LTL Equivalence en el libro "Principles of Model Checking" (Baier / Katoen) pero no estoy seguro de...
En el pasado, implementé modelos de coordinación utilizando SAT y satisfacción de restricciones regulares como el caballo de batalla principal en sus motores. Continuando en esta línea de trabajo, me gustaría hacer que los modelos sean más interactivos, y la mejor manera que veo de hacerlo es abrir...
Contexto: relaciones entre lógica y autómatas El teorema de Büchi establece que la lógica de segundo orden monádico sobre cadenas (MSO) captura la clase de lenguajes regulares. La prueba muestra que en realidad existencial MSO ( o EMSO ) sobre cadenas es suficiente para capturar los lenguajes...
Estoy buscando ejemplos naturales de algoritmos eficientes (es decir, en tiempo polinómico) st su corrección y eficiencia pueden demostrarse de manera constructiva (p. ej., en o ), peroPAGR APAGRUNPRAHUNHUNHA no se conoce ninguna prueba que utilice solo conceptos eficientes (es decir, no sabemos...
Soy un estudiante graduado en matemáticas con una sólida formación en lógica. He tomado un curso de posgrado en lógica junto con cursos de posgrado sobre teoría de modelos finitos y otro sobre forzado y teoría de conjuntos. La mayoría de los textos de CS parecen asumir solo un trasfondo muy modesto...