|
|
| |
DSTAR2TGBA(1) |
User Commands |
DSTAR2TGBA(1) |
dstar2tgba - convert automata into Büchi automata
dstar2tgba [OPTION...] [FILENAME[/COL]...]
Convert automata with any acceptance condition into variants of Büchi
automata.
This reads automata into any supported format (HOA, LBTT,
ltl2dstar, never claim) and outputs a Transition-based Generalized
Büchi Automata in GraphViz's format by default. Each supplied file
may contain multiple automata.
- -F, --file=FILENAME
- process the automaton in FILENAME
- --trust-hoa=BOOL
- If false, properties listed in HOA files are ignored, unless they can be
easily verified. If true (the default) any supported property is
trusted.
- -b, --buchi, --Buchi
- automaton with Büchi acceptance
- -B, --sba, --ba
- state-based Büchi Automaton (same as -S -b)
- --cobuchi, --coBuchi
- automaton with co-Büchi acceptance (will recognize a superset of
the input language if not co-Büchi realizable)
- -C, --complete
- output a complete automaton
- -G, --generic
- any acceptance condition is allowed
- -M, --monitor
- Monitor (accepts all finite prefixes of the given property)
-p,
--colored-parity[=any|min|max|odd|even|min
odd|min even|max odd|max
- even]
- colored automaton with parity acceptance
- -P,
--parity[=any|min|max|odd|even|min
odd|min even|max odd|max even]
- automaton with parity acceptance
- -S, --state-based-acceptance, --sbacc
- define the acceptance using states
- --tgba, --gba
- automaton with Generalized Büchi acceptance (default)
- -8, --utf8
- enable UTF-8 characters in output (ignored with --lbtt or
--spin)
- --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-sensitive-example',
'semi-determinism', or 'strength'.
- -d,
--dot[=1|a|A|b|B|c|C(COLOR)|e|E|f(FONT)|h|i(ID)|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
Büchi/co-Büchi 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, (i) or (i(GRAPHID)) add IDs, (k) use state labels 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) display 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 acceptance when possible
[default], (t) force transition-based acceptance, (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
Büchi automata)
- --name=FORMAT
- set the name of the output automaton
- -o, --output=FORMAT
- send output to a file named FORMAT instead of standard output. The first
automaton sent to a file truncates it unless FORMAT starts with
'>>'.
- -q, --quiet
- suppress 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=FORMAT
- output 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 column
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 following
LETTERS, possibly concatenated: (a) accepting, (r) rejecting, (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 restrict 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) occasional 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 propositions
- -a, --any
- no preference, do not bother making it small or deterministic
- -D, --deterministic
- prefer deterministic automata (combine with --generic to be sure to
obtain a deterministic automaton)
- --small
- prefer small automata (default)
- --high
- all available optimizations (slow, default)
- --low
- minimal optimizations (fast)
- --medium
- moderate optimizations
- -x, --extra-options=OPTS
- fine-tuning options (see spot-x (7))
- --help
- print this help
- --version
- print program version
Mandatory or optional arguments to long options are also mandatory
or optional for any corresponding short options.
dstar2tgba was introduced in Spot 1.2 as a command that reads automata in
ltl2dstar's format, and converts them into TGBA. At this time it was
the only command-line tool being able to read automata.
In Spot 1.99.1 the autfilt command was introduced, but
could only read automata in the HOA format, or in lbtt's format, or
as never claims. So dstar2tgba was still the only way to process
automata in ltl2dstar's format.
In Spot 1.99.4 the parser for ltl2dstar's format was
finally merged with the parser used by autfilt for reading the other
format. This implies not only that autfilt can now read
ltl2dstar's format, but also that dstar2tgba can read the
other formats as well.
Nowadays, the command
% dstar2tgba some files
can be used as a shorthand for
% autfilt --tgba --high --small some files
The name dstar2tgba is kept for backward compatibility and
because it is used in at least one published paper, but naming this tool
aut2tgba would make more sense.
- 1.
- The
ltl2dstarmanual.
Documents the output format of ltl2dstar.
- 2.
- Chistof Löding: Mehods for the Transformation of ω-Automata:
Complexity and Connection to Second Order Logic. Diploma Thesis.
University of Kiel. 1998.
Describes various tranformations from non-deterministic Rabin
and Streett automata to Büchi automata. Slightly optimized
variants of these transformations are used by dstar2tgba for the general
cases.
- 3.
- Sriram C. Krishnan, Anuj Puri, and Robert K. Brayton: Deterministic
ω-automata vis-a-vis Deterministic Büchi Automata. ISAAC'94.
Explains how to preserve the determinism of Rabin and Streett
automata when the property can be repreted by a Deterministic automaton.
dstar2tgba implements this for the Rabin case only. In other words,
translating a deterministic Rabin automaton with dstar2tgba will produce
a deterministic TGBA or BA if such a automaton exists.
- 4.
- Souheib Baarir and Alexandre Duret-Lutz: Mechanizing the minimization of
deterministic generalized Büchi automata. Proceedings of FORTE'14.
LNCS 8461.
Explains the SAT-based minimization techniques that can be
used (on request only) by dstar2tgba to minimize deterministic
Büchi automata.
- 5.
- Souheib Baarir and Alexandre Duret-Lutz: SAT-based minimization of
deterministic ω-automata. Proceedings of LPAR'15 (a.k.a LPAR-20).
LNCS 9450.
Extends the previous paper by allowing arbitrary acceptance
conditions.
Report bugs to <spot@lrde.epita.fr>.
Copyright © 2022 Laboratoire de Recherche et Dé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.
Visit the GSP FreeBSD Man Page Interface. Output converted with ManDoc. |