1

Complexity of Verifying Nonblockingness in
Modular Supervisory Control

arXiv:1703.05011v1 [] 15 Mar 2017

Tomáš Masopust

Abstract—Complexity analysis becomes a common task in
supervisory control. However, many results of interest are spread
across different topics. The aim of this paper is to bring several
interesting results from complexity theory and to illustrate their
relevance to supervisory control by proving new nontrivial results
concerning nonblockingness in modular supervisory control of
discrete event systems modeled by finite automata.
Index Terms—Discrete event systems; Finite automata; Modular control; Complexity.

I. I NTRODUCTION
Nonblockingness is an important property of discrete event
systems ensuring that every task can be completed. It has
therefore been intensively studied in the literature [1]. An
automaton (deterministic or nondeterministic) is nonblocking
if every sequence of events generated by the automaton can
be extended to a marked sequence. Given a set of nonblocking
automata, the modular nonblockingness problem asks whether
the parallel composition of all the automata of the set results
in a nonblocking automaton.
The property is easy to verify for a deterministic automaton
(DFA) as we discuss in Theorem 2. However, if the automaton
is nondeterministic (NFA) or a set of nonblocking DFAs is
considered, the verification becomes computationally more
demanding. We study the complexity in Theorems 3 and 6,
respectively. A result relevant to timed discrete event systems
is provided in Theorem 8.
So far, no efficient (polynomial) algorithm for verifying
modular nonblockingness is known. In the light of the results
of this paper, it is not surprising. The problem is complete
for the complexity class for which the experts believe that
no efficient algorithms exist. Therefore it is unlikely that
there is an efficient algorithm solving the problem in general.
However, there can still be optimization methods or algorithms
working well for most of the practical cases. For instance,
Malik [2] has recently shown that explicit model checking
algorithms without any special data structures work well on
standard computers for several practical systems with 100
million states.
The aim of this paper is to bring and apply some of the
interesting results from automata and complexity theory to the
nonblockingness verification problem.
II. P RELIMINARIES
An alphabet, Σ, is a finite nonempty set. The elements of an
alphabet are called events. A string over Σ is a finite sequence
Supported by the DFG in Emmy Noether grant KR 4381/1-1 (DIAMOND).
T. Masopust (tomas.masopust@tu-dresden.de) is with the Institute
of Theoretical Computer Science and cfaed, TU Dresden, Germany

(catenation) of events, for example, 001 is a string over {0, 1}.
Let Σ∗ denote the set of all finite strings over Σ; the empty
string is denoted by ε.
A nondeterministic finite automaton (NFA) over an alphabet
Σ is a structure A = (Q, Σ, δ, I, F ), where Q is the finite
nonempty set of states, I ⊆ Q is the nonempty set of initial
states, F ⊆ Q is the set of accepting (marked) states, and
δ : Q × Σ → 2Q is the transition function that can be extended
to the domain 2Q × Σ∗ by induction. The language generated
by A is the set L(A) = {w ∈ Σ∗ | δ(I, w) 6= ∅} and the
language marked by A is the set Lm (A) = {w ∈ Σ∗ |
δ(I, w) ∩ F 6= ∅}. Equivalently, the transition function is a
relation δ ⊆ Q × Σ × Q. Then the meaning of δ(q, a) = {s, t}
is that there are two transitions (q, a, s) and (q, a, t).
The prefix closure of a language L is the set L = {w ∈ Σ∗ |
there exists u ∈ Σ∗ s.t. wu ∈ L}; L is prefix-closed if L = L.
Obviously, Lm (A) ⊆ L(A) and L(A) is prefix-closed.
NFA A is deterministic (DFA) if it has a unique initial state,
|I| = 1, and no nondeterministic transitions, |δ(q, a)| ≤ 1 for
every q ∈ Q and a ∈ Σ. For DFAs, we identify singletons with
their elements and simply write p instead of {p}. Specifically,
we write δ(q, a) = p instead of δ(q, a) = {p}.
For every NFA A there exists a DFA B such that Lm (B) =
Lm (A) and L(B) = L(A).
Let Σ and Γ be alphabets, and let f : Σ∗ → Γ∗ be a map.
Then f is a morphism (for catenation) if f (xy) = f (x)f (y)
for every x, y ∈ Σ∗ . Let Σo ⊆ Σ be alphabets. A projection
P from Σ∗ to Σ∗o is a morphism defined by P (a) = ε for
a ∈ Σ\Σo , and P (a) = a for a ∈ Σo . The action of projection
P on a string w ∈ Σ∗ is to erase all events from w that do
not belong to Σo . The inverse image of P , denoted P −1 , is
defined as P −1 (s) = {w ∈ Σ∗ | P (w) = s}. The definitions
can readily be extended to languages.
Let Li be a language over Σi , i = 1, . . . , n. The parallel
composition of (Li )ni=1 is defined by kni=1 Li = ∩ni=1 Pi−1 (Li ),
where Pi is a projection from (∪ni=1 Σi )∗ to Σ∗i . For i = 1, 2,
let Ai = (Qi , Σi , δi , Ii , Fi ) be NFAs. The parallel composition of A1 and A2 is defined as the accessible part of the NFA
(Q1 × Q2 , Σ1 ∪ Σ2 , δ, I1 × I2 , F1 × F2 ), where

 δ1 (x, e) × δ2 (y, e) if e ∈ Σ1 ∩ Σ2
