Also see non-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
- upper bounds can be inherited from the general case (both with respect to the input alphabet and the writing capabilities), lower 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 unary Finite State Automata
- 1NFA→OM-D1-LA: ^1NFAtoOMD1LA
: since 1NFA→2DFA is and 2DFA→OM-D1-LA is
- 2NFA→OM-D1-LA: ^2NFAtoOMD1LA
: since 2NFA→2DFA is and 2DFA→OM-D1-LA is - relaxed form of the Sakoda and Sipser conjecture with extended 2DFA
- OM-1-LA→1DFA: ^OM1LAto1DFA
: transition table construction for the general case {PigPis14} : otherwise 2DFA→1DFA would be since 2DFA→OM-1-LA is
- OM-1-LA→1NFA: ^OM1LAto1NFA
: transition table construction for the general case {PigPis14} : otherwise 2DFA→1NFA would be since 2DFA→OM-1-LA is
- OM-1-LA→2DFA: ^OM1LAto2DFA
: since OM-1-LA→1NFA is and 1NFA→2DFA is
- OM-1-LA→2NFA: ^OM1LAto2NFA
: since OM-1-LA→1NFA is and 1NFA→2NFA is
- OM-1-LA→OM-D1-LA: ^OM1LAtoOMD1LA
: since OM-1-LA→1NFA is and 1NFA→OM-D1-LA is
- OM-D1-LA→1DFA: ^OMD1LAto1DFA
: transition table construction for the general case {PigPis14} : otherwise 2DFA→1DFA would be since 2DFA→OM-D1-LA is
- OM-D1-LA→1NFA: ^OMD1LAto1NFA
: transition table construction for the general case {PigPis14} : otherwise 2DFA→1NFA would be since 2DFA→OM-D1-LA is
- OM-D1-LA→2DFA: ^OMD1LAto2DFA
: simulation via computation trees for the general case {PigPri23a}
- OM-D1-LA→2NFA: ^OMD1LAto2NFA
: since OM-D1-LA→2DFA is and 2DFA→2NFA is