Also see unary case and 1-LA 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 specific cases (both with respect to the input alphabet and the writing capabilities), upper bounds cannot
(Row is simulated by/converted in column)
| 1DFA | 1NFA | 2DFA | 2NFA | OM-1-LA | OM-D1-LA | |
|---|---|---|---|---|---|---|
| 1DFA | / | (trivial) | (trivial) | (trivial) | (trivial) | (trivial) |
| 1NFA | / | (trivial) | (trivial) | |||
| 2DFA | / | (trivial) | (trivial) | (trivial) | ||
| 2NFA | / | (trivial) | ||||
| OM-1-LA | / | |||||
| OM-D1-LA | (trivial) | / |
- (trivial) means that the simulated machine is a (pseudo)subcase of the simulating machine
- cases not dependent on OM-1-LA are specified in the map for Finite State Automata
- 1NFA→OM-D1-LA: ^1NFAtoOMD1LA
: since 1NFA→1DFA is and 1DFA→OM-D1-LA is - relaxed form of the Sakoda and Sipser conjecture with extended 2DFA
- 2NFA→OM-D1-LA: ^2NFAtoOMD1LA
: since 2NFA→1DFA is and 1DFA→OM-D1-LA is - relaxed form of the Sakoda and Sipser conjecture with extended 2DFA
- OM-1-LA→1DFA: ^OM1LAto1DFA
: transition table construction for general 1-LA {PigPis14} : block witness language {PigPri23a}
- OM-1-LA→1NFA: ^OM1LAto1NFA
: transition table construction {PigPis14} : otherwise OM-1-LA→1DFA would be since 1NFA→1DFA is
- OM-1-LA→2DFA: ^OM1LAto2DFA
: since OM-1-LA→1DFA is and 1DFA→2DFA is : otherwise OM-1-LA→1DFA would be since 2DFA→1DFA is
- OM-1-LA→2NFA: ^OM1LAto2NFA
: since OM-1-LA→1NFA is and 1NFA→2NFA is : otherwise OM-1-LA→1DFA would be since 2NFA→1DFA is
- OM-D1-LA→1DFA: ^OMD1LAto1DFA
: transition table construction for general 1-LA {PigPis14} : otherwise with OM-D1-LA→1DFA we would get a 1DFA for with as a OM-D1-LA (2DFA) of size accepts
- OM-1-LA→OM-D1-LA: ^OM1LAtoOMD1LA
: since OM-1-LA→1DFA is and 1DFA→OM-D1-LA is : otherwise OM-1-LA→1DFA would be since OM-D1-LA→1DFA is
- OM-D1-LA→1NFA: ^OMD1LAto1NFA
: since OM-D1-LA→1DFA is and 1DFA→1NFA is (previously mistakenly considered poly) : witness language (OM-D1-LA + fooling set) (proven by us)
- OM-D1-LA→2DFA: ^OMD1LAto2DFA
: simulation via computation trees given in {PigPri23a}
- OM-D1-LA→2NFA: ^OMD1LAto2NFA
: since OM-D1-LA→2DFA is and 2DFA→2NFA is