Andreas Blass & Yuri Gurevich (1982):
On the Unique Satisfiability Problem.
Inform. Control 55,
pp. 80–88,
doi:10.1016/S0019-9958(82)90439-9.
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.
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.
Keith Ellul (2004):
Descriptional Complexity Measures of Regular Languages.
University of Waterloo,
Ontario, Canada.
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.
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.
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.
Lane A. Hemaspaandra & Mitsunori Ogihara (2002):
The Complexity Theory Companion.
Springer,
doi:10.1007/978-3-662-04880-1.
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.
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.
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.
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.
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.
Martin Kutrib, Andreas Malcher & Matthias Wendlandt (2024):
Complexity of Exclusive Nondeterministic Finite Automata.
submitted for journal publication.
Edmund Landau (1903):
Über die Maximalordnung der Permutationen gegebenen Grades.
Archiv der Math. und Phys. 3,
pp. 92–103.
Edmund Landau (1909):
Handbuch der Lehre von der Verteilung der Primzahlen.
Teubner,
Leipzig.
Hing Leung (1998):
Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata.
SIAM J. Comput. 27,
pp. 1073–1082,
doi:10.1137/S0097539793252092.
Hing Leung (2005):
Descriptional complexity of NFA of different ambiguity.
Int. J. Found. Comput. Sci. 16,
pp. 975–984,
doi:10.1142/S0129054105003418.
Filippo Mera & Giovanni Pighizzini (2005):
Complementing unary nondeterministic automata.
Theor. Comput. Sci. 330,
pp. 349–360,
doi:10.1016/J.TCS.2004.04.015.
Carlo Mereghetti & Giovanni Pighizzini (2001):
Optimal Simulations between Unary Automata.
SIAM J. Comput. 30,
pp. 1976–1992,
doi:10.1137/S009753979935431X.
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.
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.
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.
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.
Alexander Okhotin (2012):
Unambiguous finite automata over a unary alphabet.
Inform. Comput. 212,
pp. 15–36,
doi:10.1016/J.IC.2012.01.003.
Giovanni Pighizzini (2009):
Deterministic Pushdown Automata and Unary Languages.
Int. J. Found. Comput. Sci. 20(4),
pp. 629–645,
doi:10.1142/S0129054109006784.
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.
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.
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.
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.
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.
Erik Meineche Schmidt (1978):
Succinctness of Dscriptions of Context-Free, Regular and Finite Languages.
Cornell University,
Ithaca, NY.
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.
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.
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.
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.
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.