automaton.has_bounded_lag

Check if the transducer has bounded lag, i.e. that the difference of length between the input and output words is bounded, for every word accepted.

It is a pre-condition for transducer synchronization.

Preconditions:

  • The automaton has at least 2 tapes

Examples

In [1]:
import vcsn
ctx = vcsn.context("lat<lan_char(ab), lan_char(xy)>, b")
ctx
Out[1]:
$(\{a, b\})^? \times (\{x, y\})^?\to\mathbb{B}$
In [2]:
a = ctx.expression(r"'a,x''b,y'*'a,\e'").automaton()
a
Out[2]:
%3 I0 0 0 I0->0 F2 1 1 0->1 a|x 1->1 b|y 2 2 1->2 a|ε 2->F2

This automaton has a bounded lag: there is at most a difference of 1 between the length of the input and the length of the output (e.g., $abba \rightarrow xyy$).

In [3]:
a.has_bounded_lag()
Out[3]:
True
In [4]:
b = ctx.expression(r"(\e|x)(a|\e)*(b|y)").automaton()
b
Out[4]:
%3 I0 0 0 I0->0 F2 1 1 0->1 ε|x 1->1 a|ε 2 2 1->2 b|y 2->F2

This transducer, however, doesn't have a bounded lag: there can be an arbitrary large difference between the input and output. For example, $ab \rightarrow xy$, but $aaaaaaaaab \rightarrow xy$.

In [5]:
b.has_bounded_lag()
Out[5]:
False
In [6]:
ctx_3 = vcsn.context("lat<lan_char(ab), lan_char(jk), lan_char(xy)>, b")
c = ctx_3.expression(r"(a|j|x)(b|k|\e)*").automaton()
c
Out[6]:
%3 I0 0 0 I0->0 F1 1 1 0->1 a|j|x 1->F1 1->1 b|k|ε

In the case of more than 2 tapes, has_bounded_lag checks that every tape has a bounded lag compared to the first one (incidentally, if that is the case, it will insure that every tapes has a bounded lag in respect to every other). This transducer has a bounded lag if you only consider the first 2 tapes, but the third tape doesn't.

In [7]:
c.has_bounded_lag()
Out[7]:
False