Annonce

annonce@lrde.epita.fr

1 participants
565 discussions

New publication: Generic Emptiness Check for Fun and Profit (ATVA'19)

by Alexandre Duret-Lutz

I'm happy to announce the the following article has been accepted in to the 17th International Symposium on Automated Technology for Verification and Analysis (ATVA'19), to be held on October 27-31, 2019 in Taipei, Taiwan. Generic Emptiness Check for Fun and Profit Christel Baier (1), František Blahoudek (2), Alexandre Duret-Lutz (3), Joachim Klein (1), David Müller (1), and Jan Strejček (4) (1) Technische Universität Dresden, Germany (2) University of Mons, Belgium (3) LRDE, EPITA, Le Kremlin-Bicêtre, France (4) Masaryk University, Brno, Czech Republic We present a new algorithm for checking the emptiness of ω-automata with an Emerson-Lei acceptance condition (i.e., a positive Boolean formula over sets of states or transitions that must be visited infinitely or finitely often). The algorithm can also solve the model checking problem of probabilistic positiveness of MDP under a property given as a deterministic Emerson-Lei automaton. Although both these problems are known to be NP-complete and our algorithm is exponential in general, it runs in polynomial time for simpler acceptance conditions like generalized Rabin, Streett, or parity. In fact, the algorithm provides a unifying view on emptiness checks for these simpler automata classes. We have implemented the algorithm in Spot and PRISM and our experiments show improved performance over previous solutions. https://www.lrde.epita.fr/wiki/Publications/baier.19.atva -- Alexandre Duret-Lutz

5 years, 10 months

Spot 2.8 released

by Alexandre Duret-Lutz

