1 Introduction
2 Preliminaries
-
L is prefix-closed if and only if \(\overline {L}\) is a right ideal.
-
L is suffix-closed if and only if \(\overline {L}\) is a left ideal.
-
L is factor-closed if and only if \(\overline {L}\) is a two-sided ideal.
3 Syntactic Complexity of Languages with Special Quotients
∅
| Σ∗
| {ε} | Σ+
|
σ(L) ≤ | if also L is ur | if also a
−1 L is ur |
---|---|---|---|---|---|---|
√
|
n
n−1
| (n − 1)
n−1
| 1 + (n − 3)
n−1
| |||
√
|
n
n−1
| (n − 1)
n−1
| 1 + (n − 3)
n−1
| |||
√
|
√
|
n
n−2
| (n − 1)
n−2
| 1 + (n − 4)
n−2
| ||
√
|
√
|
n
n−2
| (n − 1)
n−2
| 1 + (n − 4)
n−2
| ||
√
|
√
|
n
n−2
| (n − 1)
n−2
| 1 + (n − 4)
n−2
| ||
√
|
√
|
√
|
n
n−3
| (n − 1)
n−3
| 1 + (n − 5)
n−3
| |
√
|
√
|
√
|
n
n−3
| (n − 1)
n−3
| 1 + (n − 5)
n−3
| |
√
|
√
|
√
|
√
|
n
n−4
| (n − 1)
n−4
| 1 + (n − 6)
n−4
|
4 Right Ideals and Prefix-Closed Languages
5 Left Ideals and Suffix-Closed Languages
5.1 Basic Properties
5.2 Lower Bound
5.3 Upper Bound
-
Case 1: t ∈ W li.
-
Case 2: t ∉ W li and 0t 2 ≠ 0t.
-
Case 3: t ∉ W li and 0t 2 = 0t.
-
(a): t has a cycle.
-
(b): t has no cycles and has a fixed point r ≠ p.
-
(c): t has no cycles, has no fixed point r ≠ p, and there is a state r such that p ≺ r with r t = p.
-
-
Case 1: t ∈ W li.
-
Case 2: t ∉ W li and 0t 2 ≠ 0t.
-
Case 3: t ∉ W li and 0t 2 = 0t.
-
(a): t has a cycle.
-
(b): t has no cycles and has a fixed point r ≠ p.
-
(c): t has no cycles, has no fixed point r ≠ p, and there is a state r such that p ≺ r with r t = p.
-
All cases are covered:
6 Two-Sided Ideals
6.1 Lower Bound
6.2 Upper Bound
-
Case 1: t ∈ W 2i.
-
Case 2: t ∉ W 2i, and 0t 2 ≠ 0t.
-
(a): p t k ≠ n − 1.
-
(b): p t k = n − 1 and k ≥ 2.
-
(c): p t = n − 1.
-
Case 3: t ∉ W 2i, 0t = p ≠ 0, and p t = p.
-
(a): t has a cycle.
-
-
(b): t has no cycles and has a fixed point r ∉ {p, n − 1}.
-
(c): t has neither a cycle nor a fixed point r ∉ {p, n − 1}, and has a state r ≻ p mapped to p.
-
(d): t has no cycles, no fixed point r ∉ {p, n − 1}, and no state r ≻ p mapped to p, and has a state r such that p ≺ r ≺ n − 1 that is mapped to n − 1.
-
All cases are covered: