This page is a complement to the paper Derived-Term Automata of Multitape Rational Expressions presented at CIAA 2016. This page exists in several forms:
More information is available here:
You may change the cells, and run then. To run a cell in a notebook, hit "Control-Enter" (in which case the focus stays on the same cell) or "Shift-Enter" (focus goes to the next cell). Beware that depending on the requested operations, Vcsn may generate and compile code, which may be a really slow process on small machines (about a minute): be patient! However, the code is compiled only once: successive uses will be way faster.
To run all the cells anew, select "Restart & Run All" in the "Kernel" menu above.
import vcsn
First we introduce the "context" we are interested in: labels are letter-or-empty-word, two tapes, values are rational numbers.
ctx = vcsn.context('lat<lan(abcde), lan(xy)>, q')
ctx
The expression $\mathsf{E}_1$ is:
e1 = ctx.expression('⟨5⟩ε|ε + ⟨4⟩ade*|x + ⟨3⟩bde*|x + ⟨2⟩ace*|xy + ⟨6⟩bce*|xy')
e1
Its expansion is (contrary to the paper, the empty expression is denoted $\varepsilon$ instead of $\mathsf{1}$):
e1.expansion()
The derived-term automaton of $\mathsf{E}_1$, $\mathcal{A}_{\mathsf{E}_1}$, is:
a1 = e1.derived_term()
a1
The 10 shortest "multitape words" it accepts are:
a1.shortest(10)
We introduce a three-tape context. The graphical rendering is less satisfying.
ctx3 = vcsn.context('lat<lan, lan, lan>, q')
a3 = ctx3.expression('a*|b*|c*').derived_term()
a3
Currently Vcsn is not able to extract nice rational expressions from such an automaton: it will always produce a "simple-tape expression over multitape generators":
a3.expression()
Instead of displaying the automaton, we may list its states, for instance in the case of a five-tape expression.
import re
def states(a):
'''The states of an automaton, sorted.'''
res = re.findall(r'label = "(.*?)", shape', a.dot(), re.M)
res.sort()
return res
ctx5 = vcsn.context('lat<lan(a), lan(b), lan(c), lan(d), lan(e)>, q')
e5 = ctx5.expression('a*|b*|c*|d*|e*')
e5
e5.expansion()
a5 = e5.derived_term()
states(a5)
e2 = ctx.expression('(a{+}|x + b{+}|y)*')
e2
e2.expansion()
a2 = e2.derived_term()
a2
Again, the extracted expression is less readable.
a2.expression()
The previous examples often look like sed-like substitutions, in the sense that the first tape was often a composite expression, but the second tape a simple label. There is no such limitation.
e = ctx.expression('(<2>[ab])* | (<3>[xy])*')
e
a = e.derived_term()
a
print('{:l}'.format(a.shortest(20)))