automaton.has_lightening_cycle

Whether an automaton has lightening cycles (i.e. contains at least one cycle that would decrease the weight of a path).

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

In tropical weightsets

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_lightening_cycle()
Out[2]:
False
In [3]:
aut('(<-1>a)*', 'lal_char, zmin').has_lightening_cycle()
Out[3]:
True
In [4]:
aut('a*', 'lal_char, zmin').has_lightening_cycle()
Out[4]:
False

In regular weightsets

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_lightening_cycle()
Out[5]:
True
In [6]:
aut('(<1.5>a)*', 'lal_char, r').has_lightening_cycle()
Out[6]:
False