Sofic shifts

Functions and algorithms for sofic shifts.

The functions in this module are designed to work on a networkx.MultiDiGraph, which we refer to just as graphs. Furthermore, some functions require more specific properties to ensure correctness, which include

See the documentation for the associated functions for a definition of the properties. However, all functions in this module do not explicity check if their input graphs have the property needed correctness.

is_labeled(G)

Returns True iff every edge in the graph G has the attribute label.

out_labels(G, q)

Returns a list of each of the labels appearing on the edges starting at q in G.

alphabet(G)

Returns an iset of labels appearing in G.

is_deterministic(G)

Returns True iff G is deterministic.

is_fully_deterministic(G)

Returns True iff G is fully deterministic.

subset_presentation(G)

Constructs the subset presentation of G.

dot(G, q, w)

Computes the transition action of w in G on q.

idot(G, it, w)

Computes the transition action of w in G on each element of the iterable it, returning an iset of the non-None results.

is_stranded(G, q)

Returns True iff q is stranded in G.

is_essential(G)

Returns True iff G is essential.

make_essential(G)

Modifies G by removing vertices in G that do not lie on bi-infinite paths.

from_partial_fns(pfns)

Returns a deterministic graph built from given partial functions.

random_deterministic_graph(n, m)

Randomly generates a deterministic graph defined by m partial functions over n states.

random_deterministic_graph_with_props(n, m, …)

Randomly generates a deterministic graph defined by m partial functions over n states that satisfies each each predicate in props.

is_irreducible(G)

Returns True iff G is irreducible

get_follower_equivalences(G)

Gets the follower-equivalences of G.

is_follower_separated(G)

Returns True iff G is follower-separated.

reduce(G)

Compute the reduction of G.

find_synchronizing_word(G)

Search for a synchronizing word in G.

find_separating_word(G, H)

Search for a separting word between G and H.

is_subshift(G, H)

Returns True iff the shift presented by G is contained in the shift presented by H.

is_synchronizing(G)

Returns True iff G is synchronizing.

are_shifts_equal_sync(G, H)

Returns True iff the shift presnted by G is equivalent to the shift presented by H.