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