key: cord-0043825-gqkl0rlh
authors: Caron, Pascal; Hamel-de-le-court, Edwin; Luque, Jean-Gabriel
title: A Study of a Simple Class of Modifiers: Product Modifiers
date: 2020-05-26
journal: Developments in Language Theory
DOI: 10.1007/978-3-030-48516-0_9
sha: 27c7590bd3f2d5dbb0d48578e0af8cbb9511238f
doc_id: 43825
cord_uid: gqkl0rlh

A modifier is a k-ary operator acting on DFAs and producing a DFA. Modifiers are involved in the theory of state complexity. We define and study a class of simple modifiers, called product modifiers, and we link closely the regular operations they encode to boolean operations.

State complexity is a measure of complexity defined on regular operations. It allows to write the size of the minimal automaton recognizing the output as a function of the sizes of the minimal automata recognizing the inputs. The topic dates back to the 70s, from the seminal paper of Maslov [14] describing, explicitly but without any proof, the state complexities of several operations. Since the 90s, this area of research became very active and the state complexity of numerous operations has been computed. See, for example, [6, [11] [12] [13] 15] and [8] for a survey of the subject.

However, a few general methods are commonly used in order to compute state complexities. The most common method consists in providing a witness, which is a specific example reaching what is proven to be an upper bound. The witness itself is, in general, found by trial and error, sometimes using a witness that worked for a number of other operations and modifying it to fit the specific needs of the operation considered. In many cases, for example [1, 7] or [4] , the witness is constructed by considering, explicitly or implicitly, the whole monoid of the transformations acting on the states of the minimal automata recognizing the input languages. This method has been theorized in two independently written papers [2, 5] . More precisely, the approach consists, on the one hand, in describing states as combinatorial objects and finding upper bounds using combinatorial tools, and, on the other hand, in building a huge witness, called a monster, chosen in a set of automata having as many transition functions as possible. This method can be applied to obtain the state complexity to the wide range of 1-uniform operations that are associated to operators, called modifiers, that act on automata to produce an automaton in a certain restrictive way. In this paper, we examine the regular operations described by the class of some very simple modifiers called product modifiers. These modifiers are characterized by the fact that they build the Cartesian product automaton with the transitions took from the input automata. We investigate many properties of this class and in particular we completely describe the set of the regular operations that can be encoded by product modifiers. The paper is organized as follows. Section 2 gives definitions and notations about automata. In Sect. 3, we partially recall the monster approach. Finally, in Sect. 4, we define product modifiers and characterize the regular operations they encode in Sect. 5.

The set of subsets of E is denoted by 2 E and the set of mappings of E into itself is denoted by E E . The symmetric difference of two sets E 1 and E 2 is denoted by ⊕ and defined by

Let (E 1 , . . . , E k ) be a k-tuple of finite sets, and let (δ 1 , . . . , δ k ) be a ktuple such that δ i is a function from E i to E i for every i ∈ {1, . . . , k}. For any k-tuple (e 1 , . . . , e k ) such that e i ∈ E i for all i ∈ {1, . . . , k}, we denote by (δ 1 , . . . , δ k )(e 1 , . . . , e k ) the k-tuple (δ 1 (e 1 ), . . . , δ k (e k )).

Let E be a set, f :

. . , e p−1 , g(e p , . . . , e p+k−1 ), e p+k , . . . , e j+k−1 ), for any e 1 , . . . , e j+k−1 ∈ E.

Let Σ be a finite alphabet. A word w over Σ is a finite sequence of symbols of Σ. The set of all finite words over Σ is denoted by Σ * . A language over Σ is a subset of Σ * . We define the complement of a language L ⊆ Σ * by L c = Σ * \ L.

A complete and deterministic finite automaton (DFA) is a 5-tuple A = (Σ, Q, i, F, δ) where Σ is the input alphabet, Q is a finite set of states, i ∈ Q is the initial state, F ⊂ Q is the set of final states and δ is the transition function from Q × Σ to Q that is defined for every q ∈ Q and every a ∈ Σ. We can extend transition functions in a natural way to functions from Q × Σ * to Q, and again to functions from 2 Q × Σ * to Q. For any word w, we denote by δ w the function q → δ(q, w).

The language recognized by a DFA A is the set L(A) of words recognized by A. By Kleene's theorem, a language is regular if and only if it is recognized by a DFA. It is well known that for any DFA, there exists a unique minimal one (up to isomorphism) among all DFAs recognizing the same language ([10]).