We are happy to announce the release of Spot 2.8 Spot is a library of algorithms for manipulating LTL formulas and omega-automata objects (as commonly used in model checking). This release contains code contributed by Clément Gillard and myself. A detailed list of new features is given at the end of this email. You can find the new release here: http://www.lrde.epita.fr/dload/spot/spot-2.8.tar.gz See https://spot.lrde.epita.fr/ for documentation and installation instructions. Note that since Debian 10 ("Buster") was released a few days ago, the "stable" Debian packages we distribute are now built for Buster. As always, please direct any feedback to <spot(a)lrde.epita.fr>. New in spot 2.8 (2019-07-10) Command-line tools: - autfilt learned --highlight-accepting-run=NUM to highlight some accepting run with color NUM. - ltldo, ltlcross, and autcross are now preferring posix_spawn() over fork()+exec() when available. - ltlcross has new options --determinize-max-states=N and --determinize-max-edges=M to restrict the use of determinization-based complementation to cases where it produces automata with at most N states and M edges. By default determinization is now attempted up to 500 states and 5000 edges. This is an improvement over the previous default where determinization-based complementation was not performed at all, unless -D was specified. - ltlcross will now skip unnecessary cross-checks and consistency-checks (they are unnecessary when all automata could be complemented and statistics were not required). - genaut learned --m-nba=N to generate Max Michel's NBA familly. (NBAs with N+1 states whose determinized have at least N! states.) - Due to some new simplification of parity acceptance, the output of "ltl2tgba -P -D" is now using a minimal number of colors. This means that recurrence properties have an acceptance condition among "Inf(0)", "t", or "f", and persistance properties have an acceptance condition among "Fin(0)", "t", or "f". - ltldo and ltlcross learned shorthands to call the tools ltl2na, ltl2nba, and ltl2ngba from Owl 19.06. Similarly, autcross learned a shorthand for Owl's dra2dpa. Documentation: - https://spot.lrde.epita.fr/tut90.html is a new file that explains the purpose of the spot::bdd_dict object. Library: - Add generic_accepting_run() as a variant of generic_emptiness_check() that returns an accepting run in an automaton with any acceptance condition. - twa::accepting_run() and twa::intersecting_run() now work on automata using Fin in their acceptance condition. - simulation-based reductions have learned a trick that sometimes improve transition-based output when the input is state-based. (The automaton output by 'ltl2tgba -B GFa | autfilt --small' now has 1 state instead of 2 in previous versions. Similarly, 'ltldo ltl2dstar -f 'GFa -> GFb' | autfilt --small' produces 1 state instead of 4.) - simulation-based reductions hae learned another trick to better merge states from transiant SCCs. - acc_cond::top_disjuncts() and acc_cond::top_conjuncts() can be used to split an acceptance condition on the top-level & or |. These methods also exist in acc_cond::acc_code. - minimize_obligation() learned to work on very weak automata even if the formula or negated automaton are not supplied. (This allows "autfilt [-D] --small" to minimize very-weak automata whenever they are found to represent obligation properties.) - There is a new spot::scc_and_mark_filter objet that simplifies the creation of filters to restrict spot::scc_info to some particular SCC while cutting new SCCs on given acceptance sets. This is used by spot::generic_emptiness_check() when processing SCCs recursively, and makes it easier to write similar code in Python. - print_dot has a new option 'g', to hide edge labels. This is helpful to display automata as "graphs", e.g., when illustrating algorithms that do not care about labels. - A new complement() function returns complemented automata with unspecified acceptance condition, allowing different algorithms to be used. The output can be alternating only if the input was alternating. - There is a new class output_aborter that is used to specify upper bounds on the size of automata produced by some algorithms. Several functions have been changed to accept an output_aborter. This includes: * tgba_determinize() * tgba_powerset() * minimize_obligation() * minimize_wdba() * remove_alternation() * product() * the new complement() * the postprocessor class, via the "det-max-state" and "det-max-edges" options. - SVA's first_match operator can now be used in SERE formulas and that is supported by the ltl_to_tgba_fm() translation. See doc/tl/tl.pdf for the semantics. *WARNING* Because this adds a new operator, any code that switches over the spot::op type may need a new case for op::first_match. Furthermore, the output of "randltl --psl" will be different from previous releases. - The parser for SERE learned to recognize the ##n and ##[i:j] operators from SVA. So {##2 a ##0 b[+] ##1 c ##2 e} is another way to write {[*2];a:b[+];c;1;e}. The syntax {a ##[i:j] b} is replaced in different ways depending on the values of i, a, and b. The formula::sugar_delay() function implements this SVA operator in terms of the existing PSL operators. ##[+] and ##[*] are sugar for ##[1:$] and ##[0:$]. - The F[n:m] and G[n:m] operators introduced in Spot 2.7 now support the case where m=$. - spot::relabel_apply() makes it easier to reverse the effect of spot::relabel() or spot::relabel_bse() on formula. - The LTL simplifier learned the following rules: F(G(a | Fb)) = FGa | GFb (if option "favor_event_univ") G(F(a | Gb)) = GFa | FGb (if option "favor_event_univ") F(G(a & Fb) = FGa & GFb (unless option "reduce_size_strictly") G(F(a & Gb)) = GFa & FGb (unless option "reduce_size_strictly") GF(f) = GF(dnf(f)) (unless option "reduce_size_strictly") FG(f) = FG(cnf(f)) (unless option "reduce_size_strictly") (f & g) R h = f R h if h implies g (f & g) M h = f M h if h implies g (f | g) W h = f W h if g implies h (f | g) U h = f U h if g implies h Gf | F(g & eventual) = f W (g & eventual) if !f implies g Ff & G(g | universal) = f M (g | universal) if f implies !g f U (g & eventual) = F(g & eventual) if !f implies g f R (g | universal) = G(g | universal) if f implies !g - cleanup_parity() and colorize_parity() were cleaned up a bit, resulting in fewer colors used in some cases. In particular, colorize_parity() learned that coloring transitiant edges does not require the introduction of a new color. - A new reduce_parity() function implements and generalizes the algorithm for minimizing parity acceptance by Carton and Maceiras (Computing the Rabin index of a parity automaton, 1999). This is a better replacement for cleanup_parity() and colorize_parity(). See https://spot.lrde.epita.fr/ipynb/parity.html for examples. - The postprocessor and translator classes are now using reduce_parity() for further simplifications. - The code for checking recurrence/persistence properties can also use the fact the reduce_parity() with return "Inf(0)" (or "t" or "f") for deterministic automata corresponding to recurrence properties, and "Fin(0)" (or "t" or "f") for persistence properties. This can be altered with the SPOT_PR_CHECK environment variable. Deprecation notices: - The virtual function twa::intersecting_run() no longuer takes a second "from_other" Boolean argument. This is a backward incompatibility only for code that overrides this function in a subclass. For backward compatibility with programs that simply call this function with two argument, a non-virtual version of the function has been introduced and marked as deprecated. - The spot::acc_cond::format() methods have been deprecated. These were used to display acceptance marks, but acceptance marks are unrelated to acceptance conditions, so it's better to simply print marks with operator<< without this extra step. Bugs fixed: - The gf_guarantee_to_ba() is relying on an inplace algorithm that could produce a different number of edges for the same input in two different transition order. - A symmetry-based optimization of the LAR algorithm performed in spot::to_parity() turned out to be incorrect. The optimization has been removed. "ltlsynt --algo=lar" is the only code using this function currently. -- Alexandre Duret-Lutz

