API reference¶

Automata¶

class autolib.Automaton(*args, **kwargs)¶

A finite automaton over 32-bit integer symbols, deterministic or not, with epsilon transitions.

Operators follow the operations of regular languages:

>>> a = Automaton("(0|1)*0")        # minimal DFA of a regular expression
>>> b = Automaton("1(0|1)*")
>>> c = (a | b) & ~Automaton("11")  # union, intersection, complement
>>> [1, 1, 0] in a                   # membership
True
>>> (a - b) == (a & ~b)              # equality of languages
True
>>> a <= (a | b)                     # inclusion of languages
True

Automata are values : operations return new automata.

__call__(self, word: collections.abc.Sequence[int]) → bool¶

__contains__(self, arg: collections.abc.Sequence[int], /) → bool¶

add_epsilon(self, source: int, target: int) → None¶: Adds an epsilon transition.

add_state(self, accept: bool = False) → int¶: Adds a state and returns its number.

add_transition(self, source: int, target: int, labels: int | range | IntervalSet | collections.abc.Iterable[int | range | IntervalSet]) → None¶: Adds a transition reading an integer, a range, an IntervalSet or an iterable of them.

any_symbol = <nanobind.nb_func object>¶

compile(self, lookup_table: bool = True) → autolib._autolib.CompiledDFA¶: A compiled DFA, to read many words quickly.

complement(self) → autolib._autolib.Automaton¶

concatenate(self, other: autolib._autolib.Automaton) → autolib._autolib.Automaton¶

count_words(self, length: int) → int¶: The number of accepted words of a length, exactly.

counter_example(self, other: autolib._autolib.Automaton) → list[int] | None¶: A shortest word accepted by one automaton only, or None if both languages are equal.

determinize(self) → autolib._autolib.Automaton¶

empty_language = <nanobind.nb_func object>¶

empty_word = <nanobind.nb_func object>¶

epsilons(self, state: int) → list[int]¶: The targets of the epsilon transitions leaving a state.

from_regex = <nanobind.nb_func object>¶

property initial¶: The initial state, or None.

is_accept(self, state: int) → bool¶

property is_deterministic¶: (self) -> bool

is_empty(self) → bool¶

is_finite(self) → bool¶

is_subset_of(self, other: autolib._autolib.Automaton) → bool¶

is_universal(self) → bool¶

minimize(self, algorithm: str = 'partition') → autolib._autolib.Automaton¶: The minimal DFA, by partition refinement or by Brzozowski’s method.

multi_weighted(self, *costs: float | collections.abc.Callable[[Edge], float]) → MultiWeightedAutomaton¶: This automaton weighted by vectors, one cost per dimension.

nfa = <nanobind.nb_func object>¶

of_word = <nanobind.nb_func object>¶

optional(self) → autolib._autolib.Automaton¶: Zero or one occurrence.

plus(self) → autolib._autolib.Automaton¶: One or more repetitions.

random_word(self, length: int, rng: object | None = None) → list[int] | None¶: A word of a length drawn uniformly among the accepted ones, or None; rng is a random.Random, or the random module.

reduce(self) → autolib._autolib.Automaton¶: An equivalent automaton whose states are merged by bisimulation : never blows up.

remove_epsilon(self) → autolib._autolib.Automaton¶

repeat(self, min: int, max: int | None = None) → autolib._autolib.Automaton¶: From min to max repetitions, None meaning unbounded.

reverse(self) → autolib._autolib.Automaton¶: The automaton of the mirror language.

run(self, word: collections.abc.Sequence[int]) → bool¶: Whether a word is accepted.

same_language(self, other: autolib._autolib.Automaton) → bool¶

searcher(self) → autolib._autolib.Searcher¶: A searcher of the factors of texts in the language.

set_accept(self, state: int, accept: bool = True) → None¶

set_initial(self, state: int) → None¶

shortest_word(self) → list[int] | None¶: A shortest accepted word, or None.

snapshot(self) → autolib._autolib.AutomatonSnapshot¶: The structure captured once, for several weightings.

star(self) → autolib._autolib.Automaton¶: Kleene star.

property state_count¶: The number of states.

step(self, state: int, symbol: int) → int | None¶: The state reached from a state of a deterministic automaton, or None.

symbols = <nanobind.nb_func object>¶

to_dot(self) → str¶: The Graphviz representation.

