Descriptional Complexity of 1-LA

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	1-LA	D1-LA
1DFA	/	(trivial)	(trivial)	(trivial)	(trivial)	(trivial)
1NFA	💡	/	💡	(trivial)	(trivial)	💡
2DFA	💡	💡	/	(trivial)	(trivial)	(trivial)
2NFA	💡	💡	💡	/	(trivial)	💡
1-LA	💡	💡	💡	💡	/	💡
D1-LA	💡	💡	💡	💡	(trivial)	/

• (trivial) means that the simulated machine is a (pseudo)subcase of the simulating machine
• cases not dependent on 1-LA are specified in the map for Finite State Automata
• 1NFA→D1-LA: ^1NFAtoD1LA
  • : since 1NFA→1DFA is and 1DFA→D1-LA is
  • relaxed form of the Sakoda and Sipser conjecture with extended 2DFA
• 2NFA→D1-LA: ^2NFAtoD1LA
  • : since 2NFA→1DFA is and 1DFA→D1-LA is
  • relaxed form of the Sakoda and Sipser conjecture with extended 2DFA
• 1-LA→1DFA: ^1LAto1DFA
  • : transition table construction {PigPis14}
  • : block witness language {PigPis14}; “reset” witness languages {PigPri+22}
• 1-LA→1NFA: ^1LAto1NFA
  • : transition table construction {PigPis14}
  • : 1NFA requires for block witness language , otherwise with 1NFA→1DFA we would get a 1DFA for with {PigPis14}
• 1-LA→2DFA: ^1LAto2DFA
  • : since 1-LA→1DFA is and 1DFA→2DFA is
  • : otherwise 1-LA→1DFA would be since 2DFA→1DFA is
• 1-LA→2NFA: ^1LAto2NFA
  • : since 1-LA→1NFA is and 1NFA→2NFA is
  • : otherwise 1-LA→1DFA would be since 2NFA→1DFA is
• D1-LA→1DFA: ^D1LAto1DFA
  • : transition table construction {PigPis14}
  • : otherwise with D1-LA→1DFA we would get a 1DFA for with as a D1-LA (2DFA) of size accepts {PigPis14}
• 1-LA→D1-LA: ^1LAtoD1LA
  • : since 1-LA→1DFA is and 1DFA→D1-LA is
  • : otherwise 1-LA→1DFA would be since D1-LA→1DFA is
• D1-LA→2NFA: ^D1LAto2NFA
  • : since D1-LA→1DFA is and 1DFA→2NFA is
  • : unary witness language (recognized with D1-LA presented in {PigPri19} and with 2NFA lower bound proven in {MerPig00})
• D1-LA→1NFA: ^D1LAto1NFA
  • : since D1-LA→1DFA is and 1DFA→1NFA is
  • : otherwise D1-LA→2NFA would be since 1NFA→2NFA is
• D1-LA→2DFA: ^D1LAto2DFA
  • : since D1-LA→1DFA is and 1DFA→2DFA is
  • : otherwise D1-LA→2NFA would be since 2DFA→2NFA is