Parallel insertion and deletion schema Language equations References
Schema for parallel insertion and deletion Lila Kari, Shinnosuke Seki Department of Computer Science, University of Western Ontario
UWORCS 2010 April 12th, 2010
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
Notation
Σ alphabet Σ∗ the set of all words over Σ u, v , w words L, L1 , L2 , L3 given languages R, R1 , R2 , R3 given regular languages X , Y unknown variables + sum of sets Lc complement of L, i.e., Lc = Σ∗ \ L 2L power set of L
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
p-schema-based insertion p-schema-based deletion Properties of p-schema-based operations
Parallel operations
Example ([Kari91]) Parallel insertion ⇐ is defined as follows: for a word u = a1 a2 · · · an (ai ∈ Σ) and a language L, u ⇐ L = La1 La2 L · · · Lan−1 Lan L. Question How to control parallel insertion (where to insert L)?
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
p-schema-based insertion p-schema-based deletion Properties of p-schema-based operations
p-schema-based insertion Let F = {(u1 , u2 , . . . , un−1 , un ) | n ≥ 1, u1 , . . . , un ∈ Σ∗ }. We call F ⊆ F a p-schema because it can specify how to parallel-insert a language L into a word u. Definition For a p-schema F , insertion F based on F is defined as: [ u1 Lu2 L · · · un−1 Lun . u F L = n≥0,u=u1 ···un , (u1 ,...,un )∈F
Example Let F = {(λ, ab, c), (a, bc), (abc)}. Then abc F L = LabLc ∪ aLbc ∪ abc. Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
p-schema-based insertion p-schema-based deletion Properties of p-schema-based operations
Various instances of p-schema-based insertion I
Syntactic and Semantic p-schema-based insertions Operation catenation L1 L2 insertion {xL2 y | xy ∈ L1 } parallel insertion L1 ⇐ L2 inserting exactly 2 L’s (x, y )-contextual insertion
Lila Kari, Shinnosuke Seki
p-schema F Σ∗ × {λ} ∗ ∗ Σ S ×Σ · · × Σ} ×{λ} n≥0 {λ} × Σ | × ·{z
Σ ∗ × Σ∗ × Σ∗ Σ ∗ x × y Σ∗
n times
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
p-schema-based insertion p-schema-based deletion Properties of p-schema-based operations
Various instances of p-schema-based insertion II Example Parallel insertion next to b ∈ Σ is defined as follows: for u = a1 a2 · · · an (ai ∈ Σ) and a language L, u ⇐a L = a1 L1 a2 L2 · · · an−1 Ln−1 an Ln , where Li =
(
L {λ}
if ai = b otherwise.
The p-schema F = {(u1 , . . . , un ) | n ≥ 1, u1 , . . . , un ∈ (Σ \ {b})∗ b} implements parallel insertion next to b.
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
p-schema-based insertion p-schema-based deletion Properties of p-schema-based operations
p-schema-based deletion
Definition For a p-schema G , deletion G based on G is defined as: w G L = {u1 · · · un | n ≥ 1, x1 , . . . , xn−1 ∈ L, (u1 , . . . , un ) ∈ G , w = u1 x1 u2 x2 · · · un−1 xn−1 un }. Example Let F = {(λ, a, c), (ba, bc), (babbc)} and L = b ∗ . Then babbc F L = {ac, babc, babbc}.
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
p-schema-based insertion p-schema-based deletion Properties of p-schema-based operations
p-schema-based insertion/deletion over languages
Let us extend p-schema-based operations into operations between languages as follows: [ L1 F L2 = u F L2 u∈L1
L1 G L2 =
[
w G L2 .
w ∈L1
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
p-schema-based insertion p-schema-based deletion Properties of p-schema-based operations
Distributivity I By this extension, the following distributivity hold. (L1 + L01 ) F L2 = (L1 F L2 ) + (L01 F L2 ) L1 F +G L2 = (L1 F L2 ) + (L1 G L2 ). These distributivity hold also for p-schema-based deletion. In contrast, we can say no more than L1 F (L2 + L02 ) ⊇ (L1 F L2 ) + (L1 F L02 ), L1 F (L2 + L02 ) ⊇ (L1 F L2 ) + (L1 F L02 ),
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
p-schema-based insertion p-schema-based deletion Properties of p-schema-based operations
Distributivity II
Example Let Aeven = {a2m | m ≥ 0}, Aodd = {a2m+1 | m ≥ 0}, and F = Σ∗ + Σ∗ × Σ∗ × Σ∗ . For L1 = L2 = Aeven , L1 F Aeven = L1 F Aodd = L2 However a3 ∈ L1 F (Aeven + Aodd ), which is not in L2 .
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
Solving L1 ffF X = L3 Solving L1 F X = L3
Objectives
Question Is it decidable whether language equations of the following forms: 1
X F L2 = L3 and X F L2 = L3
2
L1 X L2 = L3 and L1 X L2 = L3
3
L1 F X = L3 and L1 F X = L3
have a solution or not.
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
Solving L1 ffF X = L3 Solving L1 F X = L3
Existence of maximum solutions If X F L2 = L3 has two solutions L1 , L01 , then (L1 + L01 ) F L2 = (L1 F L2 ) + (L01 F L2 ) = L3 + L3 = L3 . This first equality holds due to the distributivity. This holds also for 1
X F L2 = L 3 ,
2
L1 X L2 = L 3 ,
3
L1 X L2 = L 3 .
This means that these equations have the maximum solutions (the sum of all of their solutions). Methods to solve such language equations have been well-established by Kari [Kari94]. Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
Solving L1 ffF X = L3 Solving L1 F X = L3
Different approach to solve language equations I On the contrary, L1 F X = L3 or L1 F X = L3 may not have the maximum solution. Let us propose another approach to solving these equations based on the notion of syntactic congruence. Definition For a language L, the syntactic congruence ≡L is an equivalence relation defined as: for u, v ∈ Σ∗ , def
u ≡L v ⇐⇒ ∀x, y ∈ Σ∗ , xuy ∈ L ⇐⇒ xvy ∈ L Definition For a word w ∈ Σ∗ , a set [w ]≡L = {u ∈ Σ∗ | u ≡L w } is called an equivalence class with w as its representative. Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
Solving L1 ffF X = L3 Solving L1 F X = L3
Different approach to solve language equations II Σ∗ / ≡L : the set of all equivalence classes w.r.t. ≡L (quotient set) index of ≡L : the size of Σ∗ / ≡L . By taking a representative from every class, we can construct a complete system of representatives of Σ∗ / ≡L . Theorem ([Rabin and Scott, 1959]) The index of ≡L is finite iff L is regular. Theorem If L is regular, then so are equivalence classes in Σ∗ / ≡L .
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
Solving L1 ffF X = L3 Solving L1 F X = L3
Solving L1 F X = L3 I Lemma Let L1 , L3 ⊆ Σ∗ . Then for any w ∈ Σ∗ and L2 ⊆ Σ∗ , (L1 F ({w }+L2 ))∩Lc3 6= ∅ ⇐⇒ (L1 F ([w ]≡Lc +L2 ))∩Lc3 6= ∅. 3
Assume that u = u1 u2 u3 u4 ∈ L1 , (u1 , u2 , u3 , u4 ) ∈ F , w1 , w2 ∈ [w ]≡L , and v ∈ L2 . Then u1 w1 u2 vu3 w2 u4 ∈ Lc3
⇐⇒
u1 w u2 vu3 w2 u4 ∈ Lc3
⇐⇒
u1 w u2 vu3 w u4 ∈ Lc3 .
For a language L, we say that a solution of L1 F X = L3 is syntactic w.r.t. L if it is a union of equivalence classes in Σ ∗ / ≡L . Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
Solving L1 ffF X = L3 Solving L1 F X = L3
Solving L1 F X = L3 II Proposition For languages L1 , L3 , L1 F X = L3 has a solution iff it has a syntactic solution w.r.t. L3 . To decide whether L1 F X = L3 has a solution, therefore, it suffices to check whether it has a syntactic solution w.r.t. L 3 . Recall that if L3 is regular, then there exist at most finite numbers of syntactic solutions, (the index of ≡L3 is finite) such syntactic solutions are regular, and solely determined by L3
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
Solving L1 ffF X = L3 Solving L1 F X = L3
Solving L1 F X = L3 III
Proposition For regular languages R1 , R3 and a regular p-schema F , it is decidable whether R1 F X = R3 has a solution. Note that all maximal solutions of L1 F X = L3 are syntactic w.r.t. L3 . Theorem For regular languages R1 , R3 and a regular p-schema F , the set of all maximal solutions of R1 F X = R3 is computable.
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
Solving L1 ffF X = L3 Solving L1 F X = L3
Solving X F Y = L3 and L1 X Y = L3 Remember that syntactic solutions of L1 F Y = L3 are solely determined by L3 . Theorem For a regular language R3 and p-schema F , it is decidable whether X F Y = R3 has a solution. Proof. N.B. |Σ∗ / ≡R3 | is finite. So for each candidate Rc of syntactic solutions, let us check whether X F Rc = R3 has a solution. Theorem For regular languages R1 , R3 , it is decidable whether R1 X Y = R3 has a solution. Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
Solving L1 ffF X = L3 Solving L1 F X = L3
Solving L1 F X = L3
Lemma Let L1 ⊆ Σ∗ . For any word w ∈ Σ∗ and a language L2 ⊆ Σ∗ , L1 F ({w } + L2 ) = L1 F ([w ]≡L1 + L2 ). In other words, a representative w can do whatever elements of [w ]≡L1 can do for F . Let R(L1 ) be a complete system of representatives of Σ∗ / ≡L1 . Then 2R(L1 ) characterizes the whole set of solutions of L1 F X = L3 as shown below.
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
Solving L1 ffF X = L3 Solving L1 F X = L3
Syntactic and representative solutions
Definition A solution of L1 F X = L3 is syntactic w.r.t. L1 if it is a union of equivalence classes in Σ∗ / ≡L1 . Definition A solution of L1 F X = L3 is representative w.r.t. R(L1 ) if it is a subset of R(L1 ).
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
Solving L1 ffF X = L3 Solving L1 F X = L3
Maximal solutions of L1 F X = L3 Proposition For languages L1 , L3 , the equation L1 F X = L3 has a solution iff it has a syntactic solution w.r.t. L1 . Proposition For a regular language R1 , a DCFL L3 , and a regular p-schema F , it is decidable whether R1 F X = L3 has a solution or not. Maximal solutions of L1 F X = L3 are syntactic w.r.t. L1 . Theorem For a regular language R1 , a DCFL L3 , and a regular p-schema F , we can compute the set of all maximal solutions of R1 F X = L3 . Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
Solving L1 ffF X = L3 Solving L1 F X = L3
Solving X F Y = L3 and L1 X Y = L3
Recall that syntactic solutions of L1 F Y = L3 is determined by L1 (not L3 ). Theorem For regular languages R1 , R3 , it is decidable whether R1 X Y = R3 has a solution. Open problem Is it decidable whether X F Y = R3 for a regular language R3 and p-schema F ?
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
Parallel insertion and deletion schema Language equations References
References I
[Kari91] L. Kari, On insertion and deletion in formal languages, Ph.D. Thesis, University of Turku, 1991. [Kari94] L. Kari, On language equations with invertible operations, Theoretical Computer Science, 132 (1994) 129-150. [Rabin and Scott, 1959] M. Rabin and D. Scott, Finite automata and their decision problems, em IBM Journal of Research and Development, 3 (1959) 114-125.
Lila Kari, Shinnosuke Seki
Schema for parallel insertion and deletion