5 years, 10 months

Séminaire des étudiants chercheurs du LRDE : Mardi 2 juillet 2019 à 13h - Amphi 2

by Daniela Becker

Bonjour, Nous avons le plaisir de vous inviter au Séminaire des étudiants chercheurs du LRDE. Ils présenteront le résultat de leurs travaux le mardi 2 juillet en amphi 2 à partir de 13h. Au programme : - Climb : 13h00 : Antoine Hacquard "Parallélisation et Indexation de Quickref" - Oléna : 13h30 : Thibault Buatois "Segmentation de tumeur cérébrale par réseau de neurones convolutionnel" 14h00 : Célian Gossec "Création d'un lien entre une bibliothèque de traitement d'images en C++ haute performance vers Python" 14h30 Pause - Spot : 14h45 : Samuel Corno "Utilisation du Scatter Search pour trouver un meilleur ordre de variable dans les BDD" 15h15 : Paul Guénézan "Exploration d'espace d'états distribuée" 15h45 : Martin Huvelle "Réimplémentation des automates testeurs dans Spot" 16h15 : Antoine Martin "Comment implémenter le support des goroutines dans go2pins" Pour plus d’informations, voir ici : https://www.lrde.epita.fr/wiki/Student_Seminar_2019-07-02 L'entrée du séminaire est libre. -- Daniela Becker Responsable administrative du LRDE

5 years, 11 months

Soutenance de thèse de Ludovic Le Frioux

by Ludovic Le Frioux

Bonjour à tous, J'ai le plaisir de vous inviter à la soutenance de ma thèse intitulée : "Vers une parallélisation efficace de la résolution du problème de satisfaisabilité" L'exposé se déroulera en français. Vous êtes également cordialement invité au pot qui suivra. Date : le mercredi 3 juillet à 14h Lieu : en salle KB604 à l'EPITA, 14-16 rue Voltaire, Le Kremlin-Bicêtre 94270 Vous trouverez également toutes les informations sur la page web suivante : https://www.lrde.epita.fr/wiki/Affiche-these-LLF Le jury sera composé de : Rapporteurs: * Michaël KRAJECKI, Professeur à l'Université de Reims, CReSTIC * Laurent SIMON, Professeur à l'Université de Bordeaux, LaBRI, CNRS Examinateurs: * Daniel LE BERRE, Professeur à l'Université d'Artois, CRIL, CNRS * Bertrand LE CUN, Ingénieur Senior à Google Inc. * Clémence MAGNIEN, Directeur de Recherche au CNRS, LIP6, CNRS Encadrants: * Souheib BAARIR, Maître de Conférence à l'Université Paris Nanterre, LIP6, CNRS * Fabrice KORDON, Professeur à Sorbonne Université, LIP6, CNRS * Julien SOPENA, Maître de Conférence à Sorbonne Université, LIP6, CNRS, INRIA Mots clés : satisfaisabilité booléenne, parallélisation, portfolio, diviser pour régner, échange de clauses, outil Le résumé de la thèse est le suivant : Les solveurs résolvants le problème de SATisfiabilité booléenne sont utilisés avec succès dans de nombreux contextes : vérification de programmes et de matériels, cryptographie, bio-informatique, preuve automatique de théorème, etc. Ceci est dû à leur capacité à résoudre d'énormes problèmes pouvant contenir des millions de variables et des dizaines de millions de contraintes. Alors que la plupart des solveurs SAT ont longtemps été séquentiels, l'émergence des machines multi-cœurs a ouvert de nouvelles perspectives dans ce domaine. Il existe de nombreux solveurs SAT parallèles différents par leurs stratégies, langages de programmation, bibliothèques utilisées, etc. Il est donc difficile de comparer l'efficacité de différentes stratégies dans un cadre unifié et équitable. De plus, l'introduction de nouvelles approches nécessite une compréhension approfondie de l'implémentation des solveurs déjà existants. Cette thèse présente Painless : une plateforme générique et modulaire permettant l'implémentation de solveurs SAT parallèles efficaces pour les machines multi-cœurs. Elle offre une implémentation des composants de base et sa modularité permet aux utilisateurs de créer facilement leurs solveurs parallèles basés sur de (nouvelles) stratégies. Painless a permis de construire et tester de nombreux solveurs. Nous avons pu imiter le comportement de trois solveurs de l'état de l'art tout en factorisant de nombreuses parties du code. L'efficacité de Painless a été soulignée par le fait que ces implémentations sont au moins aussi efficaces que les originales. De plus, lors de la participation à la compétition annuelle internationale de solveurs SAT parallèles, l'un de nos solveurs s'est classé 3ème en 2017 et un autre 1er en 2018. Nous avons utilisé Painless pour mener des expériences équitables avec des solveurs de type diviser pour régner. Celles-ci nous ont permis de mettre en lumière des compositions originales d'heuristiques plus performantes que celles déjà présentes dans l’état de l’art. Enfin nous avons été en mesure de créer et tester de nouvelles stratégies exploitant la structure modulaire des formules SAT. L'approche que nous avons proposée utilise la topologie de la formule pour guider le solveur vers des zones plus riches en informations, permettant ainsi l’accélération de la résolution parallèle du problème. A bientôt, Ludovic LE FRIOUX

