[MathJax on]
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 0s and 1s, the corresponding natural number. Note again that here the ∑ 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 ℕ × ℕ. 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 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+... 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⋅ x=y, where x is at position l[1] and y is at position l[2]. Note that N⋅ 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 ∑ m_i ⋅ 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 ∑ m_1_i ⋅ x_i + ∑ i_1 = ∑ m_2_i ⋅ y_i + ∑ 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+... 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+... 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+... 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+... 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⋅ 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 ⋅ x=y. It splits the the multiplication into a multiplications of N_1 and N_2, where N = N_1 ⋅ 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 ⋅ x=y for N=2,...,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 ]