Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 45894
Kernel: Python 3

Multitape Rational Expressions

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

Example E1\mathsf{E}_1: A Simple Multitape Expression

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

({a,b,c,d,e})?×({x,y})?→Q(\{a, b, c, d, e\})^? \times (\{x, y\})^?\to\mathbb{Q}

The expression E1\mathsf{E}_1 is:

e1 = ctx.expression('⟨5⟩ε|ε + ⟨4⟩ade*|x + ⟨3⟩bde*|x + ⟨2⟩ace*|xy + ⟨6⟩bce*|xy')
e1

⟨5⟩ ε|ε+⟨4⟩ (a d e∗)|x+⟨3⟩ (b d e∗)|x+⟨2⟩ (a c e∗)|x y+⟨6⟩ (b c e∗)|x y \left. \left\langle 5 \right\rangle \,\varepsilon \middle| \varepsilon \right. + \left. \left\langle 4 \right\rangle \,\left(a \, d \, {e}^{*}\right) \middle| x \right. + \left. \left\langle 3 \right\rangle \,\left(b \, d \, {e}^{*}\right) \middle| x \right. + \left. \left\langle 2 \right\rangle \,\left(a \, c \, {e}^{*}\right) \middle| x \, y \right. + \left. \left\langle 6 \right\rangle \,\left(b \, c \, {e}^{*}\right) \middle| x \, y \right.

Its expansion is (contrary to the paper, the empty expression is denoted ε\varepsilon instead of 1\mathsf{1}):

e1.expansion()

⟨5⟩⊕a∣x⊙[⟨2⟩c e∗|y⊕⟨4⟩d e∗|ε]⊕b∣x⊙[⟨6⟩c e∗|y⊕⟨3⟩d e∗|ε]\left\langle 5\right\rangle \oplus a|x \odot \left[\left\langle 2\right\rangle \left. c \, {e}^{*} \middle| y \right. \oplus \left\langle 4\right\rangle \left. d \, {e}^{*} \middle| \varepsilon \right. \right] \oplus b|x \odot \left[\left\langle 6\right\rangle \left. c \, {e}^{*} \middle| y \right. \oplus \left\langle 3\right\rangle \left. d \, {e}^{*} \middle| \varepsilon \right. \right]

The derived-term automaton of E1\mathsf{E}_1, AE1\mathcal{A}_{\mathsf{E}_1}, is:

a1 = e1.derived_term()
a1
Image in a Jupyter notebook

The 10 shortest "multitape words" it accepts are:

a1.shortest(10)

⟨5⟩ε∣ε⊕⟨2⟩ac∣xy⊕⟨4⟩ad∣x⊕⟨6⟩bc∣xy⊕⟨3⟩bd∣x⊕⟨2⟩ace∣xy⊕⟨4⟩ade∣x⊕⟨6⟩bce∣xy⊕⟨3⟩bde∣x⊕⟨2⟩acee∣xy\left\langle 5\right\rangle \varepsilon|\varepsilon \oplus \left\langle 2\right\rangle \mathit{ac}|\mathit{xy} \oplus \left\langle 4\right\rangle \mathit{ad}|\mathit{x} \oplus \left\langle 6\right\rangle \mathit{bc}|\mathit{xy} \oplus \left\langle 3\right\rangle \mathit{bd}|\mathit{x} \oplus \left\langle 2\right\rangle \mathit{ace}|\mathit{xy} \oplus \left\langle 4\right\rangle \mathit{ade}|\mathit{x} \oplus \left\langle 6\right\rangle \mathit{bce}|\mathit{xy} \oplus \left\langle 3\right\rangle \mathit{bde}|\mathit{x} \oplus \left\langle 2\right\rangle \mathit{acee}|\mathit{xy}

Example A3\mathcal{A}_3: An Exponential Number of States

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
Image in a Jupyter notebook

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()