property transition_count¶: The number of transitions, epsilon transitions included.

transitions(self, state: int) → list[tuple[int, autolib._autolib.IntervalSet]]¶: The transitions leaving a state, as pairs (target, labels).

trim(self) → None¶: Removes the useless states, in place.

universal = <nanobind.nb_func object>¶

weighted(self, cost: float | collections.abc.Callable[[Edge], float]) → autolib._autolib.WeightedAutomaton¶: This automaton with a cost per transition : a number or a function of an Edge.

words(self, max_length: int) → autolib._autolib.WordIterator¶: The accepted words up to a length, lazily, in shortlex order : by length, then lexicographically.

class autolib.IntervalSet(*args, **kwargs)¶

A set of 32-bit integer symbols, stored as sorted disjoint intervals.

Built from an integer, a range of step 1, or an iterable of integers and ranges:

>>> IntervalSet(range(0, 10)) | IntervalSet([20, 21])
IntervalSet({0..9, 20..21})
>>> 5 in IntervalSet.range(0, 9)
True

__contains__(self, arg: int, /) → bool¶
__contains__(self, arg: autolib._autolib.IntervalSet, /) → bool

all = <nanobind.nb_func object>¶

property cardinality¶: The number of symbols.

property intervals¶: The intervals, as pairs (min, max) of included bounds.

isdisjoint(self, other: autolib._autolib.IntervalSet) → bool¶

property max¶: The greatest symbol.

property min¶: The least symbol.

range = <nanobind.nb_func object>¶

class autolib.Regex(*args, **kwargs)¶

A parsed regular expression over integer symbols.

Symbols are the digits 0 to 9 or integers between angle brackets, <-3>, <42>; . is any symbol. Operators : concatenation, | union, & intersection, ~ complement, *, +, ?, {n}, {n,m}, {n,}, {,m}, and () for the empty word:

>>> Regex("(<10>|<20>)+.{2,}").to_dfa().shortest_word()
[10, -2147483648, -2147483648]

to_dfa(self) → autolib._autolib.Automaton¶: The minimal DFA.

to_nfa(self) → autolib._autolib.Automaton¶: The Thompson automaton, built in linear time.

exception autolib.RegexError¶: A malformed regular expression; position tells where.

autolib.MIN_SYMBOL = -2147483648¶

int([x]) -> integer int(x, base=10) -> integer

Convert a number or string to an integer, or return 0 if no arguments are given. If x is a number, return x.__int__(). For floating-point numbers, this truncates towards zero.

If x is not a number or if base is given, then x must be a string, bytes, or bytearray instance representing an integer literal in the given base. The literal can be preceded by ‘+’ or ‘-’ and be surrounded by whitespace. The base defaults to 10. Valid bases are 0 and 2-36. Base 0 means to interpret the base from the string as an integer literal. >>> int(‘0b100’, base=0) 4

autolib.MAX_SYMBOL = 2147483647¶

int([x]) -> integer int(x, base=10) -> integer

Convert a number or string to an integer, or return 0 if no arguments are given. If x is a number, return x.__int__(). For floating-point numbers, this truncates towards zero.

Words¶

class autolib.WordSampler(*args, **kwargs)¶

The words of one length of a language, numbered in lexicographic order.

Counts once, then draws, ranks and unranks words quickly:

>>> sampler = WordSampler(Automaton("(0|1)*0(0|1){3}"), 20)
>>> sampler.count
524288
>>> w = sampler.draw()
>>> sampler.unrank(sampler.rank(w)) == w
True

property count¶: The number of words, exactly.

draw(self, rng: object | None = None) → list[int]¶: A word drawn uniformly, with a random.Random, or the random module.

property length¶: (self) -> int

rank(self, word: collections.abc.Sequence[int]) → int | None¶: The rank of a word, or None if it is not one of the words.

unrank(self, rank: int) → list[int]¶: The word of a rank, from 0 to count - 1.

class autolib.WordIterator¶: The words of a language, computed one at a time.

Compiled automata and searches¶

class autolib.CompiledDFA(*args, **kwargs)¶

An immutable DFA compiled into flat arrays, to read many words quickly.

Accepts lists and numpy arrays of integers; arrays of int32 are read in place, and long words without the GIL.

__call__(self, word: collections.abc.Sequence[int]) → bool¶

__contains__(self, arg: collections.abc.Sequence[int], /) → bool¶

