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

• labeled - is_labeled()

• deterministic - is_deterministic()

• essential - is_essential()

• irreducible - is_irreducible()

• follower-separated - is_follower_separated()

• synchronizing - is_synchronizing()

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.
is_sft(G[, return_step])	Returns True iff the shift presents by G is a shift of finite type (SFT).