(a∣b∣c)∗ (ε+(ε∣ε∣c) (ε∣ε∣c)∗+(ε∣b∣ε) (ε∣b∣ε)∗+(a∣ε∣ε) (a∣ε∣ε)∗+(ε∣b∣c) (ε∣b∣c)∗ (ε+(ε∣ε∣c) (ε∣ε∣c)∗+(ε∣b∣ε) (ε∣b∣ε)∗)+(a∣ε∣c) (a∣ε∣c)∗ (ε+(ε∣ε∣c) (ε∣ε∣c)∗+(a∣ε∣ε) (a∣ε∣ε)∗)+(a∣b∣ε) (a∣b∣ε)∗ (ε+(ε∣b∣ε) (ε∣b∣ε)∗+(a∣ε∣ε) (a∣ε∣ε)∗))\left(a|b|c\right)^{*} \, \left(\varepsilon + \left(\varepsilon|\varepsilon|c\right) \, \left(\varepsilon|\varepsilon|c\right)^{*} + \left(\varepsilon|b|\varepsilon\right) \, \left(\varepsilon|b|\varepsilon\right)^{*} + \left(a|\varepsilon|\varepsilon\right) \, \left(a|\varepsilon|\varepsilon\right)^{*} + \left(\varepsilon|b|c\right) \, \left(\varepsilon|b|c\right)^{*} \, \left(\varepsilon + \left(\varepsilon|\varepsilon|c\right) \, \left(\varepsilon|\varepsilon|c\right)^{*} + \left(\varepsilon|b|\varepsilon\right) \, \left(\varepsilon|b|\varepsilon\right)^{*}\right) + \left(a|\varepsilon|c\right) \, \left(a|\varepsilon|c\right)^{*} \, \left(\varepsilon + \left(\varepsilon|\varepsilon|c\right) \, \left(\varepsilon|\varepsilon|c\right)^{*} + \left(a|\varepsilon|\varepsilon\right) \, \left(a|\varepsilon|\varepsilon\right)^{*}\right) + \left(a|b|\varepsilon\right) \, \left(a|b|\varepsilon\right)^{*} \, \left(\varepsilon + \left(\varepsilon|b|\varepsilon\right) \, \left(\varepsilon|b|\varepsilon\right)^{*} + \left(a|\varepsilon|\varepsilon\right) \, \left(a|\varepsilon|\varepsilon\right)^{*}\right)\right)

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

a∗|b∗|c∗|d∗|e∗ \left. {a}^{*} \middle| {b}^{*} \middle| {c}^{*} \middle| {d}^{*} \middle| {e}^{*} \right. 

e5.expansion()

