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()
followerseparated 
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.

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

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

Returns an 
Returns True iff G is deterministic. 

Returns True iff G is fully deterministic. 

Constructs the subset presentation of G. 


Computes the transition action of w in G on q. 

Computes the transition action of w in G on each element of the iterable it, returning an 

Returns True iff q is stranded in G. 

Returns True iff G is essential. 
Modifies G by removing vertices in G that do not lie on biinfinite paths. 


Returns a deterministic graph built from given partial functions. 
Randomly generates a deterministic graph defined by m partial functions over n states. 

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

Returns True iff G is irreducible 

Gets the followerequivalences of G. 

Returns True iff G is followerseparated. 


Compute the reduction of G. 
Search for a synchronizing word in G. 


Search for a separting word between G and H. 

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


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