property has_lookup_table¶: (self) -> bool

run(self, word: collections.abc.Sequence[int]) → bool¶

property state_count¶: (self) -> int

class autolib.Searcher(*args, **kwargs)¶

Searches the leftmost-longest factors of sequences belonging to a language, in linear time.

>>> s = Searcher(Automaton("12+"))
>>> s.find([3, 1, 2, 2, 4])
Match(1, 4)

contains(self, text: collections.abc.Sequence[int]) → bool¶: Whether a factor of the text belongs to the language.

find(self, text: collections.abc.Sequence[int], start: int = 0) → autolib._autolib.Match | None¶: The leftmost-longest match from a position, or None.

find_all(self, text: collections.abc.Sequence[int]) → list[autolib._autolib.Match]¶: The successive non-overlapping leftmost-longest matches.

class autolib.Match(*args, **kwargs)¶

A factor text[start:end] of a text.

property end¶: (self) -> int

property start¶: (self) -> int

Weighted automata¶

class autolib.WeightedAutomaton(*args, **kwargs)¶

Additive costs on the edges of a graph : the cost of a word is the least cost of its accepting paths.

>>> b = WeightedAutomaton.Builder()
>>> s, t = b.add_state(), b.add_state()
>>> b.set_initial(s)
>>> b.set_accept(t, 0.5)
>>> _ = b.add_transition(s, t, 1, 2.0)
>>> _ = b.add_transition(s, t, range(0, 10), 3.0)
>>> a = b.build()
>>> a([1])
2.5

A word not accepted costs inf, and -inf when negative cycles make its cost unbounded.

class Builder(*args, **kwargs)¶

Builds weighted automata : the graph and its costs together.

add_epsilon(self, source: int, target: int, cost: float) → int¶

add_state(self) → int¶

add_transition(self, source: int, target: int, labels: int | range | IntervalSet | collections.abc.Iterable[int | range | IntervalSet], cost: float) → int¶

build(self) → autolib._autolib.WeightedAutomaton¶

set_accept(self, state: int, cost: float = 0.0) → None¶

set_initial(self, state: int, cost: float = 0.0) → None¶

class Evaluator¶

Evaluates many words, reusing its buffers.

__call__(self, word: collections.abc.Sequence[int]) → float¶

cost(self, word: collections.abc.Sequence[int]) → float¶

optimal_cost_with_prefix(self, prefix: collections.abc.Sequence[int]) → float¶

__call__(self, word: collections.abc.Sequence[int]) → float¶

__contains__(self, arg: collections.abc.Sequence[int], /) → bool¶

best_path(self, word: collections.abc.Sequence[int] | None = None) → autolib._autolib.WeightedPath | None¶: A best accepting path, reading a word if given, or None.

best_path_of_length(self, length: int) → autolib._autolib.WeightedPath | None¶

best_word_of_length(self, length: int) → list[int] | None¶

compile(self) → autolib._autolib.CompiledWeightedDFA¶

concatenate(self, other: autolib._autolib.WeightedAutomaton) → autolib._autolib.WeightedAutomaton¶

cost(self, word: collections.abc.Sequence[int]) → float¶

cost_of_length(self, length: int) → float¶

cost_of_length_at_most(self, length: int) → float¶

determinize(self, max_states: int = 10000) → autolib._autolib.WeightedAutomaton¶: An equivalent deterministic automaton, computed exactly; ValueError beyond max_states states.

evaluator(self) → autolib._autolib.WeightedAutomaton.Evaluator¶

final_weight(self, state: int) → float¶

from_automaton = <nanobind.nb_func object>¶

property graph¶: (self) -> autolib._autolib.AutomatonGraph

property initial_weight¶: (self) -> float

intersection(self, other: autolib._autolib.WeightedAutomaton) → autolib._autolib.WeightedAutomaton¶

k_best_paths(self, k: int) → list[autolib._autolib.WeightedPath]¶

k_best_words(self, k: int) → list[autolib._autolib.WeightedWord]¶

minimize(self) → autolib._autolib.WeightedAutomaton¶: The minimal deterministic automaton with the same costs.

of = <nanobind.nb_func object>¶

property optimal_cost¶: The best cost of the accepting paths.

optimal_cost_with_prefix(self, prefix: collections.abc.Sequence[int]) → float¶