δ((x, y), e) =
δ1 (x, e) × {y}
if e ∈ Σ1 \ Σ2

{x} × δ2 (y, e) if e ∈ Σ2 \ Σ1
The parallel composition of DFAs is a DFA [3]. The relationship between the definitions is L(A1 k A2 ) = L(A1 ) k L(A2 )
and Lm (A1 k A2 ) = Lm (A1 ) k Lm (A2 ).
An NFA A is nonblocking if Lm (A) = L(A). The inclusion
Lm (A) ⊆ L(A) always holds.

2

a

a

a

a

Fig. 1. DFAs A1 and A2 and their parallel composition A1 k A2

To show that a composition of nonblocking automata can be
blocking, let A1 and A2 be DFAs over {a} depicted in Fig. 1.
Both automata are nonblocking but their parallel composition
is blocking, because a cannot be extended to a marked string.
We now briefly recall the basic notions of complexity theory.
For all unexplained notions, the reader is referred to the literature [4], [5].
There are two complexity measures: space and time. The
class NSPACE(f (n)) denotes the class of all problems decidable by a nondeterministic Turing Machine (TM) (a nondeterministic algorithm) in space O(f (n)) for an input of size
n. The class NL = NSPACE(log n) is thus the class of all
problems decidable by a nondeterministic TM in logarithmic
space, and PSPACE = NPSPACE = ∪k∈N NSPACE(nk ) is the
class of all problems decidable by a (nondeterministic) TM in
polynomial space. The space required to store the input and
output is not considered in space complexity.
The class P (NP) denotes the class of all problems decidable
by a (nondeterministic) TM in polynomial time.
The hierarchy of classes is NL ⊆ P ⊆ NP ⊆ PSPACE. Even
though NL ( PSPACE, the strictness of any other inclusion is
unknown. The (non)strictness of these inclusions is the most
interesting and important open problem of complexity theory.
The classes NL and NP are defined in terms of a nondeterministic TM (a nondeterministic algorithm). Although for
every nondeterministic TM there is an equivalent deterministic
TM, the difference is in complexity. A typical nondeterministic
step of a nondeterministic algorithm is “choose x ∈ X”.
Deterministically, one can imagine to check all the possibilities for x one by one. Nondeterministically, the situation is
different. There are two basic views how a nondeterministic
algorithm performs a nondeterministic step. The first view
is that the algorithm “guesses” the right value of x that
eventually leads to a success, if such a value exists. The other
view is that the algorithm makes a copy of itself for every
nondeterministic step with different value of x in every copy.
For a nondeterministic step “choose x ∈ {1, . . . , 100}”, 100
copies of the algorithm would be created, where the value of
x in the ith copy is x = i. The nondeterministic algorithm is
successful if at least one of the copies is successful. In this
view, the time (space) complexity is the maximum of time
(space) required by a copy.
Example 1: Let G = (V, E, s, t) be a directed graph with
s, t ∈ V the source and target nodes. The graph reachability
problem asks whether the target node t is reachable from the
source node s in G. The problem belongs to NL [4].
To show this, we describe a nondeterministic algorithm
(Algorithm 1) that solves the graph reachability problem in
logarithmic space. Algorithm 1 is nondeterministic because of
the nondeterministic step on line 3. Following the first view,
the algorithm correctly guesses the edges that lead from node
s to node t, if such a path exists. Following the second view,
the algorithm forks for every possible edge on line 3. If any

of the copies ever reaches t, the copy returns true, which is
then the overall answer. The variable numSteps counts the
number of steps and terminates the cycle if it is bigger than
the number of nodes. This is fine because if there is a path
from s to t, then there is a path of length at most |V | − 1.
Algorithm 1: (Graph reachability)
Input : A directed graph G = (V, E, s, t)
Output: true iff t is reachable from s in G
1 k := s; numSteps := 0
2 repeat
3
choose k ′ such that (k, k ′ ) ∈ E
4
k := k ′ ; numSteps := numSteps + 1
5 until k = t or numSteps > |V | − 1
6 if k = t then return true
7 return false
It remains to show that Algorithm 1 works in logarithmic
space. Since the input is not considered in space complexity,
the only space required by the algorithm is the space to store
k, k ′ , |V |−1 and numSteps. However, numSteps is a binary
number, bounded by |V |, which requires at most ⌈log |V |⌉
digits. Similarly, k is a pointer to the position in the input,
where the actual value of k is stored. Thus, it is again a binary
number with at most ⌈log(|V | + |E|)⌉ digits. Similarly for k ′
and |V | − 1.
A problem is PSPACE-complete if it can be solved using
only polynomial space (membership in PSPACE) and if every
problem that can be solved in polynomial space can be reduced
(transformed) to it in polynomial time (PSPACE-hardness).
PSPACE-complete problems are therefore the hardest problems in PSPACE. Similarly for the other complexity classes,
with only a different requirement on the reduction. Namely,
to prove NL-hardness, the reduction has to be in deterministic
logarithmic space, and to prove NP-hardness, the reduction has
to be in polynomial time (as well as for PSPACE-hardness).
For instance, satisfiability of formulae in conjunctive normal
form1 (3CNF) is an NP-complete problem [6]. Therefore, by
definition, any problem in NP can be reduced to 3CNF in
polynomial time. We show in Theorem 8 that the One-sharedevent DFA modular nonblockingness (1SE-DFA-MN) problem
is in NP, hence reducible to 3CNF in polynomial time.
The membership in NP gives an upper bound on the complexity of 1SE-DFA-MN, which can still be polynomially or
even trivially solvable. To rule out this possibility, we further
show that 1SE-DFA-MN is NP-hard (and hence NP-complete)
by reducing 3CNF to 1SE-DFA-MN. Then, consequently, any
problem in NP can be reduced to the 1SE-DFA-MN problem
in polynomial time. Hence, from the complexity point of view,
both problems are equally difficult.
1 A (boolean) formula consists of variables, operators conjunction, disjunction and negation, and parentheses. A formula is satisfiable if there is an
assigning of 1 (true) and 0 (false) to its variables making it true. A literal
is a variable or its negation. A clause is a disjunction of literals. A formula
is in 3-cnf if it is a conjunction of clauses, each clause with three literals.
For instance, ϕ = (x ∨ y ∨ z) ∧ (¬x ∨ y ∨ z) is a formula in 3-cnf with
two clauses x ∨ y ∨ z and ¬x ∨ y ∨ z. Given a formula in 3-cnf, the 3CNF
problem asks whether the formula is satisfiable. The formula ϕ is satisfiable
for, e.g., (x, y, z) = (0, 1, 0).

3

x

s

s

t

2

2

a

x x a

a, x

a

+

?

t′

d

|
|E

1

?

1

u

u

t
0

a

1

0

a
x

x
a

1

Fig. 2. Graph G = (V, E, s, t) and its corresponding DFA A of Theorem 2
Fig. 3. A nonblocking NFA B with Lm (B) = L(B) = {a}∗ and its corresponding NFA A constructed in the proof of Theorem 3

III. C OMPLEXITY

OF

N ONBLOCKINGNESS

Let A = (Q, Σ, δ, I, F ) be an NFA. We define the size of
A as | A | = |Q| + |Σ| + |δ| + |I| + |F |.
A DFA is nonblocking iff from every state a marked state
is reachable (in other words, every state is reachable and coreachable). This property can be tested in linear time using the
computation of strongly connected components [7]. From the
complexity point of view, under the assumption that NL 6= P,
a stronger result can be shown.
Theorem 2 (DFA-nonblockingness): Given a DFA A, the
problem whether Lm (A) = L(A) is NL-complete.
Proof: The membership of DFA-nonblockingness in NL
follows from Algorithm 3 below for n = 1.
We now show that DFA-nonblockingness is NL-hard by
reducing graph non-reachability [4] to DFA-nonblockingness.
Namely, let G = (V, E, s, t) be a directed graph with s, t in
V . We construct a DFA A from G in logarithmic space such
that t is not reachable from s in G iff A is nonblocking.
Let A = (V ∪ {t′ }, Σ, δ, s, V ), where δ is defined as the
relation E with every transition under a unique label, and a
transition under a new label is added from t to the new nonmarked state t′ . This reduction (transformation) of G to A can
be done in logarithmic space and is performed by Algorithm 2,
where Σ = {1, 2, . . . , |E|+1}. If the algorithm reads a node v
in V , it outputs state v. Then it prints state t′ . After this part,
it has printed the state set of A. It only needs to store a pointer
(of logarithmic size) to the position of the input currently read.
Then the algorithm counts from 1 to |E| + 1 and outputs the
numbers, that is, it prints the alphabet of A. For this, two
numbers, i and |E| + 1 with at most ⌈log(|E| + 1)⌉ digits
are stored. Then, it reads the input again (using the pointer
as above) and uses a counter c (with at most ⌈log(|E| + 1)⌉
digits) to print, for every edge (u, v) in E, the corresponding
transition (u, c, v) of δ. Finally, it prints the transition (t, |E|+
1, t′ ), state s, and all v ∈ V . After this, the output contains
the DFA A. The reduction uses logarithmic space to produce
the output. Recall that the size of the input and output is not
considered in space complexity.
Algorithm 2: (Reduction of a graph to a DFA)
Input : A directed graph G = (V, E, s, t)
Output: The DFA A = (V ∪ {t′ }, Σ, δ, s, V )
1 for each v ∈ V do output v
′
2 output t
3 for i = 1, . . . , |E| + 1 do output i
4 c := 1; for each (u, v) ∈ E do {output (u, c, v); c++}
′
5 output (t, c, t ); output s
6 for each v ∈ V do output v

It is not difficult to see that t is reachable from s in G iff t
is accessible from the initial state s in A. Namely, if t is not
accessible in A, then all accessible states are marked and the
language of A is nonblocking. If t is accessible in A, then so
is t′ , which is not marked and makes thus the language of A
blocking; cf. Fig. 2 for an illustration.
Therefore, to check nonblockingness of a DFA is easy. This
is, however, not true for NFAs. An NFA can be nonblocking
even if there is a state from which no marked state is reachable,
cf. Fig. 3.
Theorem 3 (NFA-nonblockingness): Given an NFA A, the
problem whether Lm (A) = L(A) is PSPACE-complete.
Proof: To show that the problem is in PSPACE, let A =
(Q, Σ, δ, I, F ) be an NFA. Let D be a DFA obtained from A
by the standard subset construction [5]. States of D are subsets
of states of A, and A is nonblocking iff D is nonblocking. To
check nonblockingness of D in polynomial space, D cannot
be computed and stored, because it may require exponential
space in the size of A. Instead, we use the on-the-fly technique
that keeps only a small part of D in memory and re-computes
the required parts on request. Namely, for every state X ⊆ Q
of D, we check that X is reachable from the initial state of D
(in the way depicted in Example 1). If so, we guess a marked
state Y of D, that is, Y ∩F 6= ∅, and check that Y is reachable
from X. This principle is generalized in Algorithm 3 below.
At any time during the computation, the algorithm stores only
a constant number of states of D, which are subsets of the state
set Q of A. Therefore, the algorithm uses space polynomial
in the size of A and the problem is thus in PSPACE.
To show that NFA-nonblockingness is PSPACE-hard, we reduce the NFA universality problem [6] to it. NFA universality
asks, given an NFA B over Σ, whether Lm (B) = Σ∗ .
Let B = (Q, Σ, δB , I, F ) be an NFA, and let d be a new
non-marked state. We “complete” B in the sense that if, for
an event a in Σ, no a-transition is defined in a state q, we
add the transition (q, a, d) to the transition relation, see the
dotted transitions in Fig. 3. Let x ∈
/ Σ be a new event. State d
contains self-loops under all events of Σ ∪ {x}. For each nonmarked state p, we add the transition (p, x, d), see the dashed
transitions in Fig. 3, while for each marked state p, we add
the transitions (p, x, i) for every initial state i in I, cf. the dotdash transitions in Fig. 3. Let A = (Q∪{d}, Σ∪{x}, δA, I, F )
denote the resulting NFA. Notice that Lm (B) ⊆ Lm (A). We
now show that B is universal iff A is nonblocking.
If B is universal, that is, Lm (B) = Σ∗ , we show that A is
nonblocking by showing that Lm (A) = L(A). It is sufficient
to show that L(A) ⊆ Lm (A). Let w ∈ L(A). We proceed by
induction on the number of occurrences of event x in w. If x

4

does not occur in w, then w ∈ Σ∗ = Lm (B) ⊆ Lm (A). Thus,
assume that w = w1 xw2 with w1 ∈ Σ∗ and w2 ∈ (Σ ∪ {x})∗ .
Since w1 ∈ Σ∗ = Lm (B) ⊆ Lm (A), there is a path in A from
an initial state i in I to a marked state f in F labeled by w1 .
By construction, I ⊆ δA (i, w1 x), since δA (f, x) = I. By the
induction hypothesis, δA (I, w2 ) ∩ F 6= ∅, hence w ∈ Lm (A).
Thus, Lm (A) = L(A), which means that A is nonblocking.
If B is not universal, that is, Lm (B) 6= Σ∗ , then there exists
a w in Σ∗ such that δA (I, w) ∩ F = ∅, since for any w
over Σ, δA (I, w) ∩ F = δB (I, w) ∩ F . By the construction,
δA (I, wx) = {d}, from which no marked state is reachable.
Since A is complete, wx belongs to L(A), therefore A is
blocking.
The situation with NFAs is even worse as shown now.
Theorem 4 (NFA-prefix-closed): Given an NFA A, the problem whether Lm (A) is prefix-closed is PSPACE-complete.
Proof: Let A be an NFA. Then Lm (A) = Lm (A) iff the
DFA D obtained from A by the standard subset construction
has no reachable and co-reachable non-marked states. Since
the class PSPACE is closed under complement, we can check
the opposite – a nondeterministic algorithm guesses a subset
of non-marked states of A and verifies, using the on-the-fly
technique, that they form a reachable and co-reachable state
in D. The NFA-prefix-closed problem is thus in PSPACE.
To show PSPACE-hardness, Hunt III and Rosenkrantz [8]
have shown that a property R of languages over {0, 1} such
that R({0, 1}∗) is true and there exists a regular language
that is not expressible as a quotient x\L = {w | xw ∈ L},
for some L for which R(L) is true, is as hard as to decide
“= {0, 1}∗”. Since prefix-closedness is such a property (the
class of prefix-closed languages is closed under quotient) and
universality is PSPACE-hard for NFAs, the result implies that
the NFA-prefix-closed problem is PSPACE-hard.
These results justify why the attention is mostly focused on
DFAs rather than NFAs. In the rest of the paper, we also focus
on DFAs, unless stated otherwise.
A. Modular Nonblockingness Problem
We now focus on the modular nonblockingness problem.
The simplest case is that there is no interaction between the
different subsystems. The following result is well known.
Theorem 5: Let J be a finite set, and let Aj be a nonblocking
NFA over Σj , for j ∈ J. If the alphabets are pairwise disjoint,
that is, Σj ∩ Σj ′ = ∅ for j 6= j ′ , then the parallel composition
Lm (kj∈J Aj ) = L(kj∈J AJ ) is nonblocking.
In many complex systems, it is however the case that there
are events shared between the subsystems. In such a case,
nonblockingness is in general PSPACE-complete [9]. A more
fine-grained complexity can be distinguished based on the
following criteria. Let (Ai )ni=1 be DFAs:
1) The number of DFAs is not restricted.
2) The number of DFAs is restricted by a function g(m),
that is, n ≤ g(m), where m is the length of the encoding
of the DFAs A1 , A2 , . . . , An .
3) The number of DFAs is restricted by a constant k, that
is, n ≤ k.

