مینیم‌سازی دی‌اف‌ای (Persian Wikipedia)

Analysis of information sources in references of the Wikipedia article "مینیم‌سازی دی‌اف‌ای" in Persian language version.

refsWebsite

Global rank Persian rank

451^st place

931^st place

2^nd place

69^th place

253^rd place

149^th place

190^th place

ams.org

Based on Corollary 10 of (Knuutila 2001) Knuutila, Timo (2001), "Re-describing an algorithm by Hopcroft", Theoretical Computer Science, 250 (1–2): 333–363, doi:10.1016/S0304-3975(99)00150-4, MR 1795249.
(Hopcroft 1971); (Aho، Hopcroft و Ullman 1974) Hopcroft, John (1971), "An $n log n$ algorithm for minimizing states in a finite automaton", Theory of machines and computations (Proc. Internat. Sympos.، Technion، Haifa، 1971), New York: Academic Press, pp. 189–196, MR 0403320
For instance, the language of binary strings whose $n$ th symbol is a one requires only $n + 1$ states, but its reversal requires $2 n$ states. (Leiss 1981) provides a ternary $n$ -state DFA whose reversal requires $2 n$ states, the maximum possible. For additional examples and the observation of the connection between these examples and the worst-case analysis of Brzozowski's algorithm, see (Câmpeanu و دیگران 2001). Leiss, Ernst (1981), "Succinct representation of regular languages by Boolean automata" (PDF), Theoretical Computer Science, 13 (3): 323–330, doi:10.1016/S0304-3975(81)80005-9, MR 0603263. Câmpeanu, Cezar; Culik, Karel، II; Salomaa, Kai; Yu, Sheng (2001), "State Complexity of Basic Operations on Finite Languages", 4th International Workshop on Automata Implementation (WIA '99), Lecture Notes in Computer Science, vol. 2214, Springer-Verlag, pp. 60–70, doi:10.1007/3-540-45526-4_6.

(Berstel و دیگران 2010). Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle (2010), "Minimization of Automata", Automata: from Mathematics to Applications, European Mathematical Society, arXiv:1010.5318

Based on Corollary 10 of (Knuutila 2001) Knuutila, Timo (2001), "Re-describing an algorithm by Hopcroft", Theoretical Computer Science, 250 (1–2): 333–363, doi:10.1016/S0304-3975(99)00150-4, MR 1795249.
For instance, the language of binary strings whose $n$ th symbol is a one requires only $n + 1$ states, but its reversal requires $2 n$ states. (Leiss 1981) provides a ternary $n$ -state DFA whose reversal requires $2 n$ states, the maximum possible. For additional examples and the observation of the connection between these examples and the worst-case analysis of Brzozowski's algorithm, see (Câmpeanu و دیگران 2001). Leiss, Ernst (1981), "Succinct representation of regular languages by Boolean automata" (PDF), Theoretical Computer Science, 13 (3): 323–330, doi:10.1016/S0304-3975(81)80005-9, MR 0603263. Câmpeanu, Cezar; Culik, Karel، II; Salomaa, Kai; Yu, Sheng (2001), "State Complexity of Basic Operations on Finite Languages", 4th International Workshop on Automata Implementation (WIA '99), Lecture Notes in Computer Science, vol. 2214, Springer-Verlag, pp. 60–70, doi:10.1007/3-540-45526-4_6.

For instance, the language of binary strings whose $n$ th symbol is a one requires only $n + 1$ states, but its reversal requires $2 n$ states. (Leiss 1981) provides a ternary $n$ -state DFA whose reversal requires $2 n$ states, the maximum possible. For additional examples and the observation of the connection between these examples and the worst-case analysis of Brzozowski's algorithm, see (Câmpeanu و دیگران 2001). Leiss, Ernst (1981), "Succinct representation of regular languages by Boolean automata" (PDF), Theoretical Computer Science, 13 (3): 323–330, doi:10.1016/S0304-3975(81)80005-9, MR 0603263. Câmpeanu, Cezar; Culik, Karel، II; Salomaa, Kai; Yu, Sheng (2001), "State Complexity of Basic Operations on Finite Languages", 4th International Workshop on Automata Implementation (WIA '99), Lecture Notes in Computer Science, vol. 2214, Springer-Verlag, pp. 60–70, doi:10.1007/3-540-45526-4_6.