![](https://csdnimg.cn/release/download_crawler_static/10232721/bg3.jpg)
I. Podolak et al. / Expert Systems With Applications 97 (2018) 357–371 359
Fig. 2. An exemplary 4-state synchronizing automaton over 2-letter alphabet.
RQ3 Do the machine learning models work well when we re-
strict the possible features to the ones that are computed
quickly (in linear time) and to simple, linear models?
Section 5 is the central part of our paper. It presents the de-
scriptive statistics of the data (like correlations between features),
a novel model for estimating the minimal synchronizing word
length and the experiments that verify the model performance.
We investigate the impact of particular features on the length of
shortest synchronizing words. We also discuss the issue of the
alphabet size and its impact on the experiments results. Finally,
Section 6 gives some final conclusions and remarks.
2. Preliminaries
A deterministic finite (semi)automaton A is a triple ( Q , , δ),
where Q is a set of states , is an alphabet , and δ: Q × → Q
is a transition function . We extend δ to a function Q ×
∗
: Q as
usual. When the automaton is fixed, we use the abbreviation qw =
δ(q, w ) .
Throughout the paper we denote n = | Q| and k = | | . We will
deal only with deterministic complete automata, that is, the au-
tomata with a total transition function. This means that δ is de-
fined for all pairs ( q, a ) ∈ Q ×.
The image of a subset S under the action of a word w is Sw =
{ qw : q ∈ S} and the preimage is Sw
−1
= { q ∈ Q : qw ∈ S} .
The rank of a word w is the cardinality of the image of Q : | Qw |.
A word w is called reset if Qw is a singleton ( w is of rank 1). If an
automaton admits a reset word, then it is called synchronizing .
For a given automaton A = (Q, , δ) by its underlying graph we
understand the directed (multi)graph G = (Q, E) , where (p, q ) ∈
E ⇐⇒ ∃ a ∈ : δ(p, a ) = q . A simple path in G is a path in which
no vertex occurs more than once. The length of a simple path is
the number of edges it contains.
The length of the shortest reset words of a synchronizing au-
tomaton is called a reset threshold and is denoted by rt (A ) .
The famous
ˇ
Cerný conjecture
(
ˇ
Cerný,
1964 ) says that for each
synchronizing automaton its reset threshold does not exceed the
value of (n − 1)
2
. Although the conjecture was proved for several
classes of automata (e.g. Ananichev & Volkov, 2003; Ananichev,
Volkov, & Zaks, 2006; Berlinkov & Szykuła, 2016; Dubuc, 1998;
Eppstein, 1990; Kari, 2003; Trahtman, 2007 ), in its general form
it is still an open problem.
Let us consider the automaton A = ({ 1 , 2 , 3 , 4 } , { a, b} , δ) from
Fig. 2 . It is easy to check that the word w = bbaabb is a synchroniz-
ing word, because for each state q ∈ Q we have δ(q, bbaabb) = 3 :
Qb
2
a
2
b
2
= { 2 , 3 , 4 } ba
2
b
2
= { 2 , 3 } a
2
b
2
= { 3 , 4 }
ab
2
= { 1 , 3 } b
2
= { 2 , 4 } b = { 3 } .
It can be shown that this is also a minimal synchronizing word for
this automaton.
It is easy to show that a single letter a ∈ forms a set of cycles
with some “trees” incoming to these cycles Every such a cycle to-
gether with its incoming tree forms a connected component called
cluster . For example, in Fig. 2 a represents a permutation: it forms
two cycles: (1, 2, 4) and (3). Letter b forms one cycle (2, 3) with a
path 1 → 4 → 3 incoming to state 3 in the cycle.
For a given A = (Q, , δ) we define a pair automaton A
=
(Q
, , δ
) , where Q
= {{ q, p} | p, q ∈ Q, p = q } ∪ { q
0
} ( q
0
∈ Q ) and
δ
is defined as follows:
δ
({ p, q } , a ) = { δ(p, a ) , δ(q, a ) } ∀ p = q, δ(p, a ) = δ(q, a ) , a ∈
δ
({ p, q } , a ) = q
0
∀ δ(p, a ) = δ(q, a ) , a ∈
δ
(q
0
, a ) = q
0
∀ a ∈
3. Automata features
In this section we describe the full set of so-called automata
features that we used to represent the automata in the machine-
learning algorithm for prediction of the reset threshold. The fea-
tures are related to the structural and graph-theoretic properties
of the automata and their underlying graphs. Some ML algorithms
(like neural networks or decision trees) require the input features
to be normalized or bounded. Otherwise, when a new data points
arrive with values exceeding the defined boundaries, the algorithm
may not handle this data properly. Therefore, we give the theoreti-
cal lower and upper bounds for the possible values of the features
and discuss the computational complexity issues related to com-
puting these values. High complexity indicates that a given feature
may be impractical in computations due to a long time required
for computing its values.
•
Number of states n and alphabet size k . These two values are
given with the automaton and are unbounded, 2 ≤n, k ≤∞ .
•
PairMaxHeight . This is the maximum length of a shortest
word w synchronizing a given pair of states, taken over all pairs:
P airMaxHeight = max
p,q ∈ Q,p = q
( min {| w | | w ∈
∗
such that pw = qw ) .
This informs us how hard it is to synchronize a pair of states.
The parameter can be also used to bound the performance of the
greedy algorithms finding a reset word (e.g. Ananichev & Gusev,
2016; Eppstein, 1990; Kudłacik, Roman, & Wagner, 2012 )
The minimum value is 1, when every pair can be synchroniz-
ing by a single letter, and the maximum value is n (n − 1) / 2 (the
number of pairs), which occurs for the
ˇ
Cerný automaton
(
ˇ
Cerný,
1964 ). To compute this, we need to compute the pair automaton
in O ( kn
2
) time ( Eppstein, 1990 ).
•
SinkSize . This is the number of vertices in the strongly con-
nected component. A strongly connected component (SCC) in the
automaton underlying graph is a maximal subset P ⊂Q of states
(vertices) such that for each p
1
, p
2
∈ P there exist a path from p
1
to p
2
. Sink component is a strongly connected component reach-
able from every state. It is clear that in a synchronizing automaton
there exists a unique sink component. Let Q
s
be the set of states in
the sink component. In the following, the sink component will be
denoted by SC.
The smallest possible SC is composed of a single state,
sometimes called the “sink state”, that is, a state p such that
∀ a ∈ δ(p, a ) = p. The largest possible SC is composed of all ver-
tices, so we have 1 ≤SinkSize ≤n . The strongly connected compo-
nents and so the sink size can be computed by using the Tarjan
algorithm ( Tarjan, 1972 ) in O ( nk ) time.
For the next graph-theoretic feature we restrict the properties
to the sink component. The Eccentricity of a vertex q is the length
of the longest possible simple path from q to some vertex. We
shall denote eccentricity in Q
s
with Ecc
Q
s
(q ) . For a single vertex
it can be computed in O ( kn ) using a simple BFS, and we have
0 ≤ Ecc
Q
s
(q ) ≤ n − 1 .
•
Radius . Radius is defined as the minimal value of Ecc
Q
s
taken
over all possible states:
Radius = min
q ∈ Q
s
Ecc
Q
s
(q ) .