5 years, 11 months

Séminaire des étudiants chercheurs RDI : Lundi 1er juillet 2019 à 13h - Amphi Master

by Daniela Becker

Bonjour, Nous avons le plaisir de vous inviter au Séminaire des étudiants de la majeure double compétence recherche (RDI) composée d'étudiants venant aussi bien du LRDE que du LSE. Il se déroulera le 1er juillet en amphi master à partir de 13h. Les sujets abordés sont : 13h00 : « Modeling and Identifying Troll Farm Accounts on Twitter » - Antoine Sainson (LSE) 13h30 : « Automatic troll farm detection on Twitter » - Hugo Linsenmaier (LSE) 14h00 : « Génération d'états artificiels dans des espaces d'états à l'aide d'estimations de densité paramétriques et non paramétriques. » - Thomas de Carvalho (LRDE) 14h30 : « Estimation de la fonction de niveau de bruit à l'aide de l'arbre des formes dans des images naturelles » - Baptiste Esteban (LRDE) 15h15 : « Génération d'images marines réalistes » - Charles Ginane (LRDE) 15h45 : « Integrating Mathematical Morphology with Deep Convolutional Neural Networks » - Alexandre Kirszenberg (LRDE) 16h15 : « Introduction des opérateurs morphologiques dans les réseaux de neurones convolutionels profonds » - Younes Koudhli (LRDE) 16h45 : « An implementation of Baker’s SUBTYPEP decision procedure » - Léo Valais (LRDE) Pour plus d’informations, voir ici : https://www.lrde.epita.fr/wiki/Student_Seminar_2019-07-01 L'entrée du séminaire est libre. -- Daniela Becker Responsable administrative du LRDE

5 years, 11 months

Programme du Séminaire MeFoSyLoMa du 24 mai 2019 à l'Epita

by Alexandre Duret-Lutz

