- Spot - LRE

Unambiguous refinements of collections of BDDs
by Michaël Cadilhac 02 Aug '21

02 Aug '21

Hi there all, Since I started using BDDs in automata, I have faced the following computational problem a few times. If you have any insight on how to solve it more efficiently, I'd be very interested. In particular, is there a spot in spot where this is implemented? Let me spell the problem out in general terms, then tie it to BDDs. *Definitions.* - A collection C of sets over a finite universe U is *unambiguous* if all sets in C are pairwise disjoint. In other words, C is a partition of the union of its sets. - A collection C' refines a collection C if each set in C can be obtained as the union of sets in C'. *Problem.* Given a collection C, compute a (minimal) unambiguous refinement of C. [[For complexity purposes, the computational task can also be written as: Given C and k, does there exist an unambiguous refinement of C of size < k? This is certainly NP-complete ([SP7] in Garey and Johnson is that problem without "unambiguous").]] *Motivation.* In BDDs, my use case is to have C be a collection of BDDs and a BDD represent the set of its satisfying assignments. Building an unambiguous refinement of BDDs seems an essential step in determinization: If I have a state with two outgoing transitions labeled with BDDs {F, G} such that F&G is not False, then this state is nondeterministic. To determinize it, we will have to consider the transition labels {F&G, F&!G, !F&G}. Note that this set refines {F, G}, since F = (F&G)|(F&!G) and similarly for G. *Question.* What is known about that problem? Is there a good heuristic for it that would give an unambiguous refinement not far from the optimal? *Implementations.* I implemented it in a few different ways and would be interested in alternative implementations. Two options I have are: *- The straightforward way:* 1. C' = {U} (recall that U is our universe, with BDDs this would be True) 2. for each S in C: 3. for each S' in C': 4. if (S cap S' is not empty) 5. Remove S' from C' 6. Add (S cap S') and (S^c cap S') to C' (^c denotes complement). *- A slightly more complex implementation.* I encode C' as a BDD itself, introducing lots of fresh variables; namely, if C' = {F, G} for two BDDs F and G, I introduce two fresh variables X_F and X_G, and encode C' as (F & X_F) | (G & X_G). This allows lines 3 and 4 to become: 3. Compute C' & S and project it on the X_? variables. 4. Iterate through each of the variables that appear: if X_S' appears, this means that S cap S' is nonempty. Thanks for reading! Cheers, Michaël

2 1

Time to decide inclusion
by Pierre Ganty 02 Aug '21

02 Aug '21

Dear Spot devs, I want to measure how much time it takes Spot to decide whether the language of the automaton A is contained in that of B. I've been using the following command ``` autfilt '--stats=%r, %R' A.hoa --included-in=B.hoa ``` I think I am not interpreting the results correctly because `--stats` reports very small numbers while adding `time` in front of the command reports much much larger numbers (several orders of magnitude larger). What's the right way to measure the time it takes Spot to decide the inclusion? Thank you. Pierre.

2 1

latexmk required to build spot
by Maxime Bouton 29 May '21

29 May '21

Dear spot maintainers, I am trying to compile spot v2.9.7 from source but my build errors due to latexmk not being available in the environment. From what I understand from the log, it is used in making the doc, is there a way to skip this step in the build? I built it on ubuntu (gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0) and it did not complain about latexmk, this only happened when changing to a new platform (the end goal is to cross compile it). Any help would be appreciated, Maxime I am using a linux platform with gcc: x86_64-linux-gnu-g++ (GCC) 9.1.0 Here is what I run: ./configure --prefix=${prefix}/spot-build --build=${MACHTYPE} --host=${target} --disable-python make -j${nproc} && make install Here is the partial log: ``` [15:46:03] Making all in doc [15:46:03] make[2]: Entering directory '/workspace/srcdir/jlspot/spot-2.9.7/doc' [15:46:03] Making all in tl [15:46:03] make[3]: Entering directory '/workspace/srcdir/jlspot/spot-2.9.7/doc/tl' [15:46:03] BIBINPUTS='./..' latexmk -pdf -ps- -dvi- -pvc- -e '$bibtex_use=2' -e '$pdflatex="pdflatex %O \"\\def\\SpotVersion{2.9.7}\\input{%S}\""' ./tl.tex [15:46:03] /bin/sh: latexmk: not found [15:46:03] make[3]: *** [Makefile:1399: tl.pdf] Error 127 [15:46:03] make[3]: Leaving directory '/workspace/srcdir/jlspot/spot-2.9.7/doc/tl' [15:46:03] make[2]: *** [Makefile:1319: all-recursive] Error 1 [15:46:03] make[2]: Leaving directory '/workspace/srcdir/jlspot/spot-2.9.7/doc' [15:46:03] make[1]: *** [Makefile:1341: all-recursive] Error 1 [15:46:03] make[1]: Leaving directory '/workspace/srcdir/jlspot/spot-2.9.7' ````

2 2

[Not-really-Spot] BDD libraries
by Michaël Cadilhac 27 May '21

27 May '21

Hi there ADL & all, Apologies for the not-really-spot question, but the expertise on this list is quite unique! I'm about to embark on a new project that relies on BDD. My only experience with BDD libraries was through using Spot, so I'm familiar with BuDDy, but that's it. Starting something fresh, I'm pondering what's the best C++ BDD library available nowadays. I axed through BuDDy and refactored it so that it's template-only and encapsulated the global variables in a class (hoping for some performance boost from inlining). While I'm fairly happy with the result, I now realize that there's been some progress in the BDD landscape since 1997—crazy! This paper: https://www.tvandijk.nl/pdf/2015setta.pdf by the author of Sylvan seems to indicate that Sylvan offers good performances on a single core, and great perf on multicore. It also comes with a nice C++ interface. I guess my question is: If you had to go from scratch today, which BDD library would you use? Cheers, M.

2 3

Walking through BDD formula in python
by Ayrat Khalimov 26 May '21

26 May '21

hi! With the aid of SPOT I am developing a counter-example guided synthesizer in python. See [1] if interested for details. My question is: I am trying to parse twa_run in python, namely, parse the labels of the each step (`spot.impl.step`). Is there a python way to walk through BDD? (The label is a simple cube expressed in BDD, and I need to convert it into my internal structure) (yes, this is rather a question about python interface for buddy) (no, that is not feature request:) if not possible, I will simply print the label and parse the string, that is not crucial) [1] The idea is - guess the model, - then model check it and get a counter-example - then encode the counter-example into the "guesser" (which uses an SMT solver) thanks, Ayrat

2 5

fail to install spot
by Jueming Hu 15 Apr '21

15 Apr '21

Good afternoon, I am Jueming, a Ph. D. student at Arizona State University. I would like to use spot for my research, such as getting the graph of an LTL formula. I downloaded 'linux-64/spot-2.9.6-py38_2.tar.bz2' and ran 'conda install -c adl spot' within the extracted folder. 'spot 2.5.2' is shown in conda list and also in python packages. However, 'import spot' doesn't work. The error says, 'No module named 'spot''. I have also tried 'linux-64/spot-2.9.4-py38_2.tar.bz2', 'conda install -c adl/label/adl spot', 'conda install -c adl/label/dev spot', append system path before import spot, and export LD_LIBRARY_PATH. But spot still doesn't work on my pc. Could you please help me install spot? Thanks in advance and looking forward to hearing from you. Best, Jueming

2 1

Question about Transfoming from Non-deterministic Automata to Deterministic Automata
by Meng Ruijie 23 Mar '21

23 Mar '21

Dear Spot Team, Thanks for providing a wonderful tool. During constructing Buchi automata for LTL, Spot always shows non-determinism automata although I select the "deterministic" item. Would you mind telling me how to construct deterministic automata with Spot? Here is one LTL: !(false R (iusr2_ai3_re13 & (! X (true U iusr2_ai3_re14) | X (true U (iusr2_ai3_re14 & (true U ousr2_ai3_ce8)))))). The following is its automata but non-determinism. [cid:83ad2cd0-bc60-443c-b387-4bc7953c05d2] Looking forward to your response. Kind Regards, Ruijie

2 1

Translations to DPA
by Tobias Meggendorfer 18 Mar '21

18 Mar '21

Hi, I'm using / comparing Spot and other tools in the Rabin to Parity translation. I have two questions (to ensure my comparison is fair): 1) I want to minimize the input automata using Spot to remove the effects of preprocessing done by each tool as much as possible. However, I require that the acceptance condition remains a Rabin condition. Right now, I am using the call autfilt --remove-dead-states --cleanup-acceptance --remove-unused-ap --simplify-exclusive-ap --simplify-acc --partial-degeneralize --generalized-rabin --deterministic The last two are an effort to ensure that simplify-acc doesn't change the acceptance condition. 2) What are the ways to tell spot to translate DRA to DPA? Right now, I am using autfilt --hoa --deterministic --parity. This seems to be a sort of black box (which is fine with me). Just to make sure: Are there other DRA-to-DPA translations included in Spot which are worthwhile to be investigated? Cheers, Tobias

2 3

ltlfilt filtering duplicates
by David Müller 18 Mar '21

18 Mar '21

Hi Alexandre, I hope you are not affected too badly by COVID and you and your family can deal with it in a good way. Simon and I stumbled over some slight problems with ltlfilt in combination with the flags -u and --relabel-bool=pnn. We expected to remove the duplicates, and thus being idempotent. However, we came across a set of LTL formulas, where two applications of ltlfilt -u --relabel-bool=pnn delivered a different result from applying it once. I attach the set of LTL formulas (ltlfilt-duplicates/ base.ltl in the archive) and a short script to evaluate the problem (ltlfilt- duplicates/reproduce.sh). I also tried to input a sorted list, it changed the numbers, but not the problem of being not idempotent. Could you tell us, whether we misunderstood something? Best regards, David

2 1

Re: [Spot] set property "original-states" in function "purge_dead_states()
by Alexandre Duret-Lutz 06 Mar '21

06 Mar '21

Tobias John <tobias.john(a)tu-dresden.de> writes: > thanks for your quick response. Your suggestion solves my problem. > > I think a function like "set_default_original_states()" would be > helpful but it is not necessary. In my opinion, it is more important > to mention somewhere in the documentation, e.g. at > > https://spot.lrde.epita.fr/concepts.html#named-properties > > that one needs to set the property somewhen before transforming the > automaton. Yes. The usage is however not very uniform. Some functions, like degeneralize() have to maintain the equivalent of "original-states" in order to work. This function will always define "original-states" if it wasn't present, because that comes for free. However if "original-states" was defined previously, the two mappings will be composed at an extra-cost.

1 0