# FreeBSD Manual Pages

AUTFILT(1) User Commands AUTFILT(1)NAMEautfilt - filter, convert, and transform omega-automataSYNOPSISautfilt[OPTION...] [FILENAME[/COL]...]DESCRIPTIONConvert, transform, and filter omega-automata.Input:-F,--file=FILENAMEprocess the automaton in FILENAME--trust-hoa=BOOLIf false, properties listed in HOA files are ignored, unless they can be easily verified. If true (the default) any sup- ported property is trusted.Outputautomatontype:-B,--baBA1/4chi Automaton (with state-based acceptance)--cobuchi,--coBuchiautomaton with co-BA1/4chi acceptance (will recognize a superset of the input language if not co-BA1/4chi realizable)-C,--completeoutput a complete automaton-G,--genericany acceptance is allowed (default)-M,--monitorMonitor (accepts all finite prefixes of the given property)-p,--colored-parity[=any|min|max|odd|even|minodd|min even|max odd|max even] colored automaton with parity acceptance-P,--parity[=any|min|max|odd|even|minodd|min even|max odd|max even] automaton with parity acceptance-S,--state-based-acceptance,--sbaccdefine the acceptance using states--tgbaTransition-based Generalized BA1/4chi AutomatonOutputformat:-8,--utf8enable UTF-8 characters in output (ignored with--lbttor--spin)-c,--countprint only a count of matched automata--check[=PROP] test for the additional property PROP and output the result in the HOA format (implies-H). PROP may be some prefix of 'all' (default), 'unambiguous', 'stutter-invariant', 'stutter-sensi- tive-example', 'semi-determinism', or 'strength'.-d,--dot[=1|a|A|b|B|c|C(COLOR)|e|E|f(FONT)|h|k|K|n|N|o|r|R|s|t|u|v|y|+INT|_INT|#] GraphViz's format. Add letters for (1) force numbered states, (a) show acceptance condition (default), (A) hide acceptance condition, (b) acceptance sets as bullets, (B) bullets except for BA1/4chi/co-BA1/4chi automata, (c) force circular nodes, (C) color nodes with COLOR, (d) show origins when known, (e) force elliptic nodes, (E) force rEctangular nodes, (f(FONT)) use FONT, (g) hide edge labels, (h) horizontal layout, (k) use state la- bels when possible, (K) use transition labels (default), (n) show name, (N) hide name, (o) ordered transitions, (r) rainbow colors for acceptance sets, (R) color acceptance sets by Inf/Fin, (s) with SCCs, (t) force transition-based acceptance, (u) hide true states, (v) vertical layout, (y) split universal edges by color, (+INT) add INT to all set numbers, (<INT) dis- play at most INT states, (#) show internal edge numbers-H,--hoaf[=1.1|i|k|l|m|s|t|v] Output the automaton in HOA format (default). Add letters to select (1.1) version 1.1 of the format, (i) use implicit labels for complete deterministic automata, (s) prefer state-based ac- ceptance when possible [default], (t) force transition-based ac- ceptance, (m) mix state and transition-based acceptance, (k) use state labels when possible, (l) single-line output, (v) verbose properties--lbtt[=t] LBTT's format (add =t to force transition-based acceptance even on BA1/4chi automata)-n,--max-count=NUMoutput at most NUM automata--name=FORMATset the name of the output automaton-o,--output=FORMATsend output to a file named FORMAT instead of standard output. The first automaton sent to a file truncates it unless FORMAT starts with '>>'.-q,--quietsuppress all normal output-s,--spin[=6|c] Spin neverclaim (implies--ba). Add letters to select (6) Spin's 6.2.4 style, (c) comments on states--stats=FORMAT,--format=FORMAToutput statistics about the automaton Any FORMAT string may use the following interpreted sequences (capitals for input, minuscules for output): %% a single % %< the part of the line before the automaton if it comes from a column extracted from a CSV file %> the part of the line after the automaton if it comes from a col- umn extracted from a CSV file %A, %a number of acceptance sets %C, %c, %[LETTERS]C, %[LETTERS]c number of SCCs; you may filter the SCCs to count using the fol- lowing LETTERS, possibly concatenated: (a) accepting, (r) re- jecting, (c) complete, (v) trivial, (t) terminal, (w) weak, (iw) inherently weak. Use uppercase letters to negate them. %D, %d 1 if the automaton is deterministic, 0 otherwise %E, %e number of reachable edges %F name of the input file %G, %g, %[LETTERS]G, %[LETTERS]g acceptance condition (in HOA syntax); add brackets to print an acceptance name instead and LETTERS to tweak the format: (0) no parameters, (a) accentuated, (b) abbreviated, (d) style used in dot output, (g) no generalized parameter, (l) recognize Street-like and Rabin-like, (m) no main parameter, (p) no parity parameter, (o) name unknown acceptance as 'other', (s) shorthand for 'lo0'. %H, %h the automaton in HOA format on a single line (use %[opt]H or %[opt]h to specify additional options as in--hoa=opt)%L location in the input file %M, %m name of the automaton %N, %n number of nondeterministic states %P, %p 1 if the automaton is complete, 0 otherwise %r wall-clock time elapsed in seconds (excluding parsing) %R, %[LETTERS]R CPU time (excluding parsing), in seconds; Add LETTERS to re- strict to(u) user time, (s) system time, (p) parent process, or (c) children processes. %S, %s number of reachable states %T, %t number of reachable transitions %U, %u, %[LETTER]U, %[LETTER]u 1 if the automaton contains some universal branching (or a number of [s]tates or [e]dges with universal branching) %W, %w one word accepted by the automaton %X, %x, %[LETTERS]X, %[LETTERS]x number of atomic propositions declared in the automaton; add LETTERS to list atomic propositions with (n) no quoting, (s) oc- casional double-quotes with C-style escape, (d) double-quotes with C-style escape, (c) double-quotes with CSV-style escape, (p) between parentheses, any extra non-alphanumeric character will be used to separate propositionsFilteringoptions:--acc-sccs=RANGE,--accepting-sccs=RANGEkeep automata whose number of non-trivial accepting SCCs is in RANGE--acc-sets=RANGEkeep automata whose number of acceptance sets is in RANGE--accept-word=WORDkeep automata that accept WORD--acceptance-is=NAME|FORMULAmatch automata with given acceptance condition--ap=RANGEmatch automata with a number of (declared) atomic propositions in RANGE--are-isomorphic=FILENAMEkeep automata that are isomorphic to the automaton in FILENAME--edges=RANGEkeep automata whose number of edges is in RANGE--equivalent-to=FILENAMEkeep automata that are equivalent (language-wise) to the automa- ton in FILENAME--has-exist-branchingkeep automata that use existential branching (i.e., make non-de- terministic choices)--has-univ-branchingkeep alternating automata that use universal branching--included-in=FILENAMEkeep automata whose languages are included in that of the automaton from FILENAME--inherently-weak-sccs=RANGEkeep automata whose number of accepting inherently-weak SCCs is in RANGE. An accepting SCC is inherently weak if it does not have a rejecting cycle.--intersect=FILENAMEkeep automata whose languages have an non-empty intersection with the automaton from FILENAME--is-alternatingkeep only automata using universal branching--is-coloredkeep colored automata (i.e., exactly one acceptance mark per transition or state)--is-completekeep complete automata--is-deterministickeep deterministic automata--is-emptykeep automata with an empty language--is-inherently-weakkeep only inherently weak automata--is-semi-deterministickeep semi-deterministic automata--is-stutter-invariantkeep automata representing stutter-invariant properties--is-terminalkeep only terminal automata--is-unambiguouskeep only unambiguous automata--is-very-weakkeep only very-weak automata--is-weakkeep only weak automata--nondet-states=RANGEkeep automata whose number of nondeterministic states is in RANGE-N,--nth=RANGEassuming input automata are numbered from 1, keep only those in RANGE--rej-sccs=RANGE,--rejecting-sccs=RANGEkeep automata whose number of non-trivial rejecting SCCs is in RANGE--reject-word=WORDkeep automata that reject WORD--sccs=RANGEkeep automata whose number of SCCs is in RANGE--states=RANGEkeep automata whose number of states is in RANGE--terminal-sccs=RANGEkeep automata whose number of accepting terminal SCCs is in RANGE. Terminal SCCs are weak and complete.--triv-sccs=RANGE,--trivial-sccs=RANGEkeep automata whose number of trivial SCCs is in RANGE--unused-ap=RANGEmatch automata with a number of declared, but unused atomic propositions in RANGE--used-ap=RANGEmatch automata with a number of used atomic propositions in RANGE-u,--uniquedo not output the same automaton twice (same in the sense that they are isomorphic)-v,--invert-matchselect non-matching automata--weak-sccs=RANGEkeep automata whose number of accepting weak SCCs is in RANGE. In a weak SCC, all transitions belong to the same acceptance sets. RANGE may have one of the following forms: 'INT', 'INT..INT', '..INT', or 'INT..' WORD is lasso-shaped and written as 'BF;BF;...;BF;cycle{BF;...;BF}' where BF are arbitrary Boolean formulas. The 'cycle{...}' part is mandatory, but the prefix can be omitted.Transformations:--cleanup-acceptanceremove unused acceptance sets from the automaton--cnf-acceptanceput the acceptance condition in Conjunctive Normal Form--complementcomplement each automaton (different strategies are used)--complement-acceptancecomplement the acceptance condition (without touching the autom- aton)--decompose-scc=t|w|s|N|aN,--decompose-strength=t|w|s|N|aNextract the (t) terminal, (w) weak, or (s) strong part of an au- tomaton or (N) the subautomaton leading to the Nth SCC, or (aN) to the Nth accepting SCC (option can be combined with commas to extract multiple parts)--destutallow less stuttering--dnf-acceptanceput the acceptance condition in Disjunctive Normal Form--dualizedualize each automaton--exclusive-ap=AP,AP,... if any of those APs occur in the automaton, restrict all edges to ensure two of them may not be true at the same time. Use this option multiple times to declare independent groups of ex- clusive propositions.--generalized-rabin[=unique-inf|share-inf],--gra[=unique-inf|share-inf] rewrite the acceptance condition as generalized Rabin; the de- fault "unique-inf" option uses the generalized Rabin definition from the HOA format; the "share-inf" option allows clauses to share Inf sets, therefore reducing the number of sets--generalized-streett[=unique-fin|share-fin],--gsa[=unique-fin|share-fin] rewrite the acceptance condition as generalized Streett; the "share-fin" option allows clauses to share Fin sets, therefore reducing the number of sets; the default "unique-fin" does not--instut[=1|2] allow more stuttering (two possible algorithms)--keep-states=NUM[,NUM...] only keep specified states. The first state will be the new initial state. Implies--remove-unreachable-states.--mask-acc=NUM[,NUM...] remove all transitions in specified acceptance sets--merge-transitionsmerge transitions with same destination and acceptance--partial-degeneralize[=NUM1,NUM2,...] Degeneralize automata according to sets NUM1,NUM2,... If no sets are given, partial degeneralization is performed for all con- junctions of Inf and disjunctions of Fin.--product=FILENAME,--product-and=FILENAMEbuild the product with the automaton in FILENAME to intersect languages--product-or=FILENAMEbuild the product with the automaton in FILENAME to sum lan- guages--randomize[=s|t] randomize states and transitions (specify 's' or 't' to random- ize only states or transitions)--remove-ap=AP[=0|=1][,AP...] remove atomic propositions either by existential quantification, or by assigning them 0 or 1--remove-dead-statesremove states that are unreachable, or that cannot belong to an infinite path--remove-finrewrite the automaton without using Fin acceptance--remove-unreachable-statesremove states that are unreachable from the initial state--remove-unused-apremove declared atomic propositions that are not used--sat-minimize[=options] minimize the automaton using a SAT solver (only works for deter- ministic automata). Supported options are acc=STRING, states=N, max-states=N, sat-incr=N, sat-incr-steps=N, sat-langmap, sat-naive, colored, preproc=N. Spot uses by default its PicoSAT distribution but an external SATsolver can be set thanks to the SPOT_SATSOLVER environment variable(see spot-x).--separate-setsif both Inf(x) and Fin(x) appear in the acceptance condition, replace Fin(x) by a new Fin(y) and adjust the automaton--simplify-acceptancesimplify the acceptance condition by merging identical accep- tance sets and by simplifying some terms containing complemen- tary sets--simplify-exclusive-apif--exclusive-apis used, assume those AP groups are actually exclusive in the system to simplify the expression of transition labels (implies--merge-transitions)--split-edgessplit edges into transitions labeled by conjunctions of all atomic propositions, so they can be read as letters--streett-likeconvert to an automaton with Streett-like acceptance. Works only with acceptance condition in DNF--strip-acceptanceremove the acceptance condition and all acceptance sets--sum=FILENAME,--sum-or=FILENAMEbuild the sum with the automaton in FILENAME to sum languages--sum-and=FILENAMEbuild the sum with the automaton in FILENAME to intersect lan- guagesDecorations(for-dand-H1.1output):--highlight-accepting-run[=NUM] highlight one accepting run using color NUM--highlight-languageshighlight states that recognize identical languages--highlight-nondet[=NUM] highlight nondeterministic states and edges with color NUM--highlight-nondet-edges[=NUM] highlight nondeterministic edges with color NUM--highlight-nondet-states[=NUM] highlight nondeterministic states with color NUM--highlight-word=[NUM,]WORD highlight one run matching WORD using color NUMSimplificationgoal:-a,--anyno preference, do not bother making it small or deterministic-D,--deterministicprefer deterministic automata (combine with--genericto be sure to obtain a deterministic automaton)--smallprefer small automataSimplificationlevel:--highall available optimizations (slow)--lowminimal optimizations (fast)--mediummoderate optimizations If any option among--small,--deterministic, or--anyis given, then the simplification level defaults to--highunless specified otherwise. If any option among--low,--medium, or--highis given, then the sim- plification goal defaults to--smallunless specified otherwise. If none of those options are specified, then autfilt acts as is--any--lowwere given: these actually disable the simplification routines.Miscellaneousoptions:--seed=INTseed for the random number generator (0)-x,--extra-options=OPTSfine-tuning options (see spot-x (7))--helpprint this help--versionprint program version Mandatory or optional arguments to long options are also mandatory or optional for any corresponding short options.Exitstatus:0 if some automata were output 1 if no automata were output (no match) 2 if any error has been reportedOPTIONS FOR SAT-MINIMIZATIONBy default, SAT-based minimization executes a binary search, checking N/2 etc. The upper bound being N (the size of the starting automaton), the lower bound is always 1 except whensat-langmapoption is used.acc=DOUBLEQUOTEDSTRINGDOUBLEQUOTEDSTRING is an acceptance formula in the HOA syntax, or a parametrized acceptance name (the different acc-name: op- tions from HOA).coloredforce all transitions (or all states if-Sis used) to belong to exactly one acceptance condition.max-states=MM is an upper-bound on the maximum number of states of the con- structed automaton.sat-incr=Muse an incremental approach for SAT-based minimization algo- rithm. M can be either1or2. They correspond respectively to-xsat-minimize=2and-xsat-minimize=3options. They restart the encoding only after (N-1)-sat-incr-stepsstates have been won. Each iterations of both starts by encoding the research of an N-1 automaton, N being the size of the starting automaton.1uses Picosat assumptions. It additionally assumes that the lastsat-incr-stepsstates are unnecessary. On failure, it relax the assumptions to do a binary search between N-1 and (N-1)-sat-incr-steps.sat-incr-stepsdefaults to 6.2, as for it, after an N-1 state automaton has been found, uses incremental solving for the nextsat-incr-stepsiterations by forbidding the usage of an additional state without reencoding the problem again. A full encoding occurs aftersat-incr-stepsiterations unlesssat-incr-steps=-1(see SPOT_XCNF environment variable described in spot-x). It defaults to 2.sat-incr-steps=Mset the value ofsat-incr-stepsto M. This is used bysat-incroption.sat-naiveuse the naive algorithm to find a smaller automaton. It starts from N (N being the size of the starting automaton) and then checks N-1, N-2, etc. until the last successful check.sat-langmapFind the lower bound of default sat-minimize procedure (1). This relies on the fact that the size of the minimal automaton is at least equal to the total number of different languages recog- nized by the automaton's states.states=MM is a fixed number of states to use in the result (all the states needs not be accessible in the result. Therefore, the output might be smaller nonetheless). The SAT-based procedure is just used once to synthesize one automaton, and no further mini- mization is attempted.BIBLIOGRAPHYThe following papers are related to some of the transformations imple- mented in autfilt.oEtienne Renault, Alexandre Duret-Lutz, Fabrice Kordon, and Denis Poitrenaud: Strength-based decomposition of the property BA1/4chi automaton for faster model checking. Proceedings of TACAS'13. LNCS 7795. The--strength-decomposeoption implements the definitions given in the above paper.oFrantiA!ek Blahoudek, Alexandre Duret-Lutz, VojtAech Rujbr, and Jan StrejAek: On refinement of BA1/4chi automata for explicit model checking. Proceedings of SPIN'15. LNCS 9232. That paper gives the motivation for options--exclusive-apand--simplify-exclusive-ap.oThibaud Michaud and Alexandre Duret-Lutz: Practical stutter-in- variance checks forI-regular languages. Proceedings of SPIN'15. LNCS 9232. Describes the algorithms used by the--destutand--instutop- tions. These options correpond respectively to cl() and sl() in the paper.oSouheib Baarir and Alexandre Duret-Lutz: SAT-based minimization of deterministicI-automata. Proceedings of LPAR'15 (a.k.a LPAR-20). LNCS 9450. Describes the--sat-minimizeoption.REPORTING BUGSReport bugs to <spot@lrde.epita.fr>.COPYRIGHTCopyright (C) 2020 Laboratoire de Recherche et DA(C)veloppement de l'Epita. License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>. This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law.SEE ALSOspot-x(7)dstar2tgba(1) autfilt (spot) 2.9.5 November 2020 AUTFILT(1)

NAME | SYNOPSIS | DESCRIPTION | OPTIONS FOR SAT-MINIMIZATION | BIBLIOGRAPHY | REPORTING BUGS | COPYRIGHT | SEE ALSO

Want to link to this manual page? Use this URL:

<https://man.freebsd.org/cgi/man.cgi?query=autfilt&sektion=1&manpath=FreeBSD+13.0-RELEASE+and+Ports>