Case 2 is the most general one and deserves a discussion.
Assume, for example, that our encoding of Ai requires c > 1
bits and that the encoding of A1 , . . . , An requires m = n · c
bits. If g(m) = m, then n ≤ g(nc) for every n ≥ 1, which
results in the non-restricted case 1. If g(m) = k, for a constant
k, then n ≤ g(nc) iff n ≤ k, which results in the restriction
of case 3. See also Remark 7 below.
We can now prove the following result.
Theorem 6 (DFA g(m)-bounded modular nonblockingness):
Given nonblocking DFAs (Ai )ni=1 with Ai over Σi , 2 ≤ n ≤
g(m), where m is the length of an encoding of the sequence of
DFAs A1 , A2 , . . . , An . The problem whether Lm (kni=1 Ai ) =
L(kni=1 Ai ) is NSPACE(g(m) log m)-complete.
Algorithm 3: Is A = kni=1 Ai nonblocking?
Input : Encoding of A1 , . . . , An of size m
Output: yes iff kni=1 Ai is nonblocking
n
1 for each (p1 , . . . , pn ) ∈ "i=1 Qi do
2
if (p1 , . . . , pn ) is reachable from the init st. of A then
3
choose (s1 , . . . , sn ) ∈ "ni=1 Fi
4
ki := pi , for i = 1, 2, . . . , n
5
repeat
6
choose a ∈ Σ
7
ki := δ(ki , a), for i = 1, 2, . . . , n
8
until ki = si , for i = 1, 2, . . . , n
9

