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 | 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 unary Finite State Automata
- 1NFA→D1-LA: ^1NFAtoD1LA
: since 1NFA→2DFA is and 2DFA→D1-LA is
- 2NFA→D1-LA: ^2NFAtoD1LA
: since 2NFA→2DFA is and 2DFA→D1-LA is - relaxed form of the Sakoda and Sipser conjecture with extended 2DFA
- D1-LA→2NFA: ^D1LAto2NFA
: since D1-LA→1DFA is and 1DFA→2NFA is : witness language (recognized with D1-LA presented in {PigPri19} and with 2NFA lower bound proven in {MerPig00}) (honorable mention: by {KutPig+18})
- D1-LA→1DFA: ^D1LAto1DFA
: transition table construction {PigPis14} : otherwise D1-LA→2NFA would be since 1DFA→2NFA is
- 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
- 1-LA→1DFA: ^1LAto1DFA
: transition table construction for the general case {PigPis14} : otherwise D1-LA→1DFA would be since D1-LA→1-LA is
- 1-LA→1NFA: ^1LAto1NFA
: transition table construction for the general case {PigPis14} : otherwise D1-LA→1NFA would be since D1-LA→1-LA is
- 1-LA→2DFA: ^1LAto2DFA
: since 1-LA→1NFA is and 1NFA→2DFA is : otherwise D1-LA→2DFA would be since D1-LA→1-LA is
- 1-LA→2NFA: ^1LAto2NFA
: since 1-LA→1NFA is and 1NFA→2NFA is : otherwise D1-LA→2NFA would be since D1-LA→1-LA is
- 1-LA→D1-LA: ^1LAtoD1LA
: since 1-LA→1NFA is and 1NFA→D1-LA is