Foundation for a series of efficient simulation algorithms
International audience Compute the coarsest simulation preorder included in an initial preorder is used to reduce the resources needed to analyze a given transition system. This technique is applied on many models like Kripke structures, labeled graphs, labeled transition systems or even word and tr...
Main Author: | |
---|---|
Other Authors: | , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2017
|
Subjects: | |
Online Access: | https://hal.archives-ouvertes.fr/hal-02129747 https://hal.archives-ouvertes.fr/hal-02129747/document https://hal.archives-ouvertes.fr/hal-02129747/file/2ec008c3-57bc-4488-bda8-9d8ac7f3af34-author.pdf |
id |
ftccsdartic:oai:HAL:hal-02129747v1 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-02129747v1 2023-05-15T16:50:36+02:00 Foundation for a series of efficient simulation algorithms Cece, Gérard Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST) Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC) Université Bourgogne Franche-Comté COMUE (UBFC)-Université Bourgogne Franche-Comté COMUE (UBFC)-Centre National de la Recherche Scientifique (CNRS) Reykjavik, Iceland 2017-06-20 https://hal.archives-ouvertes.fr/hal-02129747 https://hal.archives-ouvertes.fr/hal-02129747/document https://hal.archives-ouvertes.fr/hal-02129747/file/2ec008c3-57bc-4488-bda8-9d8ac7f3af34-author.pdf en eng HAL CCSD hal-02129747 https://hal.archives-ouvertes.fr/hal-02129747 https://hal.archives-ouvertes.fr/hal-02129747/document https://hal.archives-ouvertes.fr/hal-02129747/file/2ec008c3-57bc-4488-bda8-9d8ac7f3af34-author.pdf info:eu-repo/semantics/OpenAccess Symposium on Logic in Computer Science https://hal.archives-ouvertes.fr/hal-02129747 Symposium on Logic in Computer Science, Jun 2017, Reykjavik, Iceland [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] [INFO.INFO-ET]Computer Science [cs]/Emerging Technologies [cs.ET] [INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA] [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE] info:eu-repo/semantics/conferenceObject Conference papers 2017 ftccsdartic 2021-11-07T01:57:28Z International audience Compute the coarsest simulation preorder included in an initial preorder is used to reduce the resources needed to analyze a given transition system. This technique is applied on many models like Kripke structures, labeled graphs, labeled transition systems or even word and tree automata. Let (Q,→) be a given transition system and ℛinit be an initial preorder over Q. Until now, algorithms to compute ℛsim, the coarsest simulation included in ℛinit, are either memory efficient or time efficient but not both. In this paper we propose the foundation for a series of efficient simulation algorithms with the introduction of the notion of maximal transitions and the notion of stability of a preorder with respect to a coarser one. As an illustration we solve an open problem by providing the first algorithm with the best published time complexity, O(|Psim|.|→|), and a bit space complexity in O(|Psim|2.log(|Psim|)+|Q|.log(|Q|)), with Psim the partition induced by ℛsim. Conference Object Iceland Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
language |
English |
topic |
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] [INFO.INFO-ET]Computer Science [cs]/Emerging Technologies [cs.ET] [INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA] [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE] |
spellingShingle |
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] [INFO.INFO-ET]Computer Science [cs]/Emerging Technologies [cs.ET] [INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA] [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE] Cece, Gérard Foundation for a series of efficient simulation algorithms |
topic_facet |
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] [INFO.INFO-ET]Computer Science [cs]/Emerging Technologies [cs.ET] [INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA] [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE] |
description |
International audience Compute the coarsest simulation preorder included in an initial preorder is used to reduce the resources needed to analyze a given transition system. This technique is applied on many models like Kripke structures, labeled graphs, labeled transition systems or even word and tree automata. Let (Q,→) be a given transition system and ℛinit be an initial preorder over Q. Until now, algorithms to compute ℛsim, the coarsest simulation included in ℛinit, are either memory efficient or time efficient but not both. In this paper we propose the foundation for a series of efficient simulation algorithms with the introduction of the notion of maximal transitions and the notion of stability of a preorder with respect to a coarser one. As an illustration we solve an open problem by providing the first algorithm with the best published time complexity, O(|Psim|.|→|), and a bit space complexity in O(|Psim|2.log(|Psim|)+|Q|.log(|Q|)), with Psim the partition induced by ℛsim. |
author2 |
Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST) Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC) Université Bourgogne Franche-Comté COMUE (UBFC)-Université Bourgogne Franche-Comté COMUE (UBFC)-Centre National de la Recherche Scientifique (CNRS) |
format |
Conference Object |
author |
Cece, Gérard |
author_facet |
Cece, Gérard |
author_sort |
Cece, Gérard |
title |
Foundation for a series of efficient simulation algorithms |
title_short |
Foundation for a series of efficient simulation algorithms |
title_full |
Foundation for a series of efficient simulation algorithms |
title_fullStr |
Foundation for a series of efficient simulation algorithms |
title_full_unstemmed |
Foundation for a series of efficient simulation algorithms |
title_sort |
foundation for a series of efficient simulation algorithms |
publisher |
HAL CCSD |
publishDate |
2017 |
url |
https://hal.archives-ouvertes.fr/hal-02129747 https://hal.archives-ouvertes.fr/hal-02129747/document https://hal.archives-ouvertes.fr/hal-02129747/file/2ec008c3-57bc-4488-bda8-9d8ac7f3af34-author.pdf |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
Symposium on Logic in Computer Science https://hal.archives-ouvertes.fr/hal-02129747 Symposium on Logic in Computer Science, Jun 2017, Reykjavik, Iceland |
op_relation |
hal-02129747 https://hal.archives-ouvertes.fr/hal-02129747 https://hal.archives-ouvertes.fr/hal-02129747/document https://hal.archives-ouvertes.fr/hal-02129747/file/2ec008c3-57bc-4488-bda8-9d8ac7f3af34-author.pdf |
op_rights |
info:eu-repo/semantics/OpenAccess |
_version_ |
1766040735003443200 |