A unary regular operation is a function from regular languages of Σ into regular languages of Σ. A k-ary regular operation is a function from the set of k-tuples of regular languages over Σ into regular languages over Σ.

The state complexity of a regular language L denoted by sc(L) is the number of states of its minimal DFA. This notion extends to regular operations: the state complexity of a unary regular operation ⊗ is the function sc ⊗ such that, for all n ∈ N, sc ⊗ (n) is the maximum of all the state complexities of ⊗(L) when L is of state complexity n, i.e. sc ⊗ (n) = max{sc(⊗(L))|sc(L) = n}.

This can be generalized, and the state complexity of a k-ary operation ⊗ is the k-ary function sc ⊗ such that, for all (n 1 , . . . , n k ) ∈ (N) k ,

Then, a witness for ⊗ is a way to assign to each (n 1 , . . . , n k ), where each n i is assumed sufficiently big, a k-tuple of languages (L 1 , . . . , L k ) with sc(L i ) = n i , for all i ∈ {1, . . . , k}, satisfying sc ⊗ (n 1 , . . . , n k ) = sc(⊗(L 1 , . . . , L k )).

We describe a class of regular operations, called 1-uniform which are interesting for the study of state complexity [3, 5] . We then define operations on DFA called modifiers, and describe a subset of these operations that correspond to the set of 1-uniform regular operations.

Definition 1. Let Σ and Γ be two alphabets. A morphism is a function φ from Σ * to Γ * such that, for all w, v ∈ Σ * , φ(wv) = φ(w)φ (v) . Notice that φ is completely defined by its value on letters. A morphism φ is 1-uniform if the image by φ of any letter is a letter.

The preimage φ −1 (L) of a regular language L by a morphism φ is regular, see, e.g., [9] . This allows us to introduce the notion of 1-uniform regular operation.

Obviously, 1-uniformity is stable by composition. Many well-known regular operations are 1-uniform. See [5] for a non-exhaustive list of examples like the complement, the Kleene star, the reverse, the cyclic shift, and the mirror, all boolean operations and catenation among others.

Each 1-uniform regular k-ary operation corresponds to a construction over DFAs, which is handy when we need to compute the state complexity of its elements. Such a construction on DFAs has some constraints that are described in the following definitions. . We say that m describes the operation ⊗ m .

A = (Σ, Q, i, F, δ) is the triplet (Q, i, F ).

Example 1. For any DFA A = (Σ, Q, i, F, δ), define Star(A) = (Σ, 2 Q , ∅, {E|E ∩ F = ∅} ∪ {∅}, δ 1 ), where for any a ∈ Σ, δ a 1 (∅) = δ a (i) if δ a (i) / ∈ F and δ a 1 (∅) = δ a (i) otherwise, and, for all E = ∅, δ a 1 (E) = δ a (E) if δ a (E) ∩ F = ∅ and δ a 1 (E) = δ a (E) ∪

We easily check that, for modifiers, the 1-uniformity is stable by composition.

Claim. Let m 1 and m 2 be respectively a j-modifier and a k-modifier describing, respectively, operations ⊗ 1 and ⊗ 2 . The modifier

The correspondence between 1-uniform modifiers and 1-uniform operations is stated in the following Theorem proved in [3] .

Modifiers have been defined, for the first time, in [2] as a tool to compute state complexity of 1-uniform operations.

When there is no ambiguity, for any character X and any integer k given by the context, we write X for (X 1 , · · · , X k ). The number k will often be the arity of the regular operation or of the modifier we are considering.

From Definition 4, any k-modifier m can be seen as a 4-tuple of mappings F , δ a ) . For the sake of clarity, we do not write explicitly the domains of the 4-tuple of mappings but the reader can derive them easily from the above equalities. Notice that we do not need to point out explicitly the dependency of d on Q because the information is already contained in δ a . We identify modifiers and such 4-tuples of mappings with each other. Below we revisit the definition of Xor according to this formalism.

In this section, we study a kind of simple modifier called product modifiers and show that they are closely linked to boolean operations.

A k-modifier m = (Q, i, f, d) is a product modifier if, for any k-tuple of finite sets Q, for any k-tuple of finite sets F such that F j ⊆ Q j for all j, and for any i ∈ Q 1 × · · · × Q k

