<html><head><title>[automgrp] 4 Noninitial automata</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP003.htm">Previous</a>] [<a href ="CHAP005.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>4 Noninitial automata</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP004.htm#SECT001">Definition</a>
<li> <A HREF="CHAP004.htm#SECT002">Tools</a>
</ol><p>
<p>
<p>
<h2><a name="SECT001">4.1 Definition</a></h2>
<p><p>
<a name = "SSEC001.1"></a>
<li><code>MealyAutomaton( </code><var>table</var><code>[, </code><var>names</var><code>[, </code><var>alphabet</var><code>]] ) O</code>
<li><code>MealyAutomaton( </code><var>string</var><code> ) O</code>
<li><code>MealyAutomaton( </code><var>autom</var><code> ) O</code>
<p>
Creates the Mealy automaton (see <a href="CHAP001.htm#SECT001">Short math background</a>) defined by the argument <var>table</var>, <var>string</var>
or <var>autom</var>. Format of the argument <var>table</var> is
the following: it is a list of states, where each state is a list of
positive integers which represent transition function at the given state and a
permutation or transformation which represent the output function at this
state. Format of the string <var>string</var> is the same as in <code>AutomatonGroup</code> (see <a href="CHAP002.htm#SSEC001.1">AutomatonGroup</a>).
The third form of this operation takes a tree homomorphism <var>autom</var> as its argument.
It returns noninitial automaton constructed from the sections of <var>autom</var>, whose first state
corresponds to <var>autom</var> itself.
<p>
<pre>
gap> A := MealyAutomaton([[1,2,(1,2)],[3,1,()],[3,3,(1,2)]], ["a","b","c"]);
<automaton>
gap> Print(A, "\n");
a = (a, b)(1,2), b = (c, a), c = (c, c)(1,2)
gap> B:=MealyAutomaton([[1,2,Transformation([1,1])],[3,1,()],[3,3,(1,2)]],["a","b","c"]);
<automaton>
gap> Print(B, "\n");
a = (a, b)[ 1, 1 ], b = (c, a), c = (c, c)[ 2, 1 ]
gap> D := MealyAutomaton("a=(a,b)(1,2), b=(b,a)");
<automaton>
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> M := MealyAutomaton(u*v*u^-3);
<automaton>
gap> Print(M);
a1 = (a2, a5), a2 = (a3, a4), a3 = (a4, a2)(1,2), a4 = (a4, a4), a5 = (a6, a3)
(1,2), a6 = (a7, a4), a7 = (a6, a4)(1,2)
</pre>
<p>
<a name = "SSEC001.2"></a>
<li><code>IsMealyAutomaton( </code><var>A</var><code> ) C</code>
<p>
A category of non-initial finite Mealy automata with the same input and
output alphabet.
<p>
<a name = "SSEC001.3"></a>
<li><code>NumberOfStates( </code><var>A</var><code> ) A</code>
<p>
Returns the number of states of the automaton <var>A</var>.
<p>
<a name = "SSEC001.4"></a>
<li><code>SizeOfAlphabet( </code><var>A</var><code> ) A</code>
<p>
Returns the number of letters in the alphabet the automaton <var>A</var> acts on.
<p>
<a name = "SSEC001.5"></a>
<li><code>AutomatonList( </code><var>A</var><code> ) A</code>
<p>
Returns the list of <var>A</var> acceptible by <code>MealyAutomaton</code> (see <a href="CHAP004.htm#SSEC001.1">MealyAutomaton</a>)
<p>
<p>
<h2><a name="SECT002">4.2 Tools</a></h2>
<p><p>
<a name = "SSEC002.1"></a>
<li><code>IsTrivial( </code><var>A</var><code> ) O</code>
<p>
Computes whether the automaton <var>A</var> is equivalent to the trivial automaton.
<pre>
gap> A := MealyAutomaton("a=(c,c), b=(a,b), c=(b,a)");
<automaton>
gap> IsTrivial(A);
true
</pre>
<p>
<a name = "SSEC002.2"></a>
<li><code>IsInvertible( </code><var>A</var><code> ) P</code>
<p>
Is <code>true</code> if <var>A</var> is invertible and <code>false</code> otherwise.
<p>
<a name = "SSEC002.3"></a>
<li><code>MinimizationOfAutomaton( </code><var>A</var><code> ) F</code>
<p>
Returns the automaton obtained from automaton <var>A</var> by minimization.
<pre>
gap> B := MealyAutomaton("a=(1,a)(1,2), b=(1,a)(1,2), c=(a,b), d=(a,b)");
<automaton>
gap> C := MinimizationOfAutomaton(B);
<automaton>
gap> Print(C);
a = (1, a)(1,2), c = (a, a), 1 = (1, 1)
</pre>
<p>
<a name = "SSEC002.4"></a>
<li><code>MinimizationOfAutomatonTrack( </code><var>A</var><code> ) F</code>
<p>
Returns the list <code>[A_new, new_via_old, old_via_new]</code>, where <code>A_new</code> is an
automaton obtained from automaton <var>A</var> by minimization,
<code>new_via_old</code> describes how new states are expressed in terms of the old ones, and
<code>old_via_new</code> describes how old states are expressed in terms of the new ones.
<pre>
gap> B := MealyAutomaton("a=(1,a)(1,2), b=(1,a)(1,2), c=(a,b), d=(a,b)");
<automaton>
gap> B_min := MinimizationOfAutomatonTrack(B);
[ <automaton>, [ 1, 3, 5 ], [ 1, 1, 2, 2, 3 ] ]
gap> Print(B_min[1]);
a = (1, a)(1,2), c = (a, a), 1 = (1, 1)
</pre>
<p>
<a name = "SSEC002.5"></a>
<li><code>IsOfPolynomialGrowth( </code><var>A</var><code> ) P</code>
<p>
Determines whether the automaton <var>A</var> has polynomial growth in terms of Sidki <a href="biblio.htm#Sid00"><cite>Sid00</cite></a>.
<p>
See also <code>IsBounded</code> (<a href="CHAP004.htm#SSEC002.6">IsBounded</a>) and
<code>PolynomialDegreeOfGrowth</code> (<a href="CHAP004.htm#SSEC002.7">PolynomialDegreeOfGrowth</a>).
<pre>
gap> B := MealyAutomaton("a=(b,1)(1,2), b=(a,1)");
<automaton>
gap> IsOfPolynomialGrowth(B);
true
gap> D := MealyAutomaton("a=(a,b)(1,2), b=(b,a)");
<automaton>
gap> IsOfPolynomialGrowth(D);
false
</pre>
<p>
<a name = "SSEC002.6"></a>
<li><code>IsBounded( </code><var>A</var><code> ) P</code>
<p>
Determines whether the automaton <var>A</var> is bounded in terms of Sidki <a href="biblio.htm#Sid00"><cite>Sid00</cite></a>.
<p>
See also <code>IsOfPolynomialGrowth</code> (<a href="CHAP004.htm#SSEC002.5">IsOfPolynomialGrowth</a>)
and <code>PolynomialDegreeOfGrowth</code> (<a href="CHAP004.htm#SSEC002.7">PolynomialDegreeOfGrowth</a>).
<pre>
gap> B := MealyAutomaton("a=(b,1)(1,2), b=(a,1)");
<automaton>
gap> IsBounded(B);
true
gap> C := MealyAutomaton("a=(a,b)(1,2), b=(b,c), c=(c,1)(1,2)");
<automaton>
gap> IsBounded(C);
false
</pre>
<p>
<a name = "SSEC002.7"></a>
<li><code>PolynomialDegreeOfGrowth( </code><var>A</var><code> ) A</code>
<p>
For an automaton <var>A</var> of polynomial growth in terms of Sidki <a href="biblio.htm#Sid00"><cite>Sid00</cite></a>
determines its degree of
polynomial growth. This degree is 0 if and only if automaton is bounded.
If the growth of automaton is exponential returns <code>fail</code>.
<p>
See also <code>IsOfPolynomialGrowth</code> (<a href="CHAP004.htm#SSEC002.5">IsOfPolynomialGrowth</a>)
and <code>IsBounded</code> (<a href="CHAP004.htm#SSEC002.6">IsBounded</a>).
<pre>
gap> B := MealyAutomaton("a=(b,1)(1,2), b=(a,1)");
<automaton>
gap> PolynomialDegreeOfGrowth(B);
0
gap> C := MealyAutomaton("a=(a,b)(1,2), b=(b,c), c=(c,1)(1,2)");
<automaton>
gap> PolynomialDegreeOfGrowth(C);
2
</pre>
<p>
<a name = "SSEC002.8"></a>
<li><code>DualAutomaton( </code><var>A</var><code> ) O</code>
<p>
Returns the automaton dual of <var>A</var>.
<pre>
gap> A := MealyAutomaton("a=(b,a)(1,2), b=(b,a)");
<automaton>
gap> D := DualAutomaton(A);
<automaton>
gap> Print(D);
d1 = (d2, d1)[ 2, 2 ], d2 = (d1, d2)[ 1, 1 ]
</pre>
<p>
<a name = "SSEC002.9"></a>
<li><code>InverseAutomaton( </code><var>A</var><code> ) O</code>
<p>
Returns the automaton inverse to <var>A</var> if <var>A</var> is invertible.
<pre>
gap> A := MealyAutomaton("a=(b,a)(1,2), b=(b,a)");
<automaton>
gap> B := InverseAutomaton(A);
<automaton>
gap> Print(B);
a1 = (a1, a2)(1,2), a2 = (a2, a1)
</pre>
<p>
<a name = "SSEC002.10"></a>
<li><code>IsBireversible( </code><var>A</var><code> ) O</code>
<p>
Computes whether or not the automaton <var>A</var> is bireversible, i.e. <var>A</var>, the dual of <var>A</var> and
the dual of the inverse of <var>A</var> are invertible. The example below shows that the
Bellaterra automaton is bireversible.
<pre>
gap> Bellaterra := MealyAutomaton("a=(c,c)(1,2), b=(a,b), c=(b,a)");
<automaton>
gap> IsBireversible(Bellaterra);
true
</pre>
<p>
<a name = "SSEC002.11"></a>
<li><code>DisjointUnion( </code><var>A</var><code>, </code><var>B</var><code> ) O</code>
<p>
Constructs the disjoint union of automata <var>A</var> and <var>B</var>
<pre>
gap> A := MealyAutomaton("a=(a,b)(1,2), b=(a,b)");
<automaton>
gap> B := MealyAutomaton("c=(d,c), d=(c,e)(1,2), e=(e,d)");
<automaton>
gap> Print(DisjointUnion(A, B));
a1 = (a1, a2)(1,2), a2 = (a1, a2), a3 = (a4, a3), a4 = (a3, a5)
(1,2), a5 = (a5, a4)
</pre>
<p>
<a name = "SSEC002.12"></a>
<li><code></code><var>A</var><code> * </code><var>B</var><code></code>
<p>
Constructs the product of 2 noninitial automata <var>A</var> and <var>B</var>.
<pre>
gap> A := MealyAutomaton("a=(a,b)(1,2), b=(a,b)");
<automaton>
gap> B := MealyAutomaton("c=(d,c), d=(c,e)(1,2), e=(e,d)");
<automaton>
gap> Print(A*B);
a1 = (a1, a5)(1,2), a2 = (a3, a4), a3 = (a2, a6)
(1,2), a4 = (a2, a4), a5 = (a1, a6)(1,2), a6 = (a3, a5)
</pre>
<p>
<a name = "SSEC002.13"></a>
<li><code>SubautomatonWithStates( </code><var>A</var><code>, </code><var>states</var><code> ) O</code>
<p>
Returns the minimal subautomaton of the automaton <var>A</var> containing states <var>states</var>.
<pre>
gap> A := MealyAutomaton("a=(e,d)(1,2),b=(c,c),c=(b,c)(1,2),d=(a,e)(1,2),e=(e,d)");
<automaton>
gap> Print(SubautomatonWithStates(A, [1, 4]));
a = (e, d)(1,2), d = (a, e)(1,2), e = (e, d)
</pre>
<p>
<a name = "SSEC002.14"></a>
<li><code>AutomatonNucleus( </code><var>A</var><code> ) O</code>
<p>
Returns the nucleus of the automaton <var>A</var>, i.e. the minimal subautomaton
containing all cycles in <var>A</var>.
<pre>
gap> A := MealyAutomaton("a=(b,c)(1,2),b=(d,d),c=(d,b)(1,2),d=(d,b)(1,2),e=(a,d)");
<automaton>
gap> Print(AutomatonNucleus(A));
b = (d, d), d = (d, b)(1,2)
</pre>
<p>
<a name = "SSEC002.15"></a>
<li><code>AreEquivalentAutomata( </code><var>A</var><code>, </code><var>B</var><code> ) O</code>
<p>
Returns <code>true</code> if for every state <code>s</code> of the automaton <var>A</var> there is a state of the automaton <var>B</var>
equivalent to <code>s</code> and vice versa.
<pre>
gap> A := MealyAutomaton("a=(b,a)(1,2), b=(a,c), c=(b,c)(1,2)");
<automaton>
gap> B := MealyAutomaton("b=(a,c), c=(b,c)(1,2), a=(b,a)(1,2), d=(b,c)(1,2)");
<automaton>
gap> AreEquivalentAutomata(A, B);
true
</pre>
<p>
<p>
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP003.htm">Previous</a>] [<a href ="CHAP005.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<address>automgrp manual<br>September 2008
</address></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
579