paths_by_cost(self) → autolib._autolib.PathIterator¶: The accepting paths by increasing cost, lazily.

plus(self) → autolib._autolib.WeightedAutomaton¶

remove_epsilon(self) → autolib._autolib.WeightedAutomaton¶

repeat(self, min: int, max: int | None = None) → autolib._autolib.WeightedAutomaton¶

reverse(self) → autolib._autolib.WeightedAutomaton¶

run(self, word: collections.abc.Sequence[int]) → bool¶: Whether an accepting path reads the word, whatever the costs.

simplify(self) → autolib._autolib.WeightedAutomaton¶

star(self) → autolib._autolib.WeightedAutomaton¶

to_automaton(self) → autolib._autolib.Automaton¶: The automaton of the language, without the costs.

to_dot(self, highlight: autolib._autolib.WeightedPath) → str¶

to_dot(self, highlight: collections.abc.Sequence[int] | None = None) → str

Overloaded function.

to_dot(self, highlight: autolib._autolib.WeightedPath) -> str
to_dot(self, highlight: collections.abc.Sequence[int] | None = None) -> str

The Graphviz description : symbols / cost on the edges, final costs under the accepting states; the edges of highlight, a WeightedPath or a list of edges, are drawn in colour.

trim(self) → autolib._autolib.WeightedAutomaton¶

union(self, other: autolib._autolib.WeightedAutomaton) → autolib._autolib.WeightedAutomaton¶

weight(self, edge: int) → float¶

property weights¶: (self) -> list[float]

with_weights(self, weights: collections.abc.Sequence[float]) → autolib._autolib.WeightedAutomaton¶

words_by_cost(self) → autolib._autolib.WordCostIterator¶: The distinct words by increasing cost, lazily, without determinizing.

class autolib.WeightedPath¶

A path : its edges, the symbols it reads and its cost.

property cost¶: (self) -> float

property edge_count¶: (self) -> int

property edges¶: (self) -> list[int]

property end¶: (self) -> int

property graph¶: (self) -> autolib._autolib.AutomatonGraph

property start¶: (self) -> int

property symbols¶: The word read, the least symbol of each edge unless a query chose.

class autolib.WeightedWord¶

A word and its cost, the least cost of its accepting paths.

property cost¶: (self) -> float

property symbols¶: (self) -> list[int]

class autolib.AutomatonGraph(*args, **kwargs)¶

An immutable multigraph whose edges read sets of symbols, or nothing.

The structure of the weighted automata : weightings of the same graph share it. Edges keep the numbers given by their order of creation, and parallel edges are never merged.

class Builder(*args, **kwargs)¶

Builds graphs; building takes a snapshot.

add_epsilon(self, source: int, target: int) → int¶

add_state(self, accept: bool = False) → int¶

add_transition(self, source: int, target: int, labels: int | range | IntervalSet | collections.abc.Iterable[int | range | IntervalSet]) → int¶

build(self) → autolib._autolib.AutomatonGraph¶

set_accept(self, state: int, accept: bool = True) → None¶

set_initial(self, state: int) → None¶

__contains__(self, arg: collections.abc.Sequence[int], /) → bool¶

accepts(self, edge: int, symbol: int) → bool¶

coaccessible_states(self) → list[bool]¶

property edge_count¶: (self) -> int

from_automaton = <nanobind.nb_func object>¶

incoming(self, state: int) → list[int]¶

property initial¶: (self) -> int | None

is_accept(self, state: int) → bool¶

property is_acyclic¶: (self) -> bool

property is_deterministic¶: (self) -> bool

is_epsilon(self, edge: int) → bool¶

labels(self, edge: int) → autolib._autolib.IntervalSet¶

outgoing(self, state: int) → list[int]¶

run(self, word: collections.abc.Sequence[int]) → bool¶

same_as(self, other: autolib._autolib.AutomatonGraph) → bool¶: Whether both designate the same graph.

source(self, edge: int) → int¶

property state_count¶: (self) -> int

target(self, edge: int) → int¶

to_automaton(self) → autolib._autolib.Automaton¶

to_dot(self, highlight: collections.abc.Sequence[int] | None = None) → str¶: The Graphviz description, the edges of highlight drawn in colour.

topological_order(self) → list[int]¶

useful_states(self) → list[bool]¶

class autolib.AutomatonSnapshot(*args, **kwargs)¶

