MINISTRY OF EDUCATION AND TRAINING
HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY
——————————

Nguyen Huy Truong

RESEARCH ON DEVELOPMENT OF METHODS
OF GRAPH THEORY AND AUTOMATA
IN STEGANOGRAPHY AND SEARCHABLE ENCRYPTION

DOCTORAL DISSERTATION IN MATHEMATICS AND INFORMATICS

Hanoi - 2020


MINISTRY OF EDUCATION AND TRAINING
HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY
——————————

Nguyen Huy Truong

RESEARCH ON DEVELOPMENT OF METHODS
OF GRAPH THEORY AND AUTOMATA
IN STEGANOGRAPHY AND SEARCHABLE ENCRYPTION
Major: Mathematics and Informatics
Major code: 9460117

DOCTORAL DISSERTATION IN MATHEMATICS AND INFORMATICS

SUPERVISORS:
1. Assoc. Prof. Dr. Sc. Phan Thi Ha Duong

valuable comments and helpful advice.
I give thanks to PhD students of Late Assoc. Prof. Dr. Phan Trung Huy for sharing
and exchanging information in steganography and searchable encryption.
Finally, I must also thank my family for supporting all my work.


CONTENTS

Page
LIST OF SYMBOLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
LIST OF ABBREVIATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
v
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
CHAPTER 1 PRELIMINARIES . . . . . . . . . . . . . . . . . . . . . . . 4
1.1 Basic Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1.1 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1.2 Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1.3 Deterministic Finite Automata . . . . . . . . . . . . . . . . . . . .
6
m
1.1.4 The Galois Field GF (p ) . . . . . . . . . . . . . . . . . . . . . . .
7

4.2
4.3
4.4
4.5

Mathematical Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Automata Models for Solving The LCS Problem . . . . . . . . . . . . . . .
Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CHAPTER 5 CRYPTOGRAPHY BASED ON STEGANOGRAPHY
AND AUTOMATA METHODS FOR SEARCHABLE ENCRYPTION . .
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 A Novel Cryptosystem Based on The Data Hiding Scheme (2, 9, 8) . . . . .
5.3 Automata Technique for Exact Pattern Matching on Encrypted Data . . .
5.4 Automata Technique for Approximate Pattern Matching on Encrypted Data
5.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CONCLUSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
LIST OF PUBLICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

57
61
66
67
68
68
70
74

The length of a LCS(p, x)
LeftID(u)
The least element the leftmost location of u
Rmp (u)
The last component of LeftID(u) in p
(I, M, K, Em, Ex) A data hiding scheme
I
A set of all image blocks with the same size and image format
M
A finite set of secret elements
K
A finite set of secret keys
Em
An embedding function embeds a secret element in an image
block
Ex
An extracting function extracts an embedded secret element
from an image block
qcolour
The number of different ways to change the colour of each
pixel in an arbitrary image block
I
An image block
M
A secret element
K
A secret key
Adjacent(cp , a)
An adjacent vertex of cp
A string of length c

CTL
EBOM
ER
FJS
FOPA
FSBNDM
HASH
HCIH
LBNDM
LCS
LSB
MSDR
MSE
NP
OPA
PA
PCT
PSNR
RGB
SA
SAE
SBNDM
SE
SSE
TVSBS
WF
WL

Average Optimal Shift Or
Brute Force


iv


LIST OF FIGURES

Figure
Figure
Figure
Figure
Figure

1.1.
1.2.
1.3.
1.4.
1.5.

A simple graph . . . . . . . . . . . . . . . . . . .
A spanning tree of the graph given in Figure 1.1
The transition diagram of A in Example 1.3 . .
The basic diagram of digital image steganography
The degree of appearance of the pattern p . . . .

.
.
.
.
.


.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.


