DFA minimization (English Wikipedia)

Analysis of information sources in references of the Wikipedia article "DFA minimization" in English language version.

refsWebsite

Global rank English rank

5doi.org

2^nd place

4ams.org

451^st place

277^th place

2semanticscholar.org

11^th place

8^th place

1archive.org

6^th place

1arxiv.org

69^th place

59^th place

1harvard.edu

18^th place

17^th place

1stanford.edu

179^th place

183^rd place

ams.org

mathscinet.ams.org

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.
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. See also preliminary version, Technical Report STAN-CS-71-190, Stanford University, Computer Science Department, January 1971. Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), "4.13 Partitioning", The Design and Analysis of Computer Algorithms, Addison-Wesley, pp. 157–162.
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 et al. (2001). Leiss, Ernst (1981), "Succinct representation of regular languages by Boolean automata", 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", Automata Implementation, Lecture Notes in Computer Science, vol. 2214, Springer-Verlag, pp. 60–70, doi:10.1007/3-540-45526-4_6, ISBN 978-3-540-42812-1.

archive.org

Hopcroft & Ullman (1979), Section 3.4, Theorem 3.10, p.67 Hopcroft, John E.; Ullman, Jeffrey D. (1979), Introduction to Automata Theory, Languages, and Computation, Reading/MA: Addison-Wesley, ISBN 978-0-201-02988-8

arxiv.org

Berstel et al. (2010). Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle (2010), "Minimization of Automata", Automata: from Mathematics to Applications, European Mathematical Society, arXiv:1010.5318, Bibcode:2010arXiv1010.5318B

doi.org

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.
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.
David (2012). David, Julien (2012), "Average complexity of Moore's and Hopcroft's algorithms", Theoretical Computer Science, 417: 50–65, doi:10.1016/j.tcs.2011.10.011.
Kameda & Weiner (1970). Kameda, Tsunehiko; Weiner, Peter (1970), "On the state minimization of nondeterministic finite automata", IEEE Transactions on Computers, 100 (7): 617–627, doi:10.1109/T-C.1970.222994, S2CID 31188224.
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 et al. (2001). Leiss, Ernst (1981), "Succinct representation of regular languages by Boolean automata", 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", Automata Implementation, Lecture Notes in Computer Science, vol. 2214, Springer-Verlag, pp. 60–70, doi:10.1007/3-540-45526-4_6, ISBN 978-3-540-42812-1.

harvard.edu

ui.adsabs.harvard.edu

Berstel et al. (2010). Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle (2010), "Minimization of Automata", Automata: from Mathematics to Applications, European Mathematical Society, arXiv:1010.5318, Bibcode:2010arXiv1010.5318B

semanticscholar.org

api.semanticscholar.org

Xu, Yingjie (2009). "Describing an n log n algorithm for minimizing states in deterministic finite automaton". p. 5. S2CID 14461400. {{cite web}}: Missing or empty |url= (help)
Kameda & Weiner (1970). Kameda, Tsunehiko; Weiner, Peter (1970), "On the state minimization of nondeterministic finite automata", IEEE Transactions on Computers, 100 (7): 617–627, doi:10.1109/T-C.1970.222994, S2CID 31188224.

stanford.edu

i.stanford.edu

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. See also preliminary version, Technical Report STAN-CS-71-190, Stanford University, Computer Science Department, January 1971. Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), "4.13 Partitioning", The Design and Analysis of Computer Algorithms, Addison-Wesley, pp. 157–162.