with δ a (q) = (δ a 1 (q 1 ), δ a 2 (q 2 ), ..., δ a k (q k )). In other words, if m is a product modifier, then mA is the product automaton of the A j , but with final states f(Q, i, F ) and initial state i(Q, i, F ). Intuitively, product modifiers do not change the transition functions of the automata they act on, but seek only to change their final and initial states. We can easily check that the class of product modifiers is stable by composition.

For the sake of simplicity, in this section, m denotes any k-ary product (but not necessarily 1-uniform) modifier and A = (A 1 , . . . , A k ) any sequence of k DFAs, with A j = (Σ, Q j , i j , F j , δ j ). Recall that i = (i 1 , . . . , i k ), Q = (Q 1 , . . . , Q k ) and F = (F 1 , . . . , F k ) . We also denote mA = (Σ, Q , i , F , δ) .

We define the complementary product to get an easier access to the intersection of languages and their complement.

For any k-tuple P of finite sets, for any k-tuple G of finite sets such that G j ⊆ P j for all j, and for any d ⊆ {1, 2, ..., k}, we define cp(d, G, P ) = Proof. Let d = d and suppose that there exists j ∈ d \ d . For any element q ∈ cp(d, F , Q), we have q j ∈ F j and, for any element q ∈ cp(d , F , Q), we have

Furthermore, consider an element q ∈ Q and set d = {j | q j ∈ F j }. Obviously, q ∈ cp(d, F , Q) . This proves our result.

The following lemma sets a restriction on the form of f on each of its entries, given that i does not change the initial states in its entries. F , Q) . The idea of the proof is to construct, with the states in G, two k-tuple of automata B and C that recognize the same languages, and such that L(mB) and L(mC) are different.

We distinguish two cases :

• First, suppose that i ∈ G. If i ∈ F then we choose j ∈ G\F , otherwise we choose j ∈ G ∩ F . Consider the two k-tuples of DFAs B and C such that B l = ({a}, Q l , i l , F l , β l ) and C l = ({a}, Q l , i l , F l , γ l ), where, for all positive integer l ≤ k, β a l (i l ) = j l if x = i l , β a l (x) = x if x ∈ Q i l \ {i l }, and γ a l (x) = x, for any x ∈ Q i l . Let us remark that, as i, j ∈ G = cp(d, F , Q), i l and j l are either both in F l (if l / ∈ d), or both not in F l (if l ∈ d) by definition of cp. Therefore, i l and j l have the same finality in B l , which is also their finality in C l , and either B l and C l recognize a * , or B l and C l recognize ∅. As described in Fig. 1 , the transition functions β of mB and γ of mC satisfy β a (i) = j and γ a (i) = i. The finality of i is the same in mB and mC. However, it is not the same finality as j in mB and mC. Therefore, we have (a ∈ L(mB) ∧ a / ∈ L(mC)) or (a / ∈ L(mB) ∧ a ∈ L(mC)). As a consequence, L(mB) = L(mC) and this implies that m is not 1-uniform.

• Suppose now that i / ∈ G. Let j ∈ G\F , and let j ∈ G ∩ F . Consider the two k-tuple of DFAs B and C such that B l = ({a, b}, Q l , i l , F l , β l ) and C l = ({a, b}, Q l , i l , F l , γ l ), where, for all letters u ∈ {a, b}, for all positive integer l ≤ k and all x ∈ Q l , For any positive integer l ≤ k, B l and C l recognize the same language. Indeed, from Fig. 2 , as j, j ∈ G = cp(d, F , Q), j l and j l have the same finality in B l and C l by definition of cp, we distinguish the cases :

As mB and mC are cartesian products of the B l and the C l respectively, if we call β the transition function of mB and γ the transition function of mC, we have β a (i) = j, β b (j) = j , γ a (i) = j , and γ b (j ) = j. The finality of j is the same in mB and mC. However, it is different from the finality of j in mB and mC. Therefore, we have (ab ∈ L(mB) ∧ ab / ∈ L(mC)) or (ab / ∈ L(mB) ∧ ab ∈ L(mC)). As a consequence, L(mB) = L(mC) which implies that m is not 1-uniform.

The following two lemmas state that, for product modifiers, we can set i = i without changing the regular operation associated to m. Proof. Let us prove the contrapositive of our statement. Assume that i and i do not have the same finality, i.e.

. Consider the two k-tuples of DFAs B and C such that B l = ({a}, Q l , i l , F l , β l ) and C l = ({a}, Q l , i l , F l , γ l ), where, for any l ∈ {1, . . . , k}, β a l (i l ) = i l , β a l (q) = q when q = i l and γ a l (q) = q. Let us remark that B l and C l recognize {a} * if i l ∈ F l , and ∅ otherwise. In any case, they recognize the same language.