Table 2.4. The payload, ER and PSNR for the optimal data hiding scheme
(1, 2n − 1, n) for palette images with qcolour = 1 . . . . . . . . . . . . .
Table 2.5. The payload, ER and PSNR for the near optimal data hiding scheme
(2, 9, 8) for gray images with qcolour = 3 . . . . . . . . . . . . . . . . . .
Table 2.6. The payload, ER and PSNR for the near optimal data hiding scheme
(2, 9, 8) for palette images with qcolour = 3 . . . . . . . . . . . . . . . .
Table 2.7. The comparisons of embedding and extracting time between the
chapter’s and Chang et al.’s approach for the same optimal data hiding
scheme (1, N, log2 (N + 1) ), where N = 2n − 1, for the binary image
with qcolour = 1. Time is given in second unit . . . . . . . . . . . . . .
Table
Table
Table
Table
Table
Table
Table
Table
Table
Table

3.1. The performing steps of the MR1 algorithm . . . . . . . . .
3.2. Experimental results on rand4 problem . . . . . . . . . . .
3.3. Experimental results on rand8 problem . . . . . . . . . . .
3.4. Experimental results on rand16 problem . . . . . . . . . . .
3.5. Experimental results on rand32 problem . . . . . . . . . . .
3.6. Experimental results on rand64 problem . . . . . . . . . . .
3.7. Experimental results on rand128 problem . . . . . . . . . .
3.8. Experimental results on rand256 problem . . . . . . . . . .
3.9. Experimental results on a genome sequence (with |Σ| = 4) .

.
.
.
.

.
.
.
.
.
.
.
.
.
.

36
37
37

37

.
.
.
.
.
.
.
.

.
.
.
.

30
30
31


INTRODUCTION
In the modern life, when the use of computer and Internet is more and more essential,
digital data (information) can be copied as well as accessed illegally. As a result,
information security becomes increasingly important. There are two popular methods to
provide security, which are cryptography and data hiding [2, 5, 6, 20, 56, 62, 81].
Cryptography is used to encrypt data in order to make the data unreadable by a third
party [5]. Data hiding is used to embed data in digital media. Based on the purpose of
the application, data hiding is generally divided into steganography that hides the
existence of data to protect the embedded data and watermarking that protects the
copyright ownership and authentication of the digital media carrying the embedded data.
Steganography can be used as an alternative way to cryptography.
However,
steganography will become weak if attackers detect existence of hidden data. Hence
integrating cryptography with steganography is as a third choice for data security
[2, 5, 6, 12, 19, 61, 62, 81, 86, 93].
With the rapid development of applications based on Internet infrastructure, cloud
computing becomes one of the hottest topics in the information technology area. Indeed, it
is a computing system based on Internet that provides on-demand services from application
and system software, storage to processing data. For example, when cloud users use the
storage service, they can upload information to the servers and then access it on the Internet

Based on the results and suggestions introduced by P. T. Huy et al., the dissertation
will focus on following four problems in steganography and searchable encryption:
- Digital image steganography;
- Exact pattern matching;
- Longest common subsequence;
- Searchable encryption.
The first problem is stated newly in Chapter 2, the three remaining problems are recalled
and clarified in Chapter 1.
For the first three problems, the dissertation’s work is to find new and efficient solutions
using graph theory and automata. Then they will be used and applied to solve the last
problem.
The dissertation has been completed with structure as follows.
Apart from
Introduction at the beginning and Conclusion at the end of the dissertation, the main
content of it is divided into five chapters.
Chapter 1.
Preliminaries. This chapter recalls basic knowledge indicated
throughout the dissertation (strings, graph, deterministic finite automata, digital images,
the basic model of digital image steganography, some parameters to determine the
quality of digital image steganography, the exact pattern matching problem, the longest
common subsequence problem, and searchable encryption), re-presents important
concepts and results used and researched on development in remaining chapters of the
dissertation (adjacency list, breadth first search, Galois field, the fastest optimal parity
assignment method, the module method and the concept of the maximal secret data
ratio, the concept of the degree of fuzziness (appearance), the Knapsack Shaking
approach, and the definition of a cryptosystem).
Chapter 2. Digital image steganography based on the Galois field using
graph theory and automata. Firstly, from some proposed concepts of optimal and
near optimal secret data hiding schemes, this chapter states the interest problem in digital
image steganography. Secondly, the chapter proposes a new approach based on the Galois

