Hispanopedia Wiki
La alcanzabilidad es un problema fundamental que aparece en varios contextos diferentes: sistemas concurrentes de estados finitos e infinitos , modelos computacionales como autómatas celulares y redes de Petri , análisis de programas , sistemas discretos y continuos , sistemas críticos en el tiempo, sistemas híbridos , sistemas de reescritura , sistemas probabilísticos y paramétricos , y sistemas abiertos modelados como juegos . [1]
En general, el problema de alcanzabilidad se puede formular de la siguiente manera: dado un sistema computacional (estado potencialmente infinito) con un conjunto de reglas o transformaciones permitidas, decidir si un cierto estado de un sistema es alcanzable desde un estado inicial dado del sistema.
Pueden surgir variantes del problema de alcanzabilidad a partir de restricciones adicionales en los estados iniciales o finales, requisitos específicos para caminos de alcanzabilidad así como para alcanzabilidad iterativa o cambiar las preguntas hacia el análisis de estrategias ganadoras en juegos infinitos o la inevitabilidad de algunas dinámicas.
Por lo general, para una descripción de sistema fija dada en alguna forma (reglas de reducción, sistemas de ecuaciones , fórmulas lógicas, etc.) un problema de alcanzabilidad consiste en verificar si un conjunto dado de estados objetivo puede alcanzarse a partir de un conjunto fijo de estados iniciales. El conjunto de estados objetivo puede representarse explícitamente o mediante alguna representación implícita (por ejemplo, un sistema de ecuaciones, un conjunto de elementos mínimos con respecto a algún ordenamiento en los estados). Las propiedades cuantitativas y cualitativas sofisticadas a menudo pueden reducirse a preguntas básicas de alcanzabilidad. Los límites de decidibilidad y complejidad, las soluciones algorítmicas y las heurísticas eficientes son aspectos importantes a considerar en este contexto. Las soluciones algorítmicas a menudo se basan en diferentes combinaciones de estrategias de exploración, manipulaciones simbólicas de conjuntos de estados, propiedades de descomposición o reducción a problemas de programación lineal , y a menudo se benefician de aproximaciones, abstracciones, aceleraciones y heurísticas de extrapolación. Las soluciones ad hoc, así como las soluciones basadas en solucionadores de restricciones de propósito general y motores de deducción, a menudo se combinan para equilibrar la eficiencia y la flexibilidad.
Variantes de los problemas de accesibilidad
Gráfico explícito finito
El problema de accesibilidad en un grafo orientado descrito explícitamente es NL-completo. Reingold, en un artículo de 2008, demostró que el problema de accesibilidad para un grafo no orientado está en LOGSPACE. [2]
En la verificación de modelos , la accesibilidad corresponde a una propiedad de vivacidad.
Gráfico implícito finito
En la planificación , más precisamente en la planificación clásica, nos interesa saber si se puede llegar a un estado a partir de un estado inicial a partir de una descripción de acciones. La descripción de acciones define un grafo de estados implícitos, que es de tamaño exponencial en relación con el tamaño de la descripción.
En la verificación de modelos simbólicos, el modelo (el gráfico subyacente) se describe con la ayuda de una representación simbólica como los diagramas de decisión binarios .
Redes de Petri
El problema de alcanzabilidad en una red de Petri es decidible. [3] Desde 1976, se sabe que este problema es EXPSPACE-hard. [4] Hay resultados sobre cuánto implementar este problema en la práctica. [5] En 2018, se demostró que el problema era un problema no elemental . [6] En 2022 se demostró que era completo para la complejidad temporal de la función de Ackermann . [7] [8]
Sistemas de adición de vectores
En 2022 se demostró que la alcanzabilidad en sistemas de adición vectorial es Ackermann -completa y, por lo tanto, un problema no elemental . [9] [8]
Problemas abiertos
Conferencia internacional sobre problemas de accesibilidad (PR)
La serie International Conference on Reachability Problems, anteriormente conocida como Workshop on Reachability Problems , es una conferencia académica anual que reúne a investigadores de diversas disciplinas y orígenes interesados en los problemas de alcanzabilidad que aparecen en estructuras algebraicas, modelos computacionales, sistemas híbridos, juegos infinitos, lógica y verificación. El taller intenta llenar el vacío existente entre los resultados obtenidos en diferentes campos pero que comparten una estructura matemática común o dificultades conceptuales.
Referencias
- ^ Giorgio Delzanno, Igor Potapov (Eds.): Problemas de accesibilidad - 5.º taller internacional, RP 2011, Génova, Italia, 28-30 de septiembre de 2011. Actas. Lecture Notes in Computer Science 6945, Springer 2011, ISBN 978-3-642-24287-8
- ^ Reingold, Omer (3 de mayo de 2008). "Conectividad no dirigida en el espacio logarítmico". omereingold.files.wordpress.com . Archivado desde el original el 15 de junio de 2007 . Consultado el 9 de diciembre de 2021 .
- ^ Mayr, Ernst W. (11 de mayo de 1981). "Un algoritmo para el problema general de accesibilidad de la red de Petri". Actas del decimotercer simposio anual de la ACM sobre teoría de la computación - STOC '81 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 238–246. doi :10.1145/800076.802477. ISBN 978-1-4503-7392-0.S2CID15409115 .
- ^ Lipton, R. (1976). El problema de la accesibilidad requiere espacio exponencial . Informe técnico n.º 62. Departamento de Ciencias de la Computación, Universidad de Yale.
- ^ Küngas, Peep (2005). "La comprobación de la accesibilidad de las redes de Petri es polinómica con jerarquías de abstracción óptimas". En Zucker, Jean-Daniel; Saitta, Lorenza (eds.). Abstracción, reformulación y aproximación . Apuntes de clase en informática. Vol. 3607. Berlín, Heidelberg: Springer. págs. 149–164. doi :10.1007/11527862_11. ISBN. 978-3-540-31882-8.
- ^ Czerwinski, Wojciech; Lasota, Slawomir; Lazic, Ranko; Leroux, Jerónimo; Mazowiecki, Filip (11 de abril de 2019). "El problema de accesibilidad de las redes de Petri no es elemental". arXiv : 1809.07115 [cs.FL].
- ^ Leroux, Jerome (febrero de 2022). "El problema de accesibilidad de las redes de Petri no es recursivo primitivo". 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. págs. 1241–1252. arXiv : 2104.12695 . doi :10.1109/FOCS52979.2021.00121. ISBN 978-1-6654-2055-6.
- ^ de Brubaker, Ben (4 de diciembre de 2023). "Un problema que parece fácil produce números demasiado grandes para nuestro universo". Revista Quanta .
- ^ Czerwiński, Wojciech; Orlikowski, Łukasz (2021). La accesibilidad en sistemas de adición vectorial es completa en términos de Ackermann . 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). arXiv : 2104.13866 .