If we denote by β the transition function of mB and by γ the transition function of mC, we have β a (i ) = i and γ a (i ) = i . Recall that i is the initial state of mB and mC. Since i and i do not have the same finality, the word a belongs to one of the languages L(mB) or L(mC) but not both (see Fig. 3 ). Hence the two automata do not recognize the same language and, as a consequence, m is not 1-uniform. We define an equivalence relation on states of the output of product modifiers whose relationship with the finality of states is examined in Lemma 4.

Let j and j be two k-tuples. We define the equivalence relation ∼ j,j on k-tuples by (x 1 , . . . , x k ) ∼ j,j (y 1 , . . . , y k ) if and only if for all l ∈ {1, . . . , k}, j l = j l implies x l = y l .

Example 5. We have (3, 3, 2, 5, 1) ∼ (1,4,3,2,3),(2,4,2,2,6) (1, 3, 5, 5, 2).

We do not have (3, 3, 2, 5, 1) ∼ (1,4,3,2,3),(2,4,2,2,6) (1, 3, 5, 1, 2) .

If m is 1-uniform then L(mA) = L((Σ, Q , i, F , δ)).

Proof. One has to investigate the two complementary cases:

• There exists two states q ∈ F , q ∈ Q \ F such that q ∼ i,i q .

In this case we prove that i = i , in other words mA = (Σ, Q , i, F , δ). Let us show the contrapositive of the property. Suppose i = i . We have to show that m is not 1-uniform. By Lemma 3, i ∈ F ∧ i ∈ F or i / ∈ F ∧ i / ∈ F . Consider the two k-tuples of DFAs B and C such that B l = ({a}, Q l , i l , F l , β l ) and C l = ({a}, Q l , i l , F l , γ l ), where for all l ∈ {1, . . . , k} and all q ∈ Q l , β a l (q) = q l if q = i l q otherwise and γ a l (q) = q l if q = i l q otherwise.

Let us remark that either i l = i l , which implies q l = q l , and B l = C l , or i l = i l , and B l and C l recognize {a} * if i l ∈ F l and ∅ otherwise. In any case, they recognize the same language. Recall that β is the transition function of mB and γ is the transition function of mC. We have β a (i ) = q and γ a (i ) = q . Thus we have a ∈ L(mB) and a / ∈ L(mC). Therefore, L(mB) = L(mC) and m is not 1-uniform.

• For any two states q, q ∈ Q , q ∼ i,i q implies that q and q have the same finality.

First, for any letter a ∈ Σ, any two states q, q ∈ Q , the equivalence q ∼ i,i q implies δ a (q) = (δ a 1 (q 1 ), δ a 2 (q 2 ), . . . , δ a k (q k )) ∼ i,i (δ a 1 (q 1 ), δ a 2 (q 2 ), . . . , δ a k (q k )) = δ a (q ).

This property extends inductively to any word w ∈ Σ * , i.e. q ∼ i,i q implies δ w (q) ∼ i,i δ w (q ). In particular, applying this to q = i and q = i , we have δ w (i ) ∈ F if and only if δ w (i) ∈ F . As a direct consequence, the languages recognized by the two automata are the same. 

Before stating our main result, we need to clarify what is meant by a boolean operation. A boolean operation is an operation associated to an expression involving only the operators union, intersection and complement. It is well known that such an expression is equivalent to one written as a union of intersection of languages or their complement. More formally, Definition 9. A k-ary boolean operation ⊗ over regular languages L 1 , . . . , L k is defined as

for some E ⊆ 2 {1,...,k} . Notice that there is a one-to-one correspondence between the boolean k-ary operations and the sets E ⊆ 2 {1,...,k} . So we denote E ⊗ = E. Example 6. The classical boolean operation union can be written this way: for any two regular languages L 1 and L 2 ,

We easily check that boolean operations are 1-uniform and can be associated to some product modifiers. More formally, From Definition 9, we construct a wider class of operators that we prove to be in correspondence with product modifiers.

For any k-ary regular operation ⊗, for any v ∈ {0, 1} k , we denote by ⊗ v the restriction of ⊗ to the set