secret data, respectively. In searchable encryption, the cryptosystem can be used to encode
and decode secret data on users side and pattern matching algorithms can be used to
perform pattern search on cloud providers side.
The contents of the dissertation are written based on the paper [T1] published in,
the revised manuscript [T4] submitted to KSII Transactions on Internet and Information
Systems (ISI), and the papers [T2, T3] published in Journal of Computer Science and
Cybernetics in 2019. The main results of the dissertation have been presented at:
- Seminar on Mathematical Foundations for Computer Science at Institute of
Mathematics, Vietnam Academy of Science and Technology,
- The 9th Vietnam Mathematical Congress, Nha Trang, August 14-18, 2018,
- Seminar at School of Applied Mathematics and Informatics, Hanoi University of
Science and Technology.

3


CHAPTER 1

PRELIMINARIES
This chapter will attempt to recall terminologies, concepts, algorithms and results which
are really needed in order to present the dissertation’s new results clearly and logically,
as well as help readers follow the content of the dissertation easily. The background
knowledge re-presented here consists of basic structures (Section 1.1: strings (Subsection
1.1.1), graph (Subsection 1.1.2), deterministic finite automata (Subsection 1.1.3), and the
Galois field GF (pm ) (Subsection 1.1.4)), digital image steganography (Section 1.2), exact
pattern matching (Section 1.3 ), longest common subsequence (Section 1.4) and searchable
encryption (Section 1.5).

1.1 Basic Structures
1.1.1 Strings

Cover
Image

Embed

Stego
Image

Stego
Image

Extract

Cover
Image

Send
to
An edge connecting a vertex to itself
is called
a loop. Multiple edges are edges connecting
the same vertices. A graph having no loops and no multiple edges is called a simple graph.
In a simple graph, the edge associated to an unordered pair of vertices {i, j} is called the
Secret Key
Secret
edge {i,
j}. Key
Two vertices i and j in a graph G are called adjacent if they are vertices of an edge of
G.
Sender

2

1, 3, 4

3

1, 2, 4, 5

4

2, 3, 5

5

3, 4

