1368:
is a context-sensitive language (the "2" in the name of this language is intended to mean a binary alphabet). This was proved by
Hartmanis using pumping lemmas for regular and context-free languages over a binary alphabet and, after that, sketching a linear bounded multitape automaton accepting
1477:
is a context-sensitive language (the "1" in the name of this language is intended to mean a unary alphabet). This was credited by A. Salomaa to Matti
Soittola by means of a linear bounded automaton over a unary alphabet (pages 213-214, exercise 6.8) and also to Marti Penttonen by means of a
252:"c"s (abc, aabbcc, aaabbbccc, etc.). A superset of this language, called the Bach language, is defined as the set of all strings where "a", "b" and "c" (or any other set of three symbols) occurs equally often (aabccb, baabcaccb, etc.) and is also context-sensitive.
595:
is another context-sensitive language (the "3" in the name of this language is intended to mean a ternary alphabet); that is, the "product" operation defines a context-sensitive language (but the "sum" defines only a context-free language as the grammar
137:
is a constant associated with the machine. This means that every formal language that can be decided by such a machine is a context-sensitive language, and every context-sensitive language can be decided by such a machine.
383:
795:
1475:
1366:
1164:
1231:
593:
870:
1300:
1097:
385:
is another context-sensitive language; the corresponding context-sensitive grammar can be easily projected starting with two context-free grammars generating sentential forms in the formats
1014:
942:
1543:
238:
1902:
677:
706:
634:
489:
1689:
Joshi, A.; Vijay-Shanker, K.; and Weir, D. (1991). "The convergence of mildly context-sensitive grammar formalisms". In: Sells, P., Shieber, S.M. and Wasow, T. (Editors).
1412:
457:
420:
95:
135:
115:
2222:
1895:
1524:
Membership of a string in a language defined by an arbitrary context-sensitive grammar, or by an arbitrary deterministic context-sensitive grammar, is a
1099:
is a context-sensitive language. The corresponding context-sensitive grammar can be obtained as a generalization of the context-sensitive grammars for
1652:
286:
1702:
Example 9.5 (p. 224) of
Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley
2109:
1888:
1774:
1621:
1588:
1518:
711:
2034:
1419:
2124:
1307:
2049:
1102:
1807:
1169:
496:
2217:
2202:
800:
2078:
67:
1858:
1669:
1238:
1616:, Studies in Logic and the Foundations of Mathematics, vol. 143, Amsterdam: North-Holland Publishing Co., p. 236,
1021:
161:
Turing machine. Clearly LINSPACE is a subset of NLINSPACE, but it is not known whether LINSPACE = NLINSPACE.
149:)), because they can be accepted using linear space on a non-deterministic Turing machine. The class LINSPACE (or DSPACE(
2095:
2020:
2192:
947:
875:
172:
1478:
context-sensitive grammar also over a unary alphabet (See: Formal
Languages by A. Salomaa, page 14, Example 2.5).
708:
is ambiguous. This problem can be avoided considering a somehow more restrictive definition of the language, e.g.
2264:
2013:
1507:
43:
2165:
2160:
1538:
71:
28:
2246:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
158:
2176:
2114:
2039:
1840:
47:
35:
1814:; Exercise 9.10, p.230. In the 2000 edition, the chapter on context-sensitive languages has been omitted.
639:
258:
can be shown to be a context-sensitive language by constructing a linear bounded automaton which accepts
2119:
2067:
1880:
682:
599:
267:
462:
2212:
2187:
2044:
2005:
1845:
2197:
2139:
2083:
1748:
1721:
1517:
The complement of a context-sensitive language is itself context-sensitive a result known as the
1503:
1490:
1482:
1372:
425:
388:
1583:, Texts in Theoretical Computer Science. An EATCS Series, Berlin: Springer-Verlag, p. 77,
1932:
1803:
1770:
1713:
1617:
1584:
1548:
55:
2181:
2134:
2101:
1947:
1850:
1778:
1738:
1730:
1553:
263:
1631:
1598:
679:
shows). Because of the commutative property of the product, the most intuitive grammar for
17:
2144:
2059:
2026:
1942:
1915:
1911:
1673:
1627:
1594:
1525:
77:
2155:
1937:
1919:
1559:
120:
100:
2258:
2240:
1796:
271:
1752:
1825:
1666:
1510:, concatenation of two context-sensitive languages is context-sensitive, also the
2207:
2129:
2054:
1511:
66:
Computationally, a context-sensitive language is equivalent to a linear bounded
1485:
that is not context-sensitive is any recursive language whose decision is an
1782:
378:{\displaystyle L_{\textit {Cross}}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}}
1646:
1734:
1486:
169:
One of the simplest context-sensitive but not context-free languages is
790:{\displaystyle L_{\textit {ORDMUL3}}=\{a^{m}b^{n}c^{mn}:1<m<n\}}
1743:
1854:
1470:{\displaystyle L_{\textit {PRIMES1}}=\{a^{p}:p{\mbox{ is prime }}\}}
2170:
1361:{\displaystyle L_{\textit {PRIMES2}}=\{w:|w|{\mbox{ is prime }}\}}
74:. That is a non-deterministic Turing machine with a tape of only
459:
and then supplementing them with a permutation production like
27:"Context-dependent" redirects here. For the type of memory, see
1884:
1667:"Discontinuous constituents in generalized categorial grammars"
1648:
Context-freeness and the computer processing of human languages
1429:
1317:
1248:
1179:
1159:{\displaystyle L_{\textit {Square}}=\{w^{2}:w\in \Sigma ^{*}\}}
1112:
810:
721:
692:
296:
1226:{\displaystyle L_{\textit {Cube}}=\{w^{3}:w\in \Sigma ^{*}\}}
588:{\displaystyle L_{MUL3}=\{a^{m}b^{n}c^{mn}:m\geq 1,n\geq 1\}}
2239:
Each category of languages, except those marked by a , is a
1798:
Introduction to
Automata Theory, Languages, and Computation
865:{\displaystyle L_{\textit {MUL1}}=\{a^{mn}:m>1,n>1\}}
141:
This set of languages is also known as NLINSPACE or NSPACE(
1544:
List of parser generators for context-sensitive languages
1826:"Nondeterministic space is closed under complementation"
1295:{\displaystyle L_{\textit {EXP}}=\{a^{2^{n}}:n\geq 1\}}
1458:
1349:
491:, a new starting symbol and standard syntactic sugar.
1514:
of a context-sensitive language is context-sensitive.
1422:
1375:
1310:
1241:
1172:
1105:
1024:
950:
878:
803:
714:
685:
642:
602:
499:
465:
428:
391:
289:
175:
123:
103:
80:
1556:– a strict subset of the context-sensitive languages
1092:{\displaystyle L_{REP}=\{w^{|w|}:w\in \Sigma ^{*}\}}
1489:-hard problem, say, the set of pairs of equivalent
1795:
1691:Foundational Issues in Natural Language Processing
1469:
1406:
1360:
1294:
1225:
1158:
1091:
1008:
936:
864:
789:
700:
671:
628:
587:
483:
451:
414:
377:
232:
129:
109:
89:
262:. The language can easily be shown to be neither
1009:{\displaystyle L_{m^{3}}=\{a^{m^{3}}:m>1\}}
937:{\displaystyle L_{m^{2}}=\{a^{m^{2}}:m>1\}}
1896:
233:{\displaystyle L=\{a^{n}b^{n}c^{n}:n\geq 1\}}
8:
1794:John E. Hopcroft; Jeffrey D. Ullman (1979).
1464:
1438:
1355:
1326:
1289:
1257:
1220:
1188:
1153:
1121:
1086:
1044:
1003:
971:
931:
899:
859:
819:
784:
730:
582:
522:
372:
305:
240:: the language of all strings consisting of
227:
182:
2218:Counter-free (with aperiodic finite monoid)
1928:
1903:
1889:
1881:
1714:"On the Recognition of Primes by Automata"
1875:Introduction to the Theory of Computation
1844:
1742:
1497:Properties of context-sensitive languages
1457:
1445:
1428:
1427:
1421:
1380:
1374:
1348:
1343:
1335:
1316:
1315:
1309:
1269:
1264:
1247:
1246:
1240:
1214:
1195:
1178:
1177:
1171:
1147:
1128:
1111:
1110:
1104:
1080:
1060:
1052:
1051:
1029:
1023:
983:
978:
960:
955:
949:
911:
906:
888:
883:
877:
826:
809:
808:
802:
757:
747:
737:
720:
719:
713:
691:
690:
684:
658:
641:
618:
601:
549:
539:
529:
504:
498:
464:
443:
433:
427:
406:
396:
390:
342:
332:
322:
312:
295:
294:
288:
209:
199:
189:
174:
122:
102:
79:
157:))) is defined the same, except using a
1571:
42:is a language that can be defined by a
2110:Linear context-free rewriting language
1712:J. Hartmanis and H. Shank (Jul 1968).
2035:Linear context-free rewriting systems
7:
274:for each of the language classes to
244:occurrences of the symbol "a", then
1651:. Proc. 21st Annual Meeting of the
1614:Classical recursion theory. Vol. II
672:{\displaystyle R\rightarrow bRc|bc}
2243:of the category directly above it.
1211:
1144:
1077:
701:{\displaystyle L_{\textit {MUL3}}}
629:{\displaystyle S\rightarrow aSc|R}
25:
1302:is a context-sensitive language.
50:). Context-sensitive is known as
1864:from the original on 2004-06-25.
1581:Complexity theory and cryptology
484:{\displaystyle CB\rightarrow BC}
1680:, vol. 11, pp. 1–12.
68:nondeterministic Turing machine
1344:
1336:
1061:
1053:
797:. This can be specialized to
659:
646:
619:
606:
472:
1:
1519:Immerman–Szelepcsényi theorem
117:is the size of the input and
1645:Pullum, Geoffrey K. (1983).
1407:{\displaystyle L_{PRIMES2}}
270:by applying the respective
18:Context-sensitive languages
2281:
2125:Deterministic context-free
2050:Deterministic context-free
452:{\displaystyle B^{n}d^{n}}
415:{\displaystyle a^{m}C^{m}}
40:context-sensitive language
26:
2236:
2198:Nondeterministic pushdown
1926:
1693:. Cambridge MA: Bradford.
1612:Odifreddi, P. G. (1999),
44:context-sensitive grammar
1539:Linear bounded automaton
72:linear bounded automaton
62:Computational properties
29:Context-dependent memory
1824:Immerman, Neil (1988).
1783:10.1016/C2013-0-02221-9
1777:, Pergamon, 276 pages.
46:(and equivalently by a
2203:Deterministic pushdown
2079:Recursively enumerable
1765:Salomaa, Arto (1969),
1471:
1408:
1362:
1296:
1227:
1160:
1093:
1010:
938:
866:
791:
702:
673:
630:
589:
485:
453:
416:
379:
234:
131:
111:
91:
48:noncontracting grammar
36:formal language theory
1735:10.1145/321466.321470
1493:with exponentiation.
1472:
1409:
1363:
1297:
1228:
1161:
1094:
1011:
939:
867:
792:
703:
674:
631:
590:
486:
454:
417:
380:
235:
132:
112:
92:
58:of formal languages.
2188:Tree stack automaton
1877:, PWS Publishing Co.
1579:Rothe, Jörg (2005),
1460: is prime
1420:
1373:
1351: is prime
1308:
1239:
1170:
1103:
1022:
948:
876:
801:
712:
683:
640:
600:
497:
463:
426:
389:
287:
173:
121:
101:
78:
2096:range concatenation
2021:range concatenation
1873:Sipser, M. (1996),
1491:regular expressions
872:and, from this, to
1802:. Addison-Wesley.
1767:Theory of Automata
1722:Journal of the ACM
1672:2014-01-21 at the
1483:recursive language
1467:
1462:
1404:
1358:
1353:
1292:
1223:
1156:
1089:
1006:
934:
862:
787:
698:
669:
626:
585:
481:
449:
412:
375:
230:
127:
107:
90:{\displaystyle kn}
87:
2252:
2251:
2231:
2230:
2193:Embedded pushdown
2089:Context-sensitive
2014:Context-sensitive
1948:Abstract machines
1933:Chomsky hierarchy
1775:978-0-08-013376-8
1665:Bach, E. (1981).
1623:978-0-444-50205-6
1590:978-3-540-22147-0
1554:Indexed languages
1549:Chomsky hierarchy
1461:
1431:
1352:
1319:
1250:
1181:
1114:
812:
723:
694:
298:
130:{\displaystyle k}
110:{\displaystyle n}
56:Chomsky hierarchy
16:(Redirected from
2272:
2265:Formal languages
2247:
2244:
2208:Visibly pushdown
2182:Thread automaton
2130:Visibly pushdown
2098:
2055:Visibly pushdown
2023:
2010:(no common name)
1929:
1916:formal languages
1905:
1898:
1891:
1882:
1866:
1865:
1863:
1848:
1830:
1821:
1815:
1813:
1801:
1791:
1785:
1763:
1757:
1756:
1746:
1718:
1709:
1703:
1700:
1694:
1687:
1681:
1663:
1657:
1656:
1642:
1636:
1634:
1609:
1603:
1601:
1576:
1476:
1474:
1473:
1468:
1463:
1459:
1450:
1449:
1434:
1433:
1432:
1413:
1411:
1410:
1405:
1403:
1402:
1367:
1365:
1364:
1359:
1354:
1350:
1347:
1339:
1322:
1321:
1320:
1301:
1299:
1298:
1293:
1276:
1275:
1274:
1273:
1253:
1252:
1251:
1232:
1230:
1229:
1224:
1219:
1218:
1200:
1199:
1184:
1183:
1182:
1165:
1163:
1162:
1157:
1152:
1151:
1133:
1132:
1117:
1116:
1115:
1098:
1096:
1095:
1090:
1085:
1084:
1066:
1065:
1064:
1056:
1040:
1039:
1015:
1013:
1012:
1007:
990:
989:
988:
987:
967:
966:
965:
964:
943:
941:
940:
935:
918:
917:
916:
915:
895:
894:
893:
892:
871:
869:
868:
863:
834:
833:
815:
814:
813:
796:
794:
793:
788:
765:
764:
752:
751:
742:
741:
726:
725:
724:
707:
705:
704:
699:
697:
696:
695:
678:
676:
675:
670:
662:
635:
633:
632:
627:
622:
594:
592:
591:
586:
557:
556:
544:
543:
534:
533:
518:
517:
490:
488:
487:
482:
458:
456:
455:
450:
448:
447:
438:
437:
421:
419:
418:
413:
411:
410:
401:
400:
384:
382:
381:
376:
347:
346:
337:
336:
327:
326:
317:
316:
301:
300:
299:
277:
261:
257:
251:
247:
243:
239:
237:
236:
231:
214:
213:
204:
203:
194:
193:
136:
134:
133:
128:
116:
114:
113:
108:
96:
94:
93:
88:
70:, also called a
21:
2280:
2279:
2275:
2274:
2273:
2271:
2270:
2269:
2255:
2254:
2253:
2248:
2245:
2238:
2232:
2227:
2149:
2093:
2072:
2018:
1999:
1922:
1920:formal grammars
1912:Automata theory
1909:
1870:
1869:
1861:
1855:10.1137/0217058
1828:
1823:
1822:
1818:
1810:
1793:
1792:
1788:
1764:
1760:
1716:
1711:
1710:
1706:
1701:
1697:
1688:
1684:
1674:Wayback Machine
1664:
1660:
1644:
1643:
1639:
1624:
1611:
1610:
1606:
1591:
1578:
1577:
1573:
1568:
1535:
1526:PSPACE-complete
1499:
1441:
1423:
1418:
1417:
1376:
1371:
1370:
1311:
1306:
1305:
1265:
1260:
1242:
1237:
1236:
1210:
1191:
1173:
1168:
1167:
1143:
1124:
1106:
1101:
1100:
1076:
1047:
1025:
1020:
1019:
979:
974:
956:
951:
946:
945:
907:
902:
884:
879:
874:
873:
822:
804:
799:
798:
753:
743:
733:
715:
710:
709:
686:
681:
680:
638:
637:
598:
597:
545:
535:
525:
500:
495:
494:
461:
460:
439:
429:
424:
423:
402:
392:
387:
386:
338:
328:
318:
308:
290:
285:
284:
275:
259:
255:
249:
245:
241:
205:
195:
185:
171:
170:
167:
119:
118:
99:
98:
76:
75:
64:
32:
23:
22:
15:
12:
11:
5:
2278:
2276:
2268:
2267:
2257:
2256:
2250:
2249:
2237:
2234:
2233:
2229:
2228:
2226:
2225:
2223:Acyclic finite
2220:
2215:
2210:
2205:
2200:
2195:
2190:
2184:
2179:
2174:
2173:Turing Machine
2168:
2166:Linear-bounded
2163:
2158:
2156:Turing machine
2152:
2150:
2148:
2147:
2142:
2137:
2132:
2127:
2122:
2117:
2115:Tree-adjoining
2112:
2107:
2104:
2099:
2091:
2086:
2081:
2075:
2073:
2071:
2070:
2065:
2062:
2057:
2052:
2047:
2042:
2040:Tree-adjoining
2037:
2032:
2029:
2024:
2016:
2011:
2008:
2002:
2000:
1998:
1997:
1994:
1991:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1954:
1951:
1950:
1945:
1940:
1935:
1927:
1924:
1923:
1910:
1908:
1907:
1900:
1893:
1885:
1879:
1878:
1868:
1867:
1846:10.1.1.54.5941
1839:(5): 935–938.
1833:SIAM J. Comput
1816:
1808:
1786:
1758:
1729:(3): 382–389.
1704:
1695:
1682:
1658:
1637:
1622:
1604:
1589:
1570:
1569:
1567:
1564:
1563:
1562:
1560:Weir hierarchy
1557:
1551:
1546:
1541:
1534:
1531:
1530:
1529:
1522:
1515:
1498:
1495:
1481:An example of
1466:
1456:
1453:
1448:
1444:
1440:
1437:
1426:
1401:
1398:
1395:
1392:
1389:
1386:
1383:
1379:
1357:
1346:
1342:
1338:
1334:
1331:
1328:
1325:
1314:
1291:
1288:
1285:
1282:
1279:
1272:
1268:
1263:
1259:
1256:
1245:
1222:
1217:
1213:
1209:
1206:
1203:
1198:
1194:
1190:
1187:
1176:
1155:
1150:
1146:
1142:
1139:
1136:
1131:
1127:
1123:
1120:
1109:
1088:
1083:
1079:
1075:
1072:
1069:
1063:
1059:
1055:
1050:
1046:
1043:
1038:
1035:
1032:
1028:
1005:
1002:
999:
996:
993:
986:
982:
977:
973:
970:
963:
959:
954:
933:
930:
927:
924:
921:
914:
910:
905:
901:
898:
891:
887:
882:
861:
858:
855:
852:
849:
846:
843:
840:
837:
832:
829:
825:
821:
818:
807:
786:
783:
780:
777:
774:
771:
768:
763:
760:
756:
750:
746:
740:
736:
732:
729:
718:
689:
668:
665:
661:
657:
654:
651:
648:
645:
625:
621:
617:
614:
611:
608:
605:
584:
581:
578:
575:
572:
569:
566:
563:
560:
555:
552:
548:
542:
538:
532:
528:
524:
521:
516:
513:
510:
507:
503:
480:
477:
474:
471:
468:
446:
442:
436:
432:
409:
405:
399:
395:
374:
371:
368:
365:
362:
359:
356:
353:
350:
345:
341:
335:
331:
325:
321:
315:
311:
307:
304:
293:
272:pumping lemmas
229:
226:
223:
220:
217:
212:
208:
202:
198:
192:
188:
184:
181:
178:
166:
163:
126:
106:
86:
83:
63:
60:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2277:
2266:
2263:
2262:
2260:
2242:
2241:proper subset
2235:
2224:
2221:
2219:
2216:
2214:
2211:
2209:
2206:
2204:
2201:
2199:
2196:
2194:
2191:
2189:
2185:
2183:
2180:
2178:
2175:
2172:
2169:
2167:
2164:
2162:
2159:
2157:
2154:
2153:
2151:
2146:
2143:
2141:
2138:
2136:
2133:
2131:
2128:
2126:
2123:
2121:
2118:
2116:
2113:
2111:
2108:
2105:
2103:
2100:
2097:
2092:
2090:
2087:
2085:
2082:
2080:
2077:
2076:
2074:
2069:
2068:Non-recursive
2066:
2063:
2061:
2058:
2056:
2053:
2051:
2048:
2046:
2043:
2041:
2038:
2036:
2033:
2030:
2028:
2025:
2022:
2017:
2015:
2012:
2009:
2007:
2004:
2003:
2001:
1995:
1992:
1989:
1986:
1983:
1980:
1977:
1974:
1971:
1968:
1965:
1962:
1959:
1956:
1955:
1953:
1952:
1949:
1946:
1944:
1941:
1939:
1936:
1934:
1931:
1930:
1925:
1921:
1917:
1913:
1906:
1901:
1899:
1894:
1892:
1887:
1886:
1883:
1876:
1872:
1871:
1860:
1856:
1852:
1847:
1842:
1838:
1834:
1827:
1820:
1817:
1811:
1809:9780201029888
1805:
1800:
1799:
1790:
1787:
1784:
1780:
1776:
1772:
1768:
1762:
1759:
1754:
1750:
1745:
1740:
1736:
1732:
1728:
1724:
1723:
1715:
1708:
1705:
1699:
1696:
1692:
1686:
1683:
1679:
1675:
1671:
1668:
1662:
1659:
1654:
1650:
1649:
1641:
1638:
1633:
1629:
1625:
1619:
1615:
1608:
1605:
1600:
1596:
1592:
1586:
1582:
1575:
1572:
1565:
1561:
1558:
1555:
1552:
1550:
1547:
1545:
1542:
1540:
1537:
1536:
1532:
1527:
1523:
1520:
1516:
1513:
1509:
1505:
1501:
1500:
1496:
1494:
1492:
1488:
1484:
1479:
1454:
1451:
1446:
1442:
1435:
1424:
1415:
1399:
1396:
1393:
1390:
1387:
1384:
1381:
1377:
1340:
1332:
1329:
1323:
1312:
1303:
1286:
1283:
1280:
1277:
1270:
1266:
1261:
1254:
1243:
1234:
1215:
1207:
1204:
1201:
1196:
1192:
1185:
1174:
1148:
1140:
1137:
1134:
1129:
1125:
1118:
1107:
1081:
1073:
1070:
1067:
1057:
1048:
1041:
1036:
1033:
1030:
1026:
1017:
1000:
997:
994:
991:
984:
980:
975:
968:
961:
957:
952:
928:
925:
922:
919:
912:
908:
903:
896:
889:
885:
880:
856:
853:
850:
847:
844:
841:
838:
835:
830:
827:
823:
816:
805:
781:
778:
775:
772:
769:
766:
761:
758:
754:
748:
744:
738:
734:
727:
716:
687:
666:
663:
655:
652:
649:
643:
623:
615:
612:
609:
603:
579:
576:
573:
570:
567:
564:
561:
558:
553:
550:
546:
540:
536:
530:
526:
519:
514:
511:
508:
505:
501:
492:
478:
475:
469:
466:
444:
440:
434:
430:
407:
403:
397:
393:
369:
366:
363:
360:
357:
354:
351:
348:
343:
339:
333:
329:
323:
319:
313:
309:
302:
291:
282:
279:
273:
269:
265:
253:
224:
221:
218:
215:
210:
206:
200:
196:
190:
186:
179:
176:
164:
162:
160:
159:deterministic
156:
152:
148:
144:
139:
124:
104:
97:cells, where
84:
81:
73:
69:
61:
59:
57:
53:
49:
45:
41:
37:
30:
19:
2177:Nested stack
2120:Context-free
2088:
2045:Context-free
2006:Unrestricted
1874:
1836:
1832:
1819:
1797:
1789:
1766:
1761:
1726:
1720:
1707:
1698:
1690:
1685:
1677:
1661:
1647:
1640:
1613:
1607:
1580:
1574:
1508:intersection
1480:
1416:
1304:
1235:
1018:
493:
283:
280:
268:context-free
254:
168:
154:
150:
146:
142:
140:
65:
51:
39:
33:
2186:restricted
1512:Kleene plus
281:Similarly:
248:"b"s, then
1566:References
2140:Star-free
2094:Positive
2084:Decidable
2019:Positive
1943:Languages
1841:CiteSeerX
1744:1813/5864
1284:≥
1216:∗
1212:Σ
1208:∈
1149:∗
1145:Σ
1141:∈
1082:∗
1078:Σ
1074:∈
647:→
607:→
577:≥
565:≥
473:→
367:≥
355:≥
222:≥
2259:Category
1938:Grammars
1859:Archived
1753:17998039
1670:Archived
1533:See also
1528:problem.
1487:EXPSPACE
165:Examples
2161:Decider
2135:Regular
2102:Indexed
2060:Regular
2027:Indexed
1632:1718169
1599:2164257
1430:PRIMES1
1318:PRIMES2
1233:, etc.
1016:, etc.
722:ORDMUL3
264:regular
54:in the
2213:Finite
2145:Finite
1990:Type-3
1981:Type-2
1963:Type-1
1957:Type-0
1843:
1806:
1773:
1751:
1630:
1620:
1597:
1587:
1113:Square
52:type-1
2171:PTIME
1862:(PDF)
1829:(PDF)
1749:S2CID
1717:(PDF)
1504:union
297:Cross
1918:and
1804:ISBN
1771:ISBN
1678:NELS
1618:ISBN
1585:ISBN
1502:The
1180:Cube
998:>
926:>
854:>
842:>
811:MUL1
779:<
773:<
693:MUL3
636:and
422:and
266:nor
38:, a
1851:doi
1779:doi
1739:hdl
1731:doi
1653:ACL
1249:EXP
34:In
2261::
1914::
1857:.
1849:.
1837:17
1835:.
1831:.
1769:,
1747:.
1737:.
1727:15
1725:.
1719:.
1676:.
1628:MR
1626:,
1595:MR
1593:,
1506:,
1414:.
1166:,
944:,
278:.
2106:—
2064:—
2031:—
1996:—
1993:—
1987:—
1984:—
1978:—
1975:—
1972:—
1969:—
1966:—
1960:—
1904:e
1897:t
1890:v
1853::
1812:.
1781::
1755:.
1741::
1733::
1655:.
1635:.
1602:.
1521:.
1465:}
1455:p
1452::
1447:p
1443:a
1439:{
1436:=
1425:L
1400:2
1397:S
1394:E
1391:M
1388:I
1385:R
1382:P
1378:L
1356:}
1345:|
1341:w
1337:|
1333::
1330:w
1327:{
1324:=
1313:L
1290:}
1287:1
1281:n
1278::
1271:n
1267:2
1262:a
1258:{
1255:=
1244:L
1221:}
1205:w
1202::
1197:3
1193:w
1189:{
1186:=
1175:L
1154:}
1138:w
1135::
1130:2
1126:w
1122:{
1119:=
1108:L
1087:}
1071:w
1068::
1062:|
1058:w
1054:|
1049:w
1045:{
1042:=
1037:P
1034:E
1031:R
1027:L
1004:}
1001:1
995:m
992::
985:3
981:m
976:a
972:{
969:=
962:3
958:m
953:L
932:}
929:1
923:m
920::
913:2
909:m
904:a
900:{
897:=
890:2
886:m
881:L
860:}
857:1
851:n
848:,
845:1
839:m
836::
831:n
828:m
824:a
820:{
817:=
806:L
785:}
782:n
776:m
770:1
767::
762:n
759:m
755:c
749:n
745:b
739:m
735:a
731:{
728:=
717:L
688:L
667:c
664:b
660:|
656:c
653:R
650:b
644:R
624:R
620:|
616:c
613:S
610:a
604:S
583:}
580:1
574:n
571:,
568:1
562:m
559::
554:n
551:m
547:c
541:n
537:b
531:m
527:a
523:{
520:=
515:3
512:L
509:U
506:M
502:L
479:C
476:B
470:B
467:C
445:n
441:d
435:n
431:B
408:m
404:C
398:m
394:a
373:}
370:1
364:n
361:,
358:1
352:m
349::
344:n
340:d
334:m
330:c
324:n
320:b
314:m
310:a
306:{
303:=
292:L
276:L
260:L
256:L
250:n
246:n
242:n
228:}
225:1
219:n
216::
211:n
207:c
201:n
197:b
191:n
187:a
183:{
180:=
177:L
155:n
153:(
151:O
147:n
145:(
143:O
125:k
105:n
85:n
82:k
31:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.