La accesibilidad es un problema fundamental que aparece en varios contextos diferentes: sistemas concurrentes de estado finito e infinito , modelos computacionales como autómatas celulares y redes de Petri , análisis de programas , sistemas discretos y continuos , sistemas de tiempo crítico, sistemas híbridos , sistemas de reescritura , probabilísticos y sistemas paramétricos y sistemas abiertos modelados como juegos . [1]
En general, el problema de la accesibilidad se puede formular de la siguiente manera:
- Dado un sistema computacional (estado potencialmente infinito) con un conjunto de reglas o transformaciones permitidas, decida si un cierto estado de un sistema es accesible desde un estado inicial dado del sistema.
Las variantes del problema de accesibilidad pueden resultar de restricciones adicionales en los estados inicial o final, requisitos específicos para las rutas de accesibilidad, así como para la accesibilidad iterativa o cambiar las preguntas en análisis de estrategias ganadoras en juegos infinitos o la inevitabilidad de algunas dinámicas.
Normalmente, para una descripción de sistema fija dada de alguna forma (reglas de reducción, sistemas de ecuaciones , fórmulas lógicas, etc.), un problema de accesibilidad 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 se puede representar 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 orden en los estados). Las propiedades cuantitativas y cualitativas sofisticadas a menudo se pueden reducir a preguntas básicas de accesibilidad. Los límites de la confiabilidad y complejidad, las soluciones algorítmicas y la heurística eficiente son aspectos importantes que deben considerarse 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 uso general y motores de deducción, a menudo se combinan para equilibrar la eficiencia y la flexibilidad.
Variantes de problemas de accesibilidad
Problemas abiertos
Conferencia internacional sobre problemas de accesibilidad (RP)
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 antecedentes interesados en problemas de accesibilidad que aparecen en estructuras algebraicas, modelos computacionales, sistemas híbridos, juegos infinitos, lógica. y verificación. El taller intenta llenar el vacío entre los resultados obtenidos en diferentes campos pero que comparten una estructura matemática común o dificultades conceptuales.