The structure of an automaton captured once, to weight it several times on the same graph.

>>> snapshot = Automaton("12+").snapshot()
>>> price = snapshot.weighted(2.0)
>>> both = snapshot.multi_weighted(2.0, lambda edge: 0.0 if edge.epsilon else 5.0)
>>> price.graph.same_as(both.graph)
True

__contains__(self, arg: collections.abc.Sequence[int], /) → bool¶

property graph¶: (self) -> autolib._autolib.AutomatonGraph

multi_weighted(self, *costs: float | collections.abc.Callable[[Edge], float]) → MultiWeightedAutomaton¶: A weighting by vectors, one cost per dimension : numbers or functions of an Edge.

origin(self, edge: int) → autolib._autolib.Edge¶: The transition of the automaton an edge comes from.

run(self, word: collections.abc.Sequence[int]) → bool¶

to_automaton(self) → autolib._autolib.Automaton¶

weighted(self, cost: float | collections.abc.Callable[[Edge], float], initial: float = 0.0, final: float | collections.abc.Callable[[int], float] | None = None) → autolib._autolib.WeightedAutomaton¶: A weighting : cost is a number or a function of an Edge, final a number or a function of an accepting state.

class autolib.Edge¶

A transition as seen by the cost functions of a weighting.

property epsilon¶: Whether it reads nothing.

property index¶: Its rank among the transitions, or the epsilon transitions, of its source.

property labels¶: The symbols it reads, empty for an epsilon transition.

property source¶: The state it leaves.

property target¶: The state it reaches.

class autolib.LayeredAutomaton¶

The unfolding of a graph by the number of symbols read, up to a horizon.

Built once, evaluated with any weighting of the base graph, or costs depending on the position.

class Analysis¶

The distances of one weighting of an unfolding.

backward_distances(self) → list[float]¶

best_path(self) → autolib._autolib.WeightedPath | None¶

cost_at(self, position: int, symbol: int) → float¶: The best cost of the accepting paths reading a symbol at a position.

forward_distances(self) → list[float]¶

property optimal_cost¶: (self) -> float

analyze(self, automaton: autolib._autolib.WeightedAutomaton, weights: collections.abc.Callable[[int, int], float] | None = None) → autolib._autolib.LayeredAutomaton.Analysis¶

at_most = <nanobind.nb_func object>¶

property base_graph¶: (self) -> autolib._autolib.AutomatonGraph

best_path(self, automaton: autolib._autolib.WeightedAutomaton) → autolib._autolib.WeightedPath | None¶

evaluate(self, automaton: autolib._autolib.WeightedAutomaton, weights: collections.abc.Callable[[int, int], float] | None = None) → autolib._autolib.WeightedAutomaton¶

evaluate(self, automaton: autolib._autolib.MultiWeightedAutomaton) → autolib._autolib.MultiWeightedAutomaton

Overloaded function.

evaluate(self, automaton: autolib._autolib.WeightedAutomaton, weights: collections.abc.Callable[[int, int], float] | None = None) -> autolib._autolib.WeightedAutomaton

The weighting of the unfolding; weights(position, edge) gives costs depending on the position.

evaluate(self, automaton: autolib._autolib.MultiWeightedAutomaton) -> autolib._autolib.MultiWeightedAutomaton

exactly = <nanobind.nb_func object>¶

for_word = <nanobind.nb_func object>¶

property graph¶: (self) -> autolib._autolib.AutomatonGraph

property horizon¶: (self) -> int

map(self, path: autolib._autolib.WeightedPath) → autolib._autolib.WeightedPath¶
map(self, path: autolib._autolib.MultiWeightedPath) → autolib._autolib.MultiWeightedPath

original_edge(self, edge: int) → int¶

original_state(self, state: int) → int¶

position(self, state: int) → int¶

class autolib.PathIterator¶: Accepting paths by increasing cost, computed one at a time.

class autolib.WordCostIterator¶: Distinct words by increasing cost, computed one at a time.

Shortest paths¶

class autolib.ShortestPaths¶

Shortest distances from a state, with the best paths.

class Status(*values)¶

FINITE = 0¶

UNREACHABLE = 1¶

UNBOUNDED = 2¶

best_path(self) → autolib._autolib.WeightedPath | None¶

distance_to(self, state: int) → float¶

distances(self) → list[float]¶

property optimal_cost¶: (self) -> float