return yes

Proof: Let (Ai )ni=1 over (Σi )ni=1 be nonblocking DFAs.
Algorithm 3 solves the g(m)-bounded modular nonblockingness problem. It works as follows: for every reachable state
(p1 , . . . , pn ) of A (lines 1-2), the algorithm nondeterministically chooses a marked state (s1 , . . . , sn ) of A (line 3) that
is reachable from state (p1 , . . . , pn ) (lines 4-8). The algorithm
returns yes iff there is such a marked state for every reachable
state, hence iff A is nonblocking. (Compared to Example 1,
we omitted the counter numSteps for simplicity. It should
be clear how the counter is introduced to make the algorithm
always terminate.)
During the computation, the algorithm stores only a constant
number of n-tuples of pointers (t1 , . . . , tn ). The space used is
therefore O(n log m). Since n is bounded by g(m), the space
used by Algorithm 3 is O(g(m) log m), hence the problem is
in NSPACE(g(m) log m).
To prove hardness, we reduce the NSPACE(g(m) log m)complete finite DFA intersection problem (DFA-int) [10] to
our problem. DFA-int asks, given DFAs (B i )ni=1 with 2 ≤ n ≤
g(m), where m is the length of the encoding of the sequence of
B 1 , . . . , B n , whether ∩ni=1 Lm (B i ) = ∅. The DFAs B 1 , . . . , B n
are over a common alphabet Σ.
We now describe a deterministic logarithmic-space reduction from DFA-int to DFA g(m)-bounded modular nonblockingness. Notice that n ≥ 2. Let x ∈
/ Σ be a new event.
We construct A1 from B 1 by adding two new states d1 and
d′1 and x-transitions from every marked state of B 1 to d1 , and
from d1 to d′1 , see an illustration in Fig. 4. All states of A1 ,
but d1 , are marked, that is, Lm (A1 ) = L(B 1 ) ∪ Lm (B 1 )xx
and L(A1 ) = L(B 1 ) ∪ Lm (B 1 ){x, xx}.