We say that ⊗ is a k-ary quasi-boolean operation if for all v ∈ {0, 1} k , ⊗ v is a boolean operation, i.e. for any v, there exists a boolean operation ⊗ 1 such that for any L ∈ L v we have ⊗ 1 L = ⊗ v L. Example 7. Consider the unary operator defined by ⊗L = L if ∈ L and L c otherwise. This operation is clearly not boolean. Nevertheless, since for each L ∈ L (0) we have ⊗L = L and for each L ∈ L (1) we have ⊗L = L c , the operation ⊗ is quasi-boolean.

These operations do not have a higher state complexity than boolean operations, as we show in the following statement.

For any quasi-boolean k-ary operation ⊗, we have sc ⊗ (n 1 , . . . , n k ) ≤ n 1 · · · n k .

Proof. Lemma 5 implies that sc ⊗ (n 1 , . . . , n k ) ≤ n 1 · · · n k for any boolean operation ⊗. We we prove our statement, by remarking that, for any quasi-boolean operation ⊗, we have sc ⊗ (n 1 , . . . ,

We now introduce our main result that characterizes the operations encoded by 1-uniform product modifiers.

Proof. Let ⊗ be a k-ary quasi-boolean operation. We construct a modifier m such that ⊗ = ⊗ m as follows. We consider the product modifier m = (Q, i, f, d) such that i(Q, i, F ) = i and,

Let L ∈ L v for some v ∈ {0, 1} k . For any k-tuple of DFAs A such that A j = (Σ, Q j , i j , F j , δ j ) recognizes L j , we have i j ∈ F j if and only if v j = 0. From Lemma 5, one has L(mA) = ⊗ v L. Hence, m is 1 − unif orm and ⊗ = ⊗ m . Now, we prove the converse. Let ⊗ be a regular operation such that there exists a 1-uniform product modifier m satisfying ⊗ m = ⊗. We use a reductio ad absurdum argument by assuming that ⊗ is not quasi-boolean. Let v ∈ {0, 1} k be such that ⊗ v is not a boolean operation. Let A be a k-tuple of DFAs We have to examine two cases. Either there exists p ∈ F such that p / ∈ d∈E cp(d, F , Q ), or there exists p ∈ d∈E cp(d, F , Q ) such that p / ∈ F . We only describe the first case, as the other one is treated symmetrically. Therefore, Lemma 1 implies that there exists d ∈ H \ E such that p ∈ cp(d, F , Q ). Let p ∈ cp(d, F , Q). Notice that p ∈ F while each p l has the same finality in B l as p l in B l . Also remark that, as (L(A 1 ), . . . , L(A k )) and (L(A 1 ), . . . , L(A k )) are in L v , for all l ∈ {1, . . . , k}, v l = 0 implies i l ∈ F l and i l ∈ F l , and v l = 1 implies i l / ∈ F l and i l / ∈ F l . Now consider the two k-tuples of DFAs B and B such that B l = ({a}, Q l , i l , F l , β l ) and B l = ({a}, Q l , i l , F l , β l ), where β l and β l are defined, for all positive integer l ≤ k and all (q, q ) ∈ Q l × Q l , by : β a l (q) = p l if q = i l q otherwise. and β a l (q ) = p l if q = i l q otherwise.

We notice that, for all l ∈ {1, . . . , k}, B l and B l recognize the same language L l . Indeed, since i l and i l have the same finality and p l and p l have the same finality, one has to examine four cases which are summarized in Table 1 . Furthermore, we have β a (i) = p ∈ F , and β a (i ) = p ∈ F , which means that a ∈ L(mB) and a ∈ L(mB ), which contradicts the 1-uniformity of m. Table 1 . Common values of L(B l ) and L(B l ).

We have shown that some very simple modifiers, namely product modifiers, encode a class of very low state complexity operations. This is a non-trivial example of a set of modifiers closed by composition whose associated regular operations are completely described.

The proof techniques open perspectives to explore other classes of modifiers closed by composition. The aim for our future works is to establish a kind of atlas, as complete as possible, of the set of modifiers in relation to the theory of state complexity.

On the state complexity of the shuffle of regular languages

New tools for state complexity

Algebraic and combinatorial tools for state complexity : application to the star-xor problem

State complexity of catenation combined with a boolean operation: a unified approach

A general approach to state complexity of operations: formalization and limitations

State complexity of proportional removals

State complexity of power

A survey on operational state complexity

Introduction to Automata Theory, Languages, and Computation

Introduction to Automata Theory, Languages and Computation

State complexity of concatenation and complementation

State complexity of some operations on binary regular languages

State complexity of cyclic shift

Estimates of the number of states of finite automata

State complexity of regular languages