path_to(self, state: int) → autolib._autolib.WeightedPath | None¶

status_to(self, state: int) → autolib._autolib.ShortestPaths.Status¶

class autolib.PathAnalysis(*args, **kwargs)¶

Distances in both directions : costs through a state or an edge.

property backward¶: (self) -> list[float]

cost_through_edge(self, edge: int) → float¶

cost_through_state(self, state: int) → float¶

property forward¶: (self) -> autolib._autolib.ShortestPaths

autolib.shortest_paths(automaton: autolib._autolib.WeightedAutomaton, reconstruct: bool = True) → autolib._autolib.ShortestPaths¶

autolib.shortest_paths_from(automaton: autolib._autolib.WeightedAutomaton, source: int) → autolib._autolib.ShortestPaths¶

autolib.dag_shortest_paths(automaton: autolib._autolib.WeightedAutomaton) → autolib._autolib.ShortestPaths¶

autolib.dag_longest_paths(automaton: autolib._autolib.WeightedAutomaton) → autolib._autolib.ShortestPaths¶

autolib.dijkstra(automaton: autolib._autolib.WeightedAutomaton) → autolib._autolib.ShortestPaths¶

autolib.bellman_ford(automaton: autolib._autolib.WeightedAutomaton) → autolib._autolib.ShortestPaths¶

autolib.backward_distances(automaton: autolib._autolib.WeightedAutomaton) → list[float]¶

autolib.distances_to(automaton: autolib._autolib.WeightedAutomaton, destination: int) → list[float]¶

autolib.cost_through_state(automaton: autolib._autolib.WeightedAutomaton, state: int) → float¶

autolib.cost_through_edge(automaton: autolib._autolib.WeightedAutomaton, edge: int) → float¶

autolib.determinize_dag(automaton: autolib._autolib.WeightedAutomaton, max_states: int = 18446744073709551615) → autolib._autolib.WeightedAutomaton¶

autolib.minimize_dag(automaton: autolib._autolib.WeightedAutomaton) → autolib._autolib.WeightedAutomaton¶

autolib.k_best_paths_of_length(automaton: autolib._autolib.WeightedAutomaton, length: int, k: int) → list[autolib._autolib.WeightedPath]¶

autolib.k_best_words_of_length(automaton: autolib._autolib.WeightedAutomaton, length: int, k: int) → list[autolib._autolib.WeightedWord]¶

Several costs¶

class autolib.MultiWeightedAutomaton¶

An automaton weighted by vectors : several additive costs at once.

>>> b = MultiWeightedAutomaton.Builder(2)     # time and money
>>> p, q = b.add_state(), b.add_state()
>>> b.set_initial(p)
>>> b.set_accept(q)
>>> _ = b.add_transition(p, q, 7, [10, 1])
>>> _ = b.add_transition(p, q, 7, [2, 5])
>>> len(b.build().pareto_front())
2

class Builder(*args, **kwargs)¶

Builds automata weighted by vectors.

add_epsilon(self, source: int, target: int, costs: collections.abc.Sequence[float]) → int¶

add_state(self) → int¶

add_transition(self, source: int, target: int, labels: int | range | IntervalSet | collections.abc.Iterable[int | range | IntervalSet], costs: collections.abc.Sequence[float]) → int¶

build(self) → autolib._autolib.MultiWeightedAutomaton¶

set_accept(self, state: int, costs: collections.abc.Sequence[float] | None = None) → None¶

set_initial(self, state: int, costs: collections.abc.Sequence[float] | None = None) → None¶

__contains__(self, arg: collections.abc.Sequence[int], /) → bool¶

compile(self) → autolib._autolib.CompiledMultiWeightedDFA¶

concatenate_independent(self, other: autolib._autolib.MultiWeightedAutomaton) → autolib._autolib.MultiWeightedAutomaton¶

property dimensions¶: (self) -> int

final_weights(self, state: int) → list[float]¶

from_weightings = <nanobind.nb_func object>¶

property graph¶: (self) -> autolib._autolib.AutomatonGraph

property initial_weights¶: (self) -> list[float]

lexicographic_best_path(self, priority: collections.abc.Sequence[int] | None = None) → autolib._autolib.MultiWeightedPath | None¶: The best accepting path for the lexicographic order of the dimensions.

of = <nanobind.nb_func object>¶