5

For every i ≥ 2, we construct Ai from B i by adding a new
state di and x-transitions from every marked state of B i to
di . All states of Ai are marked, hence Lm (Ai ) = L(Ai ) =
L(B i ) ∪ Lm (B i )x.
We thus have that Lm (kni=1 Ai ) = ∩ni=1 L(Bi ) and
L(kni=1 Ai ) = ∩ni=1 L(B i ) ∪ ∩ni=1 Lm (B i )x .
We show Lm (kni=1 Ai ) = L(kni=1 Ai ) iff ∩ni=1 Lm (B i ) = ∅.
If ∩ni=1 Lm (B i ) = ∅, then L(kni=1 Ai ) = ∩ni=1 L(B i ) =
Lm (kni=1 Ai ).
If ∩ni=1 Lm (B i ) 6= ∅, then there exists w ∈ ∩ni=1 Lm (B i ),
hence wx ∈ L(kni=1 Ai ) \ Lm (kni=1 Ai ), because Lm (kni=1 Ai )
does not contain any string with event x.
Remark 7: Let k be a constant. If for every m, g(m) ≤ k,
then Algorithm 3 uses space O(log m), hence DFA k-bounded
modular nonblockingness is in NL = NSPACE(log m) and
it is NL-complete. If g(m) ≤ logk m, then DFA (logk m)bounded modular nonblockingness is NSPACE(logk+1 m)complete. It is called a poly-logarithmic space complexity.
B. One-Shared-Event Modular Nonblockingness
We now focus on the case where exactly one event is shared.
An application of this case is, for example, in the Brandin
and Wonham modular framework for timed discrete event
systems [11], where only one event simulating the tick of a
global clock is shared and all the other events are local [12].
Unless NP = PSPACE, nonblockingness is computationally
easier in this case.
Let A be an NFA over Σ and P be a projection from Σ∗ .
Then P (A) is a DFA such that Lm (P (A)) = P (Lm (A)) and
L(P (A)) = P (L(A)), called an observer; cf. [3], [13] for a
construction. In the worst case, P (A) has exponentially many
states compared to A [14], [15].
Theorem 8 (One-shared-event DFA modular nonblockingness): Given n ≥ 2 nonblocking DFAs (Ai )ni=1 with Ai over
Σi such that | ∪i6=j (Σi ∩ Σj )| = 1. The problem to decide
whether Lm (kni=1 Ai ) = L(kni=1 Ai ) is NP-complete.
Proof: Let (Ai )ni=1 over (Σi )ni=1 be nonblocking DFAs,
and let a be the only event such that Σi ∩ Σj = {a}, for
every i 6= j. Let P be a projection from (∪ni=1 Σi )∗ to {a}∗ .
Let m be the maximum number of states of all Ai ’s. Then
P (Ai ) is a DFA with at most 2m states, hence the composition
A = kni=1 P (Ai ) has at most 2mn states, each of the form
(X1 , . . . , Xn ), where Xi is a subset of states of Ai .
Let δ denote the transition function of A and q0 its initial
state. Notice that A is a sequence of transitions possibly with
a cycle at the end. Then A is nonblocking iff there exist
k ≤ 2mn and k < ℓ ≤ 2mn+1 such that δ(q0 , ak ) is an
accepting state of A and either δ(q0 , ak+1 ) is not defined
or δ(q0 , ak ) = δ(q0 , aℓ ). We now show how to check this
property in nondeterministic polynomial time.
The nondeterministic algorithm guesses k and ℓ in binary,
requiring at most mn + 1 digits each. To compute the states
δ(q0 , ak ) and δ(q0 , aℓ ) in polynomial time, the algorithm
proceeds as follows.
Let A′i denote the NFA obtained from Ai by replacing
each transition (s, b, t) with the transition (s, P (b), t), and by

eliminating the ε-transitions afterwards. This can be computed
in polynomial time [16] and is often used as the middle step
in the computation of the observer; namely, it preserves the
languages. Then A′i is over {a} and has the same states as Ai .
Let Ji denote the set of all initial states of A′i ; it is computed
in polynomial time as the set of all states of Ai reachable
under Σ \ {a} from the initial state of Ai (it is also the initial
state of P (Ai ), that is, q0 = (J1 , . . . , Jn )).
The transition relation of A′i can be represented as a binary
matrix Mi , where for states s, t of A′i , Mi [s, t] = 1 iff (s, a, t)
is a transition in A′i . For k ≥ 2, let Mik be the multiplication
of Mi with itself k times. Then Mik [s, t] is the number of paths
of length k from s to t in A′i [17]. Let δA′i denote the transition
function of A′i . Then δA′i (qi , ak ) = {t | Mik [qi , t] > 0} (if it is
empty, the transition is undefined). The size of matrix Mik is
polynomial in the number of states of Ai and can be computed
in time logarithmic in k by fast matrix multiplication: Mi2 =
Mi × Mi , Mi4 = Mi2 × Mi2 , Mi8 = Mi4 × Mi4 , . . . .
To compute δ(q0 , ak ), we compute Mik , for i = 1, . . . , n, in
polynomial time. Then the state δ(q0 , ak ) = (δA′1 (J1 , ak ), . . . ,
δA′n (Jn , ak )) and it is marked iff every δA′i (Ji , ak ) contains
a marked state of A′i . It should now be clear how to check,
in polynomial time, that either δ(q0 , ak+1 ) is not defined or
δ(q0 , ak ) = δ(q0 , aℓ ), cf. also Example 10 and Remark 11.
To show NP-hardness, we reduce 3CNF to our problem and
use the construction of [18]. Let ϕ be a formula in 3CNF
(see footnote 1 on page 2) with n distinct variables and m
clauses, and let Ck be the set of literals in the kth clause,
1 ≤ k ≤ m. The assignment to the variables is represented as
a binary vector of length n. Let p1 , . . . , pn denote the first n
prime numbers. For a natural number z congruent with 0 or 1
modulo pi , for all i = 1, . . . , n, z satisfies ϕ if the assignment
(z mod p1 , . . . , z mod pn ) satisfies ϕ.
For u = 1, . . . , n and j = 2, . . . , pu − 1, let B ′u,j denote a
nonblocking DFA such that
Lm (B ′u,j ) = 0j · (0pu )∗ .
u −1
Then ∪nu=1 ∪pj=2
Lm (B ′u,j ) = {0z | ∃u ≤ n, z 6≡ 0 mod
pu and z 6≡ 1 mod pu } is the set of all natural numbers that
do not encode an assignment to the variables.
For each clause Ck , we construct a nonblocking DFA B ′k
such that if 0z ∈ Lm (B ′k ) and z is an assignment, then z does
not assign value 1 to any literal in Ck . For example, if Ck =
{xr , ¬xs , xt }, for 1 ≤ r, s, t ≤ n and r, s, t distinct, let zk be
the unique integer such that 0 ≤ zk < pr ps pt , zk ≡ 0 mod pr ,
zk ≡ 1 mod ps , and zk ≡ 0 mod pt . Then

