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