Partially Ordered Automata Expressivity, Complexity, and Applications Habilitation Thesis 2019 RNDr. Tomáš Masopust, Ph.D., DSc. Abstract A nondeterministic finite automaton (NFA) is partially ordered if the only cycles in its transition diagram are self-loops. Expressivity of partially ordered NFAs (poNFAs) can be characterized by the Straubing-Therien hierarchy. The most studied level of the hierarchy, level 1, is formed by piecewise testable languages - regular languages recognized by confluent partially ordered DFAs. Omitting confluence results in partially ordered DFAs characterizing &-trivial languages, a class of languages strictly between levels 1 and | of the hierarchy. Lifting the notion from DFAs to NFAs, Schwentick, Therien and Vollmer showed that poNFAs characterize level | of the hierarchy. We extend this study and provide an NFA characterization of ^-trivial languages and piecewise testable languages. Our motivation to study partially ordered automata comes from database theory and schema languages for XML data, namely from scenarios in which we want to describe something complex by means of a simple language. The technical core consists of separation problems that are usually of the form "Given two languages K and L, does there exist a language S, coming from a family of simple languages, such that S contains everything from K and nothing from L?" We focus on the case where "simple languages" are represented by piecewise testable languages. We show that the separation problem of regular languages by piecewise testable languages is PTlME-complete. Our construction is based on the non-existence of a particular infinite sequence of words alternating between the languages, called a tower. The number of words in the tower is its height. We show that two languages are separable if and only if there is no infinite tower between them. The height is further closely related to the complexity of computing a separator. We show that the upper bound on the height of finite towers is polynomial in the number of states and exponential in the size of the alphabet, and that it is asymptotically tight if the size of the alphabet is fixed. If the alphabet may grow linearly with the number of states, then the lower bound on the height of towers is exponential with respect to that number. Another motivation comes from discrete event systems. On some level of abstraction, discrete event systems can be seen as finite automata with possible additional properties. One of the fundamental properties is that the system is deadlock free. In some sense, poNFAs are the simplest deadlock-free models, and hence the study of their lower-bound complexity questions covers most of the practical cases. The problems of our interest are the questions whether the behavior of two systems is equivalent or in inclusion. Since the lower-bound complexity of the problems is covered by the complexity of universality, we primarily investigate the question whether the behavior of a system is universal. We further discuss consequences of our results to the verification of detectability and opacity of discrete event systems. ii Acknowledgements I would like to thank all my co-authors who worked with me on the topics of this thesis. Special thanks go to the Department of Computer Science of the Palacký University, to the Institute of Mathematics of the Czech Academy of Sciences, to the Institute of applied informatics of the Bayreuth University, and to the Faculty of Informatics of the Technical University Dresden who maintained a pleasant and flexible environment for my research. During the time, my research was supported by the following projects: • by the Czech Science Foundation project P202/11/P028 (Decentralized and coordination supervisory control), • by the Czech Science Foundation project GA15-02532S (Modular and Decentralized Control of Dis crete-Event and Hybrid Systems with Communication), • by the Ministry of Education, Youth, and Sport of the Czech Republic under the Kontakt II research project LH13012 (Multi-level supervisory control (MUSIC)), • by the German Research Foundation (DFG) in Emmy Noether grant MA 4938/2-1 (Quer-schnitte: XML und formale Sprachen - Theorie und Praxis), • by the German Research Foundation (DFG) in Emmy Noether grant KR 4381/1-1 (Daten-integration und -abfrage durch die ZusammenfUhrung von Ontologien und Datenbanken), • and by the Czech Science Foundation project GC19-06175J (Compositional Methods for the Control of Concurrent Timed Discrete-Event Systems). My greatest thanks go to my wife Iveta and my daughter Sofie for their infinite patience and support. Copyright ©2019 Tomáš Masopust iii Contents 1 Introduction 3 1.1 Papers in the Collection.............................. 6 2 Basic Notation 8 3 Descriptional Complexity 9 3.1 Reversal...................................... 9 3.1.1 Reversal of ^-trivial Languages..................... 9 3.1.2 Reversal of ^-trivial Languages .................... 10 4 Separability 12 4.1 Separability of Languages ............................ 13 4.2 Asymmetric Separation and Suffix Order..................... 15 4.3 Computation of Piecewise Testable Separators.................. 16 4.3.1 Bounds on the Height of Towers..................... 17 5 Complexity of Universality 20 5.1 Partially Ordered NFAs.............................. 22 5.2 Restricted Partially Ordered NFAs........................ 22 5.2.1 Deciding Universality of rpoNFAs.................... 24 5.3 PtNFAs...................................... 25 5.3.1 Deciding Universality for ptNFAs.................... 25 5.4 Inclusion and Equivalence of Partially Ordered NFAs.............. 28 6 Piecewise Testable Languages 30 6.1 Finding a Boolean Combination......................... 30 6.1.1 Step 1: Checking Piecewise Testability ................. 31 6.1.2 Step 2: Computing the Minimal k.................... 31 6.1.3 Step 3: Computation of Representatives................. 33 6.2 Piecewise Testability and Nondeterministic Automata.............. 33 6.3 Complexity.................................... 34 6.3.1 Complexity of Deciding k-Piecewise Testability............. 34 6.3.2 Complexity of Deciding Piecewise Testability.............. 35 7 Applications 37 7.1 Deterministic Regular Expressions........................ 37 7.2 Detectability.................................... 38 7.3 Opacity...................................... 40 1 8 Conclusion 44 2 1. Introduction The relationship between logic and formal languages is studied for decades. In 60th, Biichi [22] and Elgot [40] showed that a language is regular if and only if it is definable in monadic second order logic. Later, McNaughton and Papert [87] proved that first-order logic describes star-free languages, a class of regular languages for which Schiitzenberger [109] gave an algebraic characterization - star-free languages are those regular languages whose syntactic monoid is aperiodic. Restricting the number of quantifier alternations in first-order logic formulae in the prenex normal form results in a so-called quantifier alternation hierarchy. The choice of predicates in the signature of the first-order logic then corresponds to several such hierarchies. The well-known and closely related hierarchies are the Straubing-Therien hierarchy [122, 124] and the dot-depth hierarchy [20, 29, 123]. The Straubing-Therien hierarchy is alternatively defined as follows. For an alphabet E, j£?(0) = {0, E*} and, for integers n > 0, the levels 3f(n + \) and 3f(n + 1) are defined so that • level J£{n + j) consists of all finite unions of languages LQa\L\a2... a^L^ with k > 0, Lo,... G JC(n), and <2i,... ,<2£ G E, and • level ££(n + 1) consists of all finite Boolean combinations of languages from the level ^(n + \). The hierarchy does not collapse on any level [20]. There is a constant interest in automata characterizations of the levels of the Straubing-Therien hierarchy, in particular in decision and complexity questions, such as the membership of a language in a specific level of the hierarchy. Despite a recent progress [2, 97, 99], deciding whether a language belongs to level k of the Straubing-Therien hierarchy is still open for k > |. The Straubing-Therien hierarchy further has close relations to the dot-depth hierarchy and to complexity theory [128]. The most studied level of the Straubing-Therien hierarchy is level 1, also known as piecewise testable languages introduced by Simon [115]. Simon showed that piecewise testable languages are those regular languages whose syntactic monoid is ^-trivial and that they are recognized by confluent partially ordered DFAs. An automaton is partially ordered if its transition relation induces a partial order on states - the only cycles in its transition diagram are self-loops - and it is confluent if for any state q and any two of its successor states s and t directly accessible from q by transitions labeled by a and b, respectively, there is a word w over the alphabet {a,b} such that a common state is reachable from both states s and t under w, see Figure 1.1 for an illustration. Omitting confluence from the definition results in partially ordered DFAs (poDFAs) studied by Brzozowski and Fich [19]. They showed that poDFAs characterize M'-trivial languages, a class of languages strictly between level 1 and level | of the Straubing-Therien hierarchy (the name comes from the Green's & relation because the syntactic monoid of ^-trivial languages 3 Figure 1.1: Confluence is ^-trivial). Lifting the notion from DFAs to NFAs, Schwentick, Therien and Vollmer [111] showed that partially ordered NFAs (poNFAs) characterize level | of the Straubing-Therien hierarchy. Hence poNFAs are more expressive than poDFAs. Languages of level | are also known in the literature as Alphabetical Pattern Constraints, which are regular languages effectively closed under permutation rewriting [14]. Motivated by Brzozowski's minimization algorithm based on the double computation of the reverse operation, we study the state complexity of the reverse of minimal poDFAs. State complexity of an automaton or of a language is the number of states of the minimal DFA recognizing the language. We establish a tight bound on the state complexity of the reverse of poDFAs and confluent poDFAs showing that the state complexity of the reverse of a (confluent) poDEA of the state complexity n is 2n_1. The witness is ternary for poDFAs and (n — l)-ary for confluent poDFAs, and the bound can be met neither by a binary poDFA nor by a confluent poDEA over an (n — 2)-element alphabet. We further provide a characterization of the tight bounds for poDFAs depending on the state complexity and the size of its alphabet. Chapter 3 is devoted to the overview of this study. Our main interest in partially ordered automata is in particular motivated by two problems. The first problem comes from database theory and schema languages for XML data, namely from efficient approximate query answering and increasing the user-friendliness of XML Schema. Both are motivated by scenarios in which we want to describe something complex by means of a simple language. The technical core of our scenarios consists of separation problems, which are usually of the form "Given two languages K and L, does there exist a language S, coming from a family of simple languages, such that S contains everything from K and nothing from L?" The family of simple languages could be, for example, languages definable in (a fragment of) first-order logic, piecewise testable languages, or languages definable with a special class of automata. We focus on simple languages represented by piecewise testable languages and their special variants, so-called fc-piecewise testable languages. We show that the separation problem of regular languages by piecewise testable languages is PTlME-complete. Our construction showing the membership in PTime is based on the non-existence of a particular infinite sequence of words, called a tower. A tower is a sequence of words alternating between two languages in such a way that every word is a subsequence of the following word. The height of a tower is the number of words in the sequence. If there is no tower of infinite height, then the height of all towers between the languages is bounded. We show that two languages are separable if and only if there is no infinite tower between them. The height of highest towers is closely related to the complexity of computing a separator. Therefore, we further investigate upper and lower bounds on the height of maximal finite towers. We show that the upper bound is polynomial in the number of states and exponential in the size of the alphabet, and that it is asymptotically tight if the size of the alphabet is fixed. If the alphabet may grow linearly with the number of states, then the lower bound on the height of towers is exponential with respect to that number. In this case, there is a gap between the lower bound and the upper bound, and the asymptotically optimal bound remains open. Chapter 4 is devoted to these problems. A regular language is fc-piecewise testable if it is a finite boolean combination of languages of the form Y,*a\L* ■ ■ ■ L*anL*, where at G £ and 0 < n < k. Given a DFA srf and k > 0, it is an NL- 4 complete problem to decide whether the language L(srf) is piecewise testable and, for k > 4, it is CONP-complete to decide whether the language L(srf) is fc-piecewise testable [67]. We discuss the complexity for k < 4. Furthermore, it is known that the depth of the minimal DFA equivalent to srf serves as an upper bound on k; if L(srf) is piecewise testable, then it is fc-piecewise testable for k equal to the depth of srf [68]. We show that some form of nondeterminism does not violate this upper bound result. Specifically, we define a class of self-loop deterministic poNFAs, called ptNFAs, that characterize piecewise testable languages and show that the depth of a ptNFA provides an (up to exponentially better) upper bound on k than the minimal DFA. Furthermore, if the language L(srf) is piecewise testable, we want to express it as a Boolean combination of languages of the above form. Our idea is as follows. If the language is piecewise testable, then it is fc-piecewise testable for some k, and hence there is a congruence ~k of finite index such that L(srf) is a finite union of ~£-classes. Each class is characterized by an intersection of languages of the from E*<2iE* • • -E*anE*, where n 2® is the transition function that can be extended to the domain 2^ x E* by induction. The language accepted by stf is the set L(s^) = {w E E* | <5(7, w) C\F ^ 0}. A path % from a state go to a state qn under a word a\a2 ■■■an, for some n > 0, is a sequence of states and input symbols q§a\q\a2.. .qn-\anqn such that qi+\ E 8(qi,cii+i), for all i = 0,11. The path Jt is accepting if qo El and gn G F. We use the notation go a'a2 a"> qn to denote that there exists a path from go to qn under the word a\a.2 ■ ■ ■ an. A path is simple if all states of the path are pairwise distinct. The number of states on the longest simple path of srf, starting in an initial state, decreased by one (i. e., the number of transitions on that path) is called the depth of srf, denoted by depth(£/). An automaton srf is complete if every transition is defined in every state, that is, for every state q of srf and every letter a E E, the set 8(q,a) is nonempty. An NFA srf is deterministic (DFA) if |/| = 1 and \8(q,a) \ < 1 for every q in Q and a in E. Note that we allow transitions to be undefined. To obtain a complete automaton, it is then necessary to add a sink state. The reachability relation < on the set of states is defined by p < q if there exists a word w E E* such that q E 8(p,w). An NFA srf is partially ordered (poNFA) if the reachability relation < is a partial order. For two states p and q of srf, we write p < q if p < q and p ^ q. A state p is maximal if there is no state q such that p < q. Partially ordered automata are sometimes called acyclic in the literature, but the reader should keep in mind that in this case self-loops are allowed. 8 3. Descriptional Complexity Descriptional complexity, also known as state complexity, studies the questions of the form: Given automata srf\, ^2,..., srfn and an «-ary operation op on languages. What is the minimum number of states of the automaton (deterministic or nondeterministic) recognizing the language op(L(^/i),L(^),... ,L(£/n))7 Indeed, the question makes sense if the considered class of languages is closed under the operation op, that is, if the automata srfi are of some type, then there is an automaton of the same type recognizing the language op(£/i,...,£/n). A typical and most studied example are deterministic and nondeterministic finite automata with the binary Boolean operations or with the unary operation reversal, which is the operation of our interest in this chapter. 3.1 Reversal The reverse wR of a word w is inductively defined by = e and, for a word v in E* and a symbol a in E, (va)R = avR. The reverse of a language L is the language LR = {wR \ w E L}. The reverse of a DFA srf = (<2,E, 8,i,F) is the NFA srfR obtained from srf by reversing all the transitions and by swapping the role of the initial and final states, that is, srfR = (<2,E, 8R,F, {*}), where SR(q,a) = {peQ \ 8(p7a) = q}. Let rev(s^) denote the minimal DFA equivalent to srfR. It is known that if srf is a deterministic finite automaton with n states, then the size of rev(srf) can be in the worst case of size 2" [89]. With this in mind, it could seem that the formula rev(rev(£/)) results in a DFA with a double exponential 22" state space, compared with the size of stf. It is not the case and, perhaps surprisingly, the result of these two exponential operations is the minimal DFA recognizing the language of srf. This is known as Brzozowski's minimization algorithm [18]. The principle of the double reverse further plays a role in the relationship between algebra and co-algebra [30]. 3.1.1 Reversal of ^-trivial Languages Motivated by Brzozowski's minimization algorithm, we asked the question about the state complexity of the reverse for partially ordered DEAs, recognizing ^-trivial languages, and showed that the size of the DFA for the reverse is at most 2" 1 and that the bound can be reached by DFAs over a ternary alphabet. Theorem 1. Let Lbe a language accepted by a minimal poDFA with n states. Then the minimal DFA accepting the reverse of the language L has at most 2n~l states. The bound is met by a ternary poDFA with a sink state, or by a poDFA over a growing alphabet without the sink state. 9 Worst-case sc(LR) where DFA for L is n = sc(L) without with Upper bound Lower bound sink state sink state 2n-2 + n- 1 2«-2 1 1 1 - - 2 2 2 2 1 3 4 4 4 2 4 7 7 7 4 5 12 12 12 8 6 21 21 21 16 7 34 34 38 32 8 55 64 71 64 Table 3.1: Tight bounds for the reverse of binary ^-trivial regular languages If the alphabet of the DFA is binary, then the bound is at most 2" 2 + n — 1, and hence the ternary alphabet is optimal to obtain the worst-case state complexity. Moreover, for n > 8, the tight bound for the binary case is 2n~2. We further provided a complete characterization of the tight bounds for ^-trivial regular languages depending on the state complexity of the language and the size of its alphabet. To formulate this result, we denote by fk(n) the state complexity function of the reverse on ^-trivial regular languages over a ^-element alphabet, that is, we define fk{n) = TonsLx{sc(LR) | L C E*, |E| = k,L is ^-trivial regular, and sc(L) = n} where sc(L) denotes the state complexity of the language L, that is, the number of states of its minimal DFA. Using this notation, we can summarize our results in the following theorem and Table 3.1. Theorem 2. Let n> 1 and let fk(n) be the state complexity of the reverse on M-trivial regular languages over a k-element alphabet. Then fl(n) = fi(n) = I on—2 h(n) = fk(n) = 2n-\for every k>3. 1, ifn = 1, 2n-2 + n-l7 if23 and let Lbe a J1 -trivial language over an (n — 2) -element alphabet with sc(L) = n. Then sc(LR) < 2n~l — 1 and the bound is tight. Corollary 5. Let Lbe a binary J!-trivial language with sc(L) = n, where n>4, then sc(LR) < 2«-3 _|_ min(max(2« — 3, (n — 2)2), 2n~3) + (n — 1). A few tight bounds for 2 < n < 7 are given in Table 3.1, since the bounds there are obtained for M-trivial languages that are also J"-trivial. The case of ^-trivial languages over (n — k)-element alphabets, for 2 < k < n — 3, is left open. However, Campeanu et al. [25] showed that there are finite binary languages whose reverse is of state complexity 3 • 2%~l — 1, if n even, and 2^" — 1, if « odd. Since every finite language is ^-trivial, we obtain at least these lower bounds for binary ^-trivial languages. The results of this section are mainly based on papers [60, 61] attached in Appendix ?? 11 4. Separability The motivation to study separability comes from scenarios in which we want to describe something complex by means of a simple language. The separation problem of our interest is of the following form: Given two languages K and L and a family of languages JF. Is there a language S in such that S contains everything from K and nothing from L? The family of simple languages could be, for example, languages definable in first-order logic, piecewise testable languages, or languages definable with a particular type of automata. For our theoretical research, we were motivated by several problems coming from practice: (a) increasing the user-friendliness of XML Schema and (b) efficient approximate query answering. XML Schema is currently the only industrially accepted and widely supported schema language for XML, designed to alleviate the limited expressiveness of Document Type Definition (DTD) [15], thereby making DTDs obsolete. However, XML Schema's extra expressiveness comes at the cost of simplicity. Its code is designed to be machine-readable rather than human-readable and its logical core, based on complex types, does not seem well-understood by users [77, 90]. One reason may be that the specification of XML Schema's core consists of over 100 pages of intricate text [44]. The BonXai schema language designed by Martens, Neven, Niewerth and Schwentick [77,78] is an attempt to overcome these issues and to combine the simplicity of DTDs with the expressiveness of XML Schema. It has the same expressive power as XML Schema, is designed to be human-readable, and avoids the use of complex types, aiming at simplifying the development or analysis of XSDs. The BonXai schema is a set of rules L\ —> R±,..., Ln —> Rn in which all Li and Rt are regular expressions. An unranked tree t (an XML document) is in the language of the schema if, for every node u, the word formed by the labels of w's children is in the language R^, where k is the largest number such that the word of ancestors of u is in This semantical definition is designed to ensure full compatibility with XML Schema [77, 78]. When translating an XML Schema Definition (XSD) into an equivalent BonXai schema, the regular expressions Li are obtained from a finite automaton that is embedded in the XSD. Since the current state-of-the-art in translating automata to expressions does not yet generate human-readable results, we investigated simpler classes of expressions that we expect to suffice in practice. Practical and theoretical studies show evidence that regular expressions of the form E*w (with w E E+) and E*<2iE* • • • E*an (with a\,..., an E E) and variations thereof seem to be well-suited [47, 65, 80]. Our second motivation comes from efficient approximate query answering. An efficient evaluation of regular expressions is relevant in a wide array of fields, for instance in graph databases and in the context of the SPARQL language [5, 51, 76, 94] for querying RDF data. Typically, regular expressions are used to match paths between nodes in a huge graph. In fact, the data can be so huge that the exact evaluation of a regular expression r over the graph (which can lead to a product construction between an automaton for the expression and the graph [76, 94]) may not be feasible within reasonable time. Therefore, as a trade-off to exact evaluation, one 12 could imagine that we try to rewrite the regular expression r as an expression that we can evaluate much more efficiently and is close enough to r. Specifically, we could specify two expressions rpos (resp., rneg) that define the language we want to (resp., do not want to) match in our answer and ask whether there exists a simple query (e. g., defining a piecewise testable language) that satisfies these constraints. Notice that the scenario of approximating an expression r in this way is very general and not even limited to databases. (Also, we can take rneg to be the complement of rpos.) At first sight, these two motivating scenarios may seem to be fundamentally different. In the first, we want to compute an exact simple description of a complex object and in the second we want to compute an approximate simple query that can be evaluated more efficiently. However, both scenarios boil down to the same underlying question of language separation. The effort to approximate languages by simpler languages is further related to system verification. The goal here is to express a given bad property in a simple logic for which verification is feasible or even efficient. If the property is not expressible in a simple logic, it could perhaps be over-approximated in a simple logic. If the system is then safe with respect to the over-approximated property, i. e. it does not satisfy the over-approximated bad property, then it is also safe with respect to the original property. Another situation is to require that every fair run of the system satisfies some additional conditions. Expressing fairness by a formula - - i/a =>- 2 rather than (fe, then the set of models satisfying i/a separates the sets of models of 2, respectively. Hence, this problem again boils down to the separation problem. The reader familiar with program verification might have noticed a close relationship to interpolation, a method providing means to compute separation between good and bad states [31, 105]. Separability is further of interest in logic on words. Place and Zeitoun [100] used separability to obtain new decidability results for the membership problem for some levels of the Straubing-Therien hierarchy [122, 124]. However, the problem remains open for almost all levels of the hierarchy [2, 97, 99]. Separability by piecewise testable languages has also been investigated outside the family of regular languages. Although separability of context-free languages by regular languages is undecidable [58], separability by piecewise testable languages is decidable [35]. The problem was further generalized to regular tree languages by Goubault-Larrecq and Schmitz [50], and studied for other types of languages as well, see Czerwihski and Lasota [33] for an overview of the latest development. 4.1 Separability of Languages A language S separates language Kfrom L if S contains K and does not intersect L. We say that S separates K and L if it either separates K from Lor L from K. Let be a family of languages. Languages K and L are separable by & if there exists a language S in that separates K and L. Languages K and L are layer-separable by & if there exists a finite sequence of languages Si,..., Sm in & such that 1. for all 1 < i < m, language Si \ Upi Sj intersects at most one of K and L, and 2. K or L (possibly both) is included in 1J™=1 Sj. Separability implies layer-separability, but the opposite implication does not hold. Our motivation for layered separability comes from the BonXai schema language. We need to solve layer-separability if we want to decide whether an XML Schema has an equivalent BonXai 13 schema with simple regular expressions (defining languages in JP). Layered separability implies that languages are, in a sense, separable by languages from & in a priority-based system—if we consider the ordered sequence of languages Si, S2,..., Sm, then, in order to classify a word w from K U L as either in K or in L, we have to match it against the St in the increasing order of the index i. Then, as soon as we find the lowest index j for which w E Sj, we know whether w E K ovwEL. A quasi-order is a reflexive and transitive relation. A quasi-order ^ on a set X is a well-quasi-ordering (WQO) if for every infinite sequence of elements of X, there exist indices i < j such that Xi =4 Xj. It is known that every WQO is well-founded, that is, there exist no infinite descending sequences x\ )p X2 >r • • • such that Xj ^ jq+i for all i. For a quasi-order ^, the (upward) ^-closure of a language L is the set up^(L) = {w \ v =4 w for some v EL}. Language L is (upward) ^.-closed if L = up^(L). We now extend the notion of alternating towers of Stern [119] and use it to determine when two languages are not separable. For languages K and L and a quasi-order ^, we say that a sequence (wi)\=l of words is a ^,-tower between K and L if w\ E KUL and, for all i= l,...,k— 1: (1) wt ^ Wi+\; (2) wt E K implies Wj+i E L; and (3) wt E L implies Wj+i E K. We say that k is the height of the ^-tower. We similarly define an infinite sequence of words to be an infinite ^-tower between K and L. For v = a\ ■ ■ ■ an and w E E*<2iE* • • • E*anE*, we say that v is a subsequence of w, and use the notation v -< w to denote the subsequence order. If we consider the subsequence order then we simply talk about a tower rather than about a -<-tower. We now characterize separability of two languages by a family of ^-closed languages for a WQO relation ^. Theorem 6. For languages K and L and a WQO ^ on words, the following are equivalent. 1. K and L are separable by a boolean combination of ^.-closed languages. 2. K and L are layer-separable by ^-closed languages. 3. There does not exist an infinite ^,-tower between K and L. Some of the equivalences hold even if the assumptions are weakened. For example, the equivalence between (1) and (2) does not require ^ to be a WQO. Since the subsequence order -< is a WQO on words, the languages K and L are separable by piecewise testable languages if and only if they are layer-separable by ^-closed languages. Actually, since -< as a WQO has only finitely many minimal elements within a language, the latter is equivalent to being layer-separable by shuffle ideals, that is, by languages of the form E*aiE*---E*a„E*. We have shown how to decide the existence of an infinite tower between two regular languages, given as regular expressions or NFAs, in polynomial time, which is by Theorem 6 equivalent to deciding whether the two languages can be separated by a piecewise testable language. Theorem 7. Given two NFAs stf and SB, it is possible to test in polynomial time whether L(srf) and L(0) can be separated by a piecewise testable language. We have shown that if there is an infinite tower between two regular languages, then there is an infinite tower of a special form in which every word can be decomposed in some synchronized manner. We can find these special forms of towers in polynomial time in the NFAs. The main 14 &(0,C) single unions be (boolean combinations) ^ (subsequence) NP-complete PTlME PTlME-complete ^s (suffix) PTlME PTlME PTlME Table 4.1: The complexity of deciding separability for regular languages K and L. features are that our algorithm runs exponentially faster in the alphabet size than the previous state-of-the-art [4] and that our algorithm and its proof of correctness do not require knowledge of the algebraic perspective on regular languages. To conclude this part, we have further shown that the considered problem is PTlME-hard. Consequently, the problem cannot be efficiently parallelized [6]. Theorem 8. Deciding separability of regular languages, represented as NFAs, by piecewise testable languages is PTlME-complete. It remains PTlME-hard even for minimal DFAs. 4.2 Asymmetric Separation and Suffix Order In this section, we present a bigger picture on efficient separations relevant to our motivation scenarios. Namely, we consider what happens when we restrict the allowed boolean combinations of languages. This means that separation is no longer symmetric. We also consider the suffix order ^s between words in which v^sw if and only if v is a (not necessarily strict) suffix of w. An important technical difference is that the suffix order is not a WQO. Indeed, the suffix order -o^'- Definitions imply that w E LI+i if and only if there is a tower w\ ^ w\ ^ wi ^ w'2 ^ "' ^ wi ^ w[ = w between K and L. Therefore, if the maximum height of a tower between K and L is r < 2j — 1, then LJ+i is empty. Then Sj = up(Kj) and S = |J^=0 Sj is the piecewise testable separator we are looking for. Notice that the complexity of the above construction depends on the maximal height of the tower between K and L, which motivates our study on the upper and lower bounds on the height of finite towers discussed below. The relationship between the maximal height of towers and the number K of Place et al. is another interesting question. The number of classes of the equivalence relation ~K indeed depends on K and was investigated by Karandikar et al. [63]. We showed that, in some sense, K provides an upper bound on the maximal height of towers, and that K can be arbitrarily larger than the maximal height of towers [55]. The complexity of a separator S can also be measured by the number of elementary languages of the form up(w) needed in the boolean expression defining S. Let F be the set of words such that S is a boolean combination of languages up(w), where w E F. For each word u E E*, the truth value of u E K is determined by the set o(u) = {w E F \ uE up(w)}. In particular, o(u) = o(v) implies that u E S if and only if v E S. Observe that u r — I. This means that any such a boolean expression requires at least as many elements as is the height of the maximal tower. 4.3.1 Bounds on the Height of Towers Not much is known about the upper bound on the height of towers between two regular languages if no infinite tower exists. The only result we are aware of is a result by Stern [119] giving an exponential upper bound 2^ n on the height of towers between a piecewise testable language over an alphabet E represented by an w-state minimal DFA and its complement. We present a better bound that holds in a general setting of two arbitrary regular languages (having no infinite tower) represented by NFAs. Theorem 10. Let £/q and srf\ be NFAs with n and m states, respectively, over an alphabet E. Assume that there is no infinite tower between the languages L(s&q) and L{srf\), and let (wi)ri=i be a tower between the languages such that wi G L{s^t mo(j 2)- Let 1 < /I < max(«, m) denote the maximum of the depths of and Then r < M ,—. Thus, the upper bound on the height of towers between two regular languages represented by NFAs is polynomial with respect to the depth of the NFAs and exponential with respect to the size of the alphabet. The question now is how good this bound is. We study this question next and show that it is tight if the alphabet is fixed. If the alphabet grows with the number of states of the automata, then we can construct a tower of exponential height with respect to the number of states of the automata (as well as with respect to the size of the alphabet). However, we do not know whether this bound is tight. We formulate this question as the following open problem asking how much the size of the alphabet can increase the height of the tower, given the number of states (or the depth). Open Problem 11. Let £/q and srf\ be NFAs with n and m states, respectively, over an alphabet E with |E| >n + m. Let /1 be the maximum depth of £/q and srf\. Assume that there is no infinite tower between the languages L(£/q) and L{s^\), and let (wi)ri=l be a tower between them. Is it ,.«+m+l_i true that r < M or even that r < 2n+ml The upper bound result indicates that the size of the alphabet is significant for the height of towers. This is confirmed by lower bounds considered now. We consider two cases, namely (i) the size of the alphabet is fixed and (ii) the size of the alphabet may grow with the size of the automata. We show that the upper bound is asymptotically tight if the size of the alphabet is fixed, and that the lower bound may be exponential with respect to the size of the automata if the alphabet may grow. In this case, the size of the alphabet is approximately the number of states of the automata. Theorem 12. For all integers n,m>2 there exist two NFAs with n and m states over an alphabet of cardinality n + m — 2 having a tower of height 2n+m~2 — 2m~l + 2 and no infinite tower. We can adapt the theorem to deterministic automata as follows. Theorem 13. For all integers k>\,d>2 and every odd positive integer e, there exist two DFAs with (k + l)d + k — 1 and e+1 states over an alphabet of cardinality k+1 having a tower of height (e + l)dk + 2dk~l and no infinite tower. Consequently, we have that the upper bound is tight for a fixed alphabet even for DFAs. Corollary 14. Let k > 2 be a constant. Then the maximum height of a tower between two DFAs with at most n states over an alphabet of cardinality k having no infinite tower is in 17 If the alphabet is allowed to grow with the number of states, we have shown that the height of a tower can be exponential in the number of states of NFAs. For DFAs with at most n states, we obtain that the height of a tower is Q. (^(n + 1)2^. To obtain a better lower bound for DFAs, we introduced a "determinization" strategy [55]. Theorem 15. For every n>0, there exist two DFAs with at most n+1 states over an alphabet of cardinality _|_ 1 having a tower of height 2n and no infinite tower. The "determinization" strategy further allows us to prove the following results. Theorem 16. For every two NFAs srf and SS with at most n states and k input letters, there exist two DFAs and SB' with O (m2) states and 0(k + n) input letters such that there is a tower of height r between stf and SS if and only if there is a tower of height r between srf' and SB'. In particular, there is an infinite tower between stf and SS if and only if there is an infinite tower between srf' and SB'. Theorem 17. For every two NFAs srf and SS with at most n states and k input letters, there exist two DFAs £/' and SB' with 0(kri) states and O(kn) input letters such that there is a tower of height r between srf and SS if and only if there is a tower of height r between srf' and SB'. In particular, there is an infinite tower between stf and SS if and only if there is an infinite tower between srf' and SB'. The lower bounds are not asymptotically equal to the upper bound and it is not known what the (asymptotically) tight upper bound actually is. Specifically, we do not know whether an alphabet of size greater than the number of states may help to build higher towers. Interestingly, the towers used in the constructions to demonstrate lower bounds are mostly sequences of prefixes. Therefore, we also investigated towers of prefixes. We provided a pattern that characterizes the existence of an infinite tower of prefixes and proved tight bounds on the height of towers of prefixes for DFAs and NFAs. This study can be found in our original paper [55]. Our main results are summarized in Table 4.2. The main papers [34, 83, 54, 55] on which the results of this chapter are based are attached in Appendix ??. 18 Upper bound Lower bound |E| =k E >n + m NFAs DFAs M- 1 a (2n+m) (a) Towers of subsequences over L; pi = max(«, m) Upper bound Lower bound |E| = 2 E >n + m NFAs (2"-l)(2m-l) + l / 1 2»+m—2—o(l) 2 j DFAs nm T + 1 v nm ~2 / + 1 nm - + 1 (b) Towers of prefixes; v = min(«,m) Table 4.2: Upper and lower bounds on the height of towers of subsequences and prefixes for automata with n and m states 19 5. Complexity of Universality Universality is a fundamental question asking whether a given system recognizes all words over its alphabet. Deciding universality is typically more difficult than deciding the word problem. The study of universality (and its dual - emptiness) has a long tradition in formal languages with many applications across computer science, e. g., in knowledge representation and database theory [9, 24, 118] or in verification [8]. Recent studies investigate the problem for specific types of automata or grammars, e. g., for prefixes or factors of regular languages [102]. Deciding universality for systems modeled by NFAs is pspace-complete [88], and there are two typical proof techniques to show hardness. One is based on the reduction from the DFA-union-universality problem [70], and the other on the reduction from the word problem for polynomially-space-bounded Turing machines [1]. Kozen's [70] proof showing PSpace-hardness of DFA-union universality (actually of its complemented equivalent, DFA-intersection emptiness) results in DFAs consisting of nontrivial cycles, and these cycles are essential for the proof; if all cycles of the DFAs were only self-loops, then the problem would be easier: Theorem 18. The intersection-emptiness problem for poDFAs/poNFAs is conp -complete. It is conp -hard even if the alphabet is binary. We show that deciding universality for poNFAs has the same worst-case complexity as for general NFAs, even if restricted to binary alphabets [72]. This is caused by an unbounded number of nondeterministic steps admitted in poNFAs - they either stay in the same state or move to another. Forbidding this kind of nondeterminism affects the complexity of deciding universality -it is conp-complete if the alphabet is fixed but remains pspace-complete if the alphabet may grow polynomially [72]. The growth of the alphabet thus compensates for the restricted number of nondeterministic steps. Adding further a structural assumption of confluence on top of these models preserves the complexity. Our results are summarized in Table 5.1 and further discussed below with more details. As already pointed out, we are interested in the universality problem for partially ordered NFAs (poNFAs) and special cases thereof. An NFA is partially ordered if its transition relation ST |E| = 1 \L\=k>2 E is growing DFA L-comp. [62] NL-comp. [62] NL-comp. [62] spoNFA 1 2 AC0 AC0 AC0 ptNFA 1 NL-comp. CONP-comp. pspace-comp. rpoNFA NL-comp. CONP-comp. pspace-comp. poNFA 3 2 NL-comp. pspace-comp. pspace-comp. [1] NFA CONP-comp. [121] pspace-comp. [1] pspace-comp. [1] Table 5.1: Complexity of deciding universality for poNFAs and special classes thereof; ST stands for the corresponding level of the Straubing-Therien hierarchy; E denotes the input alphabet 20 a Figure 5.1: Forbidden pattern of rpoNFAs induces a partial order on states: the only cycles allowed are self-loops on a single state. Partially ordered NFAs define a natural class of languages that has been shown to coincide with level | of the Straubing-Therien hierarchy [111] and with Alphabetical Pattern Constraint (APC) languages, a subclass of regular languages effectively closed under permutation rewriting [14]. Deciding whether an automaton recognizes an APC language (and hence whether it can be recognized by a poNFA) is PSPACE-complete for NFAs and NL-complete for DFAs [14]. Restricting to partially ordered deterministic finite automata (poDFAs), we can capture further classes of interest: two-way poDFAs characterize languages whose syntactic monoid belongs to the variety DA [111], introduced by Schutzenberger [110]; poDFAs characterize ^-trivial languages [19]; and confluent poDFAs characterize level 1 of the Straubing-Therien hierarchy, also known as ^-trivial languages or piecewise testable languages [115]. Other relevant classes of partially ordered automata include partially ordered Biichi automata [73] and two-way poDFAs with look-around [75]. The first result on the complexity of universality for poNFAs is readily obtained. It is well known that universality of regular expressions is PSPACE-complete [1, Lemma 10.2], and it is easy to verify that the regular expressions used in the proof can be expressed in poNFAs: Corollary 19 (Lemma 10.2 [1]). The universality problem for poNFAs is PSPACE-complete. A closer look at the proof reveals that the underlying encoding requires an alphabet of size linear in the input: PSPACE-hardness is not established for alphabets of bounded size. Usually, one could simply encode alphabet symbols o by sequences 0\ • • • on of symbols from a smaller alphabet, say {0,1}. However, doing this requires self-loops q A q to be replaced by nontrivial cycles q % • • • ^ q, which are not permitted in poNFAs. We settle this open problem by showing that PSPACE-hardness is retained even for binary alphabets. This negative result leads us to ask if there is a natural subclass of poNFAs for which universality does become simpler. We consider restricted poNFAs (rpoNFAs), which require self-loops to be deterministic in the sense that the automaton contains no transition as in Figure 5.1, which we call nondeterministic self-loops. Large parts of the former hardness proof hinge on transitions of this form, which, speaking intuitively, allow the automaton to navigate to an arbitrary position in the input (using the loop) and, thereafter, continue checking an arbitrary pattern. Indeed, we find that the universality becomes CONP-complete for rpoNFAs with a fixed alphabet. However, this reduction of complexity is not preserved for unrestricted alphabets. We have used a novel construction of rpoNFAs that characterize certain exponentially long words to show that universality is PSPACE-complete even for rpoNFAs if the alphabet may grow polynomially. As a by-product, we have shown that rpoNFAs provide another characterization of ^-trivial languages introduced and studied by Brzozowski and Fich [19], and we have established the complexity of deciding ^-triviality and fc-^-triviality for rpoNFAs. From the practical point of view, the problems of inclusion and equivalence of two languages, which are closely related to universality, are of interest, e. g., in optimization. Indeed, universality can be expressed either as the inclusion E* C L or as the equivalence E* = L. Although equivalence can be seen as two inclusions, the complexity of inclusion does not play the role of a lower bound. For instance, for two deterministic context-free languages, inclusion is undecidable [42], whereas equivalence is decidable [112]. However, the complexity of universality gives a lower 21 bound on the complexity of both inclusion and equivalence, and we have shown that, for the studied partially ordered NFAs, the complexities of inclusion and equivalence coincide with the complexity of universality. 5.1 Partially Ordered NFAs The languages recognized by poNFAs are exactly the languages on level | of the Straubing-Therien hierarchy [111]. Since the hierarchy is proper, this means that poNFAs can only recognize a strict subset of star-free regular languages. In spite of this rather low expressive power, the universality problem of poNFAs has the same worst-case complexity as for general NFAs, even when restricted to a fixed alphabet with only a few letters. Theorem 20. For every alphabet E with |E| > 2, the universality problem for poNFAs over E is PSPACE-complete. Ellul et al. [41, Section 5] give an example of a regular expression over a 5-letter alphabet such that the shortest non-accepted word is of exponential length, and which can also be encoded as a poNFA. Our previous proof shows such an example for an alphabet of two letters, if we use a Turing machine that runs for exponentially many steps before accepting. Note, however, that this property alone would not imply Theorem 20. Reducing the size of the alphabet to one leads to a reduction in complexity. This is expected, since the universality problem for NFAs over a unary alphabet is merely CONP-complete [121]. For poNFAs, the situation is even simpler: Theorem 21. The universality problem for poNFAs over a unary alphabet is NL-complete. It can be checked in linear time. 5.2 Restricted Partially Ordered NFAs Restricted poNFAs are distinguished by deterministic self-loops. We relate them to the known class of ^-trivial languages, and we establish complexity results for deciding whether a language falls into this class. Definition 22. A restricted partially ordered NFA (rpoNFA) is a poNFA such that, for every state q and symbol a, if q G 8(q,a) then 8(q,a) = {q}. We show that rpoNFAs characterize ^-trivial languages, a subclass of regular languages defined by Brzozowski and Fich [19]. To introduce this class of languages, we require some auxiliary definitions. A word v = a\a2 • • • a« is a subsequence of a word w, denoted by v ^ w, if w G L*aiL*a2L* •••E*a„E*. For k > 0, we write subk(v) = {u G E* | u ^ v, \u\ < k} for the set of all subsequences of v of length up to k. Two words w\^w2 are ~k-equivalent, written w\ ~£ w2, if subfc(wi) = subk(w2). Then ~k is a congruence (for concatenation) of finite index (i. e., with finitely many equivalence classes) [115]. ^-trivial languages are defined by defining a related congruence that considers subsequences of prefixes: Definition 23. Let x,y G E* and k > 0. Then x ~f y if and only if • for each prefix u of x, there exists a prefix v of y such that u ~£ v, and • for each prefix v of y, there exists a prefix u of x such that u ~£ v. 22 A regular language is k-M-trivial if it is a union of ~^ classes, and it is ^-trivial if it is fc-^-trivial for some k > 0. It is known that x y implies x ~£ y and (if k > 1) x ~f_i y [19]. Therefore, every fc-^-trivial language is also + 1)-^-trivial. Moreover, it has been shown that a language L is ^-trivial if and only if the minimal DFA recognizing L is partially ordered [19]. We can lift this result to characterize the expressive power of rpoNFAs. Theorem 24. A regular language is &-trivial if and only if it is accepted by an rpoNFA. This characterization in terms of automata with forbidden patterns can be compared to results of GlaBer and Schmitz, who use DFAs with a forbidden pattern to obtain a characterization of level | of the dot-depth hierarchy [49, 108]. We can further relate the depth of rpoNFAs to fc-^-trivial languages. Recall that the depth of an rpoNFA srf, denoted by depth(,e/), is the number of input symbols on a longest simple path of srf that starts in an initial state. Theorem 25. The language recognized by a complete rpoNFA stf is depth(^/) -8&-trivial. Similar relationships have been studied for ^-trivial languages [68, 81], but we are not aware of any such investigation for ^-trivial languages. We may ask how difficult it is to decide whether a given NFA srf accepts a language that is ^-trivial or fc-^-trivial for a specific k > 0. For most levels of the Straubing-Therien hierarchy, it is not even known if this problem is decidable, and when it is, exact complexity bounds are often missing [99]. The main exception are ^-trivial languages—level 1 of the hierarchy. To the best of our knowledge, the following complexity results for recognizing (fc-^-trivial languages had not been obtained previously. Theorem 26. Given an NFA srf, it is PSPACE-complete to decide whether the language accepted by srf is ^-trivial. Theorem 27. Given an NFA stf and k > 0, it is PSPACE-complete to decide whether the language accepted by stf is k-M-trivial. In both previous theorems, hardness is shown by reduction from the universality problem for NEAs [1, 88]. Hence it holds even for binary alphabets. For a unary alphabet, we can obtain the following result. Theorem 28. Given an NFA srf over a unary alphabet, the problems of deciding whether the language accepted by stf is 8%-trivial, or k-&-trivial for a given k > 0, are both CONP-complete. We now briefly discuss the complexity of the problem if the language is given as a poNFA rather than an NFA. Theorem 29. Given a poNFA srf, the problems of deciding whether the language accepted by stf is 8%-trivial, or k-&-trivial for a given k > 0, are both PSPACE-complete. We point out that the previous result holds even if the input alphabet of srf is binary. For unary alphabets, the classes of languages of unary poNFAs and of unary ^-trivial languages coincide. Theorem 30. The classes of unary poNFA languages and unary &-trivial languages coincide. 23 5.2.1 Deciding Universality of rpoNFAs We now return to the universality problem for the case of rpoNFAs. We first show that we can indeed obtain the hoped-for reduction in complexity when using a fixed alphabet. For the general case, however, we can recover the same PS PACE lower bound as for poNFAs, albeit with a more involved proof. Even for fixed alphabets, we can get a CONP lower bound: Lemma 31. The universality problem of rpoNFAs is CONP-hard even when restricting to alphabets with two letters. For a matching upper bound, if the size |E| of the alphabet is bounded, then non-universality is witnessed by a word of polynomial length. Together with Lemma 31, this allows us to establish the following result and its immediate corollary. Theorem 32. Let E be a fixed non-unary alphabet, and let SS be an rpoNFA over E. If' srf is an NFA (poNFA, rpoNFA, DFA, poDFA) over E, then the problem whether L(srf) C L(SS) is CONP-complete. Corollary 33. Let E be a fixed non-unary alphabet. Then the universality problem for rpoNFAs over E is CONP-complete. Since the proof of Theorem 21 also applies to rpoNFAs, we immediately have the following result. Corollary 34. The universality problem for rpoNFAs over a unary alphabet is NL-complete. □ Without fixing the alphabet, universality remains PSPACE-hard even for rpoNFAs, but a proof along the lines of Theorem 20 is not straightforward. In essence, rpoNFAs lose the ability to navigate to an arbitrary position within a word for checking some pattern there. Expressions of the form (E* • • •), which we frequently used there (see [72, Theorem 3] for details), are therefore excluded. This is problematic since the run of a polynomially space-bounded Turing machine may be of exponential length, and we need to match patterns across the full length of our (equally exponential) encoding of this run. How can we navigate such a long word without using E*? Our answer is to first define an rpoNFA that accepts all words except for a single, exponentially long word. This word will then be used as an rpoNFA-supported "substrate" for our Turing machine encoding. Lemma 35. For all positive integers k and n, there exists an rpoNFA srf^n over an n-letter alphabet with n(k + 2) states such that the unique word not accepted by is of length (kT) -1- As a corollary, we find that there are rpoNFAs srf = stfn^n for which the shortest non-accepted word is exponential in the size of srf. Note that (2n) > 2n. Corollary 36. For every integer n> 1, there is an rpoNFA &tfn over an n-letter alphabet with n(n + 2) states such that the shortest word not accepted by stfn is of length (2^) — 1. Therefore, any minimal DFA accepting the same language has at least (^) states. To simulate exponentially long runs of a Turing machine, we start from an encoding of runs using words #vt>i#- • -#wm# (see the details in the original paper [72] in the appendix) and we combine every letter of this encoding with one letter of the alphabet of srfn. We then accept all words for which the projection to the alphabet of srfn is accepted by srfn, i. e., all but those words of exponential length that are based on the unique word not accepted by srfn. We ensure that, if there is an accepting run, it will have an encoding of this length. It remains to eliminate (accept) 24 a,b a a,b Figure 5.2: A confluent automaton accepting a non-piecewise testable language all words that correspond to a non-accepting or wrongly encoded run. We can check this by restricting to the first components of our combined alphabet. The self-loop that was used to encode E* in poNFAs is replaced by a full copy of sén, with an additional transition from each state that allows us to leave this "loop". This does not simulate the full loop, but it allows us to navigate the entirety of our exponential word, which is all we need (more intuition in the next section; details in the appendix). Theorem 37. The universality problem for rpoNFAs is PSPACE-complete. 5.3 PtNFAs An NFA sé is a ptNFA if it is an rpoNFA that is complete and confluent; the name comes from piecewise testable, since ptNFAs characterize piecewise testable languages [81, 86]. An alternative and our original definition of ptNFAs uses the notion of unique maximal state property, which we now briefly discuss. Recall that for two states p and q, we write p < q if p < q and p ^ q. A state p is maximal if there is no state q such that p < q. A poNFA sé over E with the state set Q can be turned into a directed graph G(&/) with the set of vertices Q where a pair (p,q) E Qx Q is an edge in G(&/) if there is a transition from p to q in sé. For an alphabet T C E, we define the directed graph G(^/,r) with the set of vertices Q by considering only those transitions corresponding to letters in r. Let L(p) = {a E E | p A- p} denote all letters labeling self-loops in state p. We say that sé satisfies the unique maximal state (UMS) property if, for every state q of sé, q is the unique maximal state of the connected component of G(^/,E(g)) containing q. To decide whether a DFA recognizes a piecewise testable language, Klíma and Polák [68] checks confluence while Trahtman [126] checks the UMS property. Both notions have their advantages and an effect on the complexity. While Trahtman's algorithm runs in time quadratic with respect to the number of states and linear with respect to the size of the alphabet, Klíma and Polák's algorithm runs in time linear with respect to the number of states and quadratic with respect to the size of the alphabet. Notice that Cho and Huynh [27] proved that deciding piecewise testability for DFAs is NL-complete. Although the notions of UMS and confluence coincide for DFAs, they differ for NFAs. The automaton in Figure 5.2 is confluent, but it does not satisfy the UMS property. Its language is not piecewise testable, since there is an infinite sequence a^ab^aba^abab^... that alternates between accepted and non-accepted states, and hence there is a non-trivial cycle in the corresponding minimal DFA. We now relate these two notions and use the following lemma as an alternative definition of ptNFAs (we used it as a definition in our previous work [81]). Lemma 38. PoNFAs that are complete and satisfy the UMS property are exactly ptNFAs. 5.3.1 Deciding Universality for ptNFAs We now study the complexity of deciding universality for ptNFAs. 25 For unary alphabets, deciding universality for ptNFAs is solvable in polynomial time [72]. We now improve the result and show that the problem can be efficiently parallelized. Theorem 39. Deciding universality for ptNFAs over a unary alphabet is Nh-complete. We next show that if the alphabet is fixed, deciding universality for ptNFAs is CONP-complete, and that hardness holds even if restricted to binary alphabets. Our proof is based on the construction that non-equivalence for regular expressions with operations union and concatenation is NP-complete even if one of them is of the form En for some fixed n [57, 121]. Theorem 40. Deciding universality for ptNFAs over a fixed alphabet is CONP-complete even if the alphabet is binary. If the alphabet may grow polynomially with the number of states, there are basically two approaches how to tackle the universality problem for ptNFAs to show pspace-hardness: (1) to use a reduction from Kozen's DFA-union-universality problem [70], or (2) to use a reduction from the word problem of a polynomially-space-bounded Turing machines a la Aho, Hopcroft and Ullman [1]. To use the union-universality problem for our purposes, we would need to use partially ordered DFAs rather than general DFAs to ensure that the union of the DFAs is partially ordered. However, we have shown that the difficulty of the DFA-union-universality problem comes from nontrivial cycles, and hence its partially-ordered variant is easier unless PSpace = NP. We consider the complemented equivalent of the problem for which we can prove a stronger result (cf. Theorem 18). The DFA-intersection emptiness problem asks, given n DFAs, whether the intersection of their languages is empty. Indeed, the union of n DFA languages is universal if and only if the intersection of their complements is empty. Thus, we have the following corollary. Corollary 41. The poDFA-union-universality problem is CONP-complete. □ We point out that the result cannot be further improved by restricting the size of the alphabet since the intersection-emptiness problem for unary poNFAs can be solved in polynomial time. Indeed, if there is a word in the intersection nf=i L{srfi), then there is one that is a prefix of the word akl^ vkn, where kj is the depth of which is of polynomial length. It can be shown, and it is somehow intuitive, that every rpoNFA is a union of a number of poDFAs. In other words, every rpoNFA can be decomposed into the union of a number of poDFAs. Then the question whether an rpoNFA is universal is equivalent to the question whether the union of the languages of the poDFAs is universal. Since deciding universality for rpoNFAs is pspace-complete (and we show the same complexity for ptNFAs), the previous corollary implies that the decomposition cannot be constructed in polynomial time. Thus, we cannot adapt Kozen's construction to show pspace-hardness of deciding universality for ptNFAs. The situation is, however, different for the reduction from the word problem of a polynomially-space-bounded Turing machines, which we have modified to prove pspace-hardness for the problem if the alphabet may grow polynomially with the number of states of the automaton. To prove the result, we take, for a polynomial p, a /?-space-bounded deterministic Turing machine ^# together with an input x, and encode the computations of ^# on x as words over some alphabet E that depends on the alphabet and the state set of One then constructs a regular expression (or an NFA) Rx representing all computations that do not encode an accepting run of ^# on x. That is, L(RX) = E* if and only if ^# does not accept x [1]. The form of Rx is relatively simple, consisting of a union of expressions of the form L*KL* (5.1) 26 A copy of the ptNFA for K A copy of the ptNFA for K Substitute for initial S* Substitute for ending S* The ptNFA An,n Figure 5.3: Construction of a self-loop-deterministic poNFA (solid edges) solving problem (i), illustrated for two copies of the ptNFA for K, and its completion to a ptNFA (dashed edges) solving problem (ii) where K is a finite language of words of length 0(p(\x\)). Intuitively, K encodes possible violations of a correct computation of ^# on x, such as the initial configuration does not contain the input x, or the step from a configuration to the next one does not correspond to a rule of These checks are local, involving at most two consecutive configurations of each of polynomial size. Hence they can be encoded as the finite language K. The initial segment E* of (5.1) nondeterministically guesses a position of the computation where a violation encoded by K occurs, and the last E* reads the rest of the word if the violation check was successful. Nonetheless, this idea cannot be directly used to prove our result for two reasons: (i) Although expression (5.1) can easily be translated to a poNFA, it is not true for ptNFAs because the translation of the leading part Y,*K may not be self-loop-deterministic; (ii) The constructed poNFA may be incomplete and its "standard" completion by adding the missing transitions to a new sink state may violate confluence. A first observation to overcome these problems is that the length of the encoding of a computation of ^# on x is at most exponential with respect to the size of ^# and x. It would therefore be sufficient to replace the initial segment E* in (5.1) by prefixes of an exponentially long word. However, such a word cannot be constructed by a polynomial-time reduction. Instead, we replace the leading E* with a ptNFA encoding such an exponential word, which exists and is of polynomial size as we show in Lemma 42 - there we construct, in polynomial time, a ptNFA srfnjt that accepts all words but a single one, Wn,n, of exponential length. Lemma 42. For all integers k,n> 1, there exists a ptNFA ^4 n over an n-letter alphabet with n(2k+ 1) + 1 states, such that the unique non-accepted word of£/t,n is of length (k^n) — 1. Since the language K of (5.1) is finite, and hence piecewise testable, there is a ptNFA recognizing K. For every state of ^4,n, we make a copy of the ptNFA for K and identify its initial state with the state of s^n^n if it does not violate self-loop-determinism; see Figure 5.3 for an illustration. We keep track of the words read by both stfn^n and the ptNFA for K by taking the Cartesian product of their alphabets. A letter is then a pair of symbols, where the first symbol is the input for stfn^n and the second is the input for the ptNFA for K. A word over this alphabet is accepted if the first components do not form the word Wn^n or the second components form a word that is not a correct encoding of a run of ^# on x. This results in a self-loop-deterministic poNFA that overcomes problem (i). However, this technique is not sufficient to resolve problem (ii). Although the construction yields a self-loop-deterministic poNFA (rpoNFA) that is universal if and only if the regular expression Rx is [72], it is incomplete and its "standard" completion by adding the missing 27 A\B DFA ptNFA & rpoNFA poNFA NFA DFA L/NL NL/CONP/pspace NL/PSpace CONP/PSpace ptNFA NL NL/coNP/PSpace NL/PSpace coNP/PSpace rpoNFA NL NL/coNP/PSpace NL/PSpace coNP/PSpace poNFA NL NL/coNP/PSpace NL/PSpace coNP/PSpace NFA NL NL/coNP/PSpace NL/PSpace coNP/PSpace Table 5.2: Complexity of deciding inclusion L(A) C L(B) (unary/fixed[/growing] alphabet), all results are complete for the given class transitions to an additional sink state violates confluence. Because of different expressive powers, it is not always possible to complete an rpoNFA to obtain a ptNFA. But we show that it is possible in our case because the length of the input that is of interest is bounded by the length of the word Wn/J. The maximal state of s^n^n is accepting, and therefore all the missing transitions can be added so that the paths required by confluence meet in the maximal state of s^n,n- Since all words longer than |Wn/I| are accepted by s^n,n, we could complete the self-loop-deterministic poNFA by adding paths longer than \ Wn,n\ to the maximal state of s^n,n- However, this cannot be done by a polynomial-time reduction, since the length of Wnn is exponential. Instead, we add a ptNFA to encode such paths in the formal definition of s^n^n as given in Lemma 42. We then ensure confluence by adding the missing transitions to states of the ptNFA s^n^n from which the unread part of Wn^n is not accepted and from which the maximal state of stfn^n is reachable under the symbol of the added transition. The second condition ensures confluence, since all the transitions meet in the maximal state of s^n,n- The idea is illustrated in Figure 5.3. Theorem 43. Deciding universality for ptNFAs is PSPACE-complete. 5.4 Inclusion and Equivalence of Partially Ordered NFAs Universality is closely related to the inclusion and equivalence problems, which are of interest mainly from the point of view of optimization, e. g., in query answering. Given two languages K and L over E, the inclusion problem asks whether K C L and the equivalence problem asks whether K = L. Universality can then be expressed as the inclusion E* C L or the equivalence E* = L. Although equivalence means two inclusions, complexities of these two problems may differ significantly, e. g., inclusion is undecidable for deterministic context-free languages [42] while equivalence is decidable [112]. The relation of universality to inclusion and equivalence lies in the fact that the complexity of universality provides a lower bound on the complexity of both inclusion and equivalence. Therefore, it remains to show memberships of our results summarized in Tables 5.2 and 5.3. The complexity of inclusion and equivalence for regular expressions of special forms has been investigated by Martens et al. [79]. For a few of them, pspace-completeness of the inclusion problem has been achieved. The results were established for alphabets of unbounded size. Since some of the expressions define languages expressible by poNFAs, we readily have that the inclusion problem for poNFAs is pspace-complete. However, using Theorem 20 and the well-known ps pace upper bound on inclusion and equivalence for NFAs, we obtain that the inclusion and equivalence problems for poNFAs are pspace-complete even if the alphabet is binary. The expressions in Martens et al. [79] cannot be expressed as rpoNFAs. Hence the question for rpoNFAs was open. Using Theorem 37 and the upper bound for NFAs, we can easily establish 28 DFA ptNFA & rpoNFA poNFA NFA DFA ptNFA rpoNFA poNFA NFA L/NL NL/conp/pspace NL/coNP/PSpace NL/coNP/PSpace NL/PSpace NL/PSpace NL/PSpace NL/PSpace CONP/PSpace coNP/PSpace coNP/PSpace coNP/PSpace coNP/PSpace Table 5.3: Complexity of deciding equivalence (unary/fixed[/growing] alphabet), the problems are complete for the given classes that the inclusion and equivalence problems for rpoNFAs are pspace-complete. If the alphabet is fixed, the complexity of inclusion (and of equivalence) is covered by Theorem 32. For the unary case, it is known that the inclusion and equivalence problems for NFAs over a unary alphabet are CONP-complete [56, 121]. For poNFAs we have shown that the inclusion and equivalence problems for poNFAs over a unary alphabet are NL-complete. We now briefly explain the results summarized in the tables. Let srf be an automaton of any of the considered types. We now discuss the cases depending on the type of SB. We assume that both automata are over the same alphabet specified by SB. If SB is a DFA, then L(sz7) C L(SB) if and only if L{si) f]L{W) = 0, which can be checked in NL (or in L if both automata are unary DFAs), where SB denotes the DFA obtained by complementing SB. This covers the first column of Table 5.2. If SB is an rpoNFA over a fixed alphabet, then deciding L{srf) C L(SB) is in CONP [72, Theorem 23]. Furthermore, the case of a unary alphabet follows from the case of unary poNFAs, and the case of a growing alphabet from the case of general NFAs. If SB is a unary poNFA, we distinguish several cases. First, deciding whether the language of an NFA is finite is in NL. Thus, if L(srf) is infinite and L(SB) is finite, the inclusion does not hold. If both the languages are finite, then the number of words is bounded by the number of states, and hence the inclusion can be decided in NL. If L(SB) is infinite, then there is n bounded by the number of states of SB such that L(SB) contains all words of length at least n. Thus, the inclusion does not hold if and only if there is a word of length at most n in L(srf) that is not in L(SB), which can again be checked in NL. If SB is an NFA, then deciding L(srf) C L(SB) is in PSpace using the standard on-the-fly computation of SB and deciding L{srf) n L(SB) = 0. If SB is a unary NFA, then if L(SB) is finite, we proceed as in the case of SB being a unary poNFA. Therefore, assume that L(SB) is infinite and SB has n states. Then the minimal DFA recognizing L(SB) has at most 2" states (a better bound is shown by Chrobak [28]). If the inclusion L(srf) C L(SB) does not hold and srf has m states, then there exists k < m ■ 2n, the number of states of stf x SB, such that ak G L(s^) \L(SB). We can guess k in binary and verify that the inclusion does not hold in polynomial time by computing the reachable states under ak using the matrix multiplication. Hence, checking that the inclusion holds is in CONP. Notice that the upper-bound complexity for equivalence follows immediately from the upper-bound complexity for inclusion, which completes this section. The main papers [72, 84, 85] on which the results of this chapter are based are attached in Appendix ??. 29 6. Piecewise Testable Languages Recall that a regular language over E is piecewise testable (PT) if it is a finite boolean combination of languages of the form E*<2iE*<22^* • • -E*anE*, where at E E and n > 0. If n is bounded by a constant k, then the language is k-piecewise testable (fc-PT). Piecewise testable languages are exactly those regular languages whose syntactic monoid is ^-trivial [115]. Simon [116] provided various characterizations of piecewise testable languages, e. g., in terms of monoids or automata. These languages are of interest in many disciplines of mathematics, such as semigroup theory [3, 4, 96] for their relation to Green's relations or in logic on words [38, 98] for their relation to first-order logic FO[<] and the Straubing-Therien hierarchy [95, 122, 124, 125]. They are indeed studied in formal languages and automata theory [68], recently mainly in the context of separation [98, 127]. Piecewise testable languages form a strict subclass of star-free languages or, in other words, of the languages definable by LTL. They are investigated in natural language processing [43, 103], in cognitive and sub-regular complexity [104], in learning theory [45, 69], and in databases in the context of XML schema languages [34, 53, 54]. They have been extended from words to trees [13, 46]. 6.1 Finding a Boolean Combination We studied the problem of translating an automaton accepting a piecewise testable language into a Boolean combination of languages of the form Laiar-an = E*<2iE*<2iE* • • -E*anE*. Our motivation comes from the simplification of XML Schema, since such expressions resemble XPath-like expressions used in the BonXai schema language [78]. Since every piecewise testable language is k-PT for some k > 0, and a k-PT language is also (k+ 1)-PT, we focus on the Boolean combination of languages Lu, where the length of u is bounded by the minimal k for which the language is k-PT. From this point of view, we are interested in translating an automaton to the form of a generalized regular expression (an expression allowing the operation of complement). Notice that generalized regular expressions can be non-elementary more succinct than classical regular expressions [37, 121, 48] and that not much is known about these transformations [41]. There are many possible different Boolean combinations describing the same language, and it is not clear which of them is the best representation. The choice significantly depends on the applications. We are interested in those Boolean combinations that resemble the disjunctive normal form of logical formulas rather than in the most concise representation. The basic idea of our translation can be outlined as follows. Let L be a language over E represented by its minimal DFA, and let the equivalence relation ~k on E* be defined by u ~£ v if u and v have the same sets of (scattered) subwords up to length k, denoted by submit) = sub^(v). Then L is piecewise testable if and only if there exists a nonnegative integer k such that ~fcC~L5 where ~l is the Myhill congruence [91]. Thus, every k-PT language is a finite union of classes. As shown, for instance, by Klima [66], the ~£-classes can be described by languages of 30 the form uEsub^w) u^sub^w) ,\u\ 0 for which L is fc-piecewise testable. 3. Compute the finite number of representatives of the equivalence classes that form the union of the language L, express them as above and form their union. 6.1.1 Step 1: Checking Piecewise Testability The complexity of the first step has been studied in the literature. Simon [115] proved that PT languages are exactly those regular languages whose syntactic monoid is ^-trivial, which gives decidability. Stern [120] showed that the problem is decidable in polynomial time for languages represented by DFAs and Cho and Huynh [27] proved NL-completeness for DFAs. Later, Trahtman [126] showed that the problem is solvable in time quadratic with respect to the number of states of the DFA and linear with respect to the size of the alphabet, and Klíma and Polák [68] gave an algorithm that is quadratic in the size of the input alphabet and linear in the number of states of the DFA. For languages represented by NFAs, we have shown that the problem is PSPACE-complete [83]. 6.1.2 Step 2: Computing the Minimal k The second step gives rise to the k-piecewise testability problem formulated as follows: Input: an automaton (DFA or NFA) sé Output: Yes if and only if L(sé) is fc-piecewise testable The problem is trivially decidable for any k because there are only finitely many fc-PT languages over the alphabet of sé. We investigated the computational complexity of this problem. The CONP upper bound complexity for DFAs has been independently obtained by Hofman and Martens [53] (formulated in terms of separability and presented without proof), Klíma, Kunc and Polák [67], and Masopust and Thomazo [86]. Klíma, Kunc and Polák further proved that the problem is CONP-complete for DFAs if k > 4. What is the complexity if k < 4? We now answer this question. O-Piecewise Testability Let sé be a minimal DFA over an alphabet E. The language L(sď) is 0- PT if and only if it has a single state, that is, it recognizes either E* or 0. Thus, it is decidable in 0(1) whether L{st) is 0-PT. 1- Piecewise Testability We showed that the 1-PT problem belongs to AC0, which is a strict subset of LOGSPACE. There is an infinite hierarchy of classes Eř- (ITř) in AC0 based on the number of alternating levels of disjunctions and conjunctions. Specifically, Eř- (lij) is the class of problems solvable by uniform families of unlimited fan-in circuits of constant depth and polynomial size with i alternating levels of AND and OR gates (with NOT gates only in the input) and with the output gate being an OR gate (an AND gate) [10]. Theorem 44. To decide whether a minimal DFA recognizes a 1 -PT language is in AC0. 31 The proof gives that the problem belongs to II3 of the hierarchy. However, we do not know whether the 1-PT problem is n3-hard in the AC0 hierarchy or not. As a consequence of our construction, if a minimal DFA over E has more than 2^ states, then its language is not 1-piecewise testable. 2- Piecewise Testability We showed that to decide whether a minimal DFA recognizes a 2-PT language is NL-complete. Notice that this complexity coincides with the complexity of deciding whether a regular language is piecewise testable, that is, whether there exists a k for which the language is fc-piecewise testable. Theorem 45. To decide whether a minimal DFA recognizes a 2-PT language is NL-complete. Blanchet-Sadri [12] has shown that 1-PT languages are characterized as those languages whose syntactic monoid satisfies the equations x = x2 and xy = yx, and that 2-PT languages are those languages whose syntactic monoid satisfies the equations xyzx = xyxzx and (xy)2 = (yx)2. These equations could be directly used to achieve NL algorithms. Our characterizations [86], however, improve these results and show that, for 1-PT languages, it is sufficient to verify the equations x = x2 and xy = yx on letters (generators) rather than on words, and that for 2-PT languages, equation xyzx = xyxzx can be verified on letters (generators) up to the element y, which is a word (a general element of the monoid). Our results thus decrease the complexity of the problems. In addition, the partial order and confluence can be checked instead of the equation (xy)2 = (yx)2. 3- Piecewise Testability For this case, we made use of the equations (xy)3 = (yx)3, xzyxvxwy = xzxyxvxwy and ywxvxyzx = ywxvxyxzx characterizing the variety of 3-PT languages [12] to show NL-completeness of the 3-piecewise testability problem. Theorem 46. To decide whether a minimal DFA recognizes a 3-PT language is NL-complete. Structural Upper Bound on k There is an interesting observation by Klima and Polak [68] that if the depth of a minimal DFA recognizing a PT language is k, then the language is k-VT. (Bounds for finite languages and upward and downward closures have been investigated by Karandikar and Schnoebelen [64].) The observation reduces Step 2 of our approach to solving a finite number of fc-piecewise testability problems, since the upper bound on k is given by the depth of the minimal DFA equivalent to srf. The opposite implication does not hold, and hence we investigated the relationship between the depth of an NEA and fc-piecewise testability of its language. We showed that, for every k > 0, there exists a k-VT language with an NFA of depth k — 1 and with the minimal DFA of depth 2k- 1. Theorem 47. For every n > 1, there exists an n-PT language that is not (n — 1)-PT, it is recognized by an NFA of depth n — 1, and the minimal DFA recognizing it has depth 2n — 1. Although it is a well-known fact that DFAs can be exponentially larger than NFAs, an interesting by-product of the proof of the previous theorem [86] is that there are NFAs such that all the exponential number of states of their minimal DFAs form a simple path. Since the reverse of the NFA constructed in the proof is a DFA, our result also contributes to the state complexity of the reverse of piecewise testable languages, cf. [21, 61]. 32 6.1.3 Step 3: Computation of Representatives The last step of our approach is to compute those ~£-classes, whose union forms the language L, and to express them as the intersection of languages of the form Lu or its complements. To identify these equivalence classes, we make use of the ~£-canonical DFA, whose states correspond to ~£-classes- We construct the ~£-canonical DFA and compute its accepting states by intersection with the input automaton. The accepting states then represent the ~£-classes forming the language L. The ~£-canonical DFA can be effectively constructed. Moreover, although the precise size of the ~£-canonical DFA is not known, see the estimations in Karandikar, Kufleitner and Schnoebelen [63], we show that the tight upper bound on its depth is (k^n) — 1, where n is the cardinality of the alphabet. This result has also been independently obtained by Klima, Kunc and Polak [67]. Theorem 48. For any natural numbers k and n, the depth of the minimal DFA recognizing a k-PT language over an n-letter alphabet is at most (k^.n) — 1. The bound is tight for any k and n. As already pointed out, this work can be seen as translating an automaton into a form of a generalized regular expression. Generalized regular expressions can be non-elementary more succinct than classical regular expressions, however it is not yet known whether this non-elementary succinctness can be witnessed by a piecewise testable language. 6.2 Piecewise Testability and Nondeterministic Automata The knowledge of a minimal or reasonably small k for which the language is fc-piecewise testable is of interest in many applications, see, e. g., Martens et al. [78]. The complexity to test whether a piecewise testable language is fc-piecewise testable is CONP-complete for k > 4 if the language is given as a DFA [67] and PSPACE-complete if the language is given as an NFA [86]. Theorem 49. The k-piecewise testability problem for NFAs is PSPACE-complete. In Section 5.3, we defined a class of nondeterministic finite automata, called ptNFAs. Let us recall the definition of ptNFAs we use in this section. Definition 50. An NFA srf is called a ptNFA if it is partially ordered, complete, and satisfies the UMS property. The prefix "pt" in their name comes from piecewise testable, since, as we have shown [86], they characterize piecewise testable languages. And indeed include all minimal DFAs recognizing piecewise testable languages. Theorem 51. A regular language is piecewise testable if and only if it is recognized by a ptNFA. The reason why we use the UMS property in the definition of ptNFAs rather than confluence is simply because confluence does not naturally generalize to NFAs. However, it is known that partially ordered NFAs characterize the level | of the Straubing-Therien hierarchy [111] and that rpoNFAs characterize ^-trivial languages [71]. Adding confluence and completeness on top of these properties results in ptNFAs [71]. To check whether an NFA is a ptNFA requires to check whether the automaton is partially ordered, complete and satisfies the UMS property. The violation of these properties can be tested by several reachability tests, and hence its complexity belongs to coNL=NL. On the other hand, checking the properties is NL-hard even for minimal DFAs [27]. Theorem 52. It is Nh-complete to check whether an NFA is a ptNFA. 33 Unary alphabet |E| = 1 Fixed alphabet |E| > 2 Arbitrary alphabet k<3 k>4 DFA ptNFA rpoNFA poNFA NFA L-c NL-c NL-c NL-c CONP-c NL-c CONP-c CONP-c PSpace-c PSpace-c NL-c CONP-c [67] PSpace-c PSpace-c PSpace-c PSpace-c Table 6.1: Complexity of deciding fc-piecewise testability We show that, analogously to the minimal DFA case, the depth of ptNFAs provides an upper bound on fc-piecewise testability and that this new bound is up to exponentially lower than the one given by minimal DFAs. Theorem 53. If the depth of a ptNFA stf is k, then the language L(srf) is k-piecewise testable. In other words, the previous theorem says that if k is the minimum number for which a piecewise testable language L is fc-piecewise testable, then the depth of any ptNFA recognizing L is at least k. This property does not hold for general NFAs, and the gap between fc-piecewise testability and the depth of NFAs can be arbitrarily large. The opposite implication of Theorem 53 does not hold. Although the depth of ptNFAs is more suitable to provide bounds on fc-piecewise testability, the depth is significantly influenced by the size of the alphabet. For instance, for an alphabet E, the language L = Daei.^a °f ail words containing all letters of E is a 1-piecewise testable language such that any NFA recognizing it requires at least 2^ states and is of depth |E|. The depth follows from the fact that the shortest accepted word is of length |E|, and hence any path from an initial state to an accepting state must be of length at least |E|. The dependence on the alphabet is even stronger as shown below. Lemma 54. For any alphabet of cardinality n > 1, there exists an n2-piecewise testable language such that any NFA recognizing it is of depth at least nn~l. 6.3 Complexity In this subsection, we discuss the complexity of deciding (fc-)piecewise testability for languages given as a considered type of partially ordered NFA, as well as by a DFA or by an NFA. 6.3.1 Complexity of Deciding fc-Piecewise Testability Recall that a regular language over E is piecewise testable if it is a finite boolean combination of languages of the form E*<2iE*<22^* • • • E*anE*, where at E E for i = 1, ...,«,«> 0. Let k > 0 be an integer. The language is k-piecewise testable if n < k. The k-piecewise testability problem asks whether a given automaton recognizes a fc-piecewise testable language. In this section, we focus on the complexity of deciding fc-piecewise testability for partially ordered automata. Our results are summarized in Table 6.1. These results revise and improve our previous results of paper [81] and are part of the manuscript [85]. The proof technique is based on the following new lemma. Lemma 55. Let k > 0 be a constant. Then the universality problem is log-space reducible to the k-piecewise testability problem. 34 |E| = 1 |E| > 2 E is growing DFA L-c NL-c [27]1 NL-c [27] rpoNFA / CONP-c PSpace-c poNFA / PSpace-c PSpace-c NFA CONP-c PSpace-c PSpace-c Table 6.2: Complexity of deciding piecewise testability We then immediately have the following results. Theorem 56. Deciding k-piecewise testability for ptNFAs is PSPACE-complete. Theorem 57. Let E be a fixed alphabet with at least two letters. Deciding k-piecewise testability for ptNFAs over E is CONP-complete. This result is in contrast with an analogous result for DFAs, where deciding fc-piecewise testability for DFAs over a fixed alphabet is in PTime [67]. A more precise complexity can be shown. Theorem 58. Let E be a fixed alphabet with at least two letters. Deciding k-piecewise testability for DFAs over E is Nh-complete. Theorem 59. Let E be a fixed alphabet with at least two letters. Deciding k-piecewise testability forpoNFAs over E is PSPACE-complete. Theorems 57 and 59 show hardness even for binary alphabets, which improves our recent results where the alphabet had at least three letters [81]. Furthermore, we point out that hardness in Theorem 57 does not follow from the CONP-hardness proof of Klima et al. [67] showing CONP-completeness of deciding fc-piecewise testability for DFAs for k > 4, since their proof requires a growing alphabet. It remains to consider the case of unary alphabets. Theorem 60. Deciding k-piecewise testability for ptNFAs over a unary alphabet is NL-complete. It holds even ifk is given as part of the input. Theorem 61. Deciding k-piecewise testability for poNFAs and rpoNFAs over a unary alphabet is Nh-complete. It holds even ifk is given as part of the input. Theorem 62. Deciding k-piecewise testability for DFAs over a unary alphabet is L-complete. Theorem 63. Deciding k-piecewise testability for NFAs over a unary alphabet is CONP-complete. 6.3.2 Complexity of Deciding Piecewise Testability The piecewise testability problem asks, given an automaton, whether it recognizes a piecewise testable language. We now study the complexity of deciding piecewise testability for partially ordered automata. Our results are summarized in Table 6.2. Cho and Huynh [27] showed hardness for a three-letter alphabet. However, the result holds also for binary alphabets, using, e. g., a reduction from the reachability problem for directed acyclic graphs with out-degree at most two. 35 To simplify proofs, we would like to use a result similar to Lemma 55. Unfortunately, there is no such result preserving the alphabet. If there were, it would imply that deciding piecewise testability for ptNFAs has a nontrivial complexity, but these languages are trivially piecewise testable. Similarly, it would imply that deciding piecewise testability of unary (r)poNFAs is nontrivial, but we show below that they are trivially piecewise testable. Recall that ^-trivial languages, poDFA-languages, and rpoNFA-languages coincide. Theorem 64. The classes of unary poNFA languages, unary M-trivial languages, and unary piecewise testable languages coincide. Theorem 65. Deciding piecewise testability for DFAs over a unary alphabet is L-complete. Theorem 66. Deciding piecewise testability for NFAs over a unary alphabet is CONP-complete. Theorem 67. Let E be a fixed alphabet with at least two letters. Deciding piecewise testability forpoNFAs over E is PSPACE-complete. Theorem 68. Deciding piecewise testability for rpoNFAs is PSPACE-complete. Theorem 69. Deciding piecewise testability for rpoNFAs over a fixed alphabet is CONP-complete even if the alphabet is binary. The main papers [81, 86] on which the results of this chapter are based are attached in Appendix ??, including the manuscript [85]. 36 7. Applications We now present a few applications of our results in regular expressions used in the schema languages for XML data according to the W3C standards, and in the system-theoretic properties of discrete-event systems. 7.1 Deterministic Regular Expressions In this section, we discuss the relationship of partially ordered NFAs to deterministic regular expressions (DREs) [16]. DREs are of interest in schema languages for XML data - Document Type Definition (DTD) and XML Schema Definition (XSD) - since the World Wide Web Consortium standards require that the regular expressions in their specification must be deterministic. The regular expressions (REs) over an alphabet E are defined as follows: 0, e and a, a El,, are regular expressions. If r and s are regular expressions, then (r • s), (r + s) and (r)* are regular expressions. The language defined by a regular expression r, denoted by L(r), is inductively defined by L(0) = 0, L(e) = {e},L(a) = {a},L(r-s) = L(r) ■ L(s), L(r + s) =L(r)l)L(s), and ^(r*) = {£} U U!LiL(ry, where L(r) ■ L(s) denotes the concatenation of the languages L(r) and L(s). Let r be a regular expression, and let r be a regular expression obtained from r by replacing the z'-th occurrence of symbol a in r by at. For instance, if r = (a + b)*b(a + b), then r = (a\ +^i)*^2(«2 + ^3)- A regular expression r is deterministic (one-unambiguous [16] or DRE) if there are no words wa{v and wajv' in L(r) such that i ^ j. For instance, the expression (a + b)*b(a + b) is not deterministic since the strings ^2^2 and ^i^2«2 are both in L((a\ +bi)*b2(a2 + £3))- A regular language is DRE definable if there exists a DRE that defines it. Briiggemann-Klein and Wood [16] showed that not all regular languages are DRE definable. The important question is then whether a given regular language is DRE definable. This problem has been shown to be PSPACE-complete [32]. Since the language of the expression (a + b)*b(a + b) is not DRE definable [16], but it can be easily expressed by a poNFA, DRE definability is nontrivial for poNFAs. However, the complexity of deciding whether a poNFA language is DRE definable follows from the existing results, namely from the proof in Bex et al. [11] showing PSPACE-hardness of DRE-definability for regular expressions; the regular expression constructed there can be expressed as a poNFA. Thus, we readily have the following: Corollary 70. To decide whether the language of a poNFA is DRE definable is PSPACE-complete. On the other hand, the problem is trivial for the languages of rpoNFAs, which makes rpoNFAs interesting for the XML schema languages. Theorem 71. Every rpoNFA language is DRE definable. To prove the theorem, we need to introduce a few notions. For a state q of an NFA srf, the orbit of q is the maximal strongly connected component of srf containing q. State q is called a 37 gate of the orbit of q if q is accepting or has an outgoing transition that leaves the orbit. The orbit automaton of state q is the sub-automaton of srf consisting of the orbit of q in which the initial state is q and the accepting states are the gates of the orbit of q. We denote the orbit automaton of q by g/q. The orbit language of q is L(g/q). The orbit languages of srf are the orbit languages of states of srf. An NFA srf has the orbit property if, for every pair of gates q\, q2 in the same orbit in srf, the following properties hold: (i) q\ is accepting if and only if q2 is accepting, and (ii) for all states q outside the orbit of q\ and q2, there is a transition q E q\ ■ a if a and only if there is a transition q E q2 • a. Briiggemann-Klein and Wood [16] have shown that the language of a minimal DFA srf is DRE-definable if and only if srf has the orbit property and all orbit languages of srf are DRE-definable. Lemma 72. Every language of a minimal partially ordered DFA is DRE-definable. This lemma implies Theorem 71. Note that the converse of Theorem 71 does not hold. The expression b*a(b*a)* is deterministic [32] and it can be easily verified that its minimal DFA is not partially ordered, and hence the expression defines a language that is not ^-trivial (rpoNFA definable). 7.2 Detectability A discrete event system (DES) is modeled as an NFA G with all states accepting. Hence we simply write G = (<2,E, 8,1) without specifying the set of accepting states. The alphabet E is partitioned into two disjoint subsets E0 and EMO = E \ E0, where E0 is the set of observable events and EMO the set of unobservable events. The detectability problem of discrete event systems is a question whether the current and subsequent states of a DES can be determined based on observations. The problem was introduced and studied by Shu et al. [113, 114]. Detectability generalizes other notions studied in the literature [23, 101], such as stability of Ozveren and Willsky [92]. Shu et al. further argue that many practical problems can be formulated as detectability. Four variants of detectability have been defined: strong and weak detectability and strong and weak periodic detectability [114]. Let E be an alphabet, E0 C E the set of observable events, and P the projection from E to E0; the projection P: E* —> E* is a morphism defined by P(a) = e for a E E\E0, and P(a) = a for a E E0. As usual when detectability is studied, we make the following two assumptions on the DES: 1. G is deadlock free, that is, for every state of the system, at least one event can occur. Formally, for every q E Q, there is o E E such that 8(q, o) ^ 0. 2. No loop in G consists solely of unobservable events: for every q E Q and every w E E+0, qi 8{q,w). The set of infinite sequences of events generated by the DES G is denoted by La(G). Given Q' ^ Q, the set of all possible states reachable from the states of Q' after observing a word t E E* is denoted by R(Q'j) = UweIi*jP^=t8(Qf, w). For w E La(G), we denote the set of its prefixes by Pr(w). Definition 73. A DES G = (<2,E, 5,7) is strongly detectable with respect to EMO if we can determine, after a finite number of observations, the current and subsequent states of the system for all trajectories of the system, i. e., (3nEN)(VsELa(G))(Vt E Pr(s))\P(t)\>n^ \R(I,P(t))\ = 1. 38 Definition 74. A DES G = (Q,L,5,I) is strongly periodically detectable with respect to Luo if we can periodically determine the current state of the system for all trajectories of the system, i.e., (3n G N)(Vs G La(G))(Vt G Pr(s))(3t' G L*)tt' G Pr(s) A \P(t') \ n ^ \R(I,P(t))\ = 1. Definition 76. A DES G = (<2, £,5,7) is weakly periodically detectable with respect to EMO if we can periodically determine the current state of the system for some trajectories of the system, i.e., (3n G N){3s G Lffl(G))(Vf G Pr(s))(3t' G L*)tt' G Pr(s) A \P(t') \ E*, a set of secret states Qs ^ Q, and a set of non-secret states Q^s C Q. System G is current-state opaque if for every word w such that 8(I,w) fl Qs ^ 0, there exists a word w' such that P(w) = P(w') and 8(iy)nQNS^Q>. The notion of opacity independent on the structure of the system was introduced by Badouel et al. [7] and Dubreil et al. [39] under the name language-based opacity. Language-based opacity is defined over a set of secret behaviors. Lin [74] further generalized that notion to two sets of behaviors (secret and non-secret) as follows. Definition 84. Given a DES G = (<2,E, 5,7), a projection P: E* —> E*, a secret language Ls C L(G), and a non-secret language L^s ^ L(G). System G is language-based opaque if Ls C 40 Assuming that the languages L$ and L^s are regular, Wu and Lafortune [129] provided transformations among several notions of opacity, including current-state opacity and language-based opacity. Their reductions can easily be modified to deterministic log-space reductions, and hence the following results considering current-state opacity also apply to language-based opacity. The following lemma reduces current-state opacity to the inclusion problem. Lemma 85. Let G = (<2,E, <5,7) be a DES, P: E* —>• E* be a projection, Q$ C Q be a set of secret states, and Q^s ^ Q be a set of non-secret states. Let G\ = (Q,lL,8,I,Qs) and G2 = (<2,E, <5,7, Qns)- Then G is current-state opaque if and only ifP{L{G\)) C P{L{G2))- Cassez et al. [26] pointed out that the verification of current-state opacity is at least as hard as deciding universality. Indeed, L(G) = E* if and only if G is current-state opaque with respect to Qs = Q \ F and Q^s = F. This observation and Lemma 85 together with the results on the complexity of universality and inclusion give us tools to show lower and upper complexity bounds for deciding opacity. Our first result shows that deciding current-state opacity is pspace-complete even if the system is given as a DFA, that is, even if the DES is deterministic with a single initial state. Theorem 86. Deciding current-state opacity for a DES modeled by a DFA with three events, one of which is unobservable, is PSPACE-complete. Proof. Membership in PSpace was shown by Saboori [106] and also follows immediately from Lemma 85 and the fact that deciding inclusion for two NFAs is pspace-complete. To show hardness, we reduce the DFA-union universality problem [70]. Let srf\,..., srfn be DFAs over the alphabet {0,1}. Without loss of generality, we may assume that the initial state of g/i, for all i = 1,is not reachable from any other state. Let G denote the nondeterministic union of all £^'s, that is, L(G) = U"=1L(^). Kozen [70] showed that deciding whether L(G) = E* is pspace-hard, and hence deciding current-state opacity of G is pspace-hard by the observation of Cassez et al. [26], see the comment below Lemma 85. Notice that the transitions of G are deterministic, but G has n initial states, say {q\,...,qn}. We further modify G by adding a new unobservable event a and the transitions (qi, a,qi+i), for i = 11, and let q\ be the sole initial state. Denoting the result by G', we can see that G' is a DFA, and that the observers2 of G and G' coincide (here we needed the assumption that the initial state of srfi is not reachable from other states of £/f, otherwise, the languages of the observers of G and G' could be different). Altogether, G is opaque if and only if G' is opaque, which completes the proof. □ An unobservable event in the previous theorem is unavoidable because any DFA with all events observable is always in a unique state, and therefore never opaque. We now show that having only one observable event makes the problem easier. Theorem 87. Deciding current-state opacity of a DES modeled by an NFA with a single observable event is CONP-complete. Proof. Membership in CONP follows from Lemma 85 and the fact that inclusion for unary NFAs is CONP-complete; hardness follows from the complexity of deciding universality for unary NFAs, which is CONP-complete [121]. □ These results give rise to a question whether there are structurally simpler systems for which the opacity verification is tractable. Structurally the simplest systems are acyclic DFAs with full observation, recognizing finite languages. However, these systems are never opaque. Nontrivial 2An observer is a DFA obtained by replacing unobservable events by e and by the standard subset construction, considering only the reachable part. 41 r ) ( r Figure 7.1: The 'determinization'; x' and p' are a new event and a new state structures could then be acyclic NFAs that still recognize only finite languages. However, real systems are usually not that simple and often require additional properties, such as deadlock-freeness. Therefore, we consider automata with cycles in the form of self-loops (poNFAs and poDFAs) that are, in our opinion, structurally the simplest deadlock-free DES. We then immediately obtain the following result. Theorem 88. Deciding current-state opacity of a DES modeled by a poNFA with only two events, both of which are observable, is PSPACE-complete. Proof. Membership in PSpace follows from Lemma 85 and the results on the complexity of inclusion for poNFAs, and hardness from the fact that deciding universality for poNFAs with only two events is pspace-complete [72]. □ The situation is again easier if the model has only a single observable event. Theorem 89. Deciding current-state opacity of a DES modeled by a poNFA with a single observable event is NL-complete. Proof. Membership in NL follows from Lemma 85 and the corresponding compexity of inclusion, and hardness from the fact that deciding universality for unary poNFAs is NL-complete [72]. □ We now consider DES modeled by poDFAs. Since every DFA with all events observable is always in a unique state, and hence never opaque, some unobservable events are necessary to ensure opacity. We show that four events, two of which are unobservable, make the opacity verification pspace-complete even for poDFAs. Consequently, the problem is pspace-complete for basically all practical cases. Theorem 90. Deciding current-state opacity for poDFAs over an alphabet with four events, two of which are unobservable, is PSPACE-complete. Proof. Membership in PSpace follows from Lemma 85 and the corresponding complexity of inclusion. Let srf = (<2, {0,1}, <5,/,F) be a poNFA. By Theorem 88, deciding current-state opacity for poNFAs with two events, both observable, is pspace-complete. From srf, we now construct a poDEA Q) = (QU Q', {0, l,a,£}, 8',s,F) by 'determinizing' it with help of new events that we then encode in binary. In more detail, for every state p with two transitions (p,x,r) and (p,x,q) withp^q, we replace the transition (p,x,q) with two transitions (p7x'7p') and (p',x,q), where x' is a new event and p' a new state (added to Q'); see Fig. 7.1 for an illustration. In this way, we eliminate all nondeterministic transitions. The automaton is now deterministic with the set of initial states /. Let T be the set of all the new events. We encode these events as binary words over {a,b}. To encode |T| events, it suffices to consider words of length m = |~log(|r|)]. Let enc: T —> {a,b}m be an arbitrary encoding (injection). We replace every transition (p,x',p'), for x' E T, by the sequence of transitions (p,er\.c(x'),p'), which requires to add at most m — 2 new states to Q'. For instance, if (p,x,p') and (p,y,p") are two transitions with jc,y E r, and enc(jc) = aab and enc(y) = aba, then (p,x,p') is replaced by transitions (p,a,p{), (pi,a,p2),(p2ib,pr), where p\, p2 are new states added to Q', and (p,y,p") is replaced by transitions (p,a,pi), (pi,b,p3), (p3,a,p"), where p$ is a new state added to Q'; see Fig. 7.2. 42 Figure 7.2: The encoding enc(jc) = aab and enc(v) = aba To obtain a single initial state, assume that / = {#1,... ,qn}- Let m = |~log(«)]. We construct a binary rooted tree (with root labeled s) of depth m over {a, b} and add it as depicted in Fig. 7.3. The number of leaves of the tree is 2m and the number of nodes of the tree is 2m+1 — 1 = 0(n). Let the leaves be denoted by 1,2,... ,2m. We add the transitions (i,a,qi) for 1 < i < n. The resulting automaton, Q), is a poDFA over the alphabet {0, l,a,£} with polynomially many new Figure 7.3: Construction of a single initial state illustrated for 4 initial states events and states, and a single initial state s. Let P be the projection from {0, l,a,£} to {0,1}, and let P(Si) denote the poNFA obtained from Q) by replacing every transition (p,a,q) by (p,P(a),q). Then Q) is current-state opaque with respect to P if and only if P{3>) is current-state opaque (with respect to the identity map), which is if and only if srf is current-state opaque (with respect to the identity map). Notice that we have not set the secret status of states of Q', and hence we have that the states of Q; are neither secret nor non-secret (alternatively, we could set their secret status according to their "parent" state from Q). □ The main papers [81, 82] on which parts the results of this chapter are based are attached in Appendices ?? and ??, respectively. The part on opacity has not yet been published neither composed as a manuscript, which explains the presence of proofs. 43 8. Conclusion We investigated the expressiveness and properties of partially ordered automata, and the complexity of related problems. Namely, we studied the state complexity of the reverse of minimal poDFAs and established a tight bound on the state complexity of the reverse of poDFAs and confluent poDFAs showing that the state complexity of the reverse of a (confluent) poDFA of the state complexity n is 2n_1. The witness is ternary for poDFAs and (n — l)-ary for confluent poDFAs. The bound can be met neither by a binary poDFA nor by a confluent poDFA over an (n — 2)-element alphabet. We have further provided a characterization of the tight bounds for poDFAs depending on the state complexity and the size of its alphabet. Then we focused on the separation problem of regular languages by piecewise testable languages and showed that it is PTlME-complete. Our construction for membership is based on the non-existence of a sequence of words alternating between two languages in such a way that every word is a subsequence of the following word called a tower. We have shown that two languages are separable if and only if there is no infinite tower between them. The height of towers is closely related to the complexity of computing a separator. We investigated upper and lower bounds on the height of maximal finite towers and showed that the upper bound is polynomial in the number of states and exponential in the size of the alphabet, and that it is asymptotically tight if the size of the alphabet is fixed. If the alphabet may grow linearly with the number of states, then the lower bound on the height of towers is exponential with respect to that number. In this case, there is a gap between the lower and upper bound, and the asymptotically optimal bound remains open. Given a DFA srf and a k > 0, it is NL-complete to decide whether the language of srf is piecewise testable and, for k > 4, it is CONP-complete to decide whether the language is fc-piecewise testable [67]. We discussed the complexity for k < 4. It is known that the depth of the minimal DFA equivalent to srf gives an upper bound on k; if L(srf) is piecewise testable, then it is fc-piecewise testable for k being the depth of srf [68]. We showed that some form of nondeterminism does not violate this upper bound result. Specifically, we defined a class of self-loop deterministic poNFAs, called ptNEAs, showed that they characterize piecewise testable languages and that their depth provides an (up to exponentially better) upper bound on k than the depth of the minimal DFA. Furthermore, if the language L(srf) is piecewise testable, we design a procedure how to express it as a Boolean combination of languages of the above form. Our idea was as follows. If the language is piecewise testable, then it is fc-piecewise testable for some k, and hence there is a congruence ~k of finite index such that L(srf) is a finite union of ~£-classes. Each class is characterized by an intersection of languages of the from E*<2iE* • • • E*anE*, where n