Exacta abstracción booleana de sistemas de ecuaciones lineales
Autores: Allart, Emilie; Niehren, Joachim; Versari, Cristian
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Exacta abstracción booleana de sistemas de ecuaciones lineales
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Sistemas
Palabras clave
Calcular
Sistemas de ecuaciones lineales
Abstracción booleana
Exacto
Algoritmo de reescritura
Modos elementales
Redes de flujo
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 21
Citaciones: Sin citaciones
Estudiamos el problema de cómo calcular la abstracción booleana del conjunto de soluciones de un sistema de ecuaciones lineales sobre los números reales positivos. Llamamos a un sistema de ecuaciones lineales exacto para la abstracción booleana si la interpretación abstracta sobre la estructura de booleanos es igual a la abstracción booleana del conjunto de soluciones sobre los números reales positivos. La interpretación abstracta sobre los booleanos es completa para la abstracción booleana cuando se restringe a sistemas de ecuaciones lineales exactos, mientras que no es completa de manera más general. Presentamos un nuevo algoritmo de reescritura que hace que los sistemas de ecuaciones lineales sean exactos para la abstracción booleana al mismo tiempo que preserva las soluciones sobre los números reales positivos. El algoritmo de reescritura se basa en los modos elementales del sistema de ecuaciones lineales. El cálculo de los modos elementales puede requerir tiempo exponencial en el peor de los casos, pero suele ser factible en la práctica con herramientas de libre acceso. Para sistemas de ecuaciones lineales exactos, podemos calcular la abstracción booleana mediante programación de restricciones de dominio finito. Esto proporciona una solución al problema inicial que suele ser factible en la práctica. Nuestro algoritmo de reescritura exacto tiene dos aplicaciones adicionales. En primer lugar, se puede utilizar para calcular la abstracción de signo de sistemas de ecuaciones lineales sobre los reales, como se necesita para analizar programas de funciones con aritmética lineal. En segundo lugar, se puede aplicar para calcular la abstracción de diferencia de un sistema de ecuaciones lineales como se utiliza en algoritmos de predicción de cambios para redes de flujo en biología de sistemas.
Descripción
Estudiamos el problema de cómo calcular la abstracción booleana del conjunto de soluciones de un sistema de ecuaciones lineales sobre los números reales positivos. Llamamos a un sistema de ecuaciones lineales exacto para la abstracción booleana si la interpretación abstracta sobre la estructura de booleanos es igual a la abstracción booleana del conjunto de soluciones sobre los números reales positivos. La interpretación abstracta sobre los booleanos es completa para la abstracción booleana cuando se restringe a sistemas de ecuaciones lineales exactos, mientras que no es completa de manera más general. Presentamos un nuevo algoritmo de reescritura que hace que los sistemas de ecuaciones lineales sean exactos para la abstracción booleana al mismo tiempo que preserva las soluciones sobre los números reales positivos. El algoritmo de reescritura se basa en los modos elementales del sistema de ecuaciones lineales. El cálculo de los modos elementales puede requerir tiempo exponencial en el peor de los casos, pero suele ser factible en la práctica con herramientas de libre acceso. Para sistemas de ecuaciones lineales exactos, podemos calcular la abstracción booleana mediante programación de restricciones de dominio finito. Esto proporciona una solución al problema inicial que suele ser factible en la práctica. Nuestro algoritmo de reescritura exacto tiene dos aplicaciones adicionales. En primer lugar, se puede utilizar para calcular la abstracción de signo de sistemas de ecuaciones lineales sobre los reales, como se necesita para analizar programas de funciones con aritmética lineal. En segundo lugar, se puede aplicar para calcular la abstracción de diferencia de un sistema de ecuaciones lineales como se utiliza en algoritmos de predicción de cambios para redes de flujo en biología de sistemas.