References

  1. Andreas Blass & Yuri Gurevich (1982): On the Unique Satisfiability Problem. Inform. Control 55, pp. 80–88, doi:10.1016/S0019-9958(82)90439-9.
  2. Marek Chrobak (1986): Finite automata and unary languages. Theor. Comput. Sci. 47, pp. 149–158, doi:10.1016/0304-3975(86)90142-8. Errata: Chrobak:2003:ERRFAUL.
  3. Marek Chrobak (2003): Errata to ``Finite automata and unary languages''. Theor. Comput. Sci. 302, pp. 497–498, doi:10.1016/S0304-3975(03)00136-1.
  4. Keith Ellul (2004): Descriptional Complexity Measures of Regular Languages. University of Waterloo, Ontario, Canada.
  5. Viliam Geffert (2007): Magic numbers in the state hierarchy of finite automata. Inform. Comput. 205(11), pp. 1652–1670, doi:10.1016/j.ic.2007.07.001.
  6. Viliam Geffert, Carlo Mereghetti & Giovanni Pighizzini (2003): Converting two-way nondeterministic unary automata into simpler automata. Theor. Comput. Sci. 295, pp. 189–203, doi:10.1016/S0304-3975(02)00403-6.
  7. Yahya Ould Hamidoune (1979): Sur les parcours hamiltoniens dans les graphes orientes. Discrete Mathematics 26, pp. 227–234, doi:10.1016/0012-365X(79)90028-1.
  8. Lane A. Hemaspaandra & Mitsunori Ogihara (2002): The Complexity Theory Companion. Springer, doi:10.1007/978-3-662-04880-1.
  9. Markus Holzer & Martin Kutrib (2003): Unary Language Operations and Their Nondeterministic State Complexity. In: M. Ito & M. Toyama: Developments in Language Theory (DLT 2002), LNCS 2450. Springer, pp. 162–172, doi:10.1007/3-540-45005-X_14.
  10. Markus Holzer & Martin Kutrib (2011): Descriptional and Computational Complexity of Finite Automata – A Survey. Inform. Comput. 209, pp. 456–470, doi:10.1016/J.IC.2010.11.013.
  11. Neil D. Jones (1975): Space-Bounded Reducibility among Combinatorial Problems. J. Comput. Syst. Sci. 11, pp. 68–85, doi:10.1016/S0022-0000(75)80050-X.
  12. Michal Kunc & Alexander Okhotin (2012): State complexity of operations on two-way finite automata over a unary alphabet. Theor. Comput. Sci. 449, pp. 106–118, doi:10.1016/J.TCS.2012.04.010.
  13. Martin Kutrib, Andreas Malcher & Matthias Wendlandt (2023): Complexity of Exclusive Nondeterministic Finite Automata. In: Henning Bordihn, Nicholas Tran & György Vaszil: Descriptional Complexity of Formal Systems (DCFS 2023), LNCS 13918. Springer, pp. 121–133, doi:10.1007/978-3-031-34326-1_9.
  14. Martin Kutrib, Andreas Malcher & Matthias Wendlandt (2024): Complexity of Exclusive Nondeterministic Finite Automata. submitted for journal publication.
  15. Edmund Landau (1903): Über die Maximalordnung der Permutationen gegebenen Grades. Archiv der Math. und Phys. 3, pp. 92–103.
  16. Edmund Landau (1909): Handbuch der Lehre von der Verteilung der Primzahlen. Teubner, Leipzig.
  17. Hing Leung (1998): Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata. SIAM J. Comput. 27, pp. 1073–1082, doi:10.1137/S0097539793252092.
  18. Hing Leung (2005): Descriptional complexity of NFA of different ambiguity. Int. J. Found. Comput. Sci. 16, pp. 975–984, doi:10.1142/S0129054105003418.
  19. Filippo Mera & Giovanni Pighizzini (2005): Complementing unary nondeterministic automata. Theor. Comput. Sci. 330, pp. 349–360, doi:10.1016/J.TCS.2004.04.015.
  20. Carlo Mereghetti & Giovanni Pighizzini (2001): Optimal Simulations between Unary Automata. SIAM J. Comput. 30, pp. 1976–1992, doi:10.1137/S009753979935431X.
  21. Albert R. Meyer & Michael J. Fischer (1971): Economy of Description by Automata, Grammars, and Formal Systems. In: Symposium on Switching and Automata Theory (SWAT 1971). IEEE, pp. 188–191, doi:10.1109/SWAT.1971.11.
  22. William Miller (1987): The maximum order of an element of a finite symmetric group. Am. Math. Mon. 94, pp. 497–506, doi:10.1080/00029890.1987.12000673.
  23. Frank R. Moore (1971): On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata. IEEE Trans. Comput. 20(10), pp. 1211–1214, doi:10.1109/T-C.1971.223108.
  24. J.-L. Nicolas (1968): Sur l'ordre maximum d'un élément dans le groupe S_n des permutations. Acta Arith. 14, pp. 315–332, doi:10.4064/aa-14-3-315-332.
  25. Alexander Okhotin (2012): Unambiguous finite automata over a unary alphabet. Inform. Comput. 212, pp. 15–36, doi:10.1016/J.IC.2012.01.003.
  26. Giovanni Pighizzini (2009): Deterministic Pushdown Automata and Unary Languages. Int. J. Found. Comput. Sci. 20(4), pp. 629–645, doi:10.1142/S0129054109006784.
  27. Giovanni Pighizzini (2015): Investigations on Automata and Languages Over a Unary Alphabet. Int. J. Found. Comput. Sci. 26, pp. 827–850, doi:10.1142/S012905411540002X.
  28. Giovanni Pighizzini & Jeffrey Shallit (2002): Unary Language Operations, State Complexity and Jacobsthal's Function. Int. J. Found. Comput. Sci. 13, pp. 145–159, doi:10.1142/S012905410200100X.
  29. Giovanni Pighizzini, Jeffrey Shallit & Ming-Wei Wang (2002): Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds. J. Comput. Syst. Sci. 65, pp. 393–414, doi:10.1006/JCSS.2002.1855.
  30. Michael Oser Rabin & Dana Scott (1959): Finite Automata and Their Decision Problems. IBM J. Res. Dev. 3, pp. 114–125, doi:10.1147/rd.32.0114.
  31. William J. Sakoda & Michael Sipser (1978): Nondeterminism and the size of two way finite automata. In: ACM: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing (STOC 1978). ACM. ACM Press, New York, pp. 275–286, doi:10.1145/800133.804357.
  32. Erik Meineche Schmidt (1978): Succinctness of Dscriptions of Context-Free, Regular and Finite Languages. Cornell University, Ithaca, NY.
  33. Jeffrey Shallit (2008): The Frobenius Problem and Its Generalizations. In: Masami Ito & Masafumi Toyama: Developments in Language Theory (DLT 2008), LNCS 5257. Springer, pp. 72–83, doi:10.1007/978-3-540-85780-8_5.
  34. Michael Sipser (1980): Lower Bounds on the Size of Sweeping Automata. J. Comput. Syst. Sci. 21, pp. 195–202, doi:10.1016/0022-0000(80)90034-3.
  35. Larry. J. Stockmeyer & A. R. Meyer (1973): Word Problems Requiring Exponential Time. In: ACM: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing (STOC 1973). ACM Press, New York, NY, USA, pp. 1–9, doi:10.1145/800125.804029.
  36. M. Szalay (1980): On the maximal order in S_n and S_n^*. Acta Arithm. 37, pp. 321–331, doi:10.4064/aa-37-1-321-331.
  37. Anthony Widjaja To (2009): Unary finite automata vs. arithmetic progressions. Inform. Process. Lett. 109, pp. 1010–1014, doi:10.1016/J.IPL.2009.06.005.

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org