⟨1⟩⊕ε∣ε∣ε∣ε∣e⊙[ε|ε|ε|ε|e∗]⊕ε∣ε∣ε∣d∣ε⊙[ε|ε|ε|d∗|ε]⊕ε∣ε∣ε∣d∣e⊙[ε|ε|ε|d∗|e∗]⊕ε∣ε∣c∣ε∣ε⊙[ε|ε|c∗|ε|ε]⊕ε∣ε∣c∣ε∣e⊙[ε|ε|c∗|ε|e∗]⊕ε∣ε∣c∣d∣ε⊙[ε|ε|c∗|d∗|ε]⊕ε∣ε∣c∣d∣e⊙[ε|ε|c∗|d∗|e∗]⊕ε∣b∣ε∣ε∣ε⊙[ε|b∗|ε|ε|ε]⊕ε∣b∣ε∣ε∣e⊙[ε|b∗|ε|ε|e∗]⊕ε∣b∣ε∣d∣ε⊙[ε|b∗|ε|d∗|ε]⊕ε∣b∣ε∣d∣e⊙[ε|b∗|ε|d∗|e∗]⊕ε∣b∣c∣ε∣ε⊙[ε|b∗|c∗|ε|ε]⊕ε∣b∣c∣ε∣e⊙[ε|b∗|c∗|ε|e∗]⊕ε∣b∣c∣d∣ε⊙[ε|b∗|c∗|d∗|ε]⊕ε∣b∣c∣d∣e⊙[ε|b∗|c∗|d∗|e∗]⊕a∣ε∣ε∣ε∣ε⊙[a∗|ε|ε|ε|ε]⊕a∣ε∣ε∣ε∣e⊙[a∗|ε|ε|ε|e∗]⊕a∣ε∣ε∣d∣ε⊙[a∗|ε|ε|d∗|ε]⊕a∣ε∣ε∣d∣e⊙[a∗|ε|ε|d∗|e∗]⊕a∣ε∣c∣ε∣ε⊙[a∗|ε|c∗|ε|ε]⊕a∣ε∣c∣ε∣e⊙[a∗|ε|c∗|ε|e∗]⊕a∣ε∣c∣d∣ε⊙[a∗|ε|c∗|d∗|ε]⊕a∣ε∣c∣d∣e⊙[a∗|ε|c∗|d∗|e∗]⊕a∣b∣ε∣ε∣ε⊙[a∗|b∗|ε|ε|ε]⊕a∣b∣ε∣ε∣e⊙[a∗|b∗|ε|ε|e∗]⊕a∣b∣ε∣d∣ε⊙[a∗|b∗|ε|d∗|ε]⊕a∣b∣ε∣d∣e⊙[a∗|b∗|ε|d∗|e∗]⊕a∣b∣c∣ε∣ε⊙[a∗|b∗|c∗|ε|ε]⊕a∣b∣c∣ε∣e⊙[a∗|b∗|c∗|ε|e∗]⊕a∣b∣c∣d∣ε⊙[a∗|b∗|c∗|d∗|ε]⊕a∣b∣c∣d∣e⊙[a∗|b∗|c∗|d∗|e∗]\left\langle 1\right\rangle \oplus \varepsilon|\varepsilon|\varepsilon|\varepsilon|e \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| \varepsilon \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus \varepsilon|\varepsilon|\varepsilon|d|\varepsilon \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| \varepsilon \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus \varepsilon|\varepsilon|\varepsilon|d|e \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| \varepsilon \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus \varepsilon|\varepsilon|c|\varepsilon|\varepsilon \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| {c}^{*} \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus \varepsilon|\varepsilon|c|\varepsilon|e \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| {c}^{*} \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus \varepsilon|\varepsilon|c|d|\varepsilon \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| {c}^{*} \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus \varepsilon|\varepsilon|c|d|e \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| {c}^{*} \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus \varepsilon|b|\varepsilon|\varepsilon|\varepsilon \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| \varepsilon \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus \varepsilon|b|\varepsilon|\varepsilon|e \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| \varepsilon \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus \varepsilon|b|\varepsilon|d|\varepsilon \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| \varepsilon \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus \varepsilon|b|\varepsilon|d|e \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| \varepsilon \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus \varepsilon|b|c|\varepsilon|\varepsilon \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| {c}^{*} \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus \varepsilon|b|c|\varepsilon|e \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| {c}^{*} \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus \varepsilon|b|c|d|\varepsilon \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| {c}^{*} \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus \varepsilon|b|c|d|e \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| {c}^{*} \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus a|\varepsilon|\varepsilon|\varepsilon|\varepsilon \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| \varepsilon \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus a|\varepsilon|\varepsilon|\varepsilon|e \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| \varepsilon \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus a|\varepsilon|\varepsilon|d|\varepsilon \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| \varepsilon \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus a|\varepsilon|\varepsilon|d|e \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| \varepsilon \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus a|\varepsilon|c|\varepsilon|\varepsilon \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| {c}^{*} \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus a|\varepsilon|c|\varepsilon|e \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| {c}^{*} \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus a|\varepsilon|c|d|\varepsilon \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| {c}^{*} \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus a|\varepsilon|c|d|e \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| {c}^{*} \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus a|b|\varepsilon|\varepsilon|\varepsilon \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| \varepsilon \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus a|b|\varepsilon|\varepsilon|e \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| \varepsilon \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus a|b|\varepsilon|d|\varepsilon \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| \varepsilon \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus a|b|\varepsilon|d|e \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| \varepsilon \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus a|b|c|\varepsilon|\varepsilon \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| {c}^{*} \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus a|b|c|\varepsilon|e \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| {c}^{*} \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus a|b|c|d|\varepsilon \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| {c}^{*} \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus a|b|c|d|e \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| {c}^{*} \middle| {d}^{*} \middle| {e}^{*} \right. \right]

