`automaton``.has_negative_cycle`

Whether an automaton has negative cycles (i.e. contains at least one negative path between a state and itself).

Uses the Bellman-Ford algorithm.



In [1]:

    
import vcsn
def aut(e, ctx_exp):
    ctx = vcsn.context(ctx_exp)
    return ctx.expression(e).standard()

Examples

Negative loops can appear when the weight of the path from a state to itself is negative.



In [2]:

    
aut('\e', 'lal_char, zmin').has_negative_cycle()









    Out[2]:





False



In [3]:

    
aut('(<-1>a)*', 'lal_char, zmin').has_negative_cycle()









    Out[3]:





True



In [4]:

    
aut('a*', 'lal_char, zmin').has_negative_cycle()









    Out[4]:





False

Negative loops can appear when the weight of the path from a state to itself is between 0 and 1.



In [5]:

    
aut('(<0.5>a)*', 'lal_char, r').has_negative_cycle()









    Out[5]:





True



In [6]:

    
aut('(<1.5>a)*', 'lal_char, r').has_negative_cycle()









    Out[6]:





False