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...
Considere el siguiente problema: dado un gráfico de consulta y un gráfico de referencia , queremos encontrar el mapeo inyectivo que minimiza el número de bordes tal que . Esta es una generalización del problema del isomorfismo del subgrafo en el que permitimos que los subgrafos sean isomorfos hasta...
Dados los conjuntos y , una relación difuncional entre ellos se define como una relación que satisface la siguiente propiedad:UNUNAsisiB ( ∼ ) ⊆ A × B(∼)⊆UN×si(\sim) \subseteq A \times B Si y y , entonces . a ∼ bun∼sia \sim bun′∼ b′un′∼si′a' \sim b'a ∼ b′un∼si′a \sim b'un′∼ bun′∼sia' \sim...
Larry Wasserman tiene una publicación reciente donde habla sobre la "policía de valor p". Él hace un punto interesante (todo el énfasis es mío) (la premisa en cursiva que agregué y su respuesta debajo): La queja más común es que físicos y periodistas explican incorrectamente el significado de un...
¿Cuál es la complejidad computacional del siguiente problema: dados dos complejos matrices y verifique si hay una matriz de permutación tal que: n × nnorte×norten\times nUNUNAsisiBPAGPAGPB = PA PT.si=PAGUNPAGT.B = P A P^T. Si ayuda, uno puede suponer que y son hermitianos (o incluso que y son...
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 tenemos un gran gráfico (dirigido) y un árbol enraizado más pequeño H , ¿cuál es la complejidad más conocida para encontrar subgrafías de G isomorfas a H ? Soy consciente de los resultados para el isomorfismo de subárbol donde G y H son árboles y también donde G es plano o tiene un ancho de...
Antecedentes Una fórmula de lectura única sobre un conjunto de compuertas (también llamada base) es una fórmula en la que cada variable de entrada aparece una vez. Las fórmulas de lectura única se estudian comúnmente sobre la base De Morgan (que tiene las compuertas de 2 bits AND y OR, y la...
Considere una colección de conjuntos F={F1,F2,…,Fn}F={F1,F2,…,Fn}F=\{F_1,F_2,\dotsc,F_n\} sobre un conjunto base U={e1,e2,…,en}U={e1,e2,…,en}U=\{e_1,e_2,\dotsc,e_n\} donde |Fi||Fi||F_i| ≪≪\ll nnn y ei∈Fiei∈Fie_i \in F_i , y sea kkk un número entero positivo. El objetivo es encontrar otra colección...
Esta es una pregunta de seguimiento a esta sobre gráficos infinitos. Las respuestas y los comentarios a esa pregunta enumeran objetos y situaciones que se modelan naturalmente mediante gráficos infinitos. Pero también hay numerosos teoremas sobre gráficos infinitos (ver capítulo 8 en el libro de...
Estoy aprendiendo métodos formales. Escuché que se usan métodos formales (y generalmente solo se usan) para crear software de misión crítica (como el controlador del reactor nuclear, el controlador de vuelo de la aeronave, el controlador de la sonda espacial). Por eso me interesa aprenderlo: p Sin...
El sistema de prueba probabilística se conoce comúnmente como una restricción de M A , donde Arthur solo puede usar f ( n ) bits aleatorios y solo puede examinar g ( n ) bits de el certificado de prueba enviado por Merlin (ver, http://en.wikipedia.org/wiki/Interactive_proof_system#PCP...
¿Hay un algoritmo de tiempo aleatorio lineal en el lugar? Este es el algoritmo que algunas manos especialmente hábiles son capaces de realizar: dividir uniformemente una matriz de entrada de tamaño par y luego intercalar los elementos de las dos mitades. Mathworld tiene una breve página sobre...
En general, estoy interesado en el método de forzamiento utilizado por Baker-Gill-Solovay y Cohen. Estoy buscando tantas fuentes como pueda tener en cuenta en relación con la técnica en sí o su uso. ¿Alguien tiene
Para sistemas sin tipos dependientes, como el sistema de tipos Hindley-Milner, los tipos corresponden a fórmulas de lógica intuicionista. Allí sabemos que sus modelos son álgebras de Heyting y, en particular, para refutar una fórmula, podemos restringir a un álgebra de Heyting donde cada fórmula...
Editar: como no he recibido ninguna respuesta / comentario en una semana, me gustaría agregar que estoy feliz de escuchar algo sobre el problema. No trabajo en el área, así que aunque sea una simple observación, puede que no lo sepa. ¡Incluso un comentario como "Trabajo en el área, pero no he visto...
Estaba leyendo un capítulo en LYAH que realmente no tenía sentido para mí. Entiendo que las cremalleras pueden atravesar arbitrariamente una estructura similar a un árbol, pero necesito alguna aclaración al respecto. Además, ¿se pueden generalizar las cremalleras a cualquier estructura de...
Si observa los combinadores recursivos en el cálculo lambda sin tipo, como el combinador Y o el combinador omega: Está claro que todos estos combinadores terminan duplicando una variable en algún lugar de su definición.ωY==( λ x .Xx )( λ x .XX)λ f.( λx .F(xx ))( λ x.F(xx )...
Considere un poset finito sobre elementos, y un predicado monotónico desconocido sobre (es decir, para cualquier , , si y luego ) . Puedo evaluar proporcionando un nodo y descubriendo si P (x) se mantiene o no. Mi objetivo es determinar exactamente el conjunto de nodos x \ en X de forma tal que P...
Antecedentes La memoria externa, o modelo DAM, define el costo de un algoritmo por el número de E / S que realiza (esencialmente, el número de errores de caché). Estos tiempos de ejecución generalmente se dan en términos de MMETROM , el tamaño de la memoria y BsiB , el número de palabras que se...