Lm (B ′k ) = 0zk · (0pr ps pt )∗ .
Let B 1 , . . . , Bℓ denote all the DFAs B ′u,j and B ′k constructed
above, and let Ai denote B i with the sets of marked and nonmarked states exchanged, that is, Lm (Ai ) = 0∗ \ Lm (B i ).
Note that all B i and Ai are nonblocking and their generated
languages are 0∗ .
Now, ϕ is satisfiable if and only if there exists z such that z
u −1
Lm (B ′u,j ),
encodes an assignment to ϕ, i.e., 0z ∈
/ ∪nu=1 ∪pj=2
z
and z satisfies every clause Ck , that is, 0 ∈
/ Lm (B ′k ) for all
z
ℓ
k = 1, . . . , m. This is iff 0 ∈ ∩i=1 Lm (Ai ) = Lm (kℓi=1 Ai ).

6

B2

B1
1
a

A1

3

1
a

a, b
0

A2
d′1

2

0

x

3

d1

B2

1
x

a, b

x

B1

a
d2

2

3

A1
d′1

1
a

a, b
0

A1

2

x
0

x

d1

3
x

a, b
2

x

d2

Fig. 4. DFAs B1 and B2 over Σ = {a, b} and the corresponding DFAs A1 and A2 of Theorem 6; a nonblocking instance (left) with Lm (A1 k A2 ) =
L(A1 k A2 ) = {ε, a} and a blocking instance (right) with Lm (A1 k A2 ) = {ε, a} and L(A1 k A2 ) = {ε, a, x}

We show that kℓi=1 Ai is nonblocking iff Lm (kℓi=1 Ai ) 6= ∅.
If Lm (kℓi=1 Ai ) = ∅, then kℓi=1 Ai is blocking, because ε ∈
L(kℓi=1 Ai ).
If 0z ∈ Lm (kℓi=1 Ai ), then z satisfies ϕ. For a natural
number c, the number z + c · Πni=1 pi also satisfies ϕ: indeed,
if z ≡ xi mod pi , then (z + c · Πni=1 pi ) ≡ xi mod pi , for
n
all i. Thus, 0z (0Πi=1 pi )∗ ⊆ Lm (kℓi=1 Ai ). Since for every
0s ∈ L(kℓi=1 Ai ), there exists c such that s ≤ z + c · Πni=1 pi ,
we have that kℓi=1 Ai is nonblocking.
Remark 9: If the number of DFAs in Theorem 8 is at most k,
for a constant k, the problem is NL-complete. The membership
in NL is by Theorem 6 and NL-hardness by Theorem 2.
Example 10: We illustrate the polynomial computation used
in the proof of Theorem 8 for n = 1. Its generalization to n >
1 is straightforward. Let A1 = ({1, 2, 3, 4}, {a, b}, {(1, a, 2),
(2, a, 1), (2, b, 3), (3, a, 4), (4, a, 1)}, 1, {1}) be a DFA, and let
A′1 , depicted in Fig. 5, be the NFA obtained from A1 by