a5 = e5.derived_term()
states(a5)
['a*|b*|c*|d*|e*', 'a*|b*|c*|d*|ε', 'a*|b*|c*|ε|e*', 'a*|b*|c*|ε|ε', 'a*|b*|ε|d*|e*', 'a*|b*|ε|d*|ε', 'a*|b*|ε|ε|e*', 'a*|b*|ε|ε|ε', 'a*|ε|c*|d*|e*', 'a*|ε|c*|d*|ε', 'a*|ε|c*|ε|e*', 'a*|ε|c*|ε|ε', 'a*|ε|ε|d*|e*', 'a*|ε|ε|d*|ε', 'a*|ε|ε|ε|e*', 'a*|ε|ε|ε|ε', 'ε|b*|c*|d*|e*', 'ε|b*|c*|d*|ε', 'ε|b*|c*|ε|e*', 'ε|b*|c*|ε|ε', 'ε|b*|ε|d*|e*', 'ε|b*|ε|d*|ε', 'ε|b*|ε|ε|e*', 'ε|b*|ε|ε|ε', 'ε|ε|c*|d*|e*', 'ε|ε|c*|d*|ε', 'ε|ε|c*|ε|e*', 'ε|ε|c*|ε|ε', 'ε|ε|ε|d*|e*', 'ε|ε|ε|d*|ε', 'ε|ε|ε|ε|e*']

Example E2\mathsf{E}_2: A Sed-like Substitution

e2 = ctx.expression('(a{+}|x + b{+}|y)*')
e2

(a a∗|x+b b∗|y)∗\left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}

e2.expansion()

⟨1⟩⊕a∣x⊙[(a∗|ε) (a a∗|x+b b∗|y)∗]⊕b∣y⊙[(b∗|ε) (a a∗|x+b b∗|y)∗]\left\langle 1\right\rangle \oplus a|x \odot \left[\left( \left. {a}^{*} \middle| \varepsilon \right. \right) \, \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}\right] \oplus b|y \odot \left[\left( \left. {b}^{*} \middle| \varepsilon \right. \right) \, \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}\right]

a2 = e2.derived_term()
a2
Image in a Jupyter notebook

Again, the extracted expression is less readable.

a2.expression()

ε+(a∣x) (a∣ε+a∣x)∗+(b∣y+(a∣x) (a∣ε+a∣x)∗ (b∣y)) (b∣ε+b∣y+(a∣x) (a∣ε+a∣x)∗ (b∣y))∗ (ε+(a∣x) (a∣ε+a∣x)∗)\varepsilon + \left(a|x\right) \, \left(a|\varepsilon + a|x\right)^{*} + \left(b|y + \left(a|x\right) \, \left(a|\varepsilon + a|x\right)^{*} \, \left(b|y\right)\right) \, \left(b|\varepsilon + b|y + \left(a|x\right) \, \left(a|\varepsilon + a|x\right)^{*} \, \left(b|y\right)\right)^{*} \, \left(\varepsilon + \left(a|x\right) \, \left(a|\varepsilon + a|x\right)^{*}\right)

A More Complex 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

(⟨2⟩ (a+b))∗|(⟨3⟩ (x+y))∗ \left. \left( \left\langle 2 \right\rangle \,\left(a + b\right)\right)^{*} \middle| \left( \left\langle 3 \right\rangle \,\left(x + y\right)\right)^{*} \right. 

a = e.derived_term()
a
Image in a Jupyter notebook
print('{:l}'.format(a.shortest(20)))
\e|\e <3>\e|x <3>\e|y <2>a|\e <6>a|x <6>a|y <2>b|\e <6>b|x <6>b|y <9>\e|xx <9>\e|xy <9>\e|yx <9>\e|yy <18>a|xx <18>a|xy <18>a|yx <18>a|yy <18>b|xx <18>b|xy <18>b|yx