automaton.has_lightening_cycle.ipynb

Kernel: Python 3

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.

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.

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

False

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

True

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

False

In regular weightsets

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

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

True

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

False