Descriptional Complexity of unary Finite State Automata

Also see general case.

Rules of thumb

• an upper bound can propagate to restrictions of simulated machines or to extensions of simulating machines
• a lower bound can propagate to extensions of simulated machines or to restrictions of simulating machines
• upper bounds can be inherited from the general case, lower bounds cannot

(Row is simulated by/converted in column)

	1DFA	1NFA	2DFA	2NFA
1DFA	/	(trivial)	(trivial)	(trivial)
1NFA	💡	/	💡	(trivial)
2DFA	💡	💡	/	(trivial)
2NFA	💡	💡	💡	/

• (trivial) means that the simulated machine is a (pseudo)subcase of the simulating machine
• 1NFA→1DFA: ^1NFAto1DFA
  • : {Chr86}
  • : {Chr86}
• 2DFA→1DFA: ^2DFAto1DFA
  • : {Chr86}
  • : {Chr86}
• 2DFA→1NFA: ^2DFAto1NFA
  • : since 2DFA→1DFA is and 1DFA→1NFA is ({Chr86})
  • : {Chr86} (shown as an improvement of the lower bound of 2DFA→1DFA)
• 1NFA→2DFA: ^1NFAto2DFA
  • : {Chr86}
  • : {Chr86}
• 2NFA→1DFA: ^2NFAto1DFA
  • : {MerPig01}
  • : otherwise 2DFA→1DFA would be since 2DFA→2NFA is
• 2NFA→1NFA: ^2NFAto1NFA
  • : since 2NFA→1DFA is and 1DFA→1NFA is
  • : otherwise 2DFA→1NFA would be since 2DFA→2NFA is
• 2NFA→2DFA: ^2NFAto2DFA
  • : {GefMer+03} (mentioned in {Pig15})
  • (already proven since 2NFA→1DFA is and 1DFA→2DFA is )
  • Sakoda and Sipser conjecture (the case 1NFA→2DFA is solved for the unary case)