Descriptional Complexity of Finite State Automata

Also see unary 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
• lower bounds can be inherited from the unary case, upper 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
  • : subset construction {RabSco59}
  • : witness languages: Meyer and Fischer’s automaton (distinguishability) {MeyFis71}, Moore’s automaton {Moo71}
• 1NFA→2DFA: ^1NFAto2DFA
  • : since 1NFA→1DFA is and 1DFA→2DFA is
  • Sakoda and Sipser conjecture that it’s {SakSip78}
• 2DFA→1NFA: ^2DFAto1NFA
  • : since 1NFA→1DFA is and 1DFA→1NFA is
  • proven in {Bir93} (cited in {PigPis14})
• 2DFA→1DFA: ^2DFAto1DFA
  • : proven in {She59} (transition tables) and in parallel in {RabSco59} (crossing sequences)
  • : otherwise 2DFA→1NFA would be since 1DFA→1NFA is
• 2NFA→1DFA: ^2NFAto1DFA
  • : generally attributed to the same articles of 2DFA→1DFA
  • : otherwise 1NFA→1DFA would be since 1NFA→2NFA is
• 2NFA→1NFA: ^2NFAto1NFA
  • : proven in {Kap05} (precisely )
  • : proven in {Kap05} (precisely )
• 2NFA→2DFA: ^2NFAto2DFA
  • : since 2NFA→1DFA is and 1DFA→2DFA is
  • Sakoda and Sipser conjecture that it’s {SakSip78}