Probando automáticamente la contención entre clases de gráficos geométricos definidas por axiomas de inclusión, exclusión y transferencia bajo transformaciones simples
Autores: Böltz, Lucas; Frey, Hannes
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Probando automáticamente la contención entre clases de gráficos geométricos definidas por axiomas de inclusión, exclusión y transferencia bajo transformaciones simples
Categoría
Gestión y administración
Subcategoría
Gestión de la tecnología y la inovación
Palabras clave
Estudio
Gráficos geométricos
Característica estructural
Conjunto de vértices
Universo
Aristas
Predicados
Transformaciones
Expresión lógica
Relaciones de contención
Red inalámbrica
Tipos de clase base
Variantes simetrizadas
Contraejemplos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 1
Citaciones: Sin citaciones
Estudiamos clases de grafos geométricos, que corresponden a la siguiente característica estructural. Para cada instancia de un conjunto de vértices extraído de un universo de posibles vértices, cada par de vértices debe estar conectado, está prohibido que estén conectados, o la existencia o no existencia de una arista es indeterminada. Las condiciones que requieren o prohíben aristas son predicados cuantificados universalmente definidos sobre el par de vértices, y opcionalmente sobre la existencia o no existencia de otra arista que se origina en el par de vértices. Consideramos además un conjunto de transformaciones simples de grafos, donde la existencia de una arista entre dos vértices se determina lógicamente por la existencia o no existencia de aristas dirigidas entre ambos vértices en el grafo original. Derivamos y probamos la corrección de una expresión lógica, que es una condición necesaria y suficiente para las relaciones de contención entre clases de grafos que se describen de esta manera. Aplicamos la expresión en clases de grafos geométricos, que se utilizan como modelos teóricos de grafos de redes inalámbricas. Los modelos se construyen a partir de tres tipos de clases base y combinaciones de intersección de ellas, algunas consideradas directamente y otras consideradas como variantes simetrizadas utilizando dos de las transformaciones simples de grafos. Nuestro estudio luego revisa sistemáticamente todas las posibles clases de grafos resultantes de esas clases base y todas las posibles transformaciones simples de grafos. Derivamos automáticamente relaciones de contención entre esas clases de grafos. Además, en aquellos casos donde no se sostiene la contención, proporcionamos ejemplos en contra derivados automáticamente.
Descripción
Estudiamos clases de grafos geométricos, que corresponden a la siguiente característica estructural. Para cada instancia de un conjunto de vértices extraído de un universo de posibles vértices, cada par de vértices debe estar conectado, está prohibido que estén conectados, o la existencia o no existencia de una arista es indeterminada. Las condiciones que requieren o prohíben aristas son predicados cuantificados universalmente definidos sobre el par de vértices, y opcionalmente sobre la existencia o no existencia de otra arista que se origina en el par de vértices. Consideramos además un conjunto de transformaciones simples de grafos, donde la existencia de una arista entre dos vértices se determina lógicamente por la existencia o no existencia de aristas dirigidas entre ambos vértices en el grafo original. Derivamos y probamos la corrección de una expresión lógica, que es una condición necesaria y suficiente para las relaciones de contención entre clases de grafos que se describen de esta manera. Aplicamos la expresión en clases de grafos geométricos, que se utilizan como modelos teóricos de grafos de redes inalámbricas. Los modelos se construyen a partir de tres tipos de clases base y combinaciones de intersección de ellas, algunas consideradas directamente y otras consideradas como variantes simetrizadas utilizando dos de las transformaciones simples de grafos. Nuestro estudio luego revisa sistemáticamente todas las posibles clases de grafos resultantes de esas clases base y todas las posibles transformaciones simples de grafos. Derivamos automáticamente relaciones de contención entre esas clases de grafos. Además, en aquellos casos donde no se sostiene la contención, proporcionamos ejemplos en contra derivados automáticamente.