1

a
a

a

a

2

3

a

4

a
Fig. 5. The NFA A′1 of Example 10

renaming b-transitions to ε-transitions, and by the elimination
of ε-transitions afterwards. Then the 4 × 4 transition matrix
M1 and its 4th power M14 are




1 2 2 2
0 1 1 0
3 1 1 2
1 0 0 1 


M14 = 
M1 = 
1 0 0 2 .
0 0 0 1 
2 1 1 0
1 0 0 0
The reader may verify that δ({1}, a4 ) = {1, 2, 3, 4}, where δ
is the transition relation of the observer P (A1 ).
Remark 11: The number Mik [s, t] represents the number of
paths from state s to state t of length k. This information is not
important for us. The information we need is whether there is a
path, i.e., Mik [s, t] > 0, or not, i.e., Mik [s, t] = 0. The numbers
Mik [s, t] may become large and affect thus the complexity. To
keep the complexity polynomial (the numbers small), the +
operation in the definition of matrix multiplication is replaced
by max operation. This minor trick keeps the matrices Mik
binary, while providing the same information [17].
IV. C ONCLUSION
The theoretical results do not seem very optimistic. However, there are techniques to reduce the size of an automaton,

which allows to handle large automata that appear in practical applications. A well-known technique is the BDD diagrams [19]. Another technique is the state-tree structures [20]
or the method using extended finite-state machines and abstractions [21].
ACKNOWLEDGMENT
The author gratefully acknowledges very useful suggestions
and comments of the anonymous referees.
R EFERENCES
[1] S. Mohajerani, R. Malik, and M. Fabian, “A framework for compositional synthesis of modular nonblocking supervisors,” IEEE Trans.
Autom. Control, vol. 59, pp. 150–162, 2014.
[2] R. Malik, “Programming a fast explicit conflict checker,” in WODES,
2016, pp. 438–443.
[3] C. Cassandras and S. Lafortune, Introduction to discrete event systems,
2nd ed. Springer, 2008.
[4] C. Papadimitriou, Computational Complexity. Addison-Wesley, 1994.
[5] M. Sipser, Introduction to the theory of computation, 2nd ed. Thompson
Course Technology, 2006.
[6] M. Garey and D. Johnson, Computers and Intractability: A Guide to the
Theory of NP-Completeness. W. H. Freeman, 1979.
[7] R. Tarjan, “Depth-first search and linear graph algorithms,” SIAM J.
Comput., vol. 1, pp. 146–160, 1972.
[8] H. B. Hunt III and D. J. Rosenkrantz, “Computational parallels between
the regular and context-free languages,” SIAM J. Comput., vol. 7, pp.
99–114, 1978.
[9] K. Rohloff and S. Lafortune, “PSPACE-completeness of modular supervisory control problems,” Discrete Event Dyn. Syst., vol. 15, pp. 145–
167, 2005.
[10] M. Holzer and M. Kutrib, “Descriptional and computational complexity
of finite automata – A survey,” Inform. and Comput., vol. 209, pp. 456–
470, 2011.
[11] B. Brandin and W. Wonham, “Supervisory control of timed discreteevent systems,” IEEE Trans. Autom. Control, vol. 39, pp. 329–342, 1994.
[12] G. Schafaschek, M. Queiroz, and J. Cury, “Local modular supervisory
control of timed discrete-event systems,” in WODES, 2014, pp. 271–277.
[13] W. Wonham, “Supervisory control of discrete-event systems,” 2009.
[14] K. Wong, “On the complexity of projections of discrete-event systems,”
in WODES, 1998, pp. 201–206.
[15] G. Jirásková and T. Masopust, “On a structural property in the state
complexity of projected regular languages,” Theoret. Comput. Sci., vol.
449, pp. 93–105, 2012.
[16] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory,
Languages and Computation. Addison-Wesley, 1979.
[17] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to
Algorithms, 3rd ed. MIT Press, 2009.
[18] L. Stockmeyer and A. Meyer, “Word problems requiring exponential
time: Preliminary report,” in STOC, 1973, pp. 1–9.
[19] R. Bryant, “Graph-based algorithms for boolean function manipulation,”
IEEE Trans. Comput., vol. 35, pp. 677–691, 1986.
[20] C. Ma and W. Wonham, “Nonblocking supervisory control of state tree
structures,” IEEE Trans. Autom. Control, vol. 51, pp. 782–793, 2006.
[21] S. Mohajerani, R. Malik, and M. Fabian, “A framework for compositional nonblocking verification of extended finite-state machines,”
Discrete Event Dyn. Syst., vol. 26, pp. 33–84, 2016.