pareto_for_word(self, word: collections.abc.Sequence[int]) → autolib._autolib.ParetoFront¶

pareto_front(self, all_paths: bool = False) → autolib._autolib.ParetoFront¶

path_costs(self, path: autolib._autolib.WeightedPath) → list[float]¶

product_independent(self, other: autolib._autolib.MultiWeightedAutomaton) → autolib._autolib.MultiWeightedAutomaton¶

project(self, dimension: int) → autolib._autolib.WeightedAutomaton¶

reverse(self) → autolib._autolib.MultiWeightedAutomaton¶

run(self, word: collections.abc.Sequence[int]) → bool¶

scalarize(self, coefficients: collections.abc.Sequence[float]) → autolib._autolib.WeightedAutomaton¶: The scalar automaton of a linear combination of the dimensions.

select_dimensions(self, dimensions: collections.abc.Sequence[int]) → autolib._autolib.MultiWeightedAutomaton¶

simplify(self) → autolib._autolib.MultiWeightedAutomaton¶

synchronized_product = <nanobind.nb_func object>¶

to_automaton(self) → autolib._autolib.Automaton¶

to_dot(self, highlight: autolib._autolib.MultiWeightedPath) → str¶

to_dot(self, highlight: collections.abc.Sequence[int] | None = None) → str

Overloaded function.

to_dot(self, highlight: autolib._autolib.MultiWeightedPath) -> str
to_dot(self, highlight: collections.abc.Sequence[int] | None = None) -> str

The Graphviz description with the vectors of costs; the edges of highlight, a MultiWeightedPath or a list of edges, are drawn in colour.

trim(self) → autolib._autolib.MultiWeightedAutomaton¶

weight(self, edge: int, dimension: int) → float¶

weights(self, edge: int) → list[float]¶

class autolib.MultiWeightedPath¶

An accepting path and the vector of its costs.

cost(self, dimension: int) → float¶

property costs¶: (self) -> list[float]

property edges¶: (self) -> list[int]

property end¶: (self) -> int

exact_cost(self, dimension: int) → fractions.Fraction¶: The exact sum, as a fractions.Fraction.

property graph¶: (self) -> autolib._autolib.AutomatonGraph

property start¶: (self) -> int

property symbols¶: (self) -> list[int]

class autolib.ParetoFront¶

The non-dominated cost vectors, each with a path.

property includes_all_paths¶: (self) -> bool

property is_complete¶: (self) -> bool

property paths¶: (self) -> list[autolib._autolib.MultiWeightedPath]

autolib.dominates(x: collections.abc.Sequence[float], y: collections.abc.Sequence[float]) → bool¶: Whether x dominates y for minimization : smaller or equal everywhere, smaller somewhere.

Compiled weighted automata¶

class autolib.CompiledWeightedDFA(*args, **kwargs)¶

The fast evaluator of a deterministic weighted automaton.

__call__(self, word: collections.abc.Sequence[int]) → float¶

cost(self, word: collections.abc.Sequence[int]) → float¶

property index¶: (self) -> autolib._autolib.WeightedDFAIndex

reweight(self, automaton: autolib._autolib.WeightedAutomaton) → autolib._autolib.CompiledWeightedDFA¶

class autolib.CompiledMultiWeightedDFA(*args, **kwargs)¶

The fast evaluator of a deterministic automaton weighted by vectors.

costs(self, word: collections.abc.Sequence[int]) → list[float] | None¶: The cost vector of a word, or None if it is not accepted.

costs_into(self, word: collections.abc.Sequence[int], out: ndarray[dtype=float64, shape=(*), order='C']) → bool¶: Writes the costs of a word in a numpy array, without allocating; returns whether it is accepted.

property dimensions¶: (self) -> int

property graph¶: (self) -> autolib._autolib.AutomatonGraph

project(self, dimension: int) → autolib._autolib.CompiledWeightedDFA¶

reweight(self, automaton: autolib._autolib.MultiWeightedAutomaton) → autolib._autolib.CompiledMultiWeightedDFA¶

scalarize(self, coefficients: collections.abc.Sequence[float]) → autolib._autolib.CompiledWeightedDFA¶

class autolib.WeightedDFAIndex(*args, **kwargs)¶

The transitions of a deterministic graph, shared by its weightings.

property graph¶: (self) -> autolib._autolib.AutomatonGraph

transition(self, state: int | None, symbol: int) → int | None¶