1460:
The non-emptiness problem (is the language of an input AFA non-empty?), the universality problem (is the complement of the language of an input AFA empty?), and the equivalence problem (do two input AFAs recognize the same language) are
806:
479:
420:
1102:
621:
894:
239:
112:
1027:
959:
1139:
843:
1188:
513:
729:
701:
541:
1278:
666:
985:
1356:
1305:
299:
270:
170:
143:
1447:
1427:
1407:
1384:
1325:
1244:
914:
644:
736:
1615:
1223:, they are different from other types of finite automata in the succinctness of description, measured by the number of their states.
1328:
177:
29:
337:
1565:
Holzer, Markus; Kutrib, Martin (2011-03-01). "Descriptional and computational complexity of finite automata—A survey".
1607:
551:
425:
354:
34:
1034:
569:
1358:
states by performing a similar kind of powerset construction as used for the transformation of an NFA to a DFA.
1634:
40:
848:
186:
1387:
348:
59:
990:
922:
1111:
815:
1144:
492:
708:
673:
526:
1249:
1611:
1582:
1543:
1508:
1280:
states in the worst case, though a DFA for the reverse language can be constructued with only
651:
1574:
1535:
1526:
Fellah, A.; Jürgensen, H.; Yu, S. (1990). "Constructions for alternating finite automata∗".
1498:
1220:
1214:
1202:
1194:
964:
341:
1334:
1283:
347:
An alternative model which is frequently used is the one where
Boolean combinations are in
277:
248:
148:
121:
1462:
17:
1599:
1454:
1432:
1412:
1392:
1369:
1310:
1229:
899:
629:
547:
1628:
1198:
1453:. This is true even on a singleton alphabet, i.e., when the automaton accepts a
1307:
states. Another construction by Fellah, Jürgensen and Yu. converts an AFA with
546:
Alternating finite automata can be extended to accept trees in the same way as
1539:
1450:
1586:
1578:
1547:
1512:
309:
Note that due to the universal quantification a run is represented by a run
49:
1503:
1486:
801:{\displaystyle \delta \colon Q\times \Sigma \times \{0,1\}^{Q}\to \{0,1\}}
563:
1485:
Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981).
118:
nondeterministically chooses to switch the state to either
1559:
1557:
336:
A basic theorem states that any AFA is equivalent to a
1435:
1415:
1395:
1372:
1337:
1313:
1286:
1252:
1232:
1147:
1114:
1037:
993:
967:
925:
902:
851:
818:
739:
711:
676:
654:
632:
572:
529:
495:
428:
357:
280:
251:
189:
151:
124:
62:
1480:
1478:
1441:
1421:
1401:
1378:
1350:
1319:
1299:
1272:
1238:
1182:
1133:
1096:
1021:
979:
953:
908:
888:
837:
800:
723:
695:
660:
638:
615:
535:
507:
473:
414:
293:
264:
233:
164:
137:
106:
543:. This representation is usually more efficient.
305:, simulating the behavior of a parallel machine.
1528:International Journal of Computer Mathematics
474:{\displaystyle q_{1}\vee (q_{2}\wedge q_{3})}
415:{\displaystyle \{\{q_{1}\},\{q_{2},q_{3}\}\}}
8:
1097:{\displaystyle A_{aw}(q)=\delta (q,a,A_{w})}
883:
871:
795:
783:
771:
758:
502:
496:
409:
406:
380:
374:
361:
358:
616:{\displaystyle (Q,\Sigma ,q_{0},F,\delta )}
562:An alternating finite automaton (AFA) is a
1366:The membership problem asks, given an AFA
1502:
1434:
1414:
1394:
1371:
1342:
1336:
1312:
1291:
1285:
1262:
1257:
1251:
1246:-state AFA to an equivalent DFA requires
1231:
1226:Chandra et al. proved that converting an
1165:
1152:
1146:
1125:
1113:
1085:
1042:
1036:
998:
992:
966:
930:
924:
901:
856:
850:
829:
817:
774:
738:
710:
681:
675:
653:
631:
592:
571:
528:
494:
462:
449:
433:
427:
400:
387:
368:
356:
285:
279:
256:
250:
222:
209:
188:
156:
150:
129:
123:
95:
82:
61:
889:{\displaystyle A_{w}\colon Q\to \{0,1\}}
1474:
1219:Even though AFA can accept exactly the
234:{\displaystyle (q,a,q_{1}\wedge q_{2})}
731:is a set of accepting (final) states;
340:(DFA), hence AFAs accept exactly the
107:{\displaystyle (q,a,q_{1}\vee q_{2})}
7:
845:, we define the acceptance function
32:whose transitions are divided into
1122:
1022:{\displaystyle A_{\epsilon }(q)=0}
954:{\displaystyle A_{\epsilon }(q)=1}
826:
752:
655:
582:
530:
499:
14:
1329:nondeterministic finite automaton
668:is a finite set of input symbols;
333:path ends in an accepting state.
178:nondeterministic finite automaton
30:nondeterministic finite automaton
1134:{\displaystyle w\in \Sigma ^{*}}
838:{\displaystyle w\in \Sigma ^{*}}
176:. Thus, behaving like a regular
1108:The automaton accepts a string
1183:{\displaystyle A_{w}(q_{0})=1}
1171:
1158:
1091:
1066:
1057:
1051:
1010:
1004:
942:
936:
896:by induction on the length of
868:
780:
610:
573:
508:{\displaystyle \{\emptyset \}}
468:
442:
338:deterministic finite automaton
228:
190:
101:
63:
56:For an existential transition
44:transitions. For example, let
1:
1193:This model was introduced by
703:is the initial (start) state;
724:{\displaystyle F\subseteq Q}
22:alternating finite automaton
1567:Information and Computation
808:is the transition function.
183:For a universal transition
1651:
1608:Cambridge University Press
1212:
696:{\displaystyle q_{0}\in Q}
646:is a finite set of states;
536:{\displaystyle \emptyset }
1604:Theories of Computability
1540:10.1080/00207169008803893
1273:{\displaystyle 2^{2^{n}}}
552:alternating tree automata
1579:10.1016/j.ic.2010.11.013
1362:Computational complexity
661:{\displaystyle \Sigma }
349:disjunctive normal form
1443:
1423:
1403:
1380:
1352:
1321:
1301:
1274:
1240:
1184:
1135:
1098:
1023:
981:
980:{\displaystyle q\in F}
955:
910:
890:
839:
802:
725:
697:
662:
640:
617:
537:
509:
475:
416:
295:
266:
235:
166:
139:
108:
1504:10.1145/322234.322243
1444:
1424:
1404:
1381:
1353:
1351:{\displaystyle 2^{n}}
1322:
1302:
1300:{\displaystyle 2^{n}}
1275:
1241:
1185:
1136:
1099:
1024:
982:
956:
911:
891:
840:
803:
726:
698:
663:
641:
618:
538:
510:
476:
417:
296:
294:{\displaystyle q_{2}}
267:
265:{\displaystyle q_{1}}
236:
167:
165:{\displaystyle q_{2}}
140:
138:{\displaystyle q_{1}}
109:
1433:
1413:
1393:
1370:
1335:
1311:
1284:
1250:
1230:
1145:
1112:
1035:
991:
965:
923:
900:
849:
816:
737:
709:
674:
652:
630:
570:
527:
493:
489:) is represented by
426:
355:
278:
249:
187:
149:
122:
60:
1600:Pippenger, Nicholas
1491:Journal of the ACM
1449:. This problem is
1439:
1419:
1399:
1376:
1348:
1317:
1297:
1270:
1236:
1180:
1131:
1094:
1019:
977:
951:
906:
886:
835:
798:
721:
693:
658:
636:
613:
533:
505:
471:
412:
291:
262:
231:
162:
135:
104:
48:be an alternating
1617:978-0-521-55380-3
1442:{\displaystyle w}
1422:{\displaystyle A}
1402:{\displaystyle w}
1379:{\displaystyle A}
1331:(NFA) with up to
1320:{\displaystyle n}
1239:{\displaystyle n}
1221:regular languages
909:{\displaystyle w}
639:{\displaystyle Q}
558:Formal definition
515:in this case and
342:regular languages
1642:
1621:
1591:
1590:
1561:
1552:
1551:
1534:(1–4): 117–132.
1523:
1517:
1516:
1506:
1482:
1448:
1446:
1445:
1440:
1428:
1426:
1425:
1420:
1408:
1406:
1405:
1400:
1385:
1383:
1382:
1377:
1357:
1355:
1354:
1349:
1347:
1346:
1326:
1324:
1323:
1318:
1306:
1304:
1303:
1298:
1296:
1295:
1279:
1277:
1276:
1271:
1269:
1268:
1267:
1266:
1245:
1243:
1242:
1237:
1215:State complexity
1209:State complexity
1189:
1187:
1186:
1181:
1170:
1169:
1157:
1156:
1140:
1138:
1137:
1132:
1130:
1129:
1103:
1101:
1100:
1095:
1090:
1089:
1050:
1049:
1028:
1026:
1025:
1020:
1003:
1002:
986:
984:
983:
978:
960:
958:
957:
952:
935:
934:
915:
913:
912:
907:
895:
893:
892:
887:
861:
860:
844:
842:
841:
836:
834:
833:
812:For each string
807:
805:
804:
799:
779:
778:
730:
728:
727:
722:
702:
700:
699:
694:
686:
685:
667:
665:
664:
659:
645:
643:
642:
637:
622:
620:
619:
614:
597:
596:
542:
540:
539:
534:
514:
512:
511:
506:
480:
478:
477:
472:
467:
466:
454:
453:
438:
437:
422:would represent
421:
419:
418:
413:
405:
404:
392:
391:
373:
372:
300:
298:
297:
292:
290:
289:
271:
269:
268:
263:
261:
260:
240:
238:
237:
232:
227:
226:
214:
213:
171:
169:
168:
163:
161:
160:
144:
142:
141:
136:
134:
133:
113:
111:
110:
105:
100:
99:
87:
86:
1650:
1649:
1645:
1644:
1643:
1641:
1640:
1639:
1635:Finite automata
1625:
1624:
1618:
1598:
1595:
1594:
1564:
1562:
1555:
1525:
1524:
1520:
1484:
1483:
1476:
1471:
1463:PSPACE-complete
1431:
1430:
1411:
1410:
1391:
1390:
1368:
1367:
1364:
1338:
1333:
1332:
1309:
1308:
1287:
1282:
1281:
1258:
1253:
1248:
1247:
1228:
1227:
1217:
1211:
1161:
1148:
1143:
1142:
1141:if and only if
1121:
1110:
1109:
1081:
1038:
1033:
1032:
994:
989:
988:
963:
962:
926:
921:
920:
898:
897:
852:
847:
846:
825:
814:
813:
770:
735:
734:
707:
706:
677:
672:
671:
650:
649:
628:
627:
588:
568:
567:
560:
525:
524:
491:
490:
458:
445:
429:
424:
423:
396:
383:
364:
353:
352:
351:so that, e.g.,
317:accepts a word
281:
276:
275:
252:
247:
246:
218:
205:
185:
184:
152:
147:
146:
125:
120:
119:
91:
78:
58:
57:
18:automata theory
12:
11:
5:
1648:
1646:
1638:
1637:
1627:
1626:
1623:
1622:
1616:
1593:
1592:
1573:(3): 456–470.
1563:Theorem 19 of
1553:
1518:
1497:(1): 114–133.
1473:
1472:
1470:
1467:
1455:unary language
1438:
1418:
1398:
1375:
1363:
1360:
1345:
1341:
1316:
1294:
1290:
1265:
1261:
1256:
1235:
1213:Main article:
1210:
1207:
1179:
1176:
1173:
1168:
1164:
1160:
1155:
1151:
1128:
1124:
1120:
1117:
1106:
1105:
1093:
1088:
1084:
1080:
1077:
1074:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1048:
1045:
1041:
1030:
1018:
1015:
1012:
1009:
1006:
1001:
997:
976:
973:
970:
950:
947:
944:
941:
938:
933:
929:
905:
885:
882:
879:
876:
873:
870:
867:
864:
859:
855:
832:
828:
824:
821:
810:
809:
797:
794:
791:
788:
785:
782:
777:
773:
769:
766:
763:
760:
757:
754:
751:
748:
745:
742:
732:
720:
717:
714:
704:
692:
689:
684:
680:
669:
657:
647:
635:
612:
609:
606:
603:
600:
595:
591:
587:
584:
581:
578:
575:
559:
556:
532:
504:
501:
498:
470:
465:
461:
457:
452:
448:
444:
441:
436:
432:
411:
408:
403:
399:
395:
390:
386:
382:
379:
376:
371:
367:
363:
360:
325:a run tree on
307:
306:
288:
284:
259:
255:
230:
225:
221:
217:
212:
208:
204:
201:
198:
195:
192:
181:
159:
155:
132:
128:
103:
98:
94:
90:
85:
81:
77:
74:
71:
68:
65:
13:
10:
9:
6:
4:
3:
2:
1647:
1636:
1633:
1632:
1630:
1619:
1613:
1609:
1605:
1601:
1597:
1596:
1588:
1584:
1580:
1576:
1572:
1568:
1560:
1558:
1554:
1549:
1545:
1541:
1537:
1533:
1529:
1522:
1519:
1514:
1510:
1505:
1500:
1496:
1492:
1488:
1487:"Alternation"
1481:
1479:
1475:
1468:
1466:
1464:
1458:
1456:
1452:
1436:
1416:
1396:
1389:
1373:
1361:
1359:
1343:
1339:
1330:
1314:
1292:
1288:
1263:
1259:
1254:
1233:
1224:
1222:
1216:
1208:
1206:
1204:
1200:
1196:
1191:
1177:
1174:
1166:
1162:
1153:
1149:
1126:
1118:
1115:
1086:
1082:
1078:
1075:
1072:
1069:
1063:
1060:
1054:
1046:
1043:
1039:
1031:
1016:
1013:
1007:
999:
995:
974:
971:
968:
948:
945:
939:
931:
927:
919:
918:
917:
903:
880:
877:
874:
865:
862:
857:
853:
830:
822:
819:
792:
789:
786:
775:
767:
764:
761:
755:
749:
746:
743:
740:
733:
718:
715:
712:
705:
690:
687:
682:
678:
670:
648:
633:
626:
625:
624:
607:
604:
601:
598:
593:
589:
585:
579:
576:
565:
557:
555:
553:
549:
548:tree automata
544:
522:
518:
488:
484:
463:
459:
455:
450:
446:
439:
434:
430:
401:
397:
393:
388:
384:
377:
369:
365:
350:
345:
343:
339:
334:
332:
328:
324:
320:
316:
312:
304:
286:
282:
274:
257:
253:
244:
223:
219:
215:
210:
206:
202:
199:
196:
193:
182:
179:
175:
157:
153:
130:
126:
117:
96:
92:
88:
83:
79:
75:
72:
69:
66:
55:
54:
53:
51:
47:
43:
42:
37:
36:
31:
27:
23:
19:
1603:
1570:
1566:
1531:
1527:
1521:
1494:
1490:
1459:
1365:
1327:states to a
1225:
1218:
1192:
1107:
811:
561:
545:
520:
516:
486:
482:
481:. The state
346:
335:
330:
326:
322:
318:
314:
310:
308:
302:
272:
242:
173:
115:
45:
39:
33:
25:
21:
15:
550:, yielding
321:, if there
35:existential
1469:References
1465:for AFAs.
1451:P-complete
1409:, whether
1203:Stockmeyer
1029:otherwise;
329:such that
301:, reading
172:, reading
1587:0890-5401
1548:0020-7160
1513:0004-5411
1127:∗
1123:Σ
1119:∈
1064:δ
1000:ϵ
972:∈
932:ϵ
869:→
863::
831:∗
827:Σ
823:∈
781:→
756:×
753:Σ
750:×
744::
741:δ
716:⊆
688:∈
656:Σ
608:δ
583:Σ
531:∅
500:∅
456:∧
440:∨
245:moves to
216:∧
89:∨
50:automaton
41:universal
1629:Category
1602:(1997).
1429:accepts
623:, where
1195:Chandra
564:5-tuple
28:) is a
1614:
1585:
1546:
1511:
1386:and a
987:, and
323:exists
1199:Kozen
523:) by
521:false
331:every
20:, an
1612:ISBN
1583:ISSN
1544:ISSN
1509:ISSN
1388:word
1201:and
487:true
311:tree
38:and
1575:doi
1571:209
1536:doi
1499:doi
961:if
273:and
145:or
26:AFA
16:In
1631::
1610:.
1606:.
1581:.
1569:.
1556:^
1542:.
1532:35
1530:.
1507:.
1495:28
1493:.
1489:.
1477:^
1457:.
1205:.
1197:,
1190:.
916::
566:,
554:.
517:ff
483:tt
344:.
313:.
241:,
114:,
52:.
1620:.
1589:.
1577::
1550:.
1538::
1515:.
1501::
1437:w
1417:A
1397:w
1374:A
1344:n
1340:2
1315:n
1293:n
1289:2
1264:n
1260:2
1255:2
1234:n
1178:1
1175:=
1172:)
1167:0
1163:q
1159:(
1154:w
1150:A
1116:w
1104:.
1092:)
1087:w
1083:A
1079:,
1076:a
1073:,
1070:q
1067:(
1061:=
1058:)
1055:q
1052:(
1047:w
1044:a
1040:A
1017:0
1014:=
1011:)
1008:q
1005:(
996:A
975:F
969:q
949:1
946:=
943:)
940:q
937:(
928:A
904:w
884:}
881:1
878:,
875:0
872:{
866:Q
858:w
854:A
820:w
796:}
793:1
790:,
787:0
784:{
776:Q
772:}
768:1
765:,
762:0
759:{
747:Q
719:Q
713:F
691:Q
683:0
679:q
634:Q
611:)
605:,
602:F
599:,
594:0
590:q
586:,
580:,
577:Q
574:(
519:(
503:}
497:{
485:(
469:)
464:3
460:q
451:2
447:q
443:(
435:1
431:q
410:}
407:}
402:3
398:q
394:,
389:2
385:q
381:{
378:,
375:}
370:1
366:q
362:{
359:{
327:w
319:w
315:A
303:a
287:2
283:q
258:1
254:q
243:A
229:)
224:2
220:q
211:1
207:q
203:,
200:a
197:,
194:q
191:(
180:.
174:a
158:2
154:q
131:1
127:q
116:A
102:)
97:2
93:q
84:1
80:q
76:,
73:a
70:,
67:q
64:(
46:A
24:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.