59:(DFA) which can revisit characters already processed. As in a DFA, there are a finite number of states with transitions between them based on the current character, but each transition is also labelled with a value indicating whether the machine will move its position in the input to the left, right, or stay at the same position. Equivalently, 2DFAs can be seen as
1282:
Two-way and one-way finite automata, deterministic and nondeterministic and alternating, accept the same class of regular languages. However, transforming an automaton of one type to an equivalent automaton of another type incurs a blow-up in the number of states.
1268:. In an existential state a 2AFA nondeterministically chooses the next state like an NFA, and accepts if at least one of the resulting computations accepts. In a universal state 2AFA moves to all next states, and accepts if all the resulting computations accept.
94:
that use only a constant amount of space on their work tape, since any constant amount of information can be incorporated into the finite control state via a product construction (a state for each combination of work tape state and control state).
1081:
82:
which can be recognized by a 2DFA can be recognized by a DFA which only examines and consumes each character in order. Since DFAs are obviously a special case of 2DFAs, this implies that both kinds of machines recognize precisely the class of
376:
1471:
552:
657:
1200:
1154:
179:
735:
1651:
845:
791:
1585:
1761:); it has been studied by Hartmanis, Lewis, and Stearns (1965). Aho, Hopcroft, Ullman (1968) and Cook (1971) characterized the class of languages recognizable by deterministic (
1366:
953:
899:
690:
585:
1741:'s "On the Power of 2-Way Quantum Finite State Automata", in which he demonstrates that these machines can recognize nonregular languages and so are more powerful than DFAs.
976:
1258:
1231:
87:. However, the equivalent DFA for a 2DFA may require exponentially many states, making 2DFAs a much more practical representation for algorithms for some common problems.
1694:
Sweeping automata are 2DFAs of a special kind that process the input string by making alternating left-to-right and right-to-left sweeps, turning only at the endmarkers.
1540:
958:
It says that once the automaton reaches the accept or reject state, it stays in there forever and the pointer goes to the right most symbol and cycles there infinitely.
278:
227:
475:
1723:
1662:
It is an open problem whether every 2NFA can be converted to a 2DFA with only a polynomial increase in the number of states. The problem was raised by Sakoda and
1656:
1619:
1503:
1386:
1305:
441:
419:
397:
271:
249:
202:
1091:, a 2NFA accepts a string if at least one of the possible computations is accepting. Like the 2DFAs, the 2NFAs also accept only regular languages.
1391:
2047:
1897:
1822:
Kapoutsis, Christos (2005). "Removing
Bidirectionality from Nondeterministic Finite Automata". In J. Jedrzejowicz, A.Szepietowski (ed.).
1698:
constructed a sequence of languages, each accepted by an n-state NFA, yet which is not accepted by any sweeping automata with fewer than
1880:
Geffert, Viliam; Okhotin, Alexander (2014). "Transforming Two-Way
Alternating Finite Automata to One-Way Nondeterministic Automata".
2014:
1738:
1088:
483:
591:
1671:
1159:
75:
56:
1812:
This definition has been taken from lecture notes of CS682 (Theory of
Computation) by Dexter Kozen of Stanford University
1104:
1769:) two-way pushdown automata; Gray, Harrison, and Ibarra (1967) investigated the closure properties of these languages.
1113:
110:
702:
1845:
Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J. (1984). "Alternating
Pushdown and Stack Automata".
2160:
91:
60:
1624:
797:
743:
695:
It says that there must be some transition possible when the pointer reaches either end of the input word.
1545:
1683:
1310:
1284:
905:
851:
1076:{\displaystyle \delta :Q\times (\Sigma \cup \{L,R\})\rightarrow 2^{Q\times \{\mathrm {left,right} \}}}
662:
557:
970:(2NFA) may have multiple transitions defined in the same configuration. Its transition function is
1236:
1209:
371:{\displaystyle \delta :Q\times (\Sigma \cup \{L,R\})\rightarrow Q\times \{\mathrm {left,right} \}}
1750:
2064:
J. Hartmanis; P.M. Lewis II, R.E. Stearns (1965). "Hierarchies of Memory
Limited Computations".
1508:
2043:
1903:
1893:
1862:
1734:
1478:
1474:
212:
2136:
2092:
1997:
1970:
1926:
1885:
1854:
1827:
1795:
1482:
1388:-state 2DFA or a 2NFA is transformed to an NFA, the worst-case number of states required is
1277:
454:
84:
67:
52:
32:
20:
1701:
2022:
2018:
1679:
79:
24:
2112:
S.A. Cook (1971). "Linear Time
Simulation of Deterministic Two-Way Pushdown Automata".
1695:
1675:
1663:
1604:
1588:
1488:
1371:
1290:
426:
404:
382:
256:
234:
187:
103:
Formally, a two-way deterministic finite automaton can be described by the following 8-
2140:
2097:
2080:
1786:
Rabin, Michael O.; Scott, Dana (1959). "Finite automata and their decision problems".
2154:
2036:
2001:
2127:
Jim Gray; Michael A. Harrison; Oscar H. Ibarra (1967). "Two-Way
Pushdown Automata".
1889:
1974:
1674:. Berman and Lingas discovered a formal relation between this problem and the
71:
1907:
1866:
1961:
Kapoutsis, Christos A. (2014). "Two-Way
Automata Versus Logarithmic Space".
1593:
1466:{\displaystyle {\binom {2n}{n+1}}=O\left({\frac {4^{n}}{\sqrt {n}}}\right)}
1931:
1988:
Sipser, Michael (1980). "Lower Bounds on the Size of
Sweeping Automata".
1667:
2066:
Proc. 6th Ann. IEEE Symp. on
Switching Circuit Theory and Logical Design
1831:
1884:. Lecture Notes in Computer Science. Vol. 8634. pp. 291–302.
1799:
1858:
1948:
On the complexity of regular languages in terms of finite automata
447:
In addition, the following two conditions must also be satisfied:
104:
1753:
that is allowed to move either way on its input tape is called
671:
624:
566:
516:
2079:
Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1968).
2054:
Here: p.124; this paragraph is omitted in the 2003 edition.
2038:
Introduction to Automata Theory, Languages, and Computation
547:{\displaystyle \delta (q,L)=(q^{\prime },\mathrm {right} )}
2081:"Time and Tape Complexity of Pushdown Automaton Languages"
652:{\displaystyle \delta (q,R)=(q^{\prime },\mathrm {left} )}
1826:. MFCS 2005. Vol. 3618. Springer. pp. 544–555.
1195:{\displaystyle Q_{\exists }\cap Q_{\forall }=\emptyset }
1923:
Nondeterminism and the Size of Two Way Finite Automata
74:, who proved them to have equivalent power to one-way
1704:
1627:
1607:
1548:
1511:
1491:
1394:
1374:
1313:
1293:
1239:
1212:
1162:
1116:
979:
908:
854:
800:
746:
705:
665:
594:
560:
486:
457:
429:
407:
385:
281:
259:
237:
215:
190:
113:
2019:
On the Power of 2-Way Quantum Finite State Automata
1950:. Vol. Report 304. Polish Academy of Sciences.
2035:
1717:
1645:
1613:
1579:
1534:
1497:
1465:
1380:
1360:
1299:
1252:
1225:
1194:
1148:
1075:
947:
893:
839:
785:
729:
684:
651:
579:
546:
469:
435:
413:
391:
370:
265:
243:
221:
196:
173:
1882:Mathematical Foundations of Computer Science 2014
1424:
1398:
66:2DFAs were introduced in a seminal 1959 paper by
1733:The concept of 2DFAs was in 1997 generalized to
63:with no work tape, only a read-only input tape.
1149:{\displaystyle Q=Q_{\exists }\cup Q_{\forall }}
174:{\displaystyle M=(Q,\Sigma ,L,R,\delta ,s,t,r)}
229:is the finite, non-empty set of input symbols
8:
2034:John E. Hopcroft; Jeffrey D. Ullman (1979).
1921:Sakoda, William J.; Sipser, Michael (1978).
1824:Mathematical Foundations of Computer Science
1657:(more unsolved problems in computer science)
1542:states. The 2AFA to NFA conversion requires
1068:
1033:
1013:
1001:
730:{\displaystyle \sigma \in \Sigma \cup \{L\}}
724:
718:
365:
330:
315:
303:
1505:-state 2AFA can be converted to a DFA with
16:Type of finite automaton in automata theory
1307:-state 2DFA to an equivalent DFA requires
2096:
1930:
1709:
1703:
1626:
1606:
1553:
1547:
1524:
1516:
1510:
1490:
1446:
1440:
1423:
1397:
1395:
1393:
1373:
1349:
1324:
1312:
1292:
1244:
1238:
1217:
1211:
1180:
1167:
1161:
1140:
1127:
1115:
1036:
1026:
978:
968:two-way nondeterministic finite automaton
962:Two-way nondeterministic finite automaton
907:
853:
799:
745:
704:
670:
664:
632:
623:
593:
565:
559:
524:
515:
485:
456:
428:
406:
384:
333:
280:
258:
236:
214:
189:
112:
1646:{\displaystyle \operatorname {poly} (n)}
840:{\displaystyle \delta (r,\sigma )=(r,R)}
786:{\displaystyle \delta (t,\sigma )=(t,R)}
1990:Journal of Computer and System Sciences
1946:Berman, Piotr; Lingas, Andrzej (1977).
1788:IBM Journal of Research and Development
1778:
45:two-way deterministic finite automaton
39:Two-way deterministic finite automaton
35:that is allowed to re-read its input.
7:
1925:. STOC 1978. ACM. pp. 275–286.
1596:Unsolved problem in computer science
1580:{\displaystyle 2^{\Theta (n\log n)}}
1103:(2AFA) is a two-way extension of an
1101:two-way alternating finite automaton
1095:Two-way alternating finite automaton
1554:
1402:
1361:{\displaystyle n(n^{n}-(n-1)^{n})}
1245:
1218:
1189:
1181:
1168:
1141:
1128:
1064:
1061:
1058:
1055:
1052:
1046:
1043:
1040:
1037:
995:
948:{\displaystyle \delta (r,R)=(r,L)}
894:{\displaystyle \delta (t,R)=(t,L)}
712:
642:
639:
636:
633:
537:
534:
531:
528:
525:
361:
358:
355:
352:
349:
343:
340:
337:
334:
297:
216:
129:
14:
2116:. North Holland. pp. 75–80.
1729:Two-way quantum finite automaton
1368:states in the worst case. If an
1287:determined that transforming an
685:{\displaystyle q^{\prime }\in Q}
580:{\displaystyle q^{\prime }\in Q}
204:is the finite, non-empty set of
1672:computational complexity theory
1621:-state 2NFA have an equivalent
55:, a generalized version of the
1640:
1634:
1587:states in the worst case, see
1572:
1557:
1355:
1346:
1333:
1317:
1019:
1016:
992:
942:
930:
924:
912:
888:
876:
870:
858:
834:
822:
816:
804:
780:
768:
762:
750:
646:
616:
610:
598:
541:
508:
502:
490:
321:
318:
294:
168:
120:
57:deterministic finite automaton
1:
2141:10.1016/s0019-9958(67)90369-5
2098:10.1016/s0019-9958(68)91087-5
90:2DFAs are also equivalent to
2002:10.1016/0022-0000(80)90034-3
1890:10.1007/978-3-662-44522-8_25
1253:{\displaystyle Q_{\forall }}
1226:{\displaystyle Q_{\exists }}
1105:alternating finite automaton
1963:Theory of Computing Systems
2177:
1755:two-way pushdown automaton
1745:Two-way pushdown automaton
1535:{\displaystyle 2^{n2^{n}}}
1275:
1272:State complexity tradeoffs
2021:. CS-TR-1997-1350. 1997.
1975:10.1007/s00224-013-9465-0
1847:SIAM Journal on Computing
1765:) and non-deterministic (
1666:, who compared it to the
92:read-only Turing machines
61:read-only Turing machines
1686:for a precise relation.
1107:(AFA). Its state set is
1087:Like a standard one-way
29:two-way finite automaton
2129:Information and Control
2085:Information and Control
222:{\displaystyle \Sigma }
1719:
1647:
1615:
1581:
1536:
1499:
1467:
1382:
1362:
1301:
1254:
1227:
1196:
1150:
1077:
949:
895:
841:
787:
731:
686:
653:
581:
548:
471:
470:{\displaystyle q\in Q}
437:
415:
393:
372:
273:is the right endmarker
267:
245:
223:
198:
175:
1932:10.1145/800133.804357
1720:
1718:{\displaystyle 2^{n}}
1648:
1616:
1582:
1537:
1500:
1468:
1383:
1363:
1302:
1255:
1228:
1197:
1151:
1078:
950:
896:
842:
788:
732:
687:
654:
582:
549:
472:
438:
416:
394:
373:
268:
251:is the left endmarker
246:
224:
199:
176:
1702:
1625:
1605:
1546:
1509:
1489:
1392:
1372:
1311:
1291:
1237:
1210:
1160:
1114:
977:
906:
852:
798:
744:
703:
663:
592:
558:
484:
455:
427:
405:
383:
279:
257:
235:
213:
188:
111:
2114:Proc. IFIP Congress
2068:. pp. 179–190.
1832:10.1007/11549345_47
443:is the reject state
23:, in particular in
2042:. Addison-Wesley.
1800:10.1147/rd.32.0114
1751:pushdown automaton
1715:
1682:open problem, see
1643:
1611:
1577:
1532:
1495:
1463:
1378:
1358:
1297:
1285:Christos Kapoutsis
1250:
1223:
1192:
1146:
1073:
945:
891:
837:
783:
727:
682:
649:
577:
544:
467:
433:
411:
399:is the start state
389:
368:
263:
241:
219:
194:
171:
99:Formal description
2049:978-0-201-02988-8
1899:978-3-662-44521-1
1735:quantum computing
1690:Sweeping automata
1614:{\displaystyle n}
1498:{\displaystyle n}
1485:. proved that an
1457:
1456:
1422:
1381:{\displaystyle n}
1300:{\displaystyle n}
436:{\displaystyle r}
414:{\displaystyle t}
392:{\displaystyle s}
266:{\displaystyle R}
244:{\displaystyle L}
197:{\displaystyle Q}
85:regular languages
2168:
2145:
2144:
2124:
2118:
2117:
2109:
2103:
2102:
2100:
2076:
2070:
2069:
2061:
2055:
2053:
2041:
2031:
2025:
2012:
2006:
2005:
1985:
1979:
1978:
1958:
1952:
1951:
1943:
1937:
1936:
1934:
1918:
1912:
1911:
1877:
1871:
1870:
1842:
1836:
1835:
1819:
1813:
1810:
1804:
1803:
1783:
1724:
1722:
1721:
1716:
1714:
1713:
1652:
1650:
1649:
1644:
1620:
1618:
1617:
1612:
1597:
1586:
1584:
1583:
1578:
1576:
1575:
1541:
1539:
1538:
1533:
1531:
1530:
1529:
1528:
1504:
1502:
1501:
1496:
1472:
1470:
1469:
1464:
1462:
1458:
1452:
1451:
1450:
1441:
1429:
1428:
1427:
1421:
1410:
1401:
1387:
1385:
1384:
1379:
1367:
1365:
1364:
1359:
1354:
1353:
1329:
1328:
1306:
1304:
1303:
1298:
1278:State complexity
1259:
1257:
1256:
1251:
1249:
1248:
1232:
1230:
1229:
1224:
1222:
1221:
1201:
1199:
1198:
1193:
1185:
1184:
1172:
1171:
1155:
1153:
1152:
1147:
1145:
1144:
1132:
1131:
1082:
1080:
1079:
1074:
1072:
1071:
1067:
954:
952:
951:
946:
900:
898:
897:
892:
846:
844:
843:
838:
792:
790:
789:
784:
736:
734:
733:
728:
699:For all symbols
691:
689:
688:
683:
675:
674:
658:
656:
655:
650:
645:
628:
627:
586:
584:
583:
578:
570:
569:
553:
551:
550:
545:
540:
520:
519:
476:
474:
473:
468:
442:
440:
439:
434:
421:is the end state
420:
418:
417:
412:
398:
396:
395:
390:
377:
375:
374:
369:
364:
272:
270:
269:
264:
250:
248:
247:
242:
228:
226:
225:
220:
203:
201:
200:
195:
180:
178:
177:
172:
53:abstract machine
33:finite automaton
21:computer science
2176:
2175:
2171:
2170:
2169:
2167:
2166:
2165:
2161:Finite automata
2151:
2150:
2149:
2148:
2126:
2125:
2121:
2111:
2110:
2106:
2078:
2077:
2073:
2063:
2062:
2058:
2050:
2033:
2032:
2028:
2013:
2009:
1987:
1986:
1982:
1960:
1959:
1955:
1945:
1944:
1940:
1920:
1919:
1915:
1900:
1879:
1878:
1874:
1859:10.1137/0213010
1844:
1843:
1839:
1821:
1820:
1816:
1811:
1807:
1785:
1784:
1780:
1775:
1747:
1731:
1705:
1700:
1699:
1692:
1670:problem in the
1660:
1659:
1654:
1623:
1622:
1603:
1602:
1599:
1595:
1549:
1544:
1543:
1520:
1512:
1507:
1506:
1487:
1486:
1442:
1436:
1411:
1403:
1396:
1390:
1389:
1370:
1369:
1345:
1320:
1309:
1308:
1289:
1288:
1280:
1274:
1240:
1235:
1234:
1213:
1208:
1207:
1176:
1163:
1158:
1157:
1136:
1123:
1112:
1111:
1097:
1022:
975:
974:
964:
904:
903:
850:
849:
796:
795:
742:
741:
701:
700:
666:
661:
660:
619:
590:
589:
561:
556:
555:
511:
482:
481:
453:
452:
425:
424:
403:
402:
381:
380:
277:
276:
255:
254:
233:
232:
211:
210:
186:
185:
109:
108:
101:
80:formal language
78:. That is, any
41:
25:automata theory
17:
12:
11:
5:
2174:
2172:
2164:
2163:
2153:
2152:
2147:
2146:
2135:(1–2): 30–70.
2119:
2104:
2091:(3): 186–206.
2071:
2056:
2048:
2026:
2007:
1996:(2): 195–202.
1980:
1969:(2): 421–447.
1953:
1938:
1913:
1898:
1872:
1853:(1): 135–155.
1837:
1814:
1805:
1794:(2): 114–125.
1777:
1776:
1774:
1771:
1746:
1743:
1730:
1727:
1712:
1708:
1691:
1688:
1655:
1642:
1639:
1636:
1633:
1630:
1610:
1600:
1594:
1574:
1571:
1568:
1565:
1562:
1559:
1556:
1552:
1527:
1523:
1519:
1515:
1494:
1461:
1455:
1449:
1445:
1439:
1435:
1432:
1426:
1420:
1417:
1414:
1409:
1406:
1400:
1377:
1357:
1352:
1348:
1344:
1341:
1338:
1335:
1332:
1327:
1323:
1319:
1316:
1296:
1276:Main article:
1273:
1270:
1247:
1243:
1220:
1216:
1204:
1203:
1191:
1188:
1183:
1179:
1175:
1170:
1166:
1143:
1139:
1135:
1130:
1126:
1122:
1119:
1096:
1093:
1085:
1084:
1070:
1066:
1063:
1060:
1057:
1054:
1051:
1048:
1045:
1042:
1039:
1035:
1032:
1029:
1025:
1021:
1018:
1015:
1012:
1009:
1006:
1003:
1000:
997:
994:
991:
988:
985:
982:
963:
960:
956:
955:
944:
941:
938:
935:
932:
929:
926:
923:
920:
917:
914:
911:
901:
890:
887:
884:
881:
878:
875:
872:
869:
866:
863:
860:
857:
847:
836:
833:
830:
827:
824:
821:
818:
815:
812:
809:
806:
803:
793:
782:
779:
776:
773:
770:
767:
764:
761:
758:
755:
752:
749:
738:
737:
726:
723:
720:
717:
714:
711:
708:
693:
692:
681:
678:
673:
669:
648:
644:
641:
638:
635:
631:
626:
622:
618:
615:
612:
609:
606:
603:
600:
597:
587:
576:
573:
568:
564:
543:
539:
536:
533:
530:
527:
523:
518:
514:
510:
507:
504:
501:
498:
495:
492:
489:
478:
477:
466:
463:
460:
445:
444:
432:
422:
410:
400:
388:
378:
367:
363:
360:
357:
354:
351:
348:
345:
342:
339:
336:
332:
329:
326:
323:
320:
317:
314:
311:
308:
305:
302:
299:
296:
293:
290:
287:
284:
274:
262:
252:
240:
230:
218:
208:
193:
170:
167:
164:
161:
158:
155:
152:
149:
146:
143:
140:
137:
134:
131:
128:
125:
122:
119:
116:
100:
97:
40:
37:
15:
13:
10:
9:
6:
4:
3:
2:
2173:
2162:
2159:
2158:
2156:
2142:
2138:
2134:
2130:
2123:
2120:
2115:
2108:
2105:
2099:
2094:
2090:
2086:
2082:
2075:
2072:
2067:
2060:
2057:
2051:
2045:
2040:
2039:
2030:
2027:
2024:
2020:
2016:
2011:
2008:
2003:
1999:
1995:
1991:
1984:
1981:
1976:
1972:
1968:
1964:
1957:
1954:
1949:
1942:
1939:
1933:
1928:
1924:
1917:
1914:
1909:
1905:
1901:
1895:
1891:
1887:
1883:
1876:
1873:
1868:
1864:
1860:
1856:
1852:
1848:
1841:
1838:
1833:
1829:
1825:
1818:
1815:
1809:
1806:
1801:
1797:
1793:
1789:
1782:
1779:
1772:
1770:
1768:
1764:
1760:
1756:
1752:
1744:
1742:
1740:
1736:
1728:
1726:
1710:
1706:
1697:
1689:
1687:
1685:
1681:
1677:
1673:
1669:
1665:
1658:
1637:
1631:
1628:
1608:
1592:
1591:and Okhotin.
1590:
1569:
1566:
1563:
1560:
1550:
1525:
1521:
1517:
1513:
1492:
1484:
1480:
1476:
1459:
1453:
1447:
1443:
1437:
1433:
1430:
1418:
1415:
1412:
1407:
1404:
1375:
1350:
1342:
1339:
1336:
1330:
1325:
1321:
1314:
1294:
1286:
1279:
1271:
1269:
1267:
1263:
1241:
1214:
1186:
1177:
1173:
1164:
1137:
1133:
1124:
1120:
1117:
1110:
1109:
1108:
1106:
1102:
1094:
1092:
1090:
1049:
1030:
1027:
1023:
1010:
1007:
1004:
998:
989:
986:
983:
980:
973:
972:
971:
969:
961:
959:
939:
936:
933:
927:
921:
918:
915:
909:
902:
885:
882:
879:
873:
867:
864:
861:
855:
848:
831:
828:
825:
819:
813:
810:
807:
801:
794:
777:
774:
771:
765:
759:
756:
753:
747:
740:
739:
721:
715:
709:
706:
698:
697:
696:
679:
676:
667:
629:
620:
613:
607:
604:
601:
595:
588:
574:
571:
562:
521:
512:
505:
499:
496:
493:
487:
480:
479:
464:
461:
458:
450:
449:
448:
430:
423:
408:
401:
386:
379:
346:
327:
324:
312:
309:
306:
300:
291:
288:
285:
282:
275:
260:
253:
238:
231:
209:
207:
191:
184:
183:
182:
165:
162:
159:
156:
153:
150:
147:
144:
141:
138:
135:
132:
126:
123:
117:
114:
106:
98:
96:
93:
88:
86:
81:
77:
73:
69:
64:
62:
58:
54:
50:
46:
38:
36:
34:
30:
26:
22:
2132:
2128:
2122:
2113:
2107:
2088:
2084:
2074:
2065:
2059:
2037:
2029:
2015:John Watrous
2010:
1993:
1989:
1983:
1966:
1962:
1956:
1947:
1941:
1922:
1916:
1881:
1875:
1850:
1846:
1840:
1823:
1817:
1808:
1791:
1787:
1781:
1766:
1762:
1758:
1754:
1748:
1739:John Watrous
1732:
1693:
1661:
1653:-state 2DFA?
1281:
1265:
1261:
1205:
1100:
1098:
1086:
967:
965:
957:
694:
446:
205:
102:
89:
65:
48:
44:
42:
28:
18:
1601:Does every
1262:existential
1260:are called
1773:References
1483:Stockmeyer
1206:States in
1908:0302-9743
1867:0097-5397
1684:Kapoutsis
1632:
1567:
1555:Θ
1340:−
1331:−
1266:universal
1246:∀
1219:∃
1190:∅
1182:∀
1174:∩
1169:∃
1142:∀
1134:∪
1129:∃
1031:×
1020:→
999:∪
996:Σ
990:×
981:δ
910:δ
856:δ
814:σ
802:δ
760:σ
748:δ
716:∪
713:Σ
710:∈
707:σ
677:∈
672:′
659:for some
625:′
596:δ
572:∈
567:′
554:for some
517:′
488:δ
462:∈
328:×
322:→
301:∪
298:Σ
292:×
283:δ
217:Σ
148:δ
130:Σ
2155:Category
1725:states.
1668:P vs. NP
451:For all
51:) is an
1589:Geffert
2046:
1906:
1896:
1865:
1696:Sipser
1664:Sipser
1479:Lipton
1475:Ladner
1264:resp.
1156:where
206:states
181:where
1767:2NPDA
1763:2DPDA
105:tuple
72:Scott
68:Rabin
31:is a
2044:ISBN
1904:ISSN
1894:ISBN
1863:ISSN
1759:2PDA
1678:vs.
1629:poly
1481:and
1233:and
76:DFAs
70:and
49:2DFA
27:, a
2137:doi
2093:doi
2023:pdf
1998:doi
1971:doi
1927:doi
1886:doi
1855:doi
1828:doi
1796:doi
1737:by
1564:log
1089:NFA
19:In
2157::
2133:11
2131:.
2089:13
2087:.
2083:.
2017:.
1994:21
1992:.
1967:55
1965:.
1902:.
1892:.
1861:.
1851:13
1849:.
1790:.
1749:A
1680:NL
1477:,
1473:.
1099:A
966:A
107::
43:A
2143:.
2139::
2101:.
2095::
2052:.
2004:.
2000::
1977:.
1973::
1935:.
1929::
1910:.
1888::
1869:.
1857::
1834:.
1830::
1802:.
1798::
1792:3
1757:(
1711:n
1707:2
1676:L
1641:)
1638:n
1635:(
1609:n
1598::
1573:)
1570:n
1561:n
1558:(
1551:2
1526:n
1522:2
1518:n
1514:2
1493:n
1460:)
1454:n
1448:n
1444:4
1438:(
1434:O
1431:=
1425:)
1419:1
1416:+
1413:n
1408:n
1405:2
1399:(
1376:n
1356:)
1351:n
1347:)
1343:1
1337:n
1334:(
1326:n
1322:n
1318:(
1315:n
1295:n
1242:Q
1215:Q
1202:.
1187:=
1178:Q
1165:Q
1138:Q
1125:Q
1121:=
1118:Q
1083:.
1069:}
1065:t
1062:h
1059:g
1056:i
1053:r
1050:,
1047:t
1044:f
1041:e
1038:l
1034:{
1028:Q
1024:2
1017:)
1014:}
1011:R
1008:,
1005:L
1002:{
993:(
987:Q
984::
943:)
940:L
937:,
934:r
931:(
928:=
925:)
922:R
919:,
916:r
913:(
889:)
886:L
883:,
880:t
877:(
874:=
871:)
868:R
865:,
862:t
859:(
835:)
832:R
829:,
826:r
823:(
820:=
817:)
811:,
808:r
805:(
781:)
778:R
775:,
772:t
769:(
766:=
763:)
757:,
754:t
751:(
725:}
722:L
719:{
680:Q
668:q
647:)
643:t
640:f
637:e
634:l
630:,
621:q
617:(
614:=
611:)
608:R
605:,
602:q
599:(
575:Q
563:q
542:)
538:t
535:h
532:g
529:i
526:r
522:,
513:q
509:(
506:=
503:)
500:L
497:,
494:q
491:(
465:Q
459:q
431:r
409:t
387:s
366:}
362:t
359:h
356:g
353:i
350:r
347:,
344:t
341:f
338:e
335:l
331:{
325:Q
319:)
316:}
313:R
310:,
307:L
304:{
295:(
289:Q
286::
261:R
239:L
192:Q
169:)
166:r
163:,
160:t
157:,
154:s
151:,
145:,
142:R
139:,
136:L
133:,
127:,
124:Q
121:(
118:=
115:M
47:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.