Given a simple graph G, a subgraph of G that is a tree including every vertex of G is
called a spanning tree of G. A spanning tree of a connected simple graph can be built by
using breadth first search (BFS). This algorithm is shown in pseudo-code as follows.
Breadth First Search:
Input: A connected simple graph G with vertices ordered as i1 , i2 , . . . , in .
Output: A spanning tree T .
Set T to be a tree consisting only i1 ;
Set L to be an empty list;
Put i1 in L
While (L is not empty)
{
Remove the first vertex i from L;
5


using BFS as in Figure 1.2.

1
2

3

4

5

2

3

4

5

Figure 1.2. A spanning tree of the graph given in Figure 1.1

A graph with directed edges (or arcs) is called a directed graph. Each arc is associated
with the ordered pair of vertices. In a simple directed graph, the arc associated with the
ordered pair (i, j) called the arc (i, j). And the vertex i is said to be adjacent to the vertex
j and the vertex j is said to be adjacent from the vertex i.
1.1.3 Deterministic Finite Automata
Study on the problem of the construction and the use of deterministic finite automata
is one of objectives of the dissertation. Hence, this subsection will clarify this model of
computation [44, 82].
Definition 1.1 ([44]). Let Σ be a finite alphabet. A deterministic finite automaton


b

q0

q0

q1

q1

q2

q1

q2

q2

q2

a

q0

a, b

b

q1

Image
m
Galois field GF (p ), where p is prime and m ≥ 1 is an integer [88]. The algebraic structure
Send to
will be used in Chapter 2.
Let p be a prime number. Define Zp [x] to be the set of all polynomials with the variable
x, whose coefficients belong to the field Zp . Addition and multiplication in Zp [x] are defined
Secret Key
Key the coefficients modulo p at the end.
in the usual way andSecret
then reduce
For f (x) ∈ Zp [x], the degree of f (x), denoted by deg(f ), is the largest exponent of
Sender
Receiver
x in f (x). A polynomial
f (x) ∈ Zp [x] is called to be irreducible if there does
not exist
7

Cover
Image


polynomials f1 (x), f2 (x) ∈ Zp [x] such that
f (x) = f1 (x)f2 (x),
where deg(f1 ) > 0 and deg(f2 ) > 0.
Let f (x) ∈ Zp [x] be an irreducible polynomial with deg(f ) = m ≥ 1. Define
Zp [x]/(f (x)) to be the set of pm polynomials of degree at most m − 1 in Zp [x]. Addition
and multiplication in Zp [x]/(f (x)) are given as in Zp [x], followed by a reduction modulo
f (x). Then Zp [x]/(f (x)) with these operations is a field having pm elements, called the

representing a pixel and is limited by 8 bits. For a string of 8 bits, call palette images 8-bit
palette images.
The objective of digital image steganography is to protect data by hiding the data in
a digital image well enough so that unauthorized users will not even be aware of their
existence [21, 18]. Figure 1.4 shows the basic model of digital image steganography, where
the cover image is a digital image used as a carrier to embed secret data into, the stego
image is digital image obtained after embedding secret data into the cover image by the
8


function block Embed with the secret key on the Sender side. For steganography generally,
a
a, b
the secret data needs to be extracted fully by the block Extract with the secret key on
the Receiver side [20, 61, 63, 76].
The total number of the secret data
in the cover image is called
b sequence
abits embedded
q
q
q
2
1
0
a Payload. Corresponding to a certain Payload, to measure the embedding capacity of the
cover image, the embedding rate (ER) is used and defined as follows [104].
ER =

b

Send to

Secret Key

Secret Key

Sender

Receiver

Figure 1.4. The basic diagram of digital image steganography

The peak signal to noise ratio (PSNR) is used to evaluate quality of stego image. Based
on the value of PSNR, we can know the degree of similarity between the cover image and
stego image. If the PSNR value is high, then quality of stego image is high. Conversely,
quality of stego image is low. In general, for the digital image, PSNR is defined by the
2
4
following formula [20, 53]
2
255
PSNR = 10 log10
(dB),
(1.2)
MSE
1
where
MSEwhere 9 is the number of pixels in any image block, 8
is the number of secret bits which can be embedded in a block by changing colours of at
most 2 pixels in the block. This scheme is near optimal for gray and palette images with

algorithms used by users and servers in SSE. Firstly, Section 5.2 constructs a novel
cryptosystem based on the data hiding scheme proposed in Chapter 2, applies this
cryptosystem to the process of encrypting and decrypting a secret data sequence and
discusses some security analyses. Sections 5.3 and 5.4 then use the automata approach in
Chapters 3 and 4 to design exact and approximate pattern matching algorithms on
secrete data encrypted by the cryptosystem proposed in Section 5.2. Finally, Section 5.5
provides the chapter’s conclusions.

5.2 A Novel Cryptosystem Based on The Data Hiding Scheme
(2, 9, 8)
This section 5.2 proposes a new cryptosystem, a major component in SSE, based on
the data hiding scheme (2, 9, 8) proposed in Chapter 2 (Theorem 5.1 and Security analyses
(5.3), (5.4)) and applies this cryptosystem to the process of encrypting and decrypting a
secret data sequence (Proposition 5.1 and Security analyses (5.9), (5.10)).
Call Em a function which is derived from the function Em by removing two Statements
(2.5) and (2.6). As in Definition 2.10, the state q in Statement (2.4) is computed by
q = δ(q, M ) = δ2 (q, M ), where q, M ∈ GF 4 (22 ) and

δ2 (q, M ) =



{(it , at )|1 ≤ it ≤ 9, t = 1, k , k ≤ 2, vit ∈ S, at ∈ GF (22 )\{0},




k
at vit (on GF 4 (22 )}



and the function Em is shown as follows.
The function Em (computing the flip information q):
q = q0 ;
For i = 1 to N Do q = δ(q, Ii );
q = δ(q, M );
Ex is a function obtained from Ex by replacing image blocks Iit with image blocks Iit in
Statement (2.5) and then inserting two Statements (2.6) and (2.5) before Statement (2.7)
2
in Ex, then the function Ex holds Ex : 2{1,2,...,9}×GF (2 )\{0} × I × K → M, and the
function Ex is given as follows.
The function Ex (extracting M from I ):
I = I;
For each (it , at ) in q Do Iit = Adjacent(Iit , at );
q = q0 ;
For i = 1 to N Do q = δ(q, Ii );
M = q;
By Proposition 2.5, we have ∀(I, M, K) ∈ I × M × K, Ex(Em(I, M, K), K) = M and
for the construction of two functions Em and Ex , similarly, we also follow
∀(I, M, K) ∈ I × M × K, Ex (Em (I, M, K), I, K) = M.

(5.2)

Remark 5.1. From defining two functions Em and Ex as above, all image blocks I used
are not changed.
Consider Σ to be an alphabet of size 256. Set P = Σ.
By the decimal representation of the vector space GF 4 (22 ) over the field GF (22 ) in
Section 2.4, then |P| = |GF 4 (22 )| = 256, hence there exists a bijective function f from P
to GF 4 (22 ), denote the inverse function of f by f −1 . Put F to be a set of all f .
From the function δ2 , the state q of the automaton A(I, M, K) computed by

Set E = {ek |k ∈ K }, D = {dk |k ∈ K }. From Definition 1.13, the correctness of the
cryptosystem (P, C, K , E, D) is guaranteed by the following theorem.
Theorem 5.1. Let ∀x ∈ P, ∀k ∈ K , ek ∈ E and dk ∈ D. Then dk (ek (x)) = x.
Proof. Set M = f (x), q = Em (I, M, K), B = h(q), then ek (x) = B = y. We have
h−1 (y) = h−1 (B) = q, Ex (q, I, K) = M by Formula (5.2), f −1 (M ) = x, then
dk (y) = x.
Security analysis of the cryptosystem (P, C, K , E, D): Assume that publish parameters
the flip graph G, Em , Ex , GF 4 (22 ) and h in the cryptosystem (P, C, K , E, D). The
plaintext x is obtained from y by the Formula
x = dk (y) = f −1 (Ex (h−1 (y), I, K)).
So, to have accurately x, we need to know S and k = (f, K, I). The number of choices for
the image block I is 2569 with gray images, 29t with palette images, where t is the number
of bits to represent colour indexes. Furthermore, by Formula (2.45), the security of the
cryptosystem (P, C, K , E, D) is given by the following formula
c39 9!218 28 !2569 = c39 9!290 28 ! for gray images,

(5.3)

c39 9!218 29t 28 ! = c39 9!218+9t 28 ! for palette images.

(5.4)

or

Remark 5.2. By Remark 5.1, all pairs of functions (ek , dk ) in the cryptosystem
(P, C, K , E, D) do not make the image blocks I change for ∀k ∈ K , k = (f, K, I). In
addition, we can see that encrypting and hiding are done at the same time.
Consider an arbitrary subset of image blocks F as an input image, F ⊂ I,
F = {F1 , F2 , . . . , Ft2 }, t2 is the number of image blocks. Next, Section 5.2 gives a way
applying the cryptosystem (P, C, K , E, D) to the process of encrypting and decrypting

For i = 1 to t3 Do
{
ki = (f, K iK , FiF );

(5.7)

xi = dki (yi );

(5.8)

iK = (iK − 1) mod t1 + 1;
iF = (iF − 1) mod t2 + 1;
}
x = x1 x2 ..xt3 ;
Propostion 5.1. Let F, x, K and the cryptosystem (P, C, K , E, D) based on the data
hiding (2, 9, 8) as above. Then dK (eK (x)) = x.
Proof. Clearly, ∀i, i = 1, t3 , ki determined in Statement (5.5) is the same as in Statement
(5.7). In addition, by Theorem 5.1, xi is encrypted by Statement (5.6) and obtained by
Statement (5.8) such that xi = xi . Then x = x , hence dK (eK (x)) = x.
Security analysis of process of encrypting and decrypting the secret data x using two
algorithms eK and dK : Assume that also publish parameters as in the cryptosystem
(P, C, K , E, D). Hence, to restore exactly x, we need to know S and K . The number of
choices for S is c39 9! by Formula (5.1). The number of choices for K is 28 !218t1 2569t2 (for
gray images), 28 !218t1 29tt2 (for palette images, where t is the number of bits to represent
colour indexes). Then for a brute force attack, the number of all possible combinations of
S and K used in two algorithms eK and dK is
c39 9!28 !218t1 2569t2 = c39 9!28 !218t1 +72t2 for gray images,
73

(5.9)

and wishes to only store ciphertext in the cloud. Assume that Alice uses the cryptosystem
(P, C, K , E, D) proposed in Section 5.2 to encrypt data with a pair of two secret parameters
(S, k) in the cryptosystem, where S is a 2-Generators for GF 4 (22 ) with 9 elements and
k = (f, K, I) ∈ K .
Because of limited storage space and computing ability, instead of downloading
ciphertext, decrypting it and searching locally, Alice may ask Bob to perform pattern
matching tasks on the ciphertext directly with a trapdoor of the pattern received from
her.
Consider Σ to be an alphabet of size 256. Suppose that the secret data is a string over
Σ
x = x1 x2 ..xt3
for xi ∈ P, ∀i = 1, t3 , t3 ≥ 1 and t3 is often a large natural number, where P = Σ.
Before uploading the secret data x to Bob, Alice use the encrypting function ek ∈ E
to encrypt each xi . Then Alice computes yi = ek (xi ), ∀i = 1, t3 , and the encrypted secret
data is a string over Σ
y = y1 y2 ..yt3
which is sent to Bob, where Σ is an alphabet
Σ = {a |a = ek (a), a ∈ Σ}.
In general case, for x is any string over the alphabet Σ and a string y is obtained from
x by the above way. Then we can write y = ek (x) for short and y is a string over the
alphabet Σ .
Remark 5.4. By using only one pair of two secret parameters (S, k), then the security
of process of encrypting and decrypting the secret data x is similar to Formulas (5.3) (for
gray images) or (5.4) (for palette images).
Suppose that Bob needs to perform exact pattern matching task of an arbitrary pattern
p on encrypted data y. Based on previously introduced results in Chapter 3, here continues
using automata technique to meet the requirement.
74



by Definition 3.1. Hence, p1 p2 ..plm +1 is also both a proper prefix and suffix of p[1..l] by
Definition 3.1. Then Nextp (l) > lm. This is a contradiction to the supposition. So, the
proof is complete.
Propostion 5.6. Let p be a pattern over the alphabet Σ. Then for ∀l, 0 ≤ l ≤ |p| and
∀a ∈ Σ , a = dk (a ), Appearancep (l, a ) = Appearancep (l, a), where p = ek (p).
Proof. Clearly, |p| = |p | and for ∀i, 1 ≤ i ≤ |p |, ∀a , a ∈ Σ , a = pi if and only if a = pi .
By Lemma 3.1 and Proposition 5.5, Appearancep (l, a ) = Appearancep (l, a).
Theorem 5.2. Let p be a pattern over the alphabet Σ.
Let two automata
Mp = (Σ, Qp , q0 , δp , Fp ) and Mp = (Σ , Qp , q0 , δp , Fp ) be determined as in Theorem 3.2.
Then Qp = Qp , Fp = Fp , ∀q ∈ Qp , ∀a ∈ Σ , a = dk (a ), δp (q, a ) = δp (q, a), where
p = ek (p).
Proof. It is easy to verify that |p| = |p |. In addition, by Theorem 3.2 and Proposition 5.6,
then Qp = Qp , Fp = Fp and δp (q, a ) = δp (q, a).
Remark 5.5. The meaning of Theorem 5.2 in practice is to compute δp from δp .

75