[MathJax off]
2 Creating Predicata
2.1 Predicaton – an extended finite automaton
2.1-1 Predicaton
‣ Predicaton ( Automaton, VariablePositionList ) | ( function ) |
A Predicaton
represents a first-order formulas, with \(n\) free variables, containing the nullary operations \(0\) and \(1\) and the binary operation \(+\). It consists of an Automaton
and a VariablePositionList
.
The first parameter is an Automaton from the package Automata, which is created as follows: Automaton(Type, Size, Alphabet, TransitionTable, Initial, Final)
. In order to create a Predicaton
the Type must either be "det"
or "nondet"
. The Size is a positive integer giving the number of states. The Alphabet must be a list of length \(2^n\), i.e. the list of all n-tuples \(\{0,1\}^n\). The TransitionTable gives the transition matrix, where the entry at \((i,j)\) denotes the state reached with the \(i\)-th letter (\(i\)-th row) and the \(j\)-th state (\(j\)-th column). The Initial and Final are the initial and final state sets.
The second parameter VariablePositionList must be of length \(n\) and must contain \(n\) pairwise distinct positive integers. It internally represents the occurring variables in the first-order formula by assigning pairwise distinct natural numbers to each free variable. The VariablePositionList coincides with the letters, i.e. the \(i\)-th position in the \(n\)-tuples correspond to the variable position at the \(i\)-th position in the list.
A word over the alphabet \(\{0,1\}^n\) can be turned into \(n\) reversed binary representations of natural numbers by extracting the components of the letters. The \(i\)-th row of a word (choosing the \(i\)-th component of each letter) corresponds to the \(i\)-th entry in the VariablePositionList. The accepted words of the automaton represent those \(n\) natural numbers, such that upon interpretation the first-order formula is satisfied.
In the following example the Automaton A
represents the formula \(x+y=z\) with the following variables: the variable \(x\) is assigned to \(1\), the variable \(y\) is assigned to \(2 \) and the variable \(z\) is assigned to \(3\) The Predicaton P
is created with the deterministic finite automaton A
and the variable position list [ 1, 2, 3 ]
. This means the first entry in the letters corresponds to the variable with the assigned natural number 1, i.e. \(x\), the second entry to the number \(2\), i.e. the variable \(y\) and the third entry to the number \(3\), i.e. the variable \(z\).
Later also a mathematically more intuitive method is introduced, see Predicaton
(4.1-3) for creating a Predicaton
from a first-order formula.
gap> A:=Automaton("det", 3,
> [ [ 0, 0, 0 ], [ 1, 0, 0 ], [ 0, 1, 0 ], [ 1, 1, 0 ],
> [ 0, 0, 1 ], [ 1, 0, 1 ], [ 0, 1, 1 ], [ 1, 1, 1 ] ],
> [ [ 1, 3, 3 ], [ 3, 2, 3 ], [ 3, 2, 3 ], [ 2, 3, 3 ],
> [ 3, 1, 3 ], [ 1, 3, 3 ], [ 1, 3, 3 ], [ 3, 2, 3 ] ],
> [ 1 ], [ 1 ]);
< deterministic automaton on 8 letters with 3 states >
gap> P:=Predicaton( A, [ 1, 2, 3 ]);
< Predicaton: deterministic finite automaton on 8 letters with 3 states
and the variable position list [ 1, 2, 3 ]. >
2.1-2 BuildPredicaton
‣ BuildPredicaton ( Type, Size, Alphabet, TransitionTable, Initial, Final, VariablePositionList ) | ( function ) |
The function BuildPredicaton
allows the creation of a Predicaton
without specifying an Automaton
.
gap> P:=BuildPredicaton("det", 3, [ [ 0, 0, 0 ], [ 1, 0, 0 ], [ 0, 1, 0 ],
> [ 1, 1, 0 ], [ 0, 0, 1 ], [ 1, 0, 1 ], [ 0, 1, 1 ], [ 1, 1, 1 ] ],
> [ [ 1, 3, 3 ], [ 3, 2, 3 ], [ 3, 2, 3 ], [ 2, 3, 3 ], [ 3, 1, 3 ],
> [ 1, 3, 3 ], [ 1, 3, 3 ], [ 3, 2, 3 ] ], [ 1 ], [ 1 ], [ 1, 2, 3 ]);
< Predicaton: deterministic finite automaton on 8 letters with 3 states
and the variable position list [ 1, 2, 3 ]. >
gap> Display(P);
Predicaton: deterministic finite automaton on 8 letters with 3 states,
the variable position list [ 1, 2, 3 ] and the following transitions:
| 1 2 3
---------------------------
[ 0, 0, 0 ] | 1 3 3
[ 1, 0, 0 ] | 3 2 3
[ 0, 1, 0 ] | 3 2 3
[ 1, 1, 0 ] | 2 3 3
[ 0, 0, 1 ] | 3 1 3
[ 1, 0, 1 ] | 1 3 3
[ 0, 1, 1 ] | 1 3 3
[ 1, 1, 1 ] | 3 2 3
Initial states: [ 1 ]
Final states: [ 1 ]
2.1-3 IsPredicaton
‣ IsPredicaton ( P ) | ( function ) |
The function IsPredicaton
checks if P is a Predicaton
.
gap> P:=BuildPredicaton("det", 2, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 1, 2 ], [ 2, 2 ], [ 2, 2 ], [ 1, 2 ] ], [ 1 ], [ 1 ], [ 1, 2 ]);
< Predicaton: deterministic finite automaton on 4 letters with 2 states
and the variable position list [ 1, 2 ]. >
gap> IsPredicaton(P);
true
2.1-4 Display
The method Display
prints the transition table of the Predicaton
P. The left side are the letters of the alphabet, the top row are the states and the transition from the \(i\)-th letter (row) and \(j\)-th state (column) is the entry \((i,j)\).
gap> P:=Predicaton(Automaton("det", 3, [ [ 0, 0, 0 ], [ 1, 0, 0 ], [ 0, 1, 0 ],
> [ 1, 1, 0 ], [ 0, 0, 1 ], [ 1, 0, 1 ], [ 0, 1, 1 ], [ 1, 1, 1 ] ],
> [ [ 1, 3, 3 ], [ 3, 2, 3 ], [ 3, 2, 3 ], [ 2, 3, 3 ], [ 3, 1, 3 ],
> [ 1, 3, 3 ], [ 1, 3, 3 ], [ 3, 2, 3 ] ], [ 1 ], [ 1 ]), [ 1, 2, 3 ]);
< Predicaton: deterministic finite automaton on 8 letters with 3 states
and the variable position list [ 1, 2, 3 ]. >
gap> Display(P);
Predicaton: deterministic finite automaton on 8 letters with 3 states,
the variable position list [ 1, 2, 3 ] and the following transitions:
| 1 2 3
---------------------------
[ 0, 0, 0 ] | 1 3 3
[ 1, 0, 0 ] | 3 2 3
[ 0, 1, 0 ] | 3 2 3
[ 1, 1, 0 ] | 2 3 3
[ 0, 0, 1 ] | 3 1 3
[ 1, 0, 1 ] | 1 3 3
[ 0, 1, 1 ] | 1 3 3
[ 1, 1, 1 ] | 3 2 3
Initial states: [ 1 ]
Final states: [ 1 ]
2.1-5 View
The method View
applied on a Predicaton
P returns the object text.
gap> P:=Predicaton(Automaton("det", 3, [ [ 0 ], [ 1 ] ], [ [ 2, 2, 3 ],
> [ 3, 2, 2 ] ], [ 1 ], [ 3 ]), [ 1 ]);;
gap> View(P);
< Predicaton: deterministic finite automaton on 2 letters with 3 states
and the variable position list [ 1 ]. >
2.1-6 Print
The method Print
applied on a Predicaton
P prints the input as a string.
gap> P:=Predicaton(Automaton("det", 3, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 1, 3, 3 ], [ 2, 3, 3 ], [ 3, 1, 3 ], [ 3, 2, 3 ] ], [ 1 ], [ 1 ]),
> [ 1, 2 ]);;
gap> Print(P);
Predicaton(Automaton("det", 3, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ], [ [ \
1, 3, 3 ], [ 2, 3, 3 ], [ 3, 1, 3 ], [ 3, 2, 3 ] ], [ 1 ], [ 1 ]), [ 1, 2 ]);;
gap> String(P);
"Predicaton(Automaton(\"det\", 3, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ], [ [\
1, 3, 3 ], [ 2, 3, 3 ], [ 3, 1, 3 ], [ 3, 2, 3 ] ], [ 1 ], [ 1 ]), [ 1, 2 ]);;"
2.1-7 GetAlphabet
‣ GetAlphabet ( n ) | ( function ) |
The function GetAlphabet
returns the alphabet \(A^n\) for \(A:=\{0,1\}\).
gap> a1:=GetAlphabet(3);
[ [ 0, 0, 0 ], [ 1, 0, 0 ], [ 0, 1, 0 ], [ 1, 1, 0 ],
[ 0, 0, 1 ], [ 1, 0, 1 ], [ 0, 1, 1 ], [ 1, 1, 1 ] ]
gap> P1:=Predicaton(Automaton("det", 3, a1,
> [ [ 1, 3, 3 ], [ 3, 2, 3 ], [ 3, 2, 3 ], [ 2, 3, 3 ], [ 3, 1, 3 ],
> [ 1, 3, 3 ], [ 1, 3, 3 ], [ 3, 2, 3 ] ], [ 1 ], [ 1 ]), [ 1, 2, 3 ]);;
gap> Display(P1);
Predicaton: deterministic finite automaton on 8 letters with 3 states,
the variable position list [ 1, 2, 3 ] and the following transitions:
| 1 2 3
---------------------------
[ 0, 0, 0 ] | 1 3 3
[ 1, 0, 0 ] | 3 2 3
[ 0, 1, 0 ] | 3 2 3
[ 1, 1, 0 ] | 2 3 3
[ 0, 0, 1 ] | 3 1 3
[ 1, 0, 1 ] | 1 3 3
[ 0, 1, 1 ] | 1 3 3
[ 1, 1, 1 ] | 3 2 3
Initial states: [ 1 ]
Final states: [ 1 ]
gap> a2:=GetAlphabet(0);
[ [ ] ]
gap> P2:=Predicaton(Automaton("det", 1, a2, [ [ 1 ] ], [ 1 ], [ 1 ]), [ ]);;
gap> Display(P2);
Predicaton: deterministic finite automaton on 1 letter with 1 state,
the variable position list [ ] and the following transitions:
| 1
-------------
[ ] | 1
Initial states: [ 1 ]
Final states: [ 1 ]
2.2 Basic functions on Automata and Predicata
The package Automata allows lists of lists as input for the alphabet, but unfortunately is lacking in further support. The functions regarding the alphabet takes only ShallowCopy
whereas a list of lists StructuralCopy
is needed, as well as the method Display
for automata prints with some weird spacing. Therefore this package reintroduces the basic Automata functions with another name to ensure full control. Nevertheless all credit belongs to the creators of the package Automata.
Note that the Predicata
in the following examples corresponds to first-order formulas. The accepted natural numbers can be displayed with the functions from section 2.3.
Furthermore, note that the following functions can be either called with an Automaton
or a Predicaton
.
2.2-1 DisplayAut
‣ DisplayAut ( P ) | ( function ) |
The function DisplayAut
prints the Automaton
or Predicaton
P (called by Display
(2.1-4)).
gap> A:=Automaton("det", 4, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 3, 2, 2, 4 ], [ 2, 2, 4, 2 ], [ 2, 2, 3, 2 ], [ 3, 2, 2, 4 ] ],
> [ 1 ], [ 4 ]);
< deterministic automaton on 4 letters with 4 states >
gap> DisplayAut(A);
deterministic finite automaton on 4 letters with 4 states
and the following transitions:
| 1 2 3 4
---------------------------
[ 0, 0 ] | 3 2 2 4
[ 1, 0 ] | 2 2 4 2
[ 0, 1 ] | 2 2 3 2
[ 1, 1 ] | 3 2 2 4
Initial states: [ 1 ]
Final states: [ 4 ]
2.2-2 DrawPredicaton
‣ DrawPredicaton ( P ) | ( function ) |
The function DrawPredicaton
calls the function DrawAutomaton
from the package Automata which uses graphviz
[DEG+02], a software for drawing graphs developed at AT & T Labs, that can be obtained at http://www.graphviz.org/. For further details please refer to the manual of the package Automata.
gap> A:=Automaton("det", 4, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 3, 2, 2, 4 ], [ 2, 2, 4, 2 ], [ 2, 2, 3, 2 ], [ 3, 2, 2, 4 ] ],
> [ 1 ], [ 4 ]);
< deterministic automaton on 4 letters with 4 states >
gap> DisplayAut(A);
deterministic finite automaton on 4 letters with 4 states
and the following transitions:
| 1 2 3 4
---------------------------
[ 0, 0 ] | 3 2 2 4
[ 1, 0 ] | 2 2 4 2
[ 0, 1 ] | 2 2 3 2
[ 1, 1 ] | 3 2 2 4
Initial states: [ 1 ]
Final states: [ 4 ]
2.2-3 IsDeterministicAut
‣ IsDeterministicAut ( P ) | ( function ) |
The function IsDeterministicAut
checks if the Type
of an Automaton
or a Predicaton
P is "det"
. If yes then true
, otherwise false
.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0 ], [ 1 ] ], [ [ 1, 2, 2, 3, 2 ],
> [ 2, 2, 1, 2, 4 ] ], [ 5 ], [ 1 ]), [ 1 ]);
< Predicaton: deterministic finite automaton on 2 letters with 5 states
and the variable position list [ 1 ]. >
gap> IsDeterministicAut(P);
true
2.2-4 IsNonDeterministicAut
‣ IsNonDeterministicAut ( P ) | ( function ) |
The function IsNonDeterministicAut
checks if the Type
of an Automaton
or a Predicaton
P is "nondet"
. If yes then true
, otherwise false
.
gap> P:=Predicaton(Automaton("nondet", 2, [ [ 0 ], [ 1 ] ], [ [ 1 ], [ ] ],
> [ 1 ], [ 1 ]), [ 1 ]);
< Predicaton: nondeterministic finite automaton on 2 letters with 2 states
and the variable position list [ 1 ]. >
gap> Display(P);
Predicaton: nondeterministic finite automaton on 2 letters with 2 states,
the variable position list [ 1 ] and the following transitions:
| 1 2
--------------------------
[ 0 ] | [ 1 ] [ ]
[ 1 ] | [ ] [ ]
Initial states: [ 1 ]
Final states: [ 1 ]
gap> IsNonDeterministicAut(P);
true
2.2-5 TypeOfAut
‣ TypeOfAut ( P ) | ( function ) |
The function TypeOfAut
returns the Type
of an Automaton
or a Predicaton
P, either "det"
, "nondet"
or "epsilon"
. Note that a Predicaton
can only be a deterministic or nondeterministic finite automaton.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 2, 2, 2, 2, 5 ], [ 2, 2, 5, 2, 2 ], [ 2, 2, 2, 3, 2 ], [ 4, 2, 2, 2, 2 ] ],
> [ 1 ], [ 5 ]), [ 1, 2 ]);;
gap> TypeOfAut(P);
"det"
2.2-6 AlphabetOfAut
‣ AlphabetOfAut ( P ) | ( function ) |
The function AlphabetOfAut
returns the size of an Alphabet
of an Automaton
or a Predicaton
P.
gap> P:=Predicaton(Automaton("det", 2, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 1, 2 ], [ 2, 2 ], [ 2, 2 ], [ 1, 2 ] ], [ 1 ], [ 1 ]), [ 1, 2 ]);;
gap> AlphabetOfAut(P);
4
2.2-7 AlphabetOfAutAsList
‣ AlphabetOfAutAsList ( P ) | ( function ) |
The function AlphabetOfAutAsList
returns a StructuralCopy
of the Alphabet
of an Automaton
or a Predicaton
P.
gap> # Continued
gap> AlphabetOfAutAsList(P);
[ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ]
2.2-8 NumberStatesOfAut
‣ NumberStatesOfAut ( P ) | ( function ) |
The function NumberStatesOfAut
returns the number of the States
of an Automaton
or a Predicaton
P.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 2, 2, 2, 2, 5 ], [ 4, 2, 5, 3, 2 ], [ 4, 2, 5, 3, 2 ], [ 2, 2, 2, 2, 2 ] ],
> [ 1 ], [ 5 ]), [ 1, 2 ]);;
gap> NumberStatesOfAut(P);
5
2.2-9 SortedStatesAut
‣ SortedStatesAut ( P ) | ( function ) |
The function SortedStatesAut
returns the Automaton
or the Predicaton
P with sorted States
, such that the initial states have the lowest and the final states the highest number.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0 ], [ 1 ] ], [ [ 1, 2, 2, 2, 2 ],
> [ 2, 2, 1, 3, 4 ] ], [ 5 ], [ 1 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 5 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5
---------------------------
[ 0 ] | 1 2 2 2 2
[ 1 ] | 2 2 1 3 4
Initial states: [ 5 ]
Final states: [ 1 ]
gap> S:=SortedStatesAut(P);;
gap> Display(S);
Predicaton: deterministic finite automaton on 2 letters with 5 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5
---------------------------
[ 0 ] | 2 2 2 2 5
[ 1 ] | 4 2 5 3 2
Initial states: [ 1 ]
Final states: [ 5 ]
2.2-10 TransitionMatrixOfAut
‣ TransitionMatrixOfAut ( P ) | ( function ) |
The function TransitionMatrixOfAut
returns a StructuralCopy
of the TransitionMatrix
of an Automaton
or a Predicaton
P.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0 ], [ 1 ] ], [ [ 1, 2, 2, 2, 2 ],
> [ 2, 2, 1, 3, 4 ] ], [ 5 ], [ 1 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 5 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5
---------------------------
[ 0 ] | 1 2 2 2 2
[ 1 ] | 2 2 1 3 4
Initial states: [ 5 ]
Final states: [ 1 ]
gap> TransitionMatrixOfAut(P);
[ [ 1, 2, 2, 2, 2 ], [ 2, 2, 1, 3, 4 ] ]
2.2-11 InitialStatesOfAut
‣ InitialStatesOfAut ( P ) | ( function ) |
The function InitialStatesOfAut
returns the Initial
states of an Automaton
or a Predicaton
P.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0 ], [ 1 ] ], [ [ 2, 2, 2, 3, 5 ],
> [ 4, 2, 5, 2, 2 ] ], [ 1 ], [ 5 ]), [ 1 ]);;
gap> InitialStatesOfAut(P);
[ 1 ]
2.2-12 SetInitialStatesOfAut
‣ SetInitialStatesOfAut ( P ) | ( function ) |
The function SetInitialStatesOfAut
sets the Initial
states of an Automaton
or a Predicaton
P.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0 ], [ 1 ] ], [ [ 2, 2, 2, 3, 5 ],
> [ 4, 2, 5, 2, 2 ] ], [ 1 ], [ 5 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 5 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5
---------------------------
[ 0 ] | 2 2 2 3 5
[ 1 ] | 4 2 5 2 2
Initial states: [ 1 ]
Final states: [ 5 ]
gap> SetInitialStatesOfAut(P, 3);
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 5 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5
---------------------------
[ 0 ] | 2 2 2 3 5
[ 1 ] | 4 2 5 2 2
Initial states: [ 3 ]
Final states: [ 5 ]
2.2-13 FinalStatesOfAut
‣ FinalStatesOfAut ( P ) | ( function ) |
The function FinalStatesOfAut
returns the Final
states of an Automaton
or a Predicaton
P.
gap> P:=Predicaton(Automaton("det", 4, [ [ 0 ], [ 1 ] ], [ [ 2, 2, 2, 4 ],
> [ 3, 2, 4, 2 ] ], [ 1 ], [ 4 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 4 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4
------------------------
[ 0 ] | 2 2 2 4
[ 1 ] | 3 2 4 2
Initial states: [ 1 ]
Final states: [ 4 ]
gap> FinalStatesOfAut(P);
[ 4 ]
2.2-14 SetFinalStatesOfAut
‣ SetFinalStatesOfAut ( P ) | ( function ) |
The function SetFinalStatesOfAut
sets the Final
states of an Automaton
or a Predicaton
P.
gap> P:=Predicaton(Automaton("det", 4, [ [ 0 ], [ 1 ] ], [ [ 2, 2, 2, 4 ],
> [ 3, 2, 4, 2 ] ], [ 1 ], [ 4 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 4 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4
------------------------
[ 0 ] | 2 2 2 4
[ 1 ] | 3 2 4 2
Initial states: [ 1 ]
Final states: [ 4 ]
gap> SetFinalStatesOfAut(P, [ 1, 2, 3 ]);
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 4 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4
------------------------
[ 0 ] | 2 2 2 4
[ 1 ] | 3 2 4 2
Initial states: [ 1 ]
Final states: [ 1, 2, 3 ]
2.2-15 SinkStatesOfAut
‣ SinkStatesOfAut ( P ) | ( function ) |
The function SinkStatesOfAut
returns the sink states of an Automaton
or a Predicaton
P.
gap> P:=Predicaton(Automaton("det", 3, [ [ 0 ], [ 1 ] ], [ [ 2, 2, 3 ],
> [ 3, 2, 2 ] ], [ 1 ], [ 3 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 3 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3
---------------------
[ 0 ] | 2 2 3
[ 1 ] | 3 2 2
Initial states: [ 1 ]
Final states: [ 3 ]
gap> SinkStatesOfAut(P);
[ 2 ]
2.2-16 PermutedStatesAut
‣ PermutedStatesAut ( P, p ) | ( function ) |
The function PermutedStatesAut
permutes the names of the states of an Automaton
or a Predicaton
P. The list p contains all states, where the state i
(i.e. i
-th position) is mapped to the state p[i]
.
gap> P:=Predicaton(Automaton("det", 6, [ [ 0 ], [ 1 ] ], [ [ 5, 2, 2, 3, 4, 6 ],
> [ 2, 2, 6, 2, 2, 2 ] ], [ 1 ], [ 6 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 6 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6
------------------------------
[ 0 ] | 5 2 2 3 4 6
[ 1 ] | 2 2 6 2 2 2
Initial states: [ 1 ]
Final states: [ 6 ]
gap> Q:=PermutedStatesAut(P,[1,6,4,3,2,5]);;
gap> Display(Q);
Predicaton: deterministic finite automaton on 2 letters with 6 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6
------------------------------
[ 0 ] | 2 3 4 6 5 6
[ 1 ] | 6 6 6 5 6 6
Initial states: [ 1 ]
Final states: [ 5 ]
2.2-17 CopyAut
‣ CopyAut ( P ) | ( function ) |
‣ CopyPredicaton ( P ) | ( function ) |
The function CopyAut
copies either the Automaton
or the Predicaton
P.
gap> P:=Predicaton(Automaton("det", 2, [ [ 0 ], [ 1 ] ], [ [ 1, 2 ], [ 2, 2 ] ],
> [ 1 ], [ 1 ]), [ 1 ]);;
gap> C:=CopyAut(P);;
gap> SetFinalStatesOfAut(C, 2);
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 2 states,
the variable position list [ 1 ] and the following transitions:
| 1 2
------------------
[ 0 ] | 1 2
[ 1 ] | 2 2
Initial states: [ 1 ]
Final states: [ 1 ]
gap> Display(C);
Predicaton: deterministic finite automaton on 2 letters with 2 states,
the variable position list [ 1 ] and the following transitions:
| 1 2
------------------
[ 0 ] | 1 2
[ 1 ] | 2 2
Initial states: [ 1 ]
Final states: [ 2 ]
2.2-18 MinimalAut
‣ MinimalAut ( P ) | ( function ) |
The function MinimalAut
returns the minimal deterministic finite automaton of an Automaton
P. Given a Predicaton
P its automaton is minimized and returned as a Predicaton
with the same variable position list.
gap> P:=Predicaton(Automaton("det", 9, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 2, 6, 7, 4, 5, 4, 5, 8, 9 ], [ 3, 6, 6, 4, 4, 4, 4, 8, 8 ],
> [ 4, 4, 5, 4, 5, 8, 9, 4, 5 ], [ 5, 4, 4, 4, 4, 8, 8, 4, 4 ] ],
> [ 1 ], [ 9 ]), [ 1, 2 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 4 letters with 9 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4 5 6 7 8 9
------------------------------------------
[ 0, 0 ] | 2 6 7 4 5 4 5 8 9
[ 1, 0 ] | 3 6 6 4 4 4 4 8 8
[ 0, 1 ] | 4 4 5 4 5 8 9 4 5
[ 1, 1 ] | 5 4 4 4 4 8 8 4 4
Initial states: [ 1 ]
Final states: [ 9 ]
gap> M:=MinimalAut(P);;
gap> Display(M);
Predicaton: deterministic finite automaton on 4 letters with 5 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4 5
------------------------------
[ 0, 0 ] | 1 2 2 3 2
[ 1, 0 ] | 2 2 2 2 4
[ 0, 1 ] | 2 2 1 2 2
[ 1, 1 ] | 2 2 2 2 2
Initial states: [ 5 ]
Final states: [ 1 ]
gap> P:=Predicaton(Automaton("nondet", 8, [ [ 0 ], [ 1 ] ],
> [ [ [ 2 ], [ 2 ], [ 2 ], [ 4 ], [ 7 ], [ 6 ], [ 6 ], [ 8 ] ],
> [ [ 3 ], [ 2 ], [ 4 ], [ 2 ], [ 6 ], [ 6 ], [ 8 ], [ 6 ] ] ],
> [ 1, 5 ], [ 4, 8 ]), [ 1 ]);;
gap> M:=MinimalAut(P);;
gap> Display(M);
Predicaton: deterministic finite automaton on 2 letters with 4 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4
------------------------
[ 0 ] | 1 2 2 3
[ 1 ] | 2 2 1 3
Initial states: [ 4 ]
Final states: [ 1 ]
2.2-19 NegatedAut
‣ NegatedAut ( P ) | ( function ) |
The function NegatedAut
changes the Final
states to non-final ones and the non-final states to Final
ones.
gap> P:=Predicaton(Automaton("det", 4, [ [ 0 ], [ 1 ] ], [ [ 2, 2, 2, 4 ],
> [ 3, 2, 4, 2 ] ], [ 1 ], [ 4 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 4 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4
------------------------
[ 0 ] | 2 2 2 4
[ 1 ] | 3 2 4 2
Initial states: [ 1 ]
Final states: [ 4 ]
gap> Q:=NegatedAut(P);;
gap> Display(Q);
Predicaton: deterministic finite automaton on 2 letters with 4 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4
------------------------
[ 0 ] | 2 2 2 4
[ 1 ] | 3 2 4 2
Initial states: [ 1 ]
Final states: [ 1, 2, 3 ]
2.2-20 IntersectionAut
‣ IntersectionAut ( P ) | ( function ) |
The function IntersectionAut
returns the intersection of two Automata
or Predicata
P. Note that the for intersection of two automata both must have the same ordered alphabet. For the intersection of two Predicata
with different alphabets use IntersectionPredicata
(2.3-19).
gap> P1:=Predicaton(Automaton("det", 5, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 2, 2, 2, 3, 5 ], [ 2, 2, 2, 3, 5 ], [ 4, 2, 5, 2, 2 ], [ 4, 2, 5, 2, 2 ] ],
> [ 1 ], [ 5 ]), [ 1, 2 ]);;
gap> P2:=Predicaton(Automaton("det", 2, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 1, 2 ], [ 2, 2 ], [ 2, 2 ], [ 1, 2 ] ], [ 1 ], [ 1 ]), [ 1, 2 ]);;
gap> P3:=IntersectionAut(P1, P2);;
gap> Display(P3);
Predicaton: deterministic finite automaton on 4 letters with 9 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4 5 6 7 8 9
------------------------------------------
[ 0, 0 ] | 2 2 3 6 7 3 2 8 9
[ 1, 0 ] | 3 3 3 6 6 3 3 8 8
[ 0, 1 ] | 4 3 3 3 3 8 8 3 3
[ 1, 1 ] | 5 2 3 3 2 8 9 3 2
Initial states: [ 1 ]
Final states: [ 9 ]
gap> P4:=MinimalAut(P3);;
gap> Display(P4);
Predicaton: deterministic finite automaton on 4 letters with 5 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4 5
------------------------------
[ 0, 0 ] | 1 2 2 3 2
[ 1, 0 ] | 2 2 2 2 2
[ 0, 1 ] | 2 2 2 2 2
[ 1, 1 ] | 2 2 1 2 4
Initial states: [ 5 ]
Final states: [ 1 ]
2.2-21 UnionAut
‣ UnionAut ( P ) | ( function ) |
The function UnionAut
returns the union of two Automata
or Predicata
P. Note that for the union of two automata both must have the same ordered alphabet. For the union of two Predicata
with different alphabets use UnionPredicata
(2.3-20).
gap> P1:=Predicaton(Automaton("det", 2, [ [ 0 ], [ 1 ] ],
> [ [ 1, 2 ], [ 2, 2 ] ], [ 1 ], [ 1 ]), [ 1 ]);;
gap> P2:=Predicaton(Automaton("det", 4, [ [ 0 ], [ 1 ] ],
> [ [ 3, 2, 2, 4 ], [ 2, 2, 4, 2 ] ], [ 1 ], [ 4 ]), [ 1 ]);;
gap> P3:=UnionAut(P1, P2);;
gap> Display(P3);
Predicaton: nondeterministic finite automaton on 2 letters with 6 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6
------------------------------------------------------
[ 0 ] | [ 1 ] [ 2 ] [ 5 ] [ 4 ] [ 4 ] [ 6 ]
[ 1 ] | [ 2 ] [ 2 ] [ 4 ] [ 4 ] [ 6 ] [ 4 ]
Initial states: [ 1, 3 ]
Final states: [ 1, 6 ]
gap> M:=MinimalAut(P3);;
gap> Display(M);
Predicaton: deterministic finite automaton on 2 letters with 4 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4
------------------------
[ 0 ] | 1 2 2 3
[ 1 ] | 1 1 2 1
Initial states: [ 4 ]
Final states: [ 2, 3, 4 ]
2.2-22 IsRecognizedByAut
‣ IsRecognizedByAut ( P, word ) | ( function ) |
The function IsRecognizedByAut
checks if a word, given by its letters, is accepted by the Automaton
or Predicaton
P.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0 ], [ 1 ] ],
> [ [ 5, 5, 5, 4, 5 ], [ 2, 3, 4, 5, 5 ] ], [ 1 ], [ 4 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 5 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5
---------------------------
[ 0 ] | 5 5 5 4 5
[ 1 ] | 2 3 4 5 5
Initial states: [ 1 ]
Final states: [ 4 ]
gap> IsRecognizedByAut(P,[[1],[1],[1]]);
true
gap> IsRecognizedByAut(P,[[1],[1],[1],[0],[0]]);
true
gap> IsRecognizedByAut(P,[[1],[1],[0]]);
false
2.3 Basic functions on Predicata
The following functions act only on Predicata, accessing and modifying the alphabet \(A:=\{0,1\}^n\) for a natural number \(n\) (including 0).
2.3-1 DecToBin
‣ DecToBin ( D ) | ( function ) |
The function DecToBin
returns for a natural numbers D or the list of its binary representation. Note that here, motivated on how the automata read the words, the binary representation are read in the other direction than usual, for example \(4 = [0,0,1]_2\).
gap> DecToBin(4);
[ 0, 0, 1 ]
gap> DecToBin(0);
[ 0 ]
2.3-2 BinToDec
‣ BinToDec ( B ) | ( function ) |
The function BinToDec
returns for a list B (i.e. a binary representation), containing 0
s and 1
s, the corresponding natural number. Note again that here the \(\sum b_{i+1}*2^i\) starting at \(i=0\) is evaluated the other way around than it's usually done.
gap> BinToDec([ 0, 0, 1 ]);
4
gap> BinToDec([ 0, 0, 1, 0, 0, 0, 0 ]);
4
gap> BinToDec([ ]);
0
2.3-3 IsAcceptedWordByPredicaton
‣ IsAcceptedWordByPredicaton ( P, L ) | ( function ) |
‣ IsAcceptedByPredicaton ( P, L ) | ( function ) |
The function IsAcceptedWordByPredicaton
checks if a list of natural numbers L or a list of binary representation L is accepted by the Predicaton
P. Compare with IsRecognizedByAut
(2.2-22), which uses the letters instead of the words.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 2, 2, 2, 2, 5 ], [ 4, 2, 2, 3, 2 ], [ 2, 2, 2, 2, 2 ], [ 2, 2, 5, 2, 2 ] ],
> [ 1 ], [ 5 ]), [ 1, 2 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 4 letters with 5 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4 5
------------------------------
[ 0, 0 ] | 2 2 2 2 5
[ 1, 0 ] | 4 2 2 3 2
[ 0, 1 ] | 2 2 2 2 2
[ 1, 1 ] | 2 2 5 2 2
Initial states: [ 1 ]
Final states: [ 5 ]
gap> IsAcceptedWordByPredicaton(P, [ 7, 4 ]);
true
gap> IsAcceptedWordByPredicaton(P, [ DecToBin(7), DecToBin(4) ]);
true
gap> IsAcceptedWordByPredicaton(P, [ [ 1, 1, 1, 0 ], [ 0, 0, 1, 0, 0, 0 ] ]);
true
gap> IsRecognizedByAut(P, [ [ 1, 0 ], [ 1, 0 ], [ 1, 1 ] ]); # 1st row = 7, 2nd row = 4
true
2.3-4 AcceptedWordsByPredicaton
‣ AcceptedWordsByPredicaton ( P[, b] ) | ( function ) |
‣ AcceptedByPredicaton ( P[, b] ) | ( function ) |
The function AcceptedWordsByPredicaton
returns the accepted words of the Predicaton
P up to an upper bound b (on default b=10
), either a positive integer or a list with positive integers as an individual bound for each variable. Alternatively, list of lists where each list contains the to be tested values is also allowed.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 2, 2, 2, 2, 5 ], [ 4, 2, 2, 3, 2 ], [ 2, 2, 2, 2, 2 ], [ 2, 2, 5, 2, 2 ] ],
> [ 1 ], [ 5 ]), [ 1, 2 ]);;
gap> AcceptedWordsByPredicaton(P, [ 10, 20 ]);
[ [ 7, 4 ] ]
gap> P:=Predicaton(Automaton("det", 3, [ [ 0 ], [ 1 ] ],
> [ [ 1, 3, 2 ], [ 2, 1, 3 ] ], [ 1 ], [ 1 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 3 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3
---------------------
[ 0 ] | 1 3 2
[ 1 ] | 2 1 3
Initial states: [ 1 ]
Final states: [ 1 ]
gap> AcceptedWordsByPredicaton(P, 29);
[ [ 0 ], [ 3 ], [ 6 ], [ 9 ], [ 12 ], [ 15 ], [ 18 ], [ 21 ], [ 24 ], [ 27 ] ]
gap> AcceptedWordsByPredicaton(P, [ [121..144] ]);
[ [ 123 ], [ 126 ], [ 129 ], [ 132 ], [ 135 ], [ 138 ], [ 141 ], [ 144 ] ]
2.3-5 DisplayAcceptedWordsByPredicaton
‣ DisplayAcceptedWordsByPredicaton ( P[, b, t] ) | ( function ) |
‣ DisplayAcceptedByPredicaton ( P[, b, t] ) | ( function ) |
The function DisplayAcceptedWordsByPredicaton
prints the accepted words of the Predicaton
P in a nice way. For one variable as a "list" with YES/no
, for two variables as a "matrix" containing YES/no
and for three variables as a "matrix", which entries are the third accepted natural numbers. The optional parameter b gives an upper bound for the displayed natural numbers, where either a positive integer or a list of positive integers denotes the maximal natural numbers which are asked for. The second optional parameter, if true
allows to reduce YES/no
to Y/n
for the case of one variable.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 2, 2, 2, 3, 5 ], [ 4, 2, 2, 3, 2 ], [ 2, 2, 2, 3, 2 ], [ 2, 2, 5, 3, 2 ] ],
> [ 1 ], [ 5 ]), [ 1, 2 ]);;
gap> AcceptedWordsByPredicaton(P);
[ [ 5, 4 ], [ 5, 6 ], [ 7, 4 ], [ 7, 6 ] ]
gap> DisplayAcceptedWordsByPredicaton(P, [8,10]);
If the following words are accepted by the given automaton, then: YES,
otherwise if not accepted: no.
| 0 1 2 3 4 5 6 7 8 9 10
-------------------------------------------------
0 | no no no no no no no no no no no
1 | no no no no no no no no no no no
2 | no no no no no no no no no no no
3 | no no no no no no no no no no no
4 | no no no no no no no no no no no
5 | no no no no YES no YES no no no no
6 | no no no no no no no no no no no
7 | no no no no YES no YES no no no no
8 | no no no no no no no no no no no
gap> P:=Predicaton(Automaton("det", 5, [ [ 0 ], [ 1 ] ],
> [ [ 3, 2, 5, 4, 4 ], [ 3, 2, 4, 2, 4 ] ],
> [ 1 ], [ 3, 4, 5, 1 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 5 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5
---------------------------
[ 0 ] | 3 2 5 4 4
[ 1 ] | 3 2 4 2 4
Initial states: [ 1 ]
Final states: [ 1, 3, 4, 5 ]
gap> AcceptedWordsByPredicaton(P, 19);
[ [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ]
gap> DisplayAcceptedWordsByPredicaton(P, 29, true);
If the following words are accepted by the given automaton, then: Y,
otherwise if not accepted: n.
0: Y 1: Y 2: Y 3: Y 4: Y 5: Y 6: n 7: n 8: n 9: n
10: n 11: n 12: n 13: n 14: n 15: n 16: n 17: n 18: n 19: n
20: n 21: n 22: n 23: n 24: n 25: n 26: n 27: n 28: n 29: n
2.3-6 DisplayAcceptedWordsByPredicatonInNxN
‣ DisplayAcceptedWordsByPredicatonInNxN ( P[, b] ) | ( function ) |
‣ DisplayAcceptedByPredicatonInNxN ( P[, b] ) | ( function ) |
The function DisplayAcceptedWordsByPredicatonInNxN
prints the accepted words of the Predicaton
P with a variable position list of length two in a fancy way in \(ℕ \times ℕ\). It "draws" the natural number solutions of linear equations, which can be seen, due to the linearity, as "lines". The optional parameter l gives an upper bound for the displayed accepted words, it must be a list containing two positive integers.
gap> P:=Predicaton(Automaton("det", 14, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 6, 2, 2, 3, 4, 2, 2, 3, 7, 2, 10, 12, 12, 14 ],
> [ 2, 2, 12, 2, 9, 11, 7, 7, 2, 13, 2, 2, 7, 2 ],
> [ 2, 2, 12, 2, 7, 8, 14, 14, 2, 14, 2, 2, 14, 2 ],
> [ 5, 2, 2, 12, 3, 2, 2, 12, 7, 2, 13, 2, 2, 14 ] ],
> [ 1 ], [ 12, 13, 14 ]), [ 1, 2 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 4 letters with 14 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14
---------------------------------------------------------
[ 0, 0 ] | 6 2 2 3 4 2 2 3 7 2 10 12 12 14
[ 1, 0 ] | 2 2 12 2 9 11 7 7 2 13 2 2 7 2
[ 0, 1 ] | 2 2 12 2 7 8 14 14 2 14 2 2 14 2
[ 1, 1 ] | 5 2 2 12 3 2 2 12 7 2 13 2 2 14
Initial states: [ 1 ]
Final states: [ 12, 13, 14 ]
gap> DisplayAcceptedWordsByPredicatonInNxN(P, [ 15, 15 ]);
15 - o
|
14 - o
|
13 - o
|
12 - o
|
11 - o
|
10 - o o
|
9 - o o
|
8 - o
|
7 - o o
|
6 - o o
|
5 - o
|
4 - o
|
3 - o
|
2 - o
|
1 - o
|
0 - o
|
--+--|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---->
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2.3-7 AutomatonOfPredicaton
‣ AutomatonOfPredicaton ( P ) | ( function ) |
‣ AutOfPredicaton ( P ) | ( function ) |
The function AutomatonOfPredicaton
returns the Automaton
of a Predicaton
P.
gap> P:=Predicaton(Automaton("det", 4, [ [ 0 ], [ 1 ] ],
> [ [ 4, 2, 3, 3 ], [ 3, 2, 2, 3 ] ], [ 1 ], [ 3, 4, 1 ]), [ 1 ]);
< Predicaton: deterministic finite automaton on 2 letters with 4 states
and the variable position list [ 1 ]. >
gap> AutomatonOfPredicaton(P);
< deterministic automaton on 2 letters with 4 states >
2.3-8 VariablePositionListOfPredicaton
‣ VariablePositionListOfPredicaton ( P ) | ( function ) |
‣ VarPosListOfPredicaton ( P ) | ( function ) |
The function VariablePositionListOfPredicaton
returns the variable position list of a Predicaton
P.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 1, 2, 2, 3, 2 ], [ 4, 2, 2, 5, 2 ], [ 2, 2, 1, 2, 3 ], [ 2, 2, 4, 2, 5 ] ],
> [ 1 ], [ 1 ]), [ 4, 9 ]);;
gap> VariablePositionListOfPredicaton(P);
[ 4, 9 ]
2.3-9 SetVariablePositionListOfPredicaton
‣ SetVariablePositionListOfPredicaton ( P, l ) | ( function ) |
‣ SetVarPosListOfPredicaton ( P, l ) | ( function ) |
The function SetVariablePositionListOfPredicaton
sets the variable position list of a Predicaton
P, permuting the alphabet if necessary, see PermutedAlphabetPredicaton
(2.3-21).
gap> P:=Predicaton(Automaton("det", 5, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 1, 2, 2, 3, 2 ], [ 4, 2, 2, 5, 2 ], [ 2, 2, 1, 2, 3 ], [ 2, 2, 4, 2, 5 ] ],
> [ 1 ], [ 1 ]), [ 4, 9 ]);;
gap> SetVariablePositionListOfPredicaton(P, [ 1, 2 ]);
gap> VariablePositionListOfPredicaton(P);
[ 1, 2 ]
2.3-10 ProductLZeroPredicaton
‣ ProductLZeroPredicaton ( P ) | ( function ) |
The function ProductLZeroPredicaton
takes the Predicaton
P and adds a new state. This new state is final and is reached through [0,...,0]
from all Final
states. Hence the returned Predicaton
recognizes the product of the languages of the given Predicaton
and the language containing all the zero words.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0 ], [ 1 ] ], [ [ 3, 2, 4, 2, 2 ],
> [ 2, 2, 2, 5, 2 ] ], [ 1 ], [ 5 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 5 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5
---------------------------
[ 0 ] | 3 2 4 2 2
[ 1 ] | 2 2 2 5 2
Initial states: [ 1 ]
Final states: [ 5 ]
gap> IsAcceptedWordByPredicaton(P, [ [ 0, 0, 1 ] ]);
true
gap> IsAcceptedWordByPredicaton(P, [ [ 0, 0, 1, 0 ] ]);
false
gap> PredicatonToRatExp(P);
[ 0 ][ 0 ][ 1 ]
gap> Q:=ProductLZeroPredicaton(P);;
gap> Display(Q);
Predicaton: nondeterministic finite automaton on 2 letters with 6 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6
------------------------------------------------------------------------
[ 0 ] | [ 3 ] [ 2 ] [ 4 ] [ 2 ] [ 2, 6 ] [ 6 ]
[ 1 ] | [ 2 ] [ 2 ] [ 2 ] [ 5 ] [ 2 ] [ ]
Initial states: [ 1 ]
Final states: [ 5, 6 ]
gap> IsAcceptedWordByPredicaton(Q, [ [ 0, 0, 1 ] ]);
true
gap> IsAcceptedWordByPredicaton(Q, [ [ 0, 0, 1, 0 ] ]);
true
gap> PredicatonToRatExp(Q);
[ 0 ][ 0 ][ 1 ]([ 0 ][ 0 ]*U@)
gap> M:=MinimalAut(Q);;
gap> M:=PermutedStatesAut(M, [ 5, 2, 4, 3, 1 ]);;
gap> Display(M);
Predicaton: deterministic finite automaton on 2 letters with 5 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5
---------------------------
[ 0 ] | 3 2 4 2 5
[ 1 ] | 2 2 2 5 2
Initial states: [ 1 ]
Final states: [ 5 ]
gap> PredicatonToRatExp(M);
[ 0 ][ 0 ][ 1 ][ 0 ]*
2.3-11 RightQuotientLZeroPredicaton
‣ RightQuotientLZeroPredicaton ( P ) | ( function ) |
The function RightQuotientLZeroPredicaton
takes the Predicaton
P and runs through all final states. If a Final
state is reached with [0,...,0]
then this state is added to the final states. Hence the returned Predicaton
recognizes the right quotient of the language of the given Predicaton
with the language containing only the zero words.
gap> P:=Predicaton(Automaton("det", 6, [ [ 0 ], [ 1 ] ], [ [ 3, 2, 4, 2, 6, 2 ],
> [ 2, 2, 2, 5, 2, 2 ] ], [ 1 ], [ 6 ]), [ 1 ]);;
gap> Display(P);
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 6 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6
------------------------------
[ 0 ] | 3 2 4 2 6 2
[ 1 ] | 2 2 2 5 2 2
Initial states: [ 1 ]
Final states: [ 6 ]
gap> IsAcceptedWordByPredicaton(P, [ 4 ]);
false
gap> IsAcceptedWordByPredicaton(P, [ [ 0, 0, 1 ] ]);
false
gap> IsAcceptedWordByPredicaton(P, [ [ 0, 0, 1, 0 ] ]);
true
gap> PredicatonToRatExp(P);
[ 0 ][ 0 ][ 1 ][ 0 ]
gap> Q:=RightQuotientLZeroPredicaton(P);;
gap> Display(Q);
Predicaton: nondeterministic finite automaton on 2 letters with 6 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6
------------------------------------------------------
[ 0 ] | [ 3 ] [ 2 ] [ 4 ] [ 2 ] [ 6 ] [ 2 ]
[ 1 ] | [ 2 ] [ 2 ] [ 2 ] [ 5 ] [ 2 ] [ 2 ]
Initial states: [ 1 ]
Final states: [ 5, 6 ]
gap> IsAcceptedWordByPredicaton(Q, [ 4 ]);
true
gap> IsAcceptedWordByPredicaton(Q, [ [ 0, 0, 1 ] ]);
true
gap> IsAcceptedWordByPredicaton(Q, [ [ 0, 0, 1, 0 ] ]);
true
gap> PredicatonToRatExp(Q);
[ 0 ][ 0 ][ 1 ]([ 0 ]U@)
gap> M:=MinimalAut(Q);;
gap> M:=PermutedStatesAut(M, [ 6, 2, 5, 4, 3, 1 ]);;
gap> Display(M);
Predicaton: deterministic finite automaton on 2 letters with 6 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6
------------------------------
[ 0 ] | 3 2 4 2 6 2
[ 1 ] | 2 2 2 5 2 2
Initial states: [ 1 ]
Final states: [ 5, 6 ]
gap> IsAcceptedWordByPredicaton(M, [ 4 ]);
true
gap> PredicatonToRatExp(M);
[ 0 ][ 0 ][ 1 ]([ 0 ]U@)
2.3-12 NormalizedLeadingZeroPredicaton
‣ NormalizedLeadingZeroPredicaton ( P ) | ( function ) |
The function NormalizedLeadingZeroPredicaton
returns the union of ProductLZeroPredicaton
(2.3-10) and RightQuotientLZeroPredicaton
(2.3-11) of the given Predicaton
P. Therefore the returned Predicaton
accepts any previously accepted words with cancelled or added leading zeros.
gap> P:=Predicaton(Automaton("det", 7, [ [ 0 ], [ 1 ] ], [ [ 3, 2, 4, 2, 6, 2, 2],
> [ 2, 2, 7, 5, 2, 2, 2 ] ], [ 1 ], [ 6, 7 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 7 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6 7
---------------------------------
[ 0 ] | 3 2 4 2 6 2 2
[ 1 ] | 2 2 7 5 2 2 2
Initial states: [ 1 ]
Final states: [ 6, 7 ]
gap> IsAcceptedWordByPredicaton(P, [ [ 0, 1 ] ]);
true
gap> IsAcceptedWordByPredicaton(P, [ [ 0, 1, 0 ] ]);
false
gap> IsAcceptedWordByPredicaton(P, [ [ 0, 0, 1 ] ]);
false
gap> IsAcceptedWordByPredicaton(P, [ [ 0, 0, 1, 0 ] ]);
true
gap> PredicatonToRatExp(P);
[ 0 ]([ 1 ]U[ 0 ][ 1 ][ 0 ])
gap> Q:=NormalizedLeadingZeroPredicaton(P);;
gap> Display(Q);
Predicaton: nondeterministic finite automaton on 2 letters with 16 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6 7 8
----------------------------------------------------------------------------
[ 0 ] | [ 2 ] [ 4 ] [ 3 ] [ 3 ] [ 7 ] [ 8 ] [ 9 ] [ 7 ]
[ 1 ] | [ 3 ] [ 5 ] [ 3 ] [ 6 ] [ 3 ] [ 3 ] [ 3 ] [ 3 ]
...
| 9 10 11 12 13 14 15 16
----------------------------------------------------------------------------
[ 0 ] | [ 9 ] [ 11 ] [ 13 ] [ 12 ] [ 12 ] [ 12 ] [ 16 ] [ 12 ]
[ 1 ] | [ 3 ] [ 12 ] [ 14 ] [ 12 ] [ 15 ] [ 12 ] [ 12 ] [ 12 ]
Initial states: [ 1, 10 ]
Final states: [ 5, 7, 8, 9, 14, 15, 16 ]
gap> AcceptedWordsByPredicaton(Q, 10);
[ [ 2 ], [ 4 ] ]
gap> IsAcceptedWordByPredicaton(Q, [ [ 0, 1 ] ]);
true
gap> IsAcceptedWordByPredicaton(Q, [ [ 0, 1, 0 ] ]);
true
gap> IsAcceptedWordByPredicaton(Q, [ [ 0, 0, 1 ] ]);
true
gap> IsAcceptedWordByPredicaton(Q, [ [ 0, 0, 1, 0 ] ]);
true
gap> M:=MinimalAut(Q);;
gap> M:=PermutedStatesAut(M, [ 3, 5, 1, 4, 2 ]);;
gap> Display(M);
Predicaton: deterministic finite automaton on 2 letters with 5 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5
---------------------------
[ 0 ] | 3 2 4 2 5
[ 1 ] | 2 2 5 5 2
Initial states: [ 1 ]
Final states: [ 5 ]
gap> AcceptedWordsByPredicaton(M, 10);
[ [ 2 ], [ 4 ] ]
gap> PredicatonToRatExp(M);
[ 0 ]([ 0 ][ 1 ]U[ 1 ])[ 0 ]*
2.3-13 SortedAlphabetPredicaton
‣ SortedAlphabetPredicaton ( P ) | ( function ) |
‣ SortedAbcPredicaton ( P ) | ( function ) |
The function SortedAlphabetPredicaton
returns the Predicaton
P with the component-wise sorted Alphabet
(from right to left with \(0<1\)).
gap> P:=Predicaton(Automaton("det", 3, [ [ 0, 0, 0 ], [ 0, 0, 1 ], [ 1, 0, 0 ],
> [ 1, 0, 1 ], [ 0, 1, 0 ], [ 0, 1, 1 ], [ 1, 1, 0 ], [ 1, 1, 1 ] ],
> [ [ 1, 3, 3 ], [ 3, 2, 3 ], [ 3, 2, 3 ], [ 2, 3, 3 ], [ 3, 1, 3 ],
> [ 1, 3, 3 ], [ 1, 3, 3 ], [ 3, 2, 3 ] ], [ 1 ], [ 1 ]), [ 1, 2, 3 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 8 letters with 3 states,
the variable position list [ 1, 2, 3 ] and the following transitions:
| 1 2 3
---------------------------
[ 0, 0, 0 ] | 1 3 3
[ 0, 0, 1 ] | 3 2 3
[ 1, 0, 0 ] | 3 2 3
[ 1, 0, 1 ] | 2 3 3
[ 0, 1, 0 ] | 3 1 3
[ 0, 1, 1 ] | 1 3 3
[ 1, 1, 0 ] | 1 3 3
[ 1, 1, 1 ] | 3 2 3
Initial states: [ 1 ]
Final states: [ 1 ]
gap> Q:=SortedAlphabetPredicaton(P);;
gap> Display(Q);
Predicaton: deterministic finite automaton on 8 letters with 3 states,
the variable position list [ 1, 2, 3 ] and the following transitions:
| 1 2 3
---------------------------
[ 0, 0, 0 ] | 1 3 3
[ 1, 0, 0 ] | 3 2 3
[ 0, 1, 0 ] | 3 1 3
[ 1, 1, 0 ] | 1 3 3
[ 0, 0, 1 ] | 3 2 3
[ 1, 0, 1 ] | 2 3 3
[ 0, 1, 1 ] | 1 3 3
[ 1, 1, 1 ] | 3 2 3
Initial states: [ 1 ]
Final states: [ 1 ]
2.3-14 FormattedPredicaton
‣ FormattedPredicaton ( P ) | ( function ) |
The function
computes first the NormalizedLeadingZeroPredicaton
(2.3-12) and then the MinimalAut
(2.2-18) of the Predicaton
P.
gap> P:=Predicaton(Automaton("det", 7, [ [ 0 ], [ 1 ] ], [ [ 3, 2, 4, 2, 6, 2, 2],
> [ 2, 2, 7, 5, 2, 2, 2 ] ], [ 1 ], [ 6, 7 ]), [ 1 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 7 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6 7
---------------------------------
[ 0 ] | 3 2 4 2 6 2 2
[ 1 ] | 2 2 7 5 2 2 2
Initial states: [ 1 ]
Final states: [ 6, 7 ]
gap> PredicatonToRatExp(P);
[ 0 ]([ 1 ]U[ 0 ][ 1 ][ 0 ])
gap> M:=FormattedPredicaton(P);;
gap> Display(M);
Predicaton: deterministic finite automaton on 2 letters with 5 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5
---------------------------
[ 0 ] | 4 2 1 5 5
[ 1 ] | 2 5 5 2 5
Initial states: [ 3 ]
Final states: [ 2 ]
gap> PredicatonToRatExp(M);
[ 0 ]([ 0 ][ 1 ]U[ 1 ])[ 0 ]*
2.3-15 IsValidInput
‣ IsValidInput ( P, n ) | ( function ) |
The function IsValidInput
checks if the list n contains positive integers and if it is a valid variable position list of the given Predicaton
P, i.e. variable position list is a subset of n.
gap> P:=Predicaton(Automaton("det", 2, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 1, 2 ], [ 2, 2 ], [ 1, 2 ], [ 2, 2 ] ], [ 1 ], [ 1 ]), [ 2, 4 ]);;
gap> IsValidInput(P, [ 1, 2, 3 ]);
The new variable position list must contain the old one of the Predicaton.
Compare [ 2, 4 ] with [ 1, 2, 3 ].
false
gap> IsValidInput(P, [ 1, 2, 3, 4 ]);
true
2.3-16 ExpandedPredicaton
‣ ExpandedPredicaton ( P, n ) | ( function ) |
The function ExpandedPredicaton
returns the Predicaton
P with the new variable position list n. For each new variable position in n, the alphabet size doubles. In each step 0s and 1s are added at the correct position in all letters of the alphabet, whereas the transition matrix rows are copied accordingly. Formally this corresponds to the preimage of the homomorphism ignoring a component of the letters applied to the deterministic finite automaton.
gap> P:=Predicaton(Automaton("det", 3, [ [ 0 ], [ 1 ] ], [ [ 2, 2, 3 ],
> [ 3, 2, 2 ] ], [ 1 ], [ 3 ]), [ 1 ]);
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 3 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3
---------------------
[ 0 ] | 2 2 3
[ 1 ] | 3 2 2
Initial states: [ 1 ]
Final states: [ 3 ]
gap> Q:=ExpandedPredicaton(P, [ 1, 2, 3 ]);;
gap> Display(Q);
Predicaton: deterministic finite automaton on 8 letters with 3 states,
the variable position list [ 1, 2, 3 ] and the following transitions:
| 1 2 3
---------------------------
[ 0, 0, 0 ] | 2 2 3
[ 1, 0, 0 ] | 3 2 2
[ 0, 1, 0 ] | 2 2 3
[ 1, 1, 0 ] | 3 2 2
[ 0, 0, 1 ] | 2 2 3
[ 1, 0, 1 ] | 3 2 2
[ 0, 1, 1 ] | 2 2 3
[ 1, 1, 1 ] | 3 2 2
Initial states: [ 1 ]
Final states: [ 3 ]
2.3-17 ProjectedPredicaton
‣ ProjectedPredicaton ( P, p ) | ( function ) |
The function ProjectedPredicaton
returns the Predicaton
P with the new variable position list without p. The alphabet is halved, ignoring the 0s and 1s entries at position p relative to the VariablePositionList
, whereas the transition matrix rows are combined accordingly. Formally this corresponds to the image of homomorphism which ignores the p-th component of the letters applied to the deterministic finite automaton. This function is used for the interpretation of the existence quantifier.
gap> P:=Predicaton(Automaton("det", 3, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 1, 3, 3 ], [ 2, 3, 3 ], [ 3, 1, 3 ], [ 3, 2, 3 ] ], [ 1 ], [ 1 ]),
> [ 1, 2 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 4 letters with 3 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3
------------------------
[ 0, 0 ] | 1 3 3
[ 1, 0 ] | 2 3 3
[ 0, 1 ] | 3 1 3
[ 1, 1 ] | 3 2 3
Initial states: [ 1 ]
Final states: [ 1 ]
gap> Q:=ProjectedPredicaton(P, 1);;
gap> Display(Q);
Predicaton: deterministic finite automaton on 2 letters with 3 states,
the variable position list [ 2 ] and the following transitions:
| 1 2 3
---------------------
[ 0 ] | 1 2 2
[ 1 ] | 1 2 1
Initial states: [ 3 ]
Final states: [ 2, 3 ]
gap> AcceptedWordsByPredicaton(P, 10);
[ [ 0, 0 ], [ 1, 2 ], [ 2, 4 ], [ 3, 6 ], [ 4, 8 ], [ 5, 10 ] ]
gap> AcceptedWordsByPredicaton(Q, 10);
[ [ 0 ], [ 2 ], [ 4 ], [ 6 ], [ 8 ], [ 10 ] ]
gap> PredicatonToRatExp(P);
([ 1, 0 ][ 1, 1 ]*[ 0, 1 ]U[ 0, 0 ])*
gap> PredicatonToRatExp(Q);
[ 0 ]([ 0 ]U[ 1 ])*U@
2.3-18 NegatedProjectedNegatedPredicaton
‣ NegatedProjectedNegatedPredicaton ( P, p ) | ( function ) |
The function NegatedProjectedNegatedPredicaton
returns the negated (NegatedAut
(2.2-19)), projected (ProjectedPredicaton
(2.3-17) with p) and negated Predicaton
P. This function is used for the interpretation of the for all quantifier.
gap> P:=Predicaton(Automaton("det", 2, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 1, 2 ], [ 2, 2 ], [ 2, 2 ], [ 1, 2 ] ], [ 1 ], [ 1 ]), [ 1, 2 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 4 letters with 2 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2
---------------------
[ 0, 0 ] | 1 2
[ 1, 0 ] | 2 2
[ 0, 1 ] | 2 2
[ 1, 1 ] | 1 2
Initial states: [ 1 ]
Final states: [ 1 ]
gap> AcceptedWordsByPredicaton(P, 5);
[ [ 0, 0 ], [ 1, 1 ], [ 2, 2 ], [ 3, 3 ], [ 4, 4 ], [ 5, 5 ] ]
gap> Q1:=ProjectedPredicaton(P, 1);;
gap> Display(Q1);
Predicaton: deterministic finite automaton on 2 letters with 1 state,
the variable position list [ 2 ] and the following transitions:
| 1
---------------
[ 0 ] | 1
[ 1 ] | 1
Initial states: [ 1 ]
Final states: [ 1 ]
gap> AcceptedWordsByPredicaton(Q1, 5);
[ [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ]
gap> Q2:=NegatedProjectedNegatedPredicaton(Q1, 2);;
gap> Display(Q2);
Predicaton: deterministic finite automaton on 1 letter with 1 state,
the variable position list [ ] and the following transitions:
| 1
-------------
[ ] | 1
Initial states: [ 1 ]
Final states: [ 1 ]
gap> AcceptedWordsByPredicaton(Q2);
[ true ]
2.3-19 IntersectionPredicata
‣ IntersectionPredicata ( P1, P2, n ) | ( function ) |
The function IntersectionPredicata
returns the intersection (IntersectionAut
(2.2-20)) of the Predicata
of P1 and P2 after resizing (ExpandedPredicaton
(2.3-16)) and sorting (SortedAlphabetPredicaton
(2.3-13)) the alphabet to match the new variable position list n.
gap> P1:=Predicaton(Automaton("det", 5, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 4, 2, 2, 2, 5 ], [ 2, 2, 5, 2, 2 ], [ 2, 2, 2, 3, 2 ], [ 4, 2, 2, 2, 2 ] ],
> [ 1 ], [ 5 ]), [ 1, 2 ]);;
gap> Display(P1);
Predicaton: deterministic finite automaton on 4 letters with 5 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4 5
------------------------------
[ 0, 0 ] | 4 2 2 2 5
[ 1, 0 ] | 2 2 5 2 2
[ 0, 1 ] | 2 2 2 3 2
[ 1, 1 ] | 4 2 2 2 2
Initial states: [ 1 ]
Final states: [ 5 ]
gap> AcceptedByPredicaton(P1, 10);
[ [ 4, 2 ], [ 5, 3 ] ]
gap> P2:=Predicaton(Automaton("det", 6, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 5, 2, 2, 3, 2, 6 ], [ 2, 2, 6, 2, 2, 2 ], [ 4, 2, 2, 2, 3, 2 ],
> [ 2, 2, 2, 2, 2, 2 ] ], [ 1 ], [ 6 ]), [ 1, 2 ]);;
gap> Display(P2);
Predicaton: deterministic finite automaton on 4 letters with 6 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4 5 6
---------------------------------
[ 0, 0 ] | 5 2 2 3 2 6
[ 1, 0 ] | 2 2 6 2 2 2
[ 0, 1 ] | 4 2 2 2 3 2
[ 1, 1 ] | 2 2 2 2 2 2
Initial states: [ 1 ]
Final states: [ 6 ]
gap> AcceptedByPredicaton(P2, 10);
[ [ 4, 1 ], [ 4, 2 ] ]
gap> P3:=IntersectionPredicata(P1, P2, [ 1, 2 ]);;
gap> Display(P3);
Predicaton: deterministic finite automaton on 4 letters with 5 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4 5
------------------------------
[ 0, 0 ] | 1 2 2 2 4
[ 1, 0 ] | 2 2 1 2 2
[ 0, 1 ] | 2 2 2 3 2
[ 1, 1 ] | 2 2 2 2 2
Initial states: [ 5 ]
Final states: [ 1 ]
gap> AcceptedByPredicaton(P3, 10);
[ [ 4, 2 ] ]
2.3-20 UnionPredicata
‣ UnionPredicata ( P ) | ( function ) |
The function UnionPredicata
returns union (UnionAut
(2.2-21)) of the Predicata
of P1 and P2 after resizing (ExpandedPredicaton
(2.3-16)) and sorting (SortedAlphabetPredicaton
(2.3-13)) the alphabet to match the new variable position list n.
gap> P1:=Predicaton(Automaton("det", 5, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 4, 2, 2, 2, 5 ], [ 2, 2, 5, 2, 2 ], [ 2, 2, 2, 3, 2 ], [ 4, 2, 2, 2, 2 ] ],
> [ 1 ], [ 5 ]), [ 1, 2 ]);;
gap> Display(P1);
Predicaton: deterministic finite automaton on 4 letters with 5 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4 5
------------------------------
[ 0, 0 ] | 4 2 2 2 5
[ 1, 0 ] | 2 2 5 2 2
[ 0, 1 ] | 2 2 2 3 2
[ 1, 1 ] | 4 2 2 2 2
Initial states: [ 1 ]
Final states: [ 5 ]
gap> AcceptedByPredicaton(P1, 10);
[ [ 4, 2 ], [ 5, 3 ] ]
gap> P2:=Predicaton(Automaton("det", 6, [ [ 0, 0 ], [ 1, 0 ], [ 0, 1 ], [ 1, 1 ] ],
> [ [ 5, 2, 2, 3, 2, 6 ], [ 2, 2, 6, 2, 2, 2 ], [ 4, 2, 2, 2, 3, 2 ],
> [ 2, 2, 2, 2, 2, 2 ] ], [ 1 ], [ 6 ]), [ 1, 2 ]);;
gap> Display(P2);
Predicaton: deterministic finite automaton on 4 letters with 6 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4 5 6
---------------------------------
[ 0, 0 ] | 5 2 2 3 2 6
[ 1, 0 ] | 2 2 6 2 2 2
[ 0, 1 ] | 4 2 2 2 3 2
[ 1, 1 ] | 2 2 2 2 2 2
Initial states: [ 1 ]
Final states: [ 6 ]
gap> AcceptedByPredicaton(P2, 10);
[ [ 4, 1 ], [ 4, 2 ] ]
gap> P3:=UnionPredicata(P1, P2, [ 1, 2 ]);;
gap> Display(P3);
Predicaton: deterministic finite automaton on 4 letters with 6 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4 5 6
---------------------------------
[ 0, 0 ] | 1 6 6 3 2 6
[ 1, 0 ] | 6 6 1 6 6 6
[ 0, 1 ] | 6 3 6 6 4 6
[ 1, 1 ] | 6 6 6 6 2 6
Initial states: [ 5 ]
Final states: [ 1 ]
gap> AcceptedWordsByPredicaton(P3, 9);
[ [ 4, 1 ], [ 4, 2 ], [ 5, 3 ] ]
2.3-21 PermutedAlphabetPredicaton
‣ PermutedAlphabetPredicaton ( A, l ) | ( function ) |
‣ PermutedAbcPredicaton ( A, l ) | ( function ) |
The function PermutedAlphabetPredicaton
returns the Predicaton
of the Automaton
A with permuted alphabet according to l and accordingly swapped transition matrix rows. This is relevant for the first call of specific automata, where the variable order matters. E.g. the following automaton corresponds to the formula \(x+y=z\), where the the variable \(x\) is at position \(1\), \(y\) at \(2\) and \(z\) at \(3\). So creating the the automaton recognizing the same formula but with variable \(x\) at position \(3\), \(y\) at \(2\) and \(z\) at \(1\) needs the permuted alphabet, i.e. each letter is permuted according to the given variable position list l (here l=[ 3, 2, 1 ]
).
gap> A:=Automaton("det", 3, [ [ 0, 0, 0 ], [ 0, 0, 1 ], [ 1, 0, 0 ], [ 1, 0, 1 ],
> [ 0, 1, 0 ], [ 0, 1, 1 ], [ 1, 1, 0 ], [ 1, 1, 1 ] ],
> [ [ 1, 3, 3 ], [ 3, 2, 3 ], [ 3, 2, 3 ], [ 2, 3, 3 ], [ 3, 1, 3 ], [ 1, 3, 3 ],
> [ 1, 3, 3 ], [ 3, 2, 3 ] ], [ 1 ], [ 1 ]);;
gap> DisplayAut(A);
deterministic finite automaton on 8 letters with 3 states
and the following transitions:
| 1 2 3
---------------------------
[ 0, 0, 0 ] | 1 3 3
[ 0, 0, 1 ] | 3 2 3
[ 1, 0, 0 ] | 3 2 3
[ 1, 0, 1 ] | 2 3 3
[ 0, 1, 0 ] | 3 1 3
[ 0, 1, 1 ] | 1 3 3
[ 1, 1, 0 ] | 1 3 3
[ 1, 1, 1 ] | 3 2 3
Initial states: [ 1 ]
Final states: [ 1 ]
gap> P:=PermutedAlphabetPredicaton(A, [3,2,1]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 8 letters with 3 states,
the variable position list [ 1, 2, 3 ] and the following transitions:
| 1 2 3
---------------------------
[ 0, 0, 0 ] | 1 3 3
[ 1, 0, 0 ] | 3 2 3
[ 0, 0, 1 ] | 3 2 3
[ 1, 0, 1 ] | 2 3 3
[ 0, 1, 0 ] | 3 1 3
[ 1, 1, 0 ] | 1 3 3
[ 0, 1, 1 ] | 1 3 3
[ 1, 1, 1 ] | 3 2 3
Initial states: [ 1 ]
Final states: [ 1 ]
2.3-22 PredicatonFromAut
‣ PredicatonFromAut ( A, l, n ) | ( function ) |
The function PredicatonFromAut
returns the according to n resized (ExpandedPredicaton
(2.3-16)) Predicaton
of the Automaton
A with the permuted alphabet (PermutedAlphabetPredicaton
(2.3-21)), if the VariablePositionList
l isn't sorted.
gap> A:=Automaton("det", 3, [ [ 0, 0, 0 ], [ 0, 0, 1 ], [ 1, 0, 0 ], [ 1, 0, 1 ],
> [ 0, 1, 0 ], [ 0, 1, 1 ], [ 1, 1, 0 ], [ 1, 1, 1 ] ],
> [ [ 1, 3, 3 ], [ 3, 2, 3 ], [ 3, 2, 3 ], [ 2, 3, 3 ], [ 3, 1, 3 ], [ 1, 3, 3 ],
> [ 1, 3, 3 ], [ 3, 2, 3 ] ], [ 1 ], [ 1 ]);;
gap> DisplayAut(A);
deterministic finite automaton on 8 letters with 3 states
and the following transitions:
| 1 2 3
---------------------------
[ 0, 0, 0 ] | 1 3 3
[ 0, 0, 1 ] | 3 2 3
[ 1, 0, 0 ] | 3 2 3
[ 1, 0, 1 ] | 2 3 3
[ 0, 1, 0 ] | 3 1 3
[ 0, 1, 1 ] | 1 3 3
[ 1, 1, 0 ] | 1 3 3
[ 1, 1, 1 ] | 3 2 3
Initial states: [ 1 ]
Final states: [ 1 ]
gap> P:=PredicatonFromAut(A,[3,2,1],[1,2,3,4]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 16 letters with 3 states,
the variable position list [ 1, 2, 3, 4 ] and the following transitions:
| 1 2 3
------------------------------
[ 0, 0, 0, 0 ] | 1 3 3
[ 1, 0, 0, 0 ] | 3 2 3
[ 0, 0, 1, 0 ] | 3 2 3
[ 1, 0, 1, 0 ] | 2 3 3
[ 0, 1, 0, 0 ] | 3 1 3
[ 1, 1, 0, 0 ] | 1 3 3
[ 0, 1, 1, 0 ] | 1 3 3
[ 1, 1, 1, 0 ] | 3 2 3
[ 0, 0, 0, 1 ] | 1 3 3
[ 1, 0, 0, 1 ] | 3 2 3
[ 0, 0, 1, 1 ] | 3 2 3
[ 1, 0, 1, 1 ] | 2 3 3
[ 0, 1, 0, 1 ] | 3 1 3
[ 1, 1, 0, 1 ] | 1 3 3
[ 0, 1, 1, 1 ] | 1 3 3
[ 1, 1, 1, 1 ] | 3 2 3
Initial states: [ 1 ]
Final states: [ 1 ]
2.3-23 FinitelyManyWordsAccepted
‣ FinitelyManyWordsAccepted ( A ) | ( function ) |
The function FinitelyManyWordsAccepted
checks if a Predicaton
has only finitely many solutions, except the leading zero completion.
gap> P:=Predicaton(Automaton("det", 5, [ [ 0 ], [ 1 ] ],
> [ [ 4, 2, 2, 3, 5 ], [ 2, 2, 5, 2, 2 ] ], [ 1 ], [ 5 ]), [ 1 ]);;
gap> AcceptedWordsByPredicaton(P);
[ [ 4 ] ]
gap> FinitelyManyWordsAccepted(P);
true
2.3-24 PredicatonToRatExp
‣ PredicatonToRatExp ( P ) | ( function ) |
The function PredicatonToRatExp
returns the regular expression of the Automaton
or Predicaton
P.
gap> # Continued
gap> P:=Predicaton(Automaton("det", 5, [ [ 0 ], [ 1 ] ],
> [ [ 5, 5, 5, 4, 5 ], [ 2, 3, 4, 5, 5 ] ], [ 1 ], [ 4 ]), [ 1 ]);;
gap> PredicatonToRatExp(P);
[ 1 ][ 1 ][ 1 ][ 0 ]*
2.3-25 WordsOfRatExp
‣ WordsOfRatExp ( r, depth ) | ( function ) |
The function WordsOfRatExp
returns all words which can be created from the regular expression r by applying the star operator at most depth times.
gap> A:=Automaton("det", 3,
> [ [ 0, 0, 0 ], [ 1, 0, 0 ], [ 0, 1, 0 ], [ 1, 1, 0 ],
> [ 0, 0, 1 ], [ 1, 0, 1 ], [ 0, 1, 1 ], [ 1, 1, 1 ] ],
> [ [ 1, 3, 3 ], [ 3, 2, 3 ], [ 3, 2, 3 ], [ 2, 3, 3 ],
> [ 3, 1, 3 ], [ 1, 3, 3 ], [ 1, 3, 3 ], [ 3, 2, 3 ] ],
> [ 1 ], [ 1 ]);
< deterministic automaton on 8 letters with 3 states >
gap> r:=PredicatonToRatExp(A);
([ 1, 1, 0 ]([ 1, 0, 0 ]U[ 0, 1, 0 ]U[ 1, 1, 1 ])*
[ 0, 0, 1 ]U[ 0, 0, 0 ]U[ 1, 0, 1 ]U[ 0, 1, 1 ])*
gap> WordsOfRatExp(r, 1);
[ [ [ 1, 1, 0 ], [ 1, 0, 0 ], [ 0, 0, 1 ] ],
[ [ 1, 1, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
[ [ 1, 1, 0 ], [ 1, 1, 1 ], [ 0, 0, 1 ] ],
[ [ 1, 1, 0 ], [ ], [ 0, 0, 1 ] ],
[ [ 0, 0, 0 ] ], [ [ 1, 0, 1 ] ],
[ [ 0, 1, 1 ] ],
[ [ ] ] ]
2.3-26 WordsOfRatExpInterpreted
‣ WordsOfRatExpInterpreted ( r[, depth] ) | ( function ) |
The function WordsOfRatExpInterpreted
returns all words which can be created from the regular expression r by applying the star operator at most depth times (default depth=1
) as a list of natural numbers.
gap> A:=Automaton("det", 3,
> [ [ 0, 0, 0 ], [ 1, 0, 0 ], [ 0, 1, 0 ], [ 1, 1, 0 ],
> [ 0, 0, 1 ], [ 1, 0, 1 ], [ 0, 1, 1 ], [ 1, 1, 1 ] ],
> [ [ 1, 3, 3 ], [ 3, 2, 3 ], [ 3, 2, 3 ], [ 2, 3, 3 ],
> [ 3, 1, 3 ], [ 1, 3, 3 ], [ 1, 3, 3 ], [ 3, 2, 3 ] ],
> [ 1 ], [ 1 ]);
< deterministic automaton on 8 letters with 3 states >
gap> r:=PredicatonToRatExp(A);
([ 1, 1, 0 ]([ 1, 0, 0 ]U[ 0, 1, 0 ]U[ 1, 1, 1 ])*
[ 0, 0, 1 ]U[ 0, 0, 0 ]U[ 1, 0, 1 ]U[ 0, 1, 1 ])*
gap> WordsOfRatExpInterpreted(r, 1);
[ [ 0, 0, 0 ], [ 0, 1, 1 ], [ 1, 0, 1 ], [ 1, 1, 2 ], [ 1, 3, 4 ],
[ 3, 1, 4 ], [ 3, 3, 6 ] ]
2.4 Special functions on Predicata
2.4-1 IsValidInputList
‣ IsValidInputList ( l, n ) | ( function ) |
The function IsValidInputList
checks if the lists l and n correct lists for calling a Predicaton
, i.e. both lists must contain positive unique integers and l must be a subset of n.
gap> IsValidInputList([1,2,3], [1,2,3,4]);
true
gap> IsValidInputList([1,1,2,3], [1,2,3,4]);
Variable position list must contain unique positive integers.
false
gap> IsValidInputList([4,3,5], [4,5]);
Variable position list must be a subset of requested size list.
Compare: [ 4, 3, 5 ] with [ 4, 5 ]
false
gap> IsValidInputList([4,3,5], [3,4,5,6]);
true
2.4-2 BooleanPredicaton
‣ BooleanPredicaton ( B, n ) | ( function ) |
The function BooleanPredicaton
returns the Predicaton
which consists of one state. This state is a final state if B is "true"
and a non-final state if B is "false"
. The list n gives the resized variable position list.
gap> P1:=BooleanPredicaton("true",[]);;
gap> Display(P1);
Predicaton: deterministic finite automaton on 1 letter with 1 state,
the variable position list [ ] and the following transitions:
| 1
-------------
[ ] | 1
Initial states: [ 1 ]
Final states: [ 1 ]
gap> P2:=BooleanPredicaton("false", [ 1, 2 ]);;
gap> Display(P2);
Predicaton: deterministic finite automaton on 4 letters with 1 state,
the variable position list [ 1, 2 ] and the following transitions:
| 1
------------------
[ 0, 0 ] | 1
[ 1, 0 ] | 1
[ 0, 1 ] | 1
[ 1, 1 ] | 1
Initial states: [ 1 ]
Final states: [ ]
2.4-3 PredicataEqualAut
‣ PredicataEqualAut | ( global variable ) |
The variable PredicataEqualAut
returns the Automaton
which recognizes the language of \(x=y\).
gap> A:=PredicataEqualAut;
< deterministic automaton on 4 letters with 2 states >
gap> DisplayAut(A);
deterministic finite automaton on 4 letters with 2 states
and the following transitions:
| 1 2
---------------------
[ 0, 0 ] | 1 2
[ 1, 0 ] | 2 2
[ 0, 1 ] | 2 2
[ 1, 1 ] | 1 2
Initial states: [ 1 ]
Final states: [ 1 ]
2.4-4 EqualPredicaton
‣ EqualPredicaton ( l, n ) | ( function ) |
The function EqualPredicaton
returns the Predicaton
which recognizes the language of \(x=y\), where \(x\) is at position l[1] and \(y\) is at position l[2]. The list n gives the resized variable position list.
gap> P1:=EqualPredicaton([ 1, 2 ], [ 1, 2 ]);;
gap> Display(P1);
Predicaton: deterministic finite automaton on 4 letters with 2 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2
---------------------
[ 0, 0 ] | 1 2
[ 1, 0 ] | 2 2
[ 0, 1 ] | 2 2
[ 1, 1 ] | 1 2
Initial states: [ 1 ]
Final states: [ 1 ]
gap> P2:=EqualPredicaton([ 3, 4 ], [ 1, 2, 3, 4 ]);;
gap> Display(P2);
Predicaton: deterministic finite automaton on 16 letters with 2 states,
the variable position list [ 1, 2, 3, 4 ] and the following transitions:
| 1 2
---------------------------
[ 0, 0, 0, 0 ] | 1 2
[ 0, 0, 1, 0 ] | 2 2
[ 0, 0, 0, 1 ] | 2 2
[ 0, 0, 1, 1 ] | 1 2
[ 1, 0, 0, 0 ] | 1 2
[ 1, 0, 1, 0 ] | 2 2
[ 1, 0, 0, 1 ] | 2 2
[ 1, 0, 1, 1 ] | 1 2
[ 0, 1, 0, 0 ] | 1 2
[ 0, 1, 1, 0 ] | 2 2
[ 0, 1, 0, 1 ] | 2 2
[ 0, 1, 1, 1 ] | 1 2
[ 1, 1, 0, 0 ] | 1 2
[ 1, 1, 1, 0 ] | 2 2
[ 1, 1, 0, 1 ] | 2 2
[ 1, 1, 1, 1 ] | 1 2
Initial states: [ 1 ]
Final states: [ 1 ]
2.4-5 PredicataAdditionAut
‣ PredicataAdditionAut | ( global variable ) |
The variable PredicataAdditionAut
returns the Automaton
which recognizes the language \(x+y=z.\)
gap> A:=PredicataAdditionAut;
< deterministic automaton on 8 letters with 3 states >
gap> DisplayAut(A);
deterministic finite automaton on 8 letters with 3 states
and the following transitions:
| 1 2 3
---------------------------
[ 0, 0, 0 ] | 1 3 3
[ 1, 0, 0 ] | 3 2 3
[ 0, 1, 0 ] | 3 2 3
[ 1, 1, 0 ] | 2 3 3
[ 0, 0, 1 ] | 3 1 3
[ 1, 0, 1 ] | 1 3 3
[ 0, 1, 1 ] | 1 3 3
[ 1, 1, 1 ] | 3 2 3
Initial states: [ 1 ]
Final states: [ 1 ]
2.4-6 AdditionPredicaton
‣ AdditionPredicaton ( l, n ) | ( function ) |
The function AdditionPredicaton
returns the Predicaton
which recognizes the language \(x+y=z\), where \(x\) is at position l[1], \(y\) is at position l[2] and \(z\) is at position l[3]. The list n gives the resized variable position list.
gap> P:=AdditionPredicaton([1,2,3],[1,2,3]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 8 letters with 3 states,
the variable position list [ 1, 2, 3 ] and the following transitions:
| 1 2 3
---------------------------
[ 0, 0, 0 ] | 1 3 3
[ 1, 0, 0 ] | 3 2 3
[ 0, 1, 0 ] | 3 2 3
[ 1, 1, 0 ] | 2 3 3
[ 0, 0, 1 ] | 3 1 3
[ 1, 0, 1 ] | 1 3 3
[ 0, 1, 1 ] | 1 3 3
[ 1, 1, 1 ] | 3 2 3
Initial states: [ 1 ]
Final states: [ 1 ]
gap> DisplayAcceptedByPredicaton(P, [ 15, 15, 30 ]);
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
---------------------------------------------------------------------
0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2 | 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
3 | 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
4 | 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
5 | 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
6 | 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
7 | 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
8 | 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
9 | 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
10 | 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
11 | 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
12 | 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
13 | 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
14 | 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
15 | 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
2.4-7 AdditionPredicatonNSummands
‣ AdditionPredicatonNSummands ( N, l, n ) | ( function ) |
The function AdditionPredicatonNSummands
calls the function AdditionPredicatonNSummandsExplicit
(2.5-2) and returns the Predicaton
recognizing the language \(x_1+\ldots x_N=x_{N+1}\). The variables position list l gives the positions of the variables \(x_i\) and the list n gives the resized variable position list. The two functions AdditionPredicatonNSummandsIterative
(2.5-3) and AdditionPredicatonNSummandsRecursive
(2.5-4) create it in a more naive way, i.e. the first creates the Predicaton
from the simple automaton recognizing \(x+y=z\) step by step and the second creates the Predicaton
recursively by splitting the variable position list.
gap> P:=AdditionPredicatonNSummands(3, [ 1, 6, 3, 9 ], [ 1, 3, 6, 9 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 16 letters with 4 states,
the variable position list [ 1, 3, 6, 9 ] and the following transitions:
| 1 2 3 4
---------------------------------
[ 0, 0, 0, 0 ] | 1 4 2 4
[ 1, 0, 0, 0 ] | 4 2 4 4
[ 0, 0, 1, 0 ] | 4 2 4 4
[ 1, 0, 1, 0 ] | 2 4 3 4
[ 0, 1, 0, 0 ] | 4 2 4 4
[ 1, 1, 0, 0 ] | 2 4 3 4
[ 0, 1, 1, 0 ] | 2 4 3 4
[ 1, 1, 1, 0 ] | 4 3 4 4
[ 0, 0, 0, 1 ] | 4 1 4 4
[ 1, 0, 0, 1 ] | 1 4 2 4
[ 0, 0, 1, 1 ] | 1 4 2 4
[ 1, 0, 1, 1 ] | 4 2 4 4
[ 0, 1, 0, 1 ] | 1 4 2 4
[ 1, 1, 0, 1 ] | 4 2 4 4
[ 0, 1, 1, 1 ] | 4 2 4 4
[ 1, 1, 1, 1 ] | 2 4 3 4
Initial states: [ 1 ]
Final states: [ 1 ]
2.4-8 TimesNPredicaton
‣ TimesNPredicaton ( N, l, n ) | ( function ) |
The function TimesNPredicaton
returns the Predicaton
calls the function TimesNPredicatonExplicit
(2.5-5) and returns the Predicaton
recognizing the language \(N\cdot x=y\), where \(x\) is at position l[1] and \(y\) is at position l[2]. Note that \(N\cdot x\) is a shortcut for \(N\)-times the addition of \(x\). The list n gives the resized variable position list. The function TimesNPredicatonRecursive
creates the Predicaton
recursively from multiplications with \(N<10\).
gap> P:=TimesNPredicaton(10, [ 1, 2 ], [ 1, 2 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 4 letters with 11 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4 5 6 7 8 9 10 11
------------------------------------------------
[ 0, 0 ] | 1 11 2 11 3 11 4 11 5 11 11
[ 1, 0 ] | 6 11 7 11 8 11 9 11 10 11 11
[ 0, 1 ] | 11 1 11 2 11 3 11 4 11 5 11
[ 1, 1 ] | 11 6 11 7 11 8 11 9 11 10 11
Initial states: [ 1 ]
Final states: [ 1 ]
gap> AcceptedByPredicaton(P, [ 10, 60 ]);
[ [ 0, 0 ], [ 1, 10 ], [ 2, 20 ], [ 3, 30 ], [ 4, 40 ], [ 5, 50 ], [ 6, 60 ] ]
2.4-9 SumOfProductsPredicaton
‣ SumOfProductsPredicaton ( l, m, n ) | ( function ) |
The function SumOfProductsPredicatonExplicit
returns the Predicaton
recognizing the language \(\sum m_i \cdot x_i = 0\). The variables position list l gives the positions of the variables \(x_i\), the list m gives the integers (positive or negative) and the list n gives the resized variable position list.
gap> P:=SumOfProductsPredicaton([ 1, 2, 3 ], [ 7, 4, -5 ], [ 1, 2, 3 ]);
< Predicaton: deterministic finite automaton on 8 letters with 16 states
and the variable position list [ 1, 2, 3 ]. >
gap> DisplayAcceptedByPredicaton(P, [ 15, 15, 100 ]);
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
---------------------------------------------------------------------
0 | 0 -- -- -- -- 4 -- -- -- -- 8 -- -- -- -- 12
1 | -- -- 3 -- -- -- -- 7 -- -- -- -- 11 -- -- --
2 | -- -- -- -- 6 -- -- -- -- 10 -- -- -- -- 14 --
3 | -- 5 -- -- -- -- 9 -- -- -- -- 13 -- -- -- --
4 | -- -- -- 8 -- -- -- -- 12 -- -- -- -- 16 -- --
5 | 7 -- -- -- -- 11 -- -- -- -- 15 -- -- -- -- 19
6 | -- -- 10 -- -- -- -- 14 -- -- -- -- 18 -- -- --
7 | -- -- -- -- 13 -- -- -- -- 17 -- -- -- -- 21 --
8 | -- 12 -- -- -- -- 16 -- -- -- -- 20 -- -- -- --
9 | -- -- -- 15 -- -- -- -- 19 -- -- -- -- 23 -- --
10 | 14 -- -- -- -- 18 -- -- -- -- 22 -- -- -- -- 26
11 | -- -- 17 -- -- -- -- 21 -- -- -- -- 25 -- -- --
12 | -- -- -- -- 20 -- -- -- -- 24 -- -- -- -- 28 --
13 | -- 19 -- -- -- -- 23 -- -- -- -- 27 -- -- -- --
14 | -- -- -- 22 -- -- -- -- 26 -- -- -- -- 30 -- --
15 | 21 -- -- -- -- 25 -- -- -- -- 29 -- -- -- -- 33
2.4-10 TermEqualTermPredicaton
‣ TermEqualTermPredicaton ( l1, m1, i1, l2, m2, i2, n ) | ( function ) |
The function TermEqualTermPredicaton
returns the Predicaton
recognizing the language \(\sum {m_1}_i \cdot x_i + \sum i_1 = \sum {m_2}_i \cdot y_i + \sum i_2\). The variables position lists l1 and l2 gives the positions of the variables \(x_i\) and \(y_i\) respectively, the lists m1 and m2 gives the integers (positive or negative) and the list n gives the resized variable position list. Note: This function allows double occurrences of the same variable in both variable position lists l1 and l2. The lists i1 and i1 gives the integer additions on the left and right side, whereas l1 and m1 or l2 and m2 must contain at it's position "int"
. This function calls SumOfProductsPredicaton
(2.4-9).
gap> # 5*x1 + 2*x1 + 4 = 6*x2 + 1*x3
gap> P:=TermEqualTermPredicaton( [ 1, 1, "int" ], [ 5, 2, "int" ], [ 4 ],
> [ 2, 3 ], [ 6, 1 ], [ ], [ 1, 2, 3 ]);
< Predicaton: deterministic finite automaton on 8 letters with 14 states
and the variable position list [ 1, 2, 3 ]. >
gap> AcceptedByPredicaton(P);
[ [ 0, 0, 4 ], [ 1, 1, 5 ], [ 2, 2, 6 ], [ 2, 3, 0 ], [ 3, 3, 7 ], [ 3, 4, 1 ],
[ 4, 4, 8 ], [ 4, 5, 2 ], [ 5, 5, 9 ], [ 5, 6, 3 ], [ 6, 6, 10 ], [ 6, 7, 4 ],
[ 7, 8, 5 ], [ 8, 9, 6 ], [ 8, 10, 0 ], [ 9, 10, 7 ] ]
gap> DisplayAcceptedByPredicaton(P, [10, 15, 100]);
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
---------------------------------------------------------------------
0 | 4 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
1 | 11 5 -- -- -- -- -- -- -- -- -- -- -- -- -- --
2 | 18 12 6 0 -- -- -- -- -- -- -- -- -- -- -- --
3 | 25 19 13 7 1 -- -- -- -- -- -- -- -- -- -- --
4 | 32 26 20 14 8 2 -- -- -- -- -- -- -- -- -- --
5 | 39 33 27 21 15 9 3 -- -- -- -- -- -- -- -- --
6 | 46 40 34 28 22 16 10 4 -- -- -- -- -- -- -- --
7 | 53 47 41 35 29 23 17 11 5 -- -- -- -- -- -- --
8 | 60 54 48 42 36 30 24 18 12 6 0 -- -- -- -- --
9 | 67 61 55 49 43 37 31 25 19 13 7 1 -- -- -- --
10 | 74 68 62 56 50 44 38 32 26 20 14 8 2 -- -- --
2.4-11 GreaterEqualNPredicaton
‣ GreaterEqualNPredicaton ( N, l, n ) | ( function ) |
The function GreaterEqualNPredicaton
returns the Predicaton
recognizing the language \(x>=N\).
gap> P:=GreaterEqualNPredicaton(15, [ 1 ], [ 1 ]);;
gap> P:=SortedStatesAut(P);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 8 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6 7 8
------------------------------------
[ 0 ] | 7 6 3 3 4 4 6 8
[ 1 ] | 2 5 8 3 3 4 6 8
Initial states: [ 1 ]
Final states: [ 8 ]
gap> DisplayAcceptedByPredicaton(P, 29, true);
If the following words are accepted by the given automaton, then: Y,
otherwise if not accepted: n.
0: n 1: n 2: n 3: n 4: n 5: n 6: n 7: n 8: n 9: n
10: n 11: n 12: n 13: n 14: n 15: Y 16: Y 17: Y 18: Y 19: Y
20: Y 21: Y 22: Y 23: Y 24: Y 25: Y 26: Y 27: Y 28: Y 29: Y
2.4-12 GreaterNPredicaton
‣ GreaterNPredicaton ( N, l, n ) | ( function ) |
The function GreaterNPredicaton
returns the Predicaton
recognizing the language \(x>N\).
gap> P:=GreaterNPredicaton(15, [ 1 ], [ 1 ]);;
gap> P:=SortedStatesAut(P);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 6 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6
------------------------------
[ 0 ] | 5 2 2 3 4 6
[ 1 ] | 5 6 2 3 4 6
Initial states: [ 1 ]
Final states: [ 6 ]
gap> DisplayAcceptedByPredicaton(P, 29, true);
If the following words are accepted by the given automaton, then: Y,
otherwise if not accepted: n.
0: n 1: n 2: n 3: n 4: n 5: n 6: n 7: n 8: n 9: n
10: n 11: n 12: n 13: n 14: n 15: n 16: Y 17: Y 18: Y 19: Y
20: Y 21: Y 22: Y 23: Y 24: Y 25: Y 26: Y 27: Y 28: Y 29: Y
2.4-13 SmallerEqualNPredicaton
‣ SmallerEqualNPredicaton ( N, l, n ) | ( function ) |
The function SmallerEqualNPredicaton
returns the Predicaton
recognizing the language \(x<=N\).
gap> P:=SmallerEqualNPredicaton(15, [ 1 ], [ 1 ]);;
gap> P:=SortedStatesAut(P);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 6 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6
------------------------------
[ 0 ] | 6 2 3 3 4 5
[ 1 ] | 6 2 2 3 4 5
Initial states: [ 1 ]
Final states: [ 1, 3, 4, 5, 6 ]
gap> DisplayAcceptedByPredicaton(P, 29, true);
If the following words are accepted by the given automaton, then: Y,
otherwise if not accepted: n.
0: Y 1: Y 2: Y 3: Y 4: Y 5: Y 6: Y 7: Y 8: Y 9: Y
10: Y 11: Y 12: Y 13: Y 14: Y 15: Y 16: n 17: n 18: n 19: n
20: n 21: n 22: n 23: n 24: n 25: n 26: n 27: n 28: n 29: n
2.4-14 SmallerNPredicaton
‣ SmallerNPredicaton ( N, l, n ) | ( function ) |
The function SmallerNPredicaton
returns the Predicaton
recognizing the language \(x<N\).
gap> P:=SmallerNPredicaton(15, [ 1 ], [ 1 ]);;
gap> P:=SortedStatesAut(P);;
gap> Display(P);
Predicaton: deterministic finite automaton on 2 letters with 8 states,
the variable position list [ 1 ] and the following transitions:
| 1 2 3 4 5 6 7 8
------------------------------------
[ 0 ] | 8 2 7 4 4 5 5 7
[ 1 ] | 3 2 6 2 4 4 5 7
Initial states: [ 1 ]
Final states: [ 1, 3, 4, 5, 6, 7, 8 ]
gap> DisplayAcceptedByPredicaton(P, 29, true);
If the following words are accepted by the given automaton, then: Y,
otherwise if not accepted: n.
0: Y 1: Y 2: Y 3: Y 4: Y 5: Y 6: Y 7: Y 8: Y 9: Y
10: Y 11: Y 12: Y 13: Y 14: Y 15: n 16: n 17: n 18: n 19: n
20: n 21: n 22: n 23: n 24: n 25: n 26: n 27: n 28: n 29: n
2.4-15 GreaterEqualPredicaton
‣ GreaterEqualPredicaton ( l, n ) | ( function ) |
The function GreaterEqualPredicaton
returns the Predicaton
recognizing the language \(x>=y\) with the variables position list l giving the positions of the variables \(x\) and \(y\). The list n gives the resized variable position list.
gap> P:=GreaterEqualPredicaton([1,2],[1,2]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 4 letters with 2 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2
---------------------
[ 0, 0 ] | 1 2
[ 1, 0 ] | 2 2
[ 0, 1 ] | 1 1
[ 1, 1 ] | 1 2
Initial states: [ 2 ]
Final states: [ 2 ]
gap> DisplayAcceptedByPredicaton(P, 10);
If the following words are accepted by the given automaton, then: YES,
otherwise if not accepted: no.
| 0 1 2 3 4 5 6 7 8 9 10
-------------------------------------------------
0 | YES no no no no no no no no no no
1 | YES YES no no no no no no no no no
2 | YES YES YES no no no no no no no no
3 | YES YES YES YES no no no no no no no
4 | YES YES YES YES YES no no no no no no
5 | YES YES YES YES YES YES no no no no no
6 | YES YES YES YES YES YES YES no no no no
7 | YES YES YES YES YES YES YES YES no no no
8 | YES YES YES YES YES YES YES YES YES no no
9 | YES YES YES YES YES YES YES YES YES YES no
10 | YES YES YES YES YES YES YES YES YES YES YES
2.4-16 GreaterPredicaton
‣ GreaterPredicaton ( l, n ) | ( function ) |
The function GreaterPredicaton
returns the Predicaton
recognizing the language \(x>y\) with the variables position list l giving the positions of the variables \(x\) and \(y\). The list n gives the resized variable position list.
gap> P:=GreaterPredicaton([1,2],[1,2]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 4 letters with 2 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2
---------------------
[ 0, 0 ] | 1 2
[ 1, 0 ] | 1 1
[ 0, 1 ] | 2 2
[ 1, 1 ] | 1 2
Initial states: [ 2 ]
Final states: [ 1 ]
gap> DisplayAcceptedByPredicaton(P, 10);
If the following words are accepted by the given automaton, then: YES,
otherwise if not accepted: no.
| 0 1 2 3 4 5 6 7 8 9 10
-------------------------------------------------
0 | no no no no no no no no no no no
1 | YES no no no no no no no no no no
2 | YES YES no no no no no no no no no
3 | YES YES YES no no no no no no no no
4 | YES YES YES YES no no no no no no no
5 | YES YES YES YES YES no no no no no no
6 | YES YES YES YES YES YES no no no no no
7 | YES YES YES YES YES YES YES no no no no
8 | YES YES YES YES YES YES YES YES no no no
9 | YES YES YES YES YES YES YES YES YES no no
10 | YES YES YES YES YES YES YES YES YES YES no
2.4-17 SmallerEqualPredicaton
‣ SmallerEqualPredicaton ( l, n ) | ( function ) |
The function SmallerEqualPredicaton
returns the Predicaton
recognizing the language \(x<=y\) with the variables position list l giving the positions of the variables \(x\) and \(y\). The list n gives the resized variable position list.
gap> P:=SmallerEqualPredicaton([ 1, 2 ], [ 1, 2 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 4 letters with 2 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2
---------------------
[ 0, 0 ] | 1 2
[ 1, 0 ] | 1 1
[ 0, 1 ] | 2 2
[ 1, 1 ] | 1 2
Initial states: [ 2 ]
Final states: [ 2 ]
gap> DisplayAcceptedByPredicaton(P, 10);
If the following words are accepted by the given automaton, then: YES,
otherwise if not accepted: no.
| 0 1 2 3 4 5 6 7 8 9 10
-------------------------------------------------
0 | YES YES YES YES YES YES YES YES YES YES YES
1 | no YES YES YES YES YES YES YES YES YES YES
2 | no no YES YES YES YES YES YES YES YES YES
3 | no no no YES YES YES YES YES YES YES YES
4 | no no no no YES YES YES YES YES YES YES
5 | no no no no no YES YES YES YES YES YES
6 | no no no no no no YES YES YES YES YES
7 | no no no no no no no YES YES YES YES
8 | no no no no no no no no YES YES YES
9 | no no no no no no no no no YES YES
10 | no no no no no no no no no no YES
2.4-18 SmallerPredicaton
‣ SmallerPredicaton ( l, n ) | ( function ) |
The function SmallerPredicaton
returns the Predicaton
recognizing the language \(x<y\) with the variables position list l giving the positions of the variables \(x\) and \(y\). The list n gives the resized variable position list.
gap> P:=SmallerPredicaton([ 1, 2 ], [ 1, 2 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 4 letters with 2 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2
---------------------
[ 0, 0 ] | 1 2
[ 1, 0 ] | 2 2
[ 0, 1 ] | 1 1
[ 1, 1 ] | 1 2
Initial states: [ 2 ]
Final states: [ 1 ]
gap> DisplayAcceptedByPredicaton(P, 10);
If the following words are accepted by the given automaton, then: YES,
otherwise if not accepted: no.
| 0 1 2 3 4 5 6 7 8 9 10
-------------------------------------------------
0 | no YES YES YES YES YES YES YES YES YES YES
1 | no no YES YES YES YES YES YES YES YES YES
2 | no no no YES YES YES YES YES YES YES YES
3 | no no no no YES YES YES YES YES YES YES
4 | no no no no no YES YES YES YES YES YES
5 | no no no no no no YES YES YES YES YES
6 | no no no no no no no YES YES YES YES
7 | no no no no no no no no YES YES YES
8 | no no no no no no no no no YES YES
9 | no no no no no no no no no no YES
10 | no no no no no no no no no no no
2.5 Detailed look at the special functions on Predicata
This section explains how the sums and products are computed and describes different methods. The explicit method, which computes the transition matrix with a transition formula, is more efficient than the other given methods. The recursive and iterative methods explain a more naive way how to compute the requested automaton, but are lacking in speed. Therefore they are not used in any further computation.
2.5-1 AdditionPredicaton3Summands
‣ AdditionPredicaton3Summands ( l, n ) | ( function ) |
‣ AdditionPredicaton4Summands ( l, n ) | ( function ) |
‣ AdditionPredicaton5Summands ( l, n ) | ( function ) |
The functions AdditionPredicatonNSummands
returns the Predicaton
recognizing the language \(x_1+\ldots x_N=x_{N+1}\) for \(N=3,4,5\).
gap> P:=AdditionPredicaton3Summands([ 1, 2, 3, 4 ],[ 1, 2, 3, 4 ]);
< Predicaton: deterministic finite automaton on 16 letters with 4 states
and the variable position list [ 1, 2, 3, 4 ]. >
gap> P:=AdditionPredicaton4Summands([ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ]);
< Predicaton: deterministic finite automaton on 32 letters with 5 states
and the variable position list [ 1, 2, 3, 4, 5 ]. >
gap> P:=AdditionPredicaton5Summands([ 1, 2, 3, 4, 5, 6 ], [ 1, 2, 3, 4, 5, 6 ]);
< Predicaton: deterministic finite automaton on 64 letters with 6 states
and the variable position list [ 1, 2, 3, 4, 5, 6 ]. >
2.5-2 AdditionPredicatonNSummandsExplicit
‣ AdditionPredicatonNSummandsExplicit ( N, l, n ) | ( function ) |
The function AdditionPredicatonNSummandsExplicit
returns the Predicaton
recognizing the language \(x_1+\ldots x_N=x_{N+1}\). The TransitionTable
is assigned explicitly with the following transition property: The \(i\)-th state denotes carry \(i\) and there is a transition from state \(i\) to state \(j\) for the letter \(a\) if \(\sum_{i=1}^{N}a_i = a_{N+1} + i + 2 (j-i)\) holds. The variables position list l gives the positions of the variables \(x_i\) and the list n gives the resized variable position list.
gap> P:=AdditionPredicatonNSummandsExplicit(3, [6, 11, 2, 9], [2, 3, 6, 7, 9, 11]);
< Predicaton: deterministic finite automaton on 64 letters with 4 states
and the variable position list [ 2, 3, 6, 7, 9, 11 ]. >
gap> P:=AdditionPredicatonNSummandsExplicit(11, [ 1..12 ], [ 1..12 ]);
< Predicaton: deterministic finite automaton on 4096 letters with 12 states
and the variable position list
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ]. >
2.5-3 AdditionPredicatonNSummandsIterative
‣ AdditionPredicatonNSummandsIterative ( N, l, n ) | ( function ) |
The function AdditionPredicatonNSummandsIterative
returns the Predicaton
recognizing the language \(x_1+\ldots x_N=x_{N+1}\). The Predicaton
is created by intersection \((N-1)\)-times the simple automaton recognizing \(x+y=z\). Due to intersecting and minimizing that often, this function shouldn't be used for large \(N\) (for example \(N>10\)).
gap> P:=AdditionPredicatonNSummandsIterative(7, [ 1..8 ], [ 1..8 ]);
< Predicaton: deterministic finite automaton on 256 letters with 8 states
and the variable position list [ 1, 2, 3, 4, 5, 6, 7, 8 ]. >
2.5-4 AdditionPredicatonNSummandsRecursive
‣ AdditionPredicatonNSummandsRecursive ( N, l, n ) | ( function ) |
The function AdditionPredicatonNSummandsRecursive
returns the Predicaton
recognizing the language \(x_1+\ldots x_N=x_{N+1}\). The Predicaton
is created recursively splitting the variable position list until a length of 3 is reached, where the base cases are the simple automaton recognizing \(x+y=z\). It is slightly faster than AdditionPredicatonNSummandsIterative
(2.5-3) but nevertheless it shouldn't be used for large \(N\) (for example \(N>10\)).
gap> P:=AdditionPredicatonNSummandsRecursive(7, [ 1..8 ], [ 1..8 ]);
< Predicaton: deterministic finite automaton on 256 letters with 8 states
and the variable position list [ 1, 2, 3, 4, 5, 6, 7, 8 ]. >
2.5-5 TimesNPredicatonExplicit
‣ TimesNPredicatonExplicit ( N, l, n ) | ( function ) |
The function TimesNPredicatonExplicit
returns the Predicaton
recognizing the language \(N\cdot x=y\). The TransitionTable
is assigned explicitly with the following transition property: The \(i\)-th state denotes carry \(i\) and there is a transition from state \(i\) to state \(j\) for the letter \(a\) if \(N \cdot a_1 = a_2 + i + 2 (j - i).\) The variables position list l gives the positions of the variables \(x_i\) and the list n gives the resized variable position list.
gap> P:=TimesNPredicatonExplicit(1000, [ 1, 2 ], [ 1, 2 ]);
< Predicaton: deterministic finite automaton on 4 letters with 1001 states
and the variable position list [ 1, 2 ]. >
gap> IsAcceptedByPredicaton(P, [ 1, 1000 ]);
true
gap> IsAcceptedByPredicaton(P, [ 2, 2000 ]);
true
gap> IsAcceptedByPredicaton(P, [ 3, 3000 ]);
true
2.5-6 TimesNPredicatonRecursive
‣ TimesNPredicatonRecursive ( N, l, n ) | ( function ) |
The function TimesNPredicatonRecursive
returns the Predicaton
recognizing the language \(N \cdot x=y\). It splits the the multiplication into a multiplications of \(N_1\) and \(N_2\), where \(N = N_1 \cdot N_2\).
gap> P:=TimesNPredicatonRecursive(100, [1,2],[1,2]);
< Predicaton: deterministic finite automaton on 4 letters with 101 states
and the variable position list [ 1, 2 ]. >
gap> P:=TimesNPredicatonRecursive(1000, [1,2],[1,2]);
< Predicaton: deterministic finite automaton on 4 letters with 1001 states
and the variable position list [ 1, 2 ]. >
2.5-7 Times2Predicaton
‣ Times2Predicaton ( l, n ) | ( function ) |
‣ Times3Predicaton ( l, n ) | ( function ) |
‣ Times4Predicaton ( l, n ) | ( function ) |
‣ Times5Predicaton ( l, n ) | ( function ) |
‣ Times6Predicaton ( l, n ) | ( function ) |
‣ Times7Predicaton ( l, n ) | ( function ) |
‣ Times8Predicaton ( l, n ) | ( function ) |
‣ Times9Predicaton ( l, n ) | ( function ) |
The functions Times2Predicaton
, Times3Predicaton
,... returns the Predicaton
recognizing the language \(N \cdot x=y\) for \(N=2,\ldots,9\).
gap> P:=Times2Predicaton([ 1, 2 ], [ 1, 2 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 4 letters with 3 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3
------------------------
[ 0, 0 ] | 1 3 3
[ 1, 0 ] | 2 3 3
[ 0, 1 ] | 3 1 3
[ 1, 1 ] | 3 2 3
Initial states: [ 1 ]
Final states: [ 1 ]
gap> P:=Times3Predicaton([ 1, 2 ], [ 1, 2 ]);;
gap> Display(P);
Predicaton: deterministic finite automaton on 4 letters with 4 states,
the variable position list [ 1, 2 ] and the following transitions:
| 1 2 3 4
---------------------------
[ 0, 0 ] | 1 4 2 4
[ 1, 0 ] | 4 3 4 4
[ 0, 1 ] | 4 1 4 4
[ 1, 1 ] | 2 4 3 4
Initial states: [ 1 ]
Final states: [ 1 ]