820:
1259:
For a one-letter alphabet, Leiss discovered the first language equation with a nonregular solution, using complementation and concatenation operations. Later, Jeż showed that non-regular unary languages can be defined by language equations with union, intersection and concatenation, equivalent to
1246:
who proved that the satisfiability problem for a given equation is undecidable, and that if a system of language equations has a unique solution, then that solution is recursive. Later, Okhotin proved that the unsatisfiability problem is
902:
1090:
538:
273:
600:
967:
806:
464:
27:
rather than numbers. Instead of arithmetic operations in numerical equations, the variables are joined by language operations. Among the most common operations on two languages
155:
339:
306:
1220:
732:
654:
407:
987:
700:
221:
201:
1157:
1185:
1125:
674:
359:
175:
617:
812:
has such corresponding equation using left-concatenation and union, see Fig. 1. If intersection operation is allowed, equations correspond to
1520:
1446:
830:
1628:
Parikh, Rohit; Chandra, Ashok; Halpern, Joe; Meyer, Albert (1985). "Equations between
Regular Terms and an Application to Process Logic".
809:
999:
469:
226:
543:
907:
1163:
and Petre who gave an affirmative answer in a special case. A strongly negative answer to Conway's problem was given by
813:
1264:. By this method Jeż and Okhotin proved that every recursive unary language is a unique solution of some equation.
1843:
1780:
Jeż, Artur; Okhotin, Alexander (2014). "Computational completeness of equations over sets of natural numbers".
737:
1789:
425:
362:
110:
88:, since the languages generated by the grammar must be the solution of a system of language equations.
311:
278:
606:
104:
1794:
1193:
1261:
1160:
705:
627:
1848:
1569:
1334:
1164:
1104:
370:
972:
1807:
1762:
1727:
1686:
1645:
1610:
1561:
1526:
1516:
1485:
1442:
1419:
1378:
1326:
679:
100:
206:
1799:
1754:
1717:
1676:
1637:
1600:
1553:
1508:
1475:
1409:
1368:
1316:
1235:
1093:
824:
180:
96:
47:
24:
1130:
1273:
1243:
1278:
1283:
1239:
1170:
1110:
659:
344:
160:
85:
1480:
1463:
1837:
1722:
1705:
1373:
1356:
58:
1573:
1338:
1231:
1230:
Language equations with concatenation and
Boolean operations were first studied by
1092:
using left-concatenation and union and proved that their satisfiability problem is
993:
624:
where every concatenation is with a singleton constant language on the left, e.g.
1745:
Jeż, Artur (2008). "Conjunctive grammars generate non-regular unary languages".
1248:
1187:
such that the greatest solution of this equation is not recursively enumerable.
77:
1706:"Unrestricted complementation in language equations over a one-letter alphabet"
1681:
1664:
1758:
1605:
1588:
1557:
1357:"On equations for regular languages, finite automata, and sequential networks"
1811:
1803:
1766:
1731:
1690:
1649:
1614:
1565:
1530:
1489:
1423:
1382:
1330:
1512:
36:
1414:
1397:
1321:
1304:
1544:
Kunc, Michal (2007). "The Power of
Commuting with Finite Sets of Words".
1251:
and that every recursive language is a unique solution of some equation.
20:
1828:
819:
69:
1829:
Workshop on Theory and
Applications of Language Equations (TALE 2007)
1507:. Lecture Notes in Computer Science. Vol. 2300. pp. 69–76.
897:{\displaystyle S_{1}=1\cdot S_{1}\cup 0\cdot S_{2}\cup \{\epsilon \}}
605:
Language equations with added intersection analogously correspond to
1641:
1589:"Regular solutions of language inequalities and well quasi-orders"
818:
1107:
proposed the following problem: given a constant finite language
365:
argument to show that a solution always exists, and proved that
1085:{\displaystyle F(X_{1},\ldots ,X_{k})=G(X_{1},\ldots ,X_{k})}
584:
533:{\displaystyle S=(\{a\}\cdot S\cdot \{c\})\cup \{b\}\cup S}
1190:
Kunc also proved that the greatest solution of inequality
268:{\displaystyle X=\alpha _{1}\cup \ldots \cup \alpha _{m}}
84:. Therefore, language equations can be used to represent
1747:
International
Journal of Foundations of Computer Science
595:{\displaystyle \{a^{n}bc^{n}\mid n\in {\mathcal {N}}\}}
1350:
1348:
1196:
1173:
1133:
1113:
1002:
975:
910:
833:
740:
708:
682:
662:
630:
546:
472:
428:
373:
347:
314:
281:
229:
209:
183:
163:
113:
107:
by language equations. To every context-free grammar
1398:"Unification of Concept Terms in Description Logics"
962:{\displaystyle S_{2}=1\cdot S_{2}\cup 0\cdot S_{1}}
157:, is associated a system of equations in variables
1214:
1179:
1151:
1119:
1084:
981:
961:
896:
800:
726:
694:
668:
648:
594:
532:
458:
401:
353:
333:
300:
267:
215:
195:
169:
149:
1505:The Branching Point Approach to Conway's Problem
808:with one variable on the right-hand side. Every
8:
1305:"Two Families of Languages Related to ALGOL"
1159:always regular? This problem was studied by
891:
885:
721:
715:
637:
631:
589:
547:
521:
515:
506:
500:
488:
482:
92:Language equations and context-free grammars
1303:Ginsburg, Seymour; Rice, H. Gordon (1962).
1127:, is the greatest solution of the equation
68:. Finally, as an operation taking a single
1665:"Decision problems for language equations"
1396:Baader, Franz; Narendran, Paliath (2001).
1226:Language equations with Boolean operations
19:are mathematical statements that resemble
1793:
1721:
1680:
1604:
1479:
1413:
1372:
1320:
1195:
1172:
1132:
1112:
1073:
1054:
1032:
1013:
1001:
974:
953:
934:
915:
909:
876:
857:
838:
832:
789:
764:
745:
739:
707:
681:
661:
629:
583:
582:
567:
554:
545:
471:
427:
384:
372:
346:
325:
313:
292:
280:
259:
240:
228:
208:
182:
162:
112:
1255:Language equations over a unary alphabet
801:{\displaystyle X_{i}=F(X_{1},...,X_{k})}
540:which has as solution every superset of
1669:Journal of Computer and System Sciences
1295:
1503:Karhumäki, Juhani; Petre, Ion (2002).
1464:"Conway's problem for three-word sets"
1462:Karhumäki, Juhani; Petre, Ion (2002).
613:Language equations and finite automata
23:, but the variables assume values of
7:
1355:Brzozowski, J.A.; Leiss, E. (1980).
827:with associated system of equations
459:{\displaystyle S\to aSc\mid b\mid S}
1439:Regular Algebra and Finite Machines
466:corresponds to the equation system
1167:who constructed a finite language
415:i.e. any other solution must be a
210:
129:
103:gave an alternative definition of
14:
810:nondeterministic finite automaton
150:{\displaystyle G=(V,\Sigma ,R,S)}
996:and Narendran studied equations
334:{\displaystyle X\to \alpha _{m}}
301:{\displaystyle X\to \alpha _{1}}
1402:Journal of Symbolic Computation
734:. Each equation is of the form
223:and is defined by the equation
1215:{\displaystyle LX\subseteq XL}
1079:
1047:
1038:
1006:
795:
757:
509:
479:
432:
396:
390:
318:
285:
144:
120:
1:
1481:10.1016/S0304-3975(01)00389-9
1723:10.1016/0304-3975(94)90227-5
1710:Theoretical Computer Science
1593:Theoretical Computer Science
1468:Theoretical Computer Science
1437:Conway, John Horton (1971).
1374:10.1016/0304-3975(80)90069-9
1361:Theoretical Computer Science
727:{\displaystyle X\cdot \{a\}}
649:{\displaystyle \{a\}\cdot X}
203:is an unknown language over
1782:Information and Computation
1663:Okhotin, Alexander (2010).
1546:Theory of Computing Systems
814:alternating finite automata
361:. Ginsburg and Rice used a
1865:
1682:10.1016/j.jcss.2009.08.002
422:For example, the grammar
402:{\displaystyle X=L_{G}(X)}
1759:10.1142/S012905410800584X
1630:SIAM Journal on Computing
1606:10.1016/j.tcs.2005.09.018
1558:10.1007/s00224-006-1321-z
982:{\displaystyle \epsilon }
1804:10.1016/j.ic.2014.05.001
695:{\displaystyle X\cdot Y}
341:are all productions for
1513:10.1007/3-540-45711-9_5
1099:
622:left language equations
216:{\displaystyle \Sigma }
1415:10.1006/jsco.2000.0426
1216:
1181:
1153:
1121:
1086:
990:
983:
963:
898:
802:
728:
696:
670:
650:
596:
534:
460:
403:
355:
335:
302:
269:
217:
197:
196:{\displaystyle X\in V}
171:
151:
1587:Kunc, Michal (2005).
1322:10.1145/321127.321132
1217:
1182:
1154:
1152:{\displaystyle LX=XL}
1122:
1087:
984:
964:
899:
822:
803:
729:
697:
671:
651:
597:
535:
461:
404:
363:fixed-point iteration
356:
336:
303:
270:
218:
198:
172:
152:
105:context-free grammars
1704:Leiss, E.L. (1994).
1441:. Chapman and Hall.
1262:conjunctive grammars
1194:
1171:
1131:
1111:
1000:
973:
908:
831:
738:
706:
680:
660:
628:
607:conjunctive grammars
544:
470:
426:
371:
345:
312:
279:
227:
207:
181:
161:
111:
1222:is always regular.
21:numerical equations
1309:Journal of the ACM
1212:
1177:
1149:
1117:
1082:
991:
989:is the empty word.
979:
959:
894:
798:
724:
692:
666:
646:
620:and Leiss studied
592:
530:
456:
399:
351:
331:
298:
265:
213:
193:
167:
147:
17:Language equations
1522:978-3-540-43190-9
1448:978-0-486-48583-6
1180:{\displaystyle L}
1120:{\displaystyle L}
669:{\displaystyle X}
354:{\displaystyle X}
170:{\displaystyle V}
1856:
1844:Formal languages
1816:
1815:
1797:
1777:
1771:
1770:
1742:
1736:
1735:
1725:
1701:
1695:
1694:
1684:
1675:(3–4): 251–266.
1660:
1654:
1653:
1625:
1619:
1618:
1608:
1599:(2–3): 277–293.
1584:
1578:
1577:
1541:
1535:
1534:
1500:
1494:
1493:
1483:
1459:
1453:
1452:
1434:
1428:
1427:
1417:
1393:
1387:
1386:
1376:
1352:
1343:
1342:
1324:
1300:
1221:
1219:
1218:
1213:
1186:
1184:
1183:
1178:
1158:
1156:
1155:
1150:
1126:
1124:
1123:
1118:
1100:Conway's problem
1094:EXPTIME-complete
1091:
1089:
1088:
1083:
1078:
1077:
1059:
1058:
1037:
1036:
1018:
1017:
988:
986:
985:
980:
968:
966:
965:
960:
958:
957:
939:
938:
920:
919:
903:
901:
900:
895:
881:
880:
862:
861:
843:
842:
825:finite automaton
807:
805:
804:
799:
794:
793:
769:
768:
750:
749:
733:
731:
730:
725:
701:
699:
698:
693:
675:
673:
672:
667:
655:
653:
652:
647:
601:
599:
598:
593:
588:
587:
572:
571:
559:
558:
539:
537:
536:
531:
465:
463:
462:
457:
418:
414:
408:
406:
405:
400:
389:
388:
360:
358:
357:
352:
340:
338:
337:
332:
330:
329:
307:
305:
304:
299:
297:
296:
274:
272:
271:
266:
264:
263:
245:
244:
222:
220:
219:
214:
202:
200:
199:
194:
177:. Each variable
176:
174:
173:
168:
156:
154:
153:
148:
80:of the language
48:set intersection
25:formal languages
1864:
1863:
1859:
1858:
1857:
1855:
1854:
1853:
1834:
1833:
1825:
1820:
1819:
1795:10.1.1.395.2250
1779:
1778:
1774:
1744:
1743:
1739:
1703:
1702:
1698:
1662:
1661:
1657:
1642:10.1137/0214066
1627:
1626:
1622:
1586:
1585:
1581:
1543:
1542:
1538:
1523:
1502:
1501:
1497:
1461:
1460:
1456:
1449:
1436:
1435:
1431:
1395:
1394:
1390:
1354:
1353:
1346:
1302:
1301:
1297:
1292:
1274:Boolean grammar
1270:
1257:
1228:
1192:
1191:
1169:
1168:
1129:
1128:
1109:
1108:
1102:
1069:
1050:
1028:
1009:
998:
997:
971:
970:
949:
930:
911:
906:
905:
872:
853:
834:
829:
828:
785:
760:
741:
736:
735:
704:
703:
678:
677:
658:
657:
626:
625:
615:
563:
550:
542:
541:
468:
467:
424:
423:
416:
413:to this system,
380:
369:
368:
367:the assignment
366:
343:
342:
321:
310:
309:
288:
277:
276:
255:
236:
225:
224:
205:
204:
179:
178:
159:
158:
109:
108:
94:
86:formal grammars
12:
11:
5:
1862:
1860:
1852:
1851:
1846:
1836:
1835:
1832:
1831:
1824:
1823:External links
1821:
1818:
1817:
1772:
1753:(3): 597–615.
1737:
1716:(1–2): 71–84.
1696:
1655:
1636:(4): 935–942.
1620:
1579:
1552:(4): 521–551.
1536:
1521:
1495:
1474:(1): 705–725.
1454:
1447:
1429:
1408:(3): 277–305.
1388:
1344:
1315:(3): 350–371.
1294:
1293:
1291:
1288:
1287:
1286:
1284:Set constraint
1281:
1276:
1269:
1266:
1256:
1253:
1227:
1224:
1211:
1208:
1205:
1202:
1199:
1176:
1148:
1145:
1142:
1139:
1136:
1116:
1101:
1098:
1081:
1076:
1072:
1068:
1065:
1062:
1057:
1053:
1049:
1046:
1043:
1040:
1035:
1031:
1027:
1024:
1021:
1016:
1012:
1008:
1005:
978:
956:
952:
948:
945:
942:
937:
933:
929:
926:
923:
918:
914:
893:
890:
887:
884:
879:
875:
871:
868:
865:
860:
856:
852:
849:
846:
841:
837:
797:
792:
788:
784:
781:
778:
775:
772:
767:
763:
759:
756:
753:
748:
744:
723:
720:
717:
714:
711:
691:
688:
685:
665:
656:with variable
645:
642:
639:
636:
633:
614:
611:
591:
586:
581:
578:
575:
570:
566:
562:
557:
553:
549:
529:
526:
523:
520:
517:
514:
511:
508:
505:
502:
499:
496:
493:
490:
487:
484:
481:
478:
475:
455:
452:
449:
446:
443:
440:
437:
434:
431:
411:least solution
398:
395:
392:
387:
383:
379:
376:
350:
328:
324:
320:
317:
295:
291:
287:
284:
262:
258:
254:
251:
248:
243:
239:
235:
232:
212:
192:
189:
186:
166:
146:
143:
140:
137:
134:
131:
128:
125:
122:
119:
116:
93:
90:
13:
10:
9:
6:
4:
3:
2:
1861:
1850:
1847:
1845:
1842:
1841:
1839:
1830:
1827:
1826:
1822:
1813:
1809:
1805:
1801:
1796:
1791:
1787:
1783:
1776:
1773:
1768:
1764:
1760:
1756:
1752:
1748:
1741:
1738:
1733:
1729:
1724:
1719:
1715:
1711:
1707:
1700:
1697:
1692:
1688:
1683:
1678:
1674:
1670:
1666:
1659:
1656:
1651:
1647:
1643:
1639:
1635:
1631:
1624:
1621:
1616:
1612:
1607:
1602:
1598:
1594:
1590:
1583:
1580:
1575:
1571:
1567:
1563:
1559:
1555:
1551:
1547:
1540:
1537:
1532:
1528:
1524:
1518:
1514:
1510:
1506:
1499:
1496:
1491:
1487:
1482:
1477:
1473:
1469:
1465:
1458:
1455:
1450:
1444:
1440:
1433:
1430:
1425:
1421:
1416:
1411:
1407:
1403:
1399:
1392:
1389:
1384:
1380:
1375:
1370:
1366:
1362:
1358:
1351:
1349:
1345:
1340:
1336:
1332:
1328:
1323:
1318:
1314:
1310:
1306:
1299:
1296:
1289:
1285:
1282:
1280:
1277:
1275:
1272:
1271:
1267:
1265:
1263:
1254:
1252:
1250:
1245:
1241:
1237:
1233:
1225:
1223:
1209:
1206:
1203:
1200:
1197:
1188:
1174:
1166:
1162:
1146:
1143:
1140:
1137:
1134:
1114:
1106:
1097:
1095:
1074:
1070:
1066:
1063:
1060:
1055:
1051:
1044:
1041:
1033:
1029:
1025:
1022:
1019:
1014:
1010:
1003:
995:
976:
954:
950:
946:
943:
940:
935:
931:
927:
924:
921:
916:
912:
888:
882:
877:
873:
869:
866:
863:
858:
854:
850:
847:
844:
839:
835:
826:
821:
817:
815:
811:
790:
786:
782:
779:
776:
773:
770:
765:
761:
754:
751:
746:
742:
718:
712:
709:
689:
686:
683:
663:
643:
640:
634:
623:
619:
612:
610:
608:
603:
579:
576:
573:
568:
564:
560:
555:
551:
527:
524:
518:
512:
503:
497:
494:
491:
485:
476:
473:
453:
450:
447:
444:
441:
438:
435:
429:
420:
419:of this one.
412:
393:
385:
381:
377:
374:
364:
348:
326:
322:
315:
293:
289:
282:
260:
256:
252:
249:
246:
241:
237:
233:
230:
190:
187:
184:
164:
141:
138:
135:
132:
126:
123:
117:
114:
106:
102:
98:
91:
89:
87:
83:
79:
75:
71:
67:
63:
60:
59:concatenation
56:
52:
49:
45:
41:
38:
34:
30:
26:
22:
18:
1785:
1781:
1775:
1750:
1746:
1740:
1713:
1709:
1699:
1672:
1668:
1658:
1633:
1629:
1623:
1596:
1592:
1582:
1549:
1545:
1539:
1504:
1498:
1471:
1467:
1457:
1438:
1432:
1405:
1401:
1391:
1367:(1): 19–35.
1364:
1360:
1312:
1308:
1298:
1279:Arden's rule
1258:
1229:
1189:
1103:
992:
621:
616:
604:
421:
410:
95:
81:
76:denotes the
73:
65:
61:
54:
50:
43:
39:
32:
28:
16:
15:
1249:RE-complete
78:Kleene star
1838:Categories
1290:References
823:Fig. 1: A
676:, but not
618:Brzozowski
72:, the set
57:, and the
1849:Equations
1812:0890-5401
1790:CiteSeerX
1788:: 56–94.
1767:0129-0541
1732:0304-3975
1691:0022-0000
1650:0097-5397
1615:0304-3975
1566:1432-4350
1531:0302-9743
1490:0304-3975
1424:0747-7171
1383:0304-3975
1331:0004-5411
1204:⊆
1161:Karhumäki
1064:…
1023:…
977:ϵ
947:⋅
941:∪
928:⋅
889:ϵ
883:∪
870:⋅
864:∪
851:⋅
713:⋅
687:⋅
641:⋅
580:∈
574:∣
525:∪
513:∪
498:⋅
492:⋅
451:∣
445:∣
433:→
323:α
319:→
290:α
286:→
257:α
253:∪
250:…
247:∪
238:α
211:Σ
188:∈
130:Σ
37:set union
1574:13406797
1339:16718187
1268:See also
97:Ginsburg
35:are the
1240:Halpern
1236:Chandra
409:is the
308:, ...,
70:operand
1810:
1792:
1765:
1730:
1689:
1648:
1613:
1572:
1564:
1529:
1519:
1488:
1445:
1422:
1381:
1337:
1329:
1232:Parikh
1105:Conway
994:Baader
969:where
417:subset
275:where
46:, the
1570:S2CID
1335:S2CID
1244:Meyer
1808:ISSN
1763:ISSN
1728:ISSN
1687:ISSN
1646:ISSN
1611:ISSN
1562:ISSN
1527:ISSN
1517:ISBN
1486:ISSN
1443:ISBN
1420:ISSN
1379:ISSN
1327:ISSN
1242:and
1165:Kunc
702:nor
101:Rice
99:and
31:and
1800:doi
1786:237
1755:doi
1718:doi
1714:132
1677:doi
1638:doi
1601:doi
1597:348
1554:doi
1509:doi
1476:doi
1472:289
1410:doi
1369:doi
1317:doi
1840::
1806:.
1798:.
1784:.
1761:.
1751:19
1749:.
1726:.
1712:.
1708:.
1685:.
1673:76
1671:.
1667:.
1644:.
1634:14
1632:.
1609:.
1595:.
1591:.
1568:.
1560:.
1550:40
1548:.
1525:.
1515:.
1484:.
1470:.
1466:.
1418:.
1406:31
1404:.
1400:.
1377:.
1365:10
1363:.
1359:.
1347:^
1333:.
1325:.
1311:.
1307:.
1238:,
1234:,
1096:.
904:,
816:.
609:.
602:.
53:∩
42:∪
1814:.
1802::
1769:.
1757::
1734:.
1720::
1693:.
1679::
1652:.
1640::
1617:.
1603::
1576:.
1556::
1533:.
1511::
1492:.
1478::
1451:.
1426:.
1412::
1385:.
1371::
1341:.
1319::
1313:9
1210:L
1207:X
1201:X
1198:L
1175:L
1147:L
1144:X
1141:=
1138:X
1135:L
1115:L
1080:)
1075:k
1071:X
1067:,
1061:,
1056:1
1052:X
1048:(
1045:G
1042:=
1039:)
1034:k
1030:X
1026:,
1020:,
1015:1
1011:X
1007:(
1004:F
955:1
951:S
944:0
936:2
932:S
925:1
922:=
917:2
913:S
892:}
886:{
878:2
874:S
867:0
859:1
855:S
848:1
845:=
840:1
836:S
796:)
791:k
787:X
783:,
780:.
777:.
774:.
771:,
766:1
762:X
758:(
755:F
752:=
747:i
743:X
722:}
719:a
716:{
710:X
690:Y
684:X
664:X
644:X
638:}
635:a
632:{
590:}
585:N
577:n
569:n
565:c
561:b
556:n
552:a
548:{
528:S
522:}
519:b
516:{
510:)
507:}
504:c
501:{
495:S
489:}
486:a
483:{
480:(
477:=
474:S
454:S
448:b
442:c
439:S
436:a
430:S
397:)
394:X
391:(
386:G
382:L
378:=
375:X
349:X
327:m
316:X
294:1
283:X
261:m
242:1
234:=
231:X
191:V
185:X
165:V
145:)
142:S
139:,
136:R
133:,
127:,
124:V
121:(
118:=
115:G
82:A
74:A
66:B
64:⋅
62:A
55:B
51:A
44:B
40:A
33:B
29:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