======================================================================== Séminaire MeFoSyLoMa http://www.mefosyloma.fr/ Méthodes Formelles pour les Systèmes Logiciels et Matériels vendredi 24 mai 2019, 14h-16h30 Adresse: Amphi 3 14-16 rue Voltaire, 94270 Le Kremlin-Bicêtre Métro Porte d'Italie Plans d'accès : https://www.google.com/maps/place/14+Rue+Voltaire,+94270+Le+Kremlin-Bicêtre/ https://www.lrde.epita.fr/~adl/dl/acces-amphi3.png S'il y en a parmi vous qui comptent venir en voiture, le parking du centre commercial Okabé est gratuit pendant 3h. http://www.okabe.com/okabe/fr/okabe-parking ======================================================================== Le séminaire MeFoSyLoMa est animé conjointement par les laboratoires Cedric (Cnam), IBISC (Univ. Evry), LACL (Univ. Paris 12), LIP6 (UPMC), LIPN (Univ. Paris 13), LRDE (Epita), LSV (École Normale Supérieure de Cachan) et LTCI (TELECOM ParisTech). Son objet est de permettre la confrontation de différentes approches ou points de vue sur l'utilisation des méthodes formelles dans les domaines du génie logiciel, de la conception de circuit, des systèmes répartis, des systèmes temps-réel ou encore des systèmes d'information. Il s'organise autour de réunions bimestrielles où sont exposés des travaux de recherche récents sur ce thème. ======================================================================== Programme 14h00-14h45: Benoît Barbot (LACL) Generation of Signals under Temporal Constraints for CPS Testing This work is concerned with validation of cyber-physical systems (CPS) via simulation based on sampling of the input signal space. Such a space is infinite and in general too difficult to treat symbolically meaning that the only reasonable option is to sample a finite subset of it and simulate the corresponding system behaviours. It is thus of great interest to choose a finite sample so that it best "covers" the whole space of input signals. We use timed automata to model temporal constraints, in order to avoid spurious bugs coming from unrealistic inputs and this can also reduce the input space to explore. We propose a method for low discrepancy generation of signals with temporal constraints recognised by timed automata. The discrepancy notion reflects how uniform the input signal space is sampled and additionally allows deriving validation and performance guarantees. We also show how this notion can be used to measure the discrepancy of a given set of input signals. We describe a prototype tool chain and demonstrate the proposed methods on a Kinetic Battery Model (KiBaM) and a Sigma Delta modulator. 14h45-15h30 : Alexandre Duret-Lutz (LRDE) Generic Emptiness Check for Fun and Profit Abstract: We present a new algorithm for checking the emptiness of ω-automata with an Emerson-Lei acceptance condition (i.e., a positive Boolean formula over sets of states or transitions that must be visited infinitely or finitely often). The algorithm can also solve the model checking problem of probabilistic positiveness of MDP under a property given as a deterministic Emerson-Lei automaton. Although these problems are known to be NP-complete and our algorithm is exponential in general, it runs in polynomial time for simpler acceptance conditions like generalized Rabin, Streett, or parity. In fact, the algorithm provides a unifying view on emptiness checks for these simpler automata classes. We have implemented the algorithm in Spot and PRISM and our experiments show improved performance over previous solutions. Joint work with C. Baier, F. Blahoudek, J. Klein, D. Müller, and J. Strejček. 15h30-16h00: pause café 16h00-16h30: vie du groupe ======================================================================== -- Alexandre Duret-Lutz

6 years

New publication at TUG 2019

by Didier Verna

Hello, I'm happy to announce the acceptance of a new publication for TUG 2019 (the TeX users group conference) to be held in Palo Alto, CA, USA, next August. See below for the title and abstract: Quickref: a Stress Test for Texinfo Quickref is a global documentation project for the Common Lisp ecosystem. It creates reference manuals automatically by introspecting libraries and generating a corresponding documentation in Texinfo format. The Texinfo files may subsequently be converted into PDF or HTML. Quickref is non-intrusive: software developers do not have anything to do to get their libraries documented by the system. Quickref may be used to create a local website documenting your current, partial, working environment, but it is also able to document the whole Common Lisp ecosystem at once. The result is a website containing almost two thousand reference manuals. Quickref provides a Docker image for an easy recreation of this website, but a public version is also available and kept up to date on quickref.common-lisp.net. Quickref constitutes an enormous (and successful) stress test for Texinfo, and not only because of the number of files generated and processed. The Texinfo file sizes range from 7K to 15M (make it double for the generated HTML ones). The number of lines of Texinfo code in those files extend from 364 to 285,020, the indexes may contain between 14 and 44500 entries, and the processing times vary from .3s to 1m 38s per file. In this paper, we give an overview of the design and architecture of the system, describe the challenges and difficulties in generating valid Texinfo code automatically, and put some emphasis on the currently remaining problems and deficiencies. -- Resistance is futile. You will be jazzimilated. Lisp, Jazz, Aïkido: http://www.didierverna.info

6 years, 1 month

Quickref 2.0 is released

by Didier Verna

I'm happy to announce the release of Quickref 2.0, codename "Be Quick or Be Dead". Quickref is a global documentation project for Common Lisp libraries, currently offering 1720 reference manuals on the official website: http://quickref.common-lisp.net. Quickref can also be run locally, either from the provided Docker image, or directly from the Lisp REPL. This release is appropriately named after its most important new feature: a support for parallelism which has been presented last week at ELS 2019, the 12th European Lisp Symposium. In addition to that, we also have a new, author based, index to the provided manuals, and a continuous integration infrastructure for keeping track of new Quicklisp (or Quickref) releases more easily. Thanks to Antoine Hacquard, Antoine Martin, and Erik Huelsmann for their contribution to this version! -- Resistance is futile. You will be jazzimilated. Lisp, Jazz, Aïkido: http://www.didierverna.info

6 years, 1 month

[Seminaire-LRDE] Mercredi 10 avril 2019: Guillaume Charpiat (TAU-team, INRIA Saclay / LRI - Université Paris-Sud)

by Edwin Carlinet

Chers collègues, La prochaine session du séminaire Performance et Généricité du LRDE (Laboratoire de Recherche et Développement de l'EPITA) aura lieu le Mercredi 10 avril 2019 (11h -- 12h), Amphi 4. Vous trouverez sur le site du séminaire [1] les prochaines séances, les résumés, captations vidéos et planches des exposés précédents [2], le détail de cette séance [3] ainsi que le plan d'accès [4]. [1] http://seminaire.lrde.epita.fr [2] http://seminaire.lrde.epita.fr/Archives [3] http://seminaire.lrde.epita.fr/2019-04-10 [4] http://www.lrde.epita.fr/wiki/Contact Au programme du Mercredi 10 avril 2019 : * 11h -- 12h: Deep Learning for Satellite Imagery: Semantic Segmentation, Non-Rigid Alignment, and Self-Denoising -- Guillaume Charpiat (TAU-team, INRIA Saclay / LRI - Université Paris-Sud) https://www.lri.fr/~gcharpia/ Neural networks have been producing impressive results in computer vision these last years, in image classification or segmentation in particular. To be transferred to remote sensing, this tool needs adaptation to its specifics: large images, many small objects per image, keeping high-resolution output, unreliable ground truth (usually mis-registered). We will review the work done in our group for remote sensing semantic segmentation, explaining the evolution of our neural net architecture design to face these challenges, and finally training a network to register binary cadaster maps to RGB images while detecting new buildings if any, in a multi-scale approach. We will show in particular that it is possible to train on noisy datasets, and to make predictions at an accuracy much better than the variance of the original noise. To explain this phenomenon, we build theoretical tools to express input similarity from the neural network point of view, and use them to quantify data redundancy and associated expected denoising effects. If time permits, we might also present work on hurricane track forecast from reanalysis data (2-3D coverage of the Earth's surface with temperature/pressure/etc. fields) using deep learning. -- After a PhD thesis at ENS on shape statistics for image segmentation, and a year in Bernhard Schölkopf's team at MPI Tübingen on kernel methods for medical imaging, Guillaume Charpiat joined INRIA Sophia-Antipolis to work on computer vision, and later INRIA Saclay to work on machine learning. Lately, he has been focusing on deep learning, with in particular remote sensing imagery as an application field. L'entrée du séminaire est libre. Merci de bien vouloir diffuser cette information le plus largement possible. N'hésitez pas à nous faire parvenir vos suggestions d'orateurs. -- Edwin Carlinet Laboratoire R&D de l'EPITA (LRDE) _______________________________________________ Seminaire mailing list Seminaire(a)lrde.epita.fr https://lists.lrde.epita.fr/listinfo/seminaire

6 years, 1 month

New journal publication: Model checking with generalized Rabin and Fin-less automata

by Alexandre Duret-Lutz

I'm happy to announce that the following journal article has been published in the International Journal on Software Tools for Technology Transfer Model checking with generalized Rabin and Fin-less automata Vincent Bloemen (1), Alexandre Duret-Lutz (2), Jaco van de Pol (3) (1) University of Twente, Enschede, The Netherlands (2) LRDE, EPITA, Kremlin-Bicêtre, France (3) University of Aarhus, Aarhus, Denmark https://www.lrde.epita.fr/wiki/Publications/bloemen.19.sttt Abstract: In the automata theoretic approach to explicit state LTL model checking, the synchronized product of the model and an automaton that represents the negated formula is checked for emptiness. In practice, a (transition-based generalized) Büchi automaton (TGBA) is used for this procedure. This paper investigates whether using a more general form of acceptance, namely a transition-based generalized Rabin automaton (TGRA), improves the model checking procedure. TGRAs can have significantly fewer states than TGBAshowever the corresponding emptiness checking procedure is more involved. With recent advances in probabilistic model checking and LTL to TGRA translators, it is only natural to ask whether checking a TGRA directly is more advantageous in practice. We designed a multi-core TGRA checking algorithm and performed experiments on a subset of the models and formulas from the 2015 Model Checking Contest and generated LTL formulas for models from the BEEM database. While we found little to no improvement by checking TGRAs directlywe show how various aspects of a TGRA's structure influences the model checking performance. In this paper, we also introduce a Fin-less acceptance condition, which is a disjunction of TGBAs. We show how to convert TGRAs into automata with Fin-less acceptance and show how a TGBA emptiness procedure can be extended to check Fin-less automata. -- Alexandre Duret-Lutz

6 years, 1 month

← Newer
1
...
6
7
8
9
10
11
12
...
57
Older →

Jump to page:

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

Annonce