2272:
435:
variables denoting subtrees. That is, members of Δ are here rewrite rules from nodes whose roots are states to nodes whose children's roots are states. A top-down automaton starts in some of its initial states at the root and moves downward along branches of the tree, associating along a run a state
53:
or not. According to how the automaton processes the input tree, finite tree automata can be of two types: (a) bottom up, (b) top down. This is an important issue, as although non-deterministic (ND) top-down and ND bottom-up tree automata are equivalent in expressive power, deterministic top-down
462:
top-down tree automata are less powerful than their bottom-up counterparts, because in a deterministic tree automaton no two transition rules have the same left-hand side. For tree automata, transition rules are rewrite rules; and for top-down ones, the left-hand side will be parent nodes.
463:
Consequently, a deterministic top-down tree automaton will only be able to test for tree properties that are true in all branches, because the choice of the state to write into each child branch is determined at the parent node, without knowing the child branches contents.
54:
automata are strictly less powerful than their deterministic bottom-up counterparts, because tree properties specified by deterministic top-down tree automata can only depend on path properties. (Deterministic bottom-up tree automata are as powerful as ND tree automata.)
2286:
Using the same colorization as above, this example shows how tree automata generalize ordinary string automata. The finite deterministic string automaton shown in the picture accepts all strings of binary digits that denote a multiple of 3. Using the notions from
2404:)))" in the tree automaton setting; this way, strings can be generalized to trees, or terms. The top-down finite tree automaton accepting the set of all terms corresponding to multiples of 3 in binary string notation is then defined by:
3711:
is a tree with one hole (or, correspondingly, a term with one occurrence of one variable). A context is called "trivial" if the tree consists only of the hole node (or, correspondingly, if the term is just the variable). The notation
222:
variables denoting subtrees. That is, members of Δ are rewrite rules from nodes whose childs' roots are states, to nodes whose roots are states. Thus the state of a node is deduced from the states of its children.
455:). Non-deterministic top-down tree automata have the same expressive power as non-deterministic bottom-up ones; the transition rules are simply reversed, and the final states become the initial states.
3955:
3603:
Proceedings of the 35th Annual
Meeting of the Association for Computational Linguistics and Eighth Conference of the European Chapter of the Association for Computational Linguistics
258:). Since these transition rules for constant symbols (leaves) do not require a state, no explicitly defined initial states are needed. A bottom-up tree automaton is run on a
4275:
3948:
532:
having arity 2 and all other symbols having arity 0, a bottom-up tree automaton accepting the set of all finite lists of boolean values can be defined as (
739:
In this example, the rules can be understood intuitively as assigning to each term its type in a bottom-up manner; e.g. rule (4) can be read as "A term
3587:
but they are used there (sect. 1.6, proposition 1.6.2, p. 38). They accept the class of path-closed tree languages (sect. 1.8, exercise 1.6, p. 43-44).
3825:
Comon, Hubert; Dauchet, Max; Gilleron, Rémi; Jacquemard, Florent; Lugiez, Denis; Löding, Christof; Tison, Sophie; Tommasi, Marc (November 2008).
4162:
3941:
4332:
3852:
4087:
4177:
4102:
4317:
4270:
4255:
4322:
4131:
2288:
2275:
1348:
119:
4148:
4073:
3627:, sect. 1.4, theorem 1.4.3, p. 31-32) of tree homomorphism is more general than that of the article "tree homomorphism".
3102:
can be vertically tripartited such that arbitrary repetition ("pumping") of the middle part keeps the resulting term in
4245:
4141:
474:
3453:
4327:
4066:
3511:
3109:
For the language of all finite lists of boolean values from the above example, all terms beyond the height limit
36:
4218:
4213:
3300:
The class of recognizable tree languages is closed under union, under complementation, and under intersection.
4299:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
3516:
3501:
466:
50:
4229:
4167:
4092:
3491:
17:
3058:
if there is at least one transition rule available for every possible symbol-states combination. A state
1142:
Cf. the derivation of the same term from a regular tree grammar corresponding to the automaton, shown at
4172:
4120:
3933:
3505:
43:
4265:
4240:
4097:
4058:
3313:
2956:
1376:
1143:
477:
theory with two successors. Finite tree automata (nondeterministic if top-down) suffice for WS2S.
4250:
4192:
4136:
3927:
3878:
3863:
436:
with each subterm inductively. A tree is accepted if every branch can be gone through this way.
3985:
3848:
2271:
470:
270:
with each subterm. The term is accepted if its root is associated to an accepting state from
266:, starting at all its leaves simultaneously and moving upwards, associating a run state from
4234:
4187:
4154:
4000:
3606:
3497:
4197:
4112:
4079:
3995:
3968:
3964:
3725:
2952:
1333:
96:
3921:
4208:
3990:
3972:
32:
4311:
4293:
469:
extend top-down automata to infinite trees, and can be used to prove decidability of
28:
3650:
3494:- an application of tree automata to prove an algorithmic meta-theorem about graphs
2368:
In the tree automaton setting, the input alphabet is changed such that the symbols
3046:
A linear (that is, arity-preserving) tree homomorphism preserves recognizability.
3903:
4260:
4182:
4107:
259:
3930:- a library for efficient manipulation of non-deterministic tree automata (C++)
3598:
2959:, respectively, each accepting the same language as its automaton counterpart.
3909:
447:) if no two rules from Δ have the same left hand side; otherwise it is called
42:
The following article deals with branching tree automata, which correspond to
3826:
3605:. ACL '98/EACL '98. USA: Association for Computational Linguistics: 468–475.
3456:
for tree automata states that the following three statements are equivalent:
2976:(that is, a tree) is accepted if there exists a reduction that starts from
3610:
3912:- tools for reachability analysis and tree automata calculations (OCaml)
3469:
is the union of some equivalence classes of a congruence of finite index
3405:. It is of finite index if its number of equivalence-classes is finite.
49:
As with classical automata, finite tree automata (FTA) can be either a
3583:
In a strict sense, deterministic top-down automata are not defined by
3883:
3868:
4223:
2270:
100:
3915:
2951:
For comparison purposes, the table gives in column (A) and (D) a
3918:- library for working with finite tree and hedge automata (Java)
309:, Δ), with two differences with bottom-up tree automata. First,
3937:
3113:=2 can be pumped, since they need to contain an occurrence of
1300:
Top-down automaton accepting multiples of 3 in binary notation
246:()); often the empty parentheses are omitted for convenience:
3877:
Engelfriet, Joost (1975). "Tree
Automata and Tree Grammars".
4292:
Each category of languages, except those marked by a , is a
3308:
A congruence on the set of all trees over a ranked alphabet
2386:" in the string automaton setting corresponds to the term "
2992:
is a final state. For a top-down automaton, a ground term
2497:
the transitions being as shown in column (C) of the table.
2364:
the transitions being as shown in column (B) of the table.
3862:
Gécseg, Ferenc; Steinby, Magnus (1984). "Tree
Automata".
3845:
Foundations of XML Processing: The Tree-Automata
Approach
2996:
is accepted if there exists a reduction that starts from
2382:
is used for tree leaves. For example, the binary string "
335:; second, its transition rules are oriented conversely:
2519:)))" is accepted by the following tree automaton run:
3906:- ranked and unranked tree automata libraries (OCaml)
2792:))" leads to following non-accepting automaton run:
99:(i.e., an alphabet whose symbols have an associated
3043:if there exists a tree automaton that accepts it.
2289:Deterministic finite automaton#Formal definition
16:For a different notion of tree automaton, see
3949:
3597:Morawietz, Frank; Cornell, Tom (1997-07-07).
3054:A non-deterministic finite tree automaton is
2925:Since there are no other initial states than
791:, respectively". An accepting example run is
490:Employing coloring to distinguish members of
234:, the above transition rule definition reads
8:
3808:
3796:
3784:
3772:
3733:
3636:
3624:
3584:
3571:
3559:
3547:
3535:
3500:- extend tree automata in the same way that
118:is a set of final states, and Δ is a set of
4271:Counter-free (with aperiodic finite monoid)
3035:is the set of all ground terms accepted by
2948:))" is not accepted by the tree automaton.
2278:accepting multiples of 3 in binary notation
486:Bottom-up automaton accepting boolean lists
3981:
3956:
3942:
3934:
2934:to start an automaton run with, the term "
2376:are both unary, and a nullary symbol, say
1278:Intuitively, this corresponds to the term
324:, the set of its initial states, replaces
3882:
3867:
3828:Tree Automata Techniques and Applications
2972:For a bottom-up automaton, a ground term
3736:, p. 17, gives a formal definition.
3599:"Representing constraints with automata"
3070:such that there exists a reduction from
1303:
3716:means the result of inserting the tree
3528:
2276:Deterministic finite (string) automaton
4163:Linear context-free rewriting language
4088:Linear context-free rewriting systems
3922:Machine-checked tree automata library
3094:Every sufficiently large ground term
39:of more conventional state machines.
7:
1270:by (2), no further rule applicable.
230:=0, that is, for a constant symbol
4296:of the category directly above it.
3799:, sect. 1.3, theorem 1.3.1, p. 30.
3574:, sect. 1.6, theorem 1.6.1, p. 38.
3086:if all its states are accessible.
2485:the set of initial states being {
2442:the ranked input alphabet being {
14:
3843:Hosoya, Haruo (4 November 2010).
3412:, a congruence can be defined by
2919:by 3, no further rule applicable
3098:in a recognizable tree language
2953:(right) regular (string) grammar
2352:the set of final states being {
498:, and using the ranked alphabet
3481:is a congruence of finite index
3463:is a recognizable tree language
64:bottom-up finite tree automaton
3847:. Cambridge University Press.
3066:if there exists a ground term
583:and Δ consisting of the rules
286:top-down finite tree automaton
1:
3763:means the result of stacking
3682:Formally: there is a context
3292:all belong to that language.
1144:Regular tree grammar#Examples
4333:Theoretical computer science
1375:
1362:
1347:
1332:
1323:
1318:
1313:
1308:
3039:. A set of ground terms is
2329:the input alphabet being {
1252:
1238:
1230:
1205:
1197:
1189:
1174:
1166:
1158:
1149:A rejecting example run is
1123:
1115:
1107:
1099:
1085:
1067:
1059:
1045:
1031:
1023:
1005:
997:
983:
975:
967:
942:
928:
920:
912:
904:
879:
871:
863:
855:
847:
832:
824:
816:
808:
800:
439:A tree automaton is called
4349:
4178:Deterministic context-free
4103:Deterministic context-free
3408:For a given tree-language
3050:Completeness and reduction
44:regular languages of trees
31:. Tree automata deal with
15:
4289:
4251:Nondeterministic pushdown
3979:
3666:> 0 depending only on
3512:Alternating tree automata
2916:))))
1131:)))
2769:)))
2412:of states being still {
2340:the initial state being
1296:) not being well-typed.
4318:Trees (data structures)
3686:, a nontrivial context
2778:In contrast, the term "
2501:For example, the tree "
1267:)
728:))
292:is defined as a tuple (
70:is defined as a tuple (
51:deterministic automaton
4323:Automata (computation)
4256:Deterministic pushdown
4132:Recursively enumerable
3724:(or, correspondingly,
3639:, sect. 1.1, p. 23-24.
3517:Infinite-tree automata
3031:, by a tree automaton
2279:
467:Infinite-tree automata
18:tree walking automaton
3611:10.3115/976909.979677
3454:Myhill–Nerode theorem
3304:Myhill–Nerode theorem
3012:is an initial state.
2274:
4241:Tree stack automaton
3771:one in another, cf.
3692:, and a ground term
3314:equivalence relation
2957:regular tree grammar
2291:, it is defined by:
475:monadic second-order
91:is a set of states,
4149:range concatenation
4074:range concatenation
3811:, sect. 1.5, p .36.
3787:, sect. 1.2, p. 29.
3585:Comon et al. (2008)
3562:, sect. 1.1, p. 23.
3550:, sect. 1.6, p. 38.
3538:, sect. 1.1, p. 20.
3492:Courcelle's theorem
3759:≥ 0. The notation
3625:Comon et al. (2008
3015:The tree language
2482:)=0, as explained,
2299:of states being {
2280:
1134:by (4), accepted.
35:, rather than the
4305:
4304:
4284:
4283:
4246:Embedded pushdown
4142:Context-sensitive
4067:Context-sensitive
4001:Abstract machines
3986:Chomsky hierarchy
3854:978-1-139-49236-2
3809:Comon et al. 2008
3797:Comon et al. 2008
3785:Comon et al. 2008
3773:Comon et al. 2008
3734:Comon et al. 2008
3720:into the hole of
3637:Comon et al. 2008
3572:Comon et al. 2008
3560:Comon et al. 2008
3548:Comon et al. 2008
3536:Comon et al. 2008
3445:for each context
3288:
3287:
2923:
2922:
2776:
2775:
2284:
2283:
2265:
2264:
2261:
2260:
2053:
2052:
1808:
1807:
1623:
1622:
1431:
1430:
1274:
1273:
1138:
1137:
735:
734:
4340:
4328:Formal languages
4300:
4297:
4261:Visibly pushdown
4235:Thread automaton
4183:Visibly pushdown
4151:
4108:Visibly pushdown
4076:
4063:(no common name)
3982:
3969:formal languages
3958:
3951:
3944:
3935:
3888:
3886:
3873:
3871:
3858:
3839:
3837:
3835:
3812:
3806:
3800:
3794:
3788:
3782:
3776:
3754:
3743:
3737:
3728:the variable to
3706:
3691:
3680:
3674:
3646:
3640:
3634:
3628:
3621:
3615:
3614:
3594:
3588:
3581:
3575:
3569:
3563:
3557:
3551:
3545:
3539:
3533:
3502:word transducers
3498:Tree transducers
3480:
3444:
3426:
3404:
3394:
3351:
3331:
3277:
3271:
3265:
3257:
3251:
3245:
3239:
3233:
3227:
3211:
3205:
3199:
3191:
3185:
3179:
3173:
3157:
3151:
3145:
3137:
3131:
3124:
3123:
3118:
3004:) and ends with
2947:
2941:
2937:
2933:
2913:
2905:
2894:
2886:
2870:
2860:
2854:
2843:
2830:
2820:
2812:
2806:
2795:
2794:
2791:
2785:
2781:
2766:
2756:
2748:
2740:
2722:
2714:
2703:
2695:
2687:
2669:
2659:
2653:
2642:
2634:
2616:
2606:
2598:
2592:
2581:
2566:
2556:
2548:
2540:
2534:
2522:
2521:
2518:
2512:
2508:
2504:
2493:
2481:
2471:
2463:
2455:
2449:
2445:
2438:
2429:
2420:
2403:
2397:
2393:
2389:
2385:
2381:
2375:
2371:
2360:
2348:
2336:
2332:
2325:
2316:
2307:
2267:
2266:
2256:
2247:
2239:
2226:
2217:
2209:
2196:
2187:
2179:
2166:
2157:
2149:
2136:
2127:
2119:
2106:
2097:
2089:
2077:
2067:
2057:
2056:
2048:
2039:
2030:
2026:
2013:
2004:
1995:
1991:
1978:
1969:
1960:
1956:
1943:
1934:
1925:
1921:
1908:
1899:
1890:
1886:
1873:
1864:
1855:
1851:
1839:
1828:
1822:
1812:
1811:
1804:
1792:
1788:
1775:
1763:
1759:
1746:
1734:
1730:
1717:
1705:
1701:
1688:
1676:
1672:
1659:
1647:
1643:
1627:
1626:
1619:
1611:
1603:
1591:
1583:
1575:
1563:
1555:
1547:
1535:
1527:
1519:
1507:
1499:
1491:
1479:
1471:
1463:
1445:
1435:
1434:
1394:
1393:
1304:
1295:
1289:
1283:
1263:
1257:
1249:
1243:
1235:
1216:
1210:
1202:
1194:
1179:
1171:
1163:
1154:
1153:
1128:
1120:
1112:
1104:
1096:
1090:
1072:
1064:
1056:
1050:
1042:
1036:
1028:
1010:
1002:
994:
988:
980:
972:
953:
947:
939:
933:
925:
917:
909:
890:
884:
876:
868:
860:
852:
837:
829:
821:
813:
805:
796:
795:
790:
784:
764:
744:
719:
713:
698:
688:
682:
669:
663:
653:
640:
634:
624:
611:
605:
595:
588:
587:
582:
580:
565:
559:
531:
525:
519:
513:
507:
449:nondeterministic
425:
334:
323:
280:
212:
120:transition rules
117:
4348:
4347:
4343:
4342:
4341:
4339:
4338:
4337:
4308:
4307:
4306:
4301:
4298:
4291:
4285:
4280:
4202:
4146:
4125:
4071:
4052:
3975:
3973:formal grammars
3965:Automata theory
3962:
3900:
3898:Implementations
3895:
3876:
3861:
3855:
3842:
3833:
3831:
3824:
3821:
3816:
3815:
3807:
3803:
3795:
3791:
3783:
3779:
3746:
3744:
3740:
3697:
3687:
3681:
3677:
3647:
3643:
3635:
3631:
3622:
3618:
3596:
3595:
3591:
3582:
3578:
3570:
3566:
3558:
3554:
3546:
3542:
3534:
3530:
3525:
3488:
3479:
3473:
3428:
3422:
3413:
3396:
3392:
3383:
3372:
3363:
3353:
3350:
3341:
3333:
3330:
3323:
3317:
3306:
3298:
3273:
3267:
3261:
3253:
3247:
3241:
3235:
3229:
3223:
3207:
3201:
3195:
3187:
3181:
3175:
3169:
3153:
3147:
3141:
3133:
3127:
3119:. For example,
3114:
3092:
3052:
2970:
2968:Recognizability
2965:
2943:
2939:
2935:
2932:
2926:
2909:
2904:
2898:
2892:
2884:
2866:
2858:
2853:
2847:
2841:
2826:
2818:
2810:
2805:
2799:
2787:
2783:
2779:
2762:
2754:
2746:
2738:
2718:
2713:
2707:
2701:
2693:
2685:
2665:
2657:
2652:
2646:
2640:
2632:
2612:
2604:
2596:
2591:
2585:
2579:
2562:
2554:
2546:
2538:
2533:
2527:
2514:
2510:
2506:
2502:
2492:
2486:
2477:
2469:
2461:
2451:
2447:
2443:
2437:
2431:
2428:
2422:
2419:
2413:
2399:
2395:
2391:
2387:
2383:
2377:
2373:
2369:
2359:
2353:
2347:
2341:
2334:
2330:
2324:
2318:
2315:
2309:
2306:
2300:
2255:
2249:
2245:
2238:
2232:
2225:
2219:
2215:
2208:
2202:
2195:
2189:
2185:
2178:
2172:
2165:
2159:
2155:
2148:
2142:
2135:
2129:
2125:
2118:
2112:
2105:
2099:
2095:
2088:
2082:
2073:
2066:
2060:
2047:
2041:
2037:
2028:
2025:
2019:
2012:
2006:
2002:
1993:
1990:
1984:
1977:
1971:
1967:
1958:
1955:
1949:
1942:
1936:
1932:
1923:
1920:
1914:
1907:
1901:
1897:
1888:
1885:
1879:
1872:
1866:
1862:
1853:
1850:
1844:
1835:
1824:
1821:
1815:
1803:
1797:
1790:
1787:
1781:
1774:
1768:
1761:
1758:
1752:
1745:
1739:
1732:
1729:
1723:
1716:
1710:
1703:
1700:
1694:
1687:
1681:
1674:
1671:
1665:
1658:
1652:
1645:
1642:
1636:
1618:
1612:
1609:
1602:
1596:
1590:
1584:
1581:
1574:
1568:
1562:
1556:
1553:
1546:
1540:
1534:
1528:
1525:
1518:
1512:
1506:
1500:
1497:
1490:
1484:
1478:
1472:
1469:
1462:
1456:
1444:
1438:
1385:
1380:
1370:
1366:
1357:
1352:
1342:
1337:
1302:
1291:
1285:
1279:
1259:
1253:
1245:
1239:
1231:
1212:
1206:
1198:
1190:
1175:
1167:
1159:
1124:
1116:
1108:
1100:
1092:
1086:
1068:
1060:
1052:
1046:
1038:
1032:
1024:
1006:
998:
990:
984:
976:
968:
949:
943:
935:
929:
921:
913:
905:
886:
880:
872:
864:
856:
848:
833:
825:
817:
809:
801:
786:
780:
778:
771:
760:
758:
751:
740:
727:
723:
715:
709:
702:
694:
692:
684:
678:
665:
659:
649:
636:
630:
620:
607:
601:
591:
576:
574:
561:
555:
550:
548:
527:
521:
515:
509:
503:
488:
483:
434:
420:
400:
394:
385:
376:
369:
358:
349:
333:
325:
318:
310:
308:
279:
271:
221:
207:
187:
181:
172:
157:
148:
139:
132:
112:
104:
97:ranked alphabet
86:
60:
33:tree structures
21:
12:
11:
5:
4346:
4344:
4336:
4335:
4330:
4325:
4320:
4310:
4309:
4303:
4302:
4290:
4287:
4286:
4282:
4281:
4279:
4278:
4276:Acyclic finite
4273:
4268:
4263:
4258:
4253:
4248:
4243:
4237:
4232:
4227:
4226:Turing Machine
4221:
4219:Linear-bounded
4216:
4211:
4209:Turing machine
4205:
4203:
4201:
4200:
4195:
4190:
4185:
4180:
4175:
4170:
4168:Tree-adjoining
4165:
4160:
4157:
4152:
4144:
4139:
4134:
4128:
4126:
4124:
4123:
4118:
4115:
4110:
4105:
4100:
4095:
4093:Tree-adjoining
4090:
4085:
4082:
4077:
4069:
4064:
4061:
4055:
4053:
4051:
4050:
4047:
4044:
4041:
4038:
4035:
4032:
4029:
4026:
4023:
4020:
4017:
4014:
4011:
4007:
4004:
4003:
3998:
3993:
3988:
3980:
3977:
3976:
3963:
3961:
3960:
3953:
3946:
3938:
3932:
3931:
3925:
3919:
3913:
3907:
3899:
3896:
3894:
3893:External links
3891:
3890:
3889:
3874:
3859:
3853:
3840:
3820:
3817:
3814:
3813:
3801:
3789:
3777:
3738:
3707:. A "context"
3675:
3641:
3629:
3623:The notion in
3616:
3589:
3576:
3564:
3552:
3540:
3527:
3526:
3524:
3521:
3520:
3519:
3514:
3509:
3495:
3487:
3484:
3483:
3482:
3475:
3470:
3464:
3418:
3388:
3381:
3368:
3361:
3346:
3337:
3328:
3321:
3305:
3302:
3297:
3294:
3290:
3289:
3286:
3285:
3282:
3279:
3259:
3220:
3219:
3216:
3213:
3193:
3166:
3165:
3162:
3159:
3139:
3091:
3088:
3082:). An NFTA is
3051:
3048:
2980:and ends with
2969:
2966:
2964:
2961:
2930:
2921:
2920:
2917:
2914:
2907:
2902:
2896:
2890:
2888:
2882:
2878:
2877:
2874:
2871:
2864:
2862:
2856:
2851:
2845:
2839:
2835:
2834:
2831:
2824:
2822:
2816:
2814:
2808:
2803:
2774:
2773:
2770:
2767:
2760:
2758:
2752:
2750:
2744:
2742:
2736:
2734:
2730:
2729:
2726:
2723:
2716:
2711:
2705:
2699:
2697:
2691:
2689:
2683:
2681:
2677:
2676:
2673:
2670:
2663:
2661:
2655:
2650:
2644:
2638:
2636:
2630:
2628:
2624:
2623:
2620:
2617:
2610:
2608:
2602:
2600:
2594:
2589:
2583:
2577:
2575:
2571:
2570:
2567:
2560:
2558:
2552:
2550:
2544:
2542:
2536:
2531:
2525:
2499:
2498:
2495:
2490:
2483:
2440:
2435:
2426:
2417:
2366:
2365:
2362:
2357:
2350:
2345:
2338:
2327:
2322:
2313:
2304:
2282:
2281:
2263:
2262:
2259:
2258:
2253:
2243:
2240:
2236:
2229:
2228:
2223:
2213:
2210:
2206:
2199:
2198:
2193:
2183:
2180:
2176:
2169:
2168:
2163:
2153:
2150:
2146:
2139:
2138:
2133:
2123:
2120:
2116:
2109:
2108:
2103:
2093:
2090:
2086:
2079:
2078:
2071:
2068:
2064:
2054:
2051:
2050:
2045:
2035:
2032:
2023:
2016:
2015:
2010:
2000:
1997:
1988:
1981:
1980:
1975:
1965:
1962:
1953:
1946:
1945:
1940:
1930:
1927:
1918:
1911:
1910:
1905:
1895:
1892:
1883:
1876:
1875:
1870:
1860:
1857:
1848:
1841:
1840:
1833:
1830:
1819:
1809:
1806:
1805:
1801:
1794:
1785:
1777:
1776:
1772:
1765:
1756:
1748:
1747:
1743:
1736:
1727:
1719:
1718:
1714:
1707:
1698:
1690:
1689:
1685:
1678:
1669:
1661:
1660:
1656:
1649:
1640:
1632:
1631:
1624:
1621:
1620:
1616:
1607:
1604:
1600:
1593:
1592:
1588:
1579:
1576:
1572:
1565:
1564:
1560:
1551:
1548:
1544:
1537:
1536:
1532:
1523:
1520:
1516:
1509:
1508:
1504:
1495:
1492:
1488:
1481:
1480:
1476:
1467:
1464:
1460:
1453:
1452:
1449:
1446:
1442:
1432:
1429:
1428:
1424:
1423:
1419:
1418:
1414:
1413:
1409:
1408:
1404:
1403:
1399:
1398:
1390:
1389:
1374:
1361:
1346:
1331:
1328:
1327:
1322:
1317:
1312:
1307:
1301:
1298:
1276:
1275:
1272:
1271:
1268:
1265:
1251:
1237:
1229:
1225:
1224:
1221:
1218:
1204:
1196:
1188:
1184:
1183:
1180:
1173:
1165:
1157:
1140:
1139:
1136:
1135:
1132:
1129:
1122:
1114:
1106:
1098:
1084:
1080:
1079:
1076:
1073:
1066:
1058:
1044:
1030:
1022:
1018:
1017:
1014:
1011:
1004:
996:
982:
974:
966:
962:
961:
958:
955:
941:
927:
919:
911:
903:
899:
898:
895:
892:
878:
870:
862:
854:
846:
842:
841:
838:
831:
823:
815:
807:
799:
776:
769:
756:
749:
737:
736:
733:
732:
729:
725:
721:
707:
704:
700:
690:
675:
674:
671:
657:
654:
646:
645:
642:
628:
625:
617:
616:
613:
599:
596:
570:
544:
526:(.,.) }, with
487:
484:
482:
479:
430:
416:
390:
381:
374:
367:
354:
347:
329:
314:
304:
275:
217:
203:
177:
170:
153:
144:
137:
130:
108:
82:
59:
56:
25:tree automaton
13:
10:
9:
6:
4:
3:
2:
4345:
4334:
4331:
4329:
4326:
4324:
4321:
4319:
4316:
4315:
4313:
4295:
4294:proper subset
4288:
4277:
4274:
4272:
4269:
4267:
4264:
4262:
4259:
4257:
4254:
4252:
4249:
4247:
4244:
4242:
4238:
4236:
4233:
4231:
4228:
4225:
4222:
4220:
4217:
4215:
4212:
4210:
4207:
4206:
4204:
4199:
4196:
4194:
4191:
4189:
4186:
4184:
4181:
4179:
4176:
4174:
4171:
4169:
4166:
4164:
4161:
4158:
4156:
4153:
4150:
4145:
4143:
4140:
4138:
4135:
4133:
4130:
4129:
4127:
4122:
4121:Non-recursive
4119:
4116:
4114:
4111:
4109:
4106:
4104:
4101:
4099:
4096:
4094:
4091:
4089:
4086:
4083:
4081:
4078:
4075:
4070:
4068:
4065:
4062:
4060:
4057:
4056:
4054:
4048:
4045:
4042:
4039:
4036:
4033:
4030:
4027:
4024:
4021:
4018:
4015:
4012:
4009:
4008:
4006:
4005:
4002:
3999:
3997:
3994:
3992:
3989:
3987:
3984:
3983:
3978:
3974:
3970:
3966:
3959:
3954:
3952:
3947:
3945:
3940:
3939:
3936:
3929:
3926:
3923:
3920:
3917:
3914:
3911:
3908:
3905:
3902:
3901:
3897:
3892:
3885:
3880:
3875:
3870:
3865:
3860:
3856:
3850:
3846:
3841:
3830:
3829:
3823:
3822:
3818:
3810:
3805:
3802:
3798:
3793:
3790:
3786:
3781:
3778:
3775:, p. 17.
3774:
3770:
3766:
3762:
3758:
3753:
3749:
3742:
3739:
3735:
3731:
3727:
3726:instantiating
3723:
3719:
3715:
3710:
3704:
3700:
3695:
3690:
3685:
3679:
3676:
3673:
3669:
3665:
3661:
3657:
3653:
3652:
3645:
3642:
3638:
3633:
3630:
3626:
3620:
3617:
3612:
3608:
3604:
3600:
3593:
3590:
3586:
3580:
3577:
3573:
3568:
3565:
3561:
3556:
3553:
3549:
3544:
3541:
3537:
3532:
3529:
3522:
3518:
3515:
3513:
3510:
3507:
3506:word automata
3503:
3499:
3496:
3493:
3490:
3489:
3485:
3478:
3472:the relation
3471:
3468:
3465:
3462:
3459:
3458:
3457:
3455:
3450:
3448:
3443:
3439:
3435:
3431:
3425:
3421:
3416:
3411:
3406:
3403:
3399:
3391:
3387:
3380:
3376:
3371:
3367:
3360:
3356:
3349:
3345:
3340:
3336:
3327:
3320:
3315:
3311:
3303:
3301:
3295:
3293:
3283:
3280:
3276:
3270:
3264:
3260:
3256:
3250:
3244:
3238:
3232:
3226:
3222:
3221:
3217:
3214:
3210:
3204:
3198:
3194:
3190:
3184:
3178:
3172:
3168:
3167:
3163:
3160:
3156:
3150:
3144:
3140:
3136:
3130:
3126:
3125:
3122:
3121:
3120:
3117:
3112:
3107:
3105:
3101:
3097:
3090:Pumping lemma
3089:
3087:
3085:
3081:
3077:
3073:
3069:
3065:
3061:
3057:
3049:
3047:
3044:
3042:
3038:
3034:
3030:
3026:
3022:
3018:
3013:
3011:
3007:
3003:
2999:
2995:
2991:
2987:
2983:
2979:
2975:
2967:
2962:
2960:
2958:
2954:
2949:
2946:
2929:
2918:
2915:
2912:
2908:
2901:
2897:
2891:
2889:
2883:
2880:
2879:
2875:
2872:
2869:
2865:
2863:
2857:
2850:
2846:
2840:
2837:
2836:
2832:
2829:
2825:
2823:
2817:
2815:
2809:
2802:
2797:
2796:
2793:
2790:
2771:
2768:
2765:
2761:
2759:
2753:
2751:
2745:
2743:
2737:
2735:
2732:
2731:
2727:
2724:
2721:
2717:
2710:
2706:
2700:
2698:
2692:
2690:
2684:
2682:
2679:
2678:
2674:
2671:
2668:
2664:
2662:
2656:
2649:
2645:
2639:
2637:
2631:
2629:
2626:
2625:
2621:
2618:
2615:
2611:
2609:
2603:
2601:
2595:
2588:
2584:
2578:
2576:
2573:
2572:
2568:
2565:
2561:
2559:
2553:
2551:
2545:
2543:
2537:
2530:
2526:
2524:
2523:
2520:
2517:
2496:
2489:
2484:
2480:
2475:
2467:
2459:
2454:
2441:
2434:
2425:
2416:
2411:
2407:
2406:
2405:
2402:
2380:
2363:
2356:
2351:
2344:
2339:
2328:
2321:
2312:
2303:
2298:
2294:
2293:
2292:
2290:
2277:
2273:
2269:
2268:
2252:
2244:
2241:
2235:
2231:
2230:
2222:
2214:
2211:
2205:
2201:
2200:
2192:
2184:
2181:
2175:
2171:
2170:
2162:
2154:
2151:
2145:
2141:
2140:
2132:
2124:
2121:
2115:
2111:
2110:
2102:
2094:
2091:
2085:
2081:
2080:
2076:
2072:
2069:
2063:
2059:
2058:
2055:
2044:
2036:
2033:
2022:
2018:
2017:
2009:
2001:
1998:
1987:
1983:
1982:
1974:
1966:
1963:
1952:
1948:
1947:
1939:
1931:
1928:
1917:
1913:
1912:
1904:
1896:
1893:
1882:
1878:
1877:
1869:
1861:
1858:
1847:
1843:
1842:
1838:
1834:
1831:
1827:
1818:
1814:
1813:
1810:
1800:
1795:
1784:
1779:
1778:
1771:
1766:
1755:
1750:
1749:
1742:
1737:
1726:
1721:
1720:
1713:
1708:
1697:
1692:
1691:
1684:
1679:
1668:
1663:
1662:
1655:
1650:
1639:
1634:
1633:
1629:
1628:
1625:
1615:
1608:
1605:
1599:
1595:
1594:
1587:
1580:
1577:
1571:
1567:
1566:
1559:
1552:
1549:
1543:
1539:
1538:
1531:
1524:
1521:
1515:
1511:
1510:
1503:
1496:
1493:
1487:
1483:
1482:
1475:
1468:
1465:
1459:
1455:
1454:
1450:
1447:
1441:
1437:
1436:
1433:
1426:
1425:
1421:
1420:
1416:
1415:
1411:
1410:
1406:
1405:
1401:
1400:
1396:
1395:
1392:
1391:
1388:
1384:
1383:
1379:
1373:
1369:
1365:
1360:
1356:
1355:
1351:
1345:
1341:
1340:
1336:
1330:
1329:
1326:
1321:
1316:
1311:
1306:
1305:
1299:
1297:
1294:
1288:
1282:
1269:
1266:
1262:
1256:
1248:
1242:
1234:
1227:
1226:
1222:
1219:
1215:
1209:
1201:
1193:
1186:
1185:
1181:
1178:
1170:
1162:
1156:
1155:
1152:
1151:
1150:
1147:
1145:
1133:
1130:
1127:
1119:
1111:
1103:
1095:
1089:
1082:
1081:
1077:
1074:
1071:
1063:
1055:
1049:
1041:
1035:
1027:
1020:
1019:
1015:
1012:
1009:
1001:
993:
987:
979:
971:
964:
963:
959:
956:
952:
946:
938:
932:
924:
916:
908:
901:
900:
896:
893:
889:
883:
875:
867:
859:
851:
844:
843:
839:
836:
828:
820:
812:
804:
798:
797:
794:
793:
792:
789:
783:
775:
768:
763:
755:
748:
743:
730:
718:
712:
708:
705:
697:
687:
681:
677:
676:
672:
668:
662:
658:
655:
652:
648:
647:
643:
639:
633:
629:
626:
623:
619:
618:
614:
610:
604:
600:
597:
594:
590:
589:
586:
585:
584:
579:
573:
569:
564:
558:
553:
547:
543:
539:
535:
530:
524:
518:
512:
506:
501:
497:
493:
485:
480:
478:
476:
472:
468:
464:
461:
460:deterministic
458:In contrast,
456:
454:
450:
446:
443:(abbreviated
442:
441:deterministic
437:
433:
429:
424:
419:
415:
411:
407:
403:
398:
393:
389:
384:
380:
373:
366:
362:
357:
353:
346:
342:
338:
332:
328:
322:
317:
313:
307:
303:
299:
295:
291:
287:
282:
278:
274:
269:
265:
261:
257:
253:
249:
245:
241:
237:
233:
229:
224:
220:
216:
211:
206:
202:
198:
194:
190:
185:
180:
176:
169:
165:
161:
156:
152:
147:
143:
136:
129:
125:
121:
116:
111:
107:
102:
98:
94:
90:
85:
81:
77:
73:
69:
65:
57:
55:
52:
47:
45:
40:
38:
34:
30:
29:state machine
27:is a type of
26:
19:
4230:Nested stack
4173:Context-free
4098:Context-free
4059:Unrestricted
3844:
3832:. Retrieved
3827:
3804:
3792:
3780:
3768:
3764:
3760:
3756:
3751:
3747:
3741:
3729:
3721:
3717:
3713:
3708:
3702:
3698:
3693:
3688:
3683:
3678:
3671:
3667:
3663:
3659:
3655:
3649:
3644:
3632:
3619:
3602:
3592:
3579:
3567:
3555:
3543:
3531:
3476:
3466:
3460:
3451:
3446:
3441:
3437:
3433:
3429:
3423:
3419:
3414:
3409:
3407:
3401:
3397:
3395:, for every
3389:
3385:
3378:
3374:
3369:
3365:
3358:
3354:
3347:
3343:
3338:
3334:
3332:and ... and
3325:
3318:
3309:
3307:
3299:
3291:
3274:
3268:
3262:
3254:
3248:
3242:
3236:
3230:
3224:
3208:
3202:
3196:
3188:
3182:
3176:
3170:
3154:
3148:
3142:
3134:
3128:
3115:
3110:
3108:
3103:
3099:
3095:
3093:
3083:
3079:
3075:
3071:
3067:
3063:
3059:
3055:
3053:
3045:
3041:recognizable
3040:
3036:
3032:
3028:
3024:
3020:
3016:
3014:
3009:
3005:
3001:
2997:
2993:
2989:
2985:
2981:
2977:
2973:
2971:
2950:
2944:
2927:
2924:
2910:
2899:
2867:
2848:
2827:
2800:
2788:
2777:
2763:
2719:
2708:
2666:
2647:
2613:
2586:
2563:
2528:
2515:
2500:
2487:
2478:
2473:
2465:
2457:
2452:
2432:
2423:
2414:
2409:
2400:
2378:
2367:
2354:
2342:
2319:
2310:
2301:
2296:
2285:
2250:
2233:
2220:
2203:
2190:
2173:
2160:
2143:
2130:
2113:
2100:
2083:
2074:
2061:
2042:
2020:
2007:
1985:
1972:
1950:
1937:
1915:
1902:
1880:
1867:
1845:
1836:
1825:
1816:
1798:
1782:
1769:
1753:
1740:
1724:
1711:
1695:
1682:
1666:
1653:
1637:
1613:
1597:
1585:
1569:
1557:
1541:
1529:
1513:
1501:
1485:
1473:
1457:
1439:
1386:
1381:
1377:
1371:
1367:
1363:
1358:
1353:
1349:
1343:
1338:
1334:
1324:
1319:
1314:
1309:
1292:
1286:
1280:
1277:
1260:
1254:
1246:
1240:
1232:
1213:
1207:
1199:
1191:
1176:
1168:
1160:
1148:
1141:
1125:
1117:
1109:
1101:
1093:
1087:
1069:
1061:
1053:
1047:
1039:
1033:
1025:
1007:
999:
991:
985:
977:
969:
950:
944:
936:
930:
922:
914:
906:
887:
881:
873:
865:
857:
849:
834:
826:
818:
810:
802:
787:
781:
773:
766:
761:
753:
746:
741:
738:
716:
710:
695:
685:
679:
666:
660:
650:
637:
631:
621:
608:
602:
592:
577:
571:
567:
562:
556:
551:
545:
541:
537:
533:
528:
522:
516:
510:
504:
499:
495:
491:
489:
465:
459:
457:
452:
448:
444:
440:
438:
431:
427:
422:
417:
413:
409:
405:
401:
396:
391:
387:
382:
378:
371:
364:
360:
355:
351:
344:
340:
336:
330:
326:
320:
315:
311:
305:
301:
297:
293:
289:
285:
283:
276:
272:
267:
263:
255:
251:
247:
243:
239:
235:
231:
227:
225:
218:
214:
209:
204:
200:
196:
192:
188:
183:
178:
174:
167:
163:
159:
154:
150:
145:
141:
134:
127:
123:
122:of the form
114:
109:
105:
92:
88:
87:, Δ), where
83:
79:
75:
71:
67:
63:
61:
48:
41:
24:
22:
4239:restricted
3924:(Isabelle )
3834:11 February
1372:transitions
1359:transitions
765:, provided
759:) has type
395:)), for an
260:ground term
182:)), for an
58:Definitions
4312:Categories
3884:1510.02036
3869:1509.06233
3819:References
3767:copies of
3745:Formally:
3696:such that
3648:Formally:
3316:such that
3064:accessible
3029:recognized
2963:Properties
549:, Δ) with
4193:Star-free
4147:Positive
4137:Decidable
4072:Positive
3996:Languages
3670:, not on
2988:), where
1368:automaton
1354:automaton
779:has type
673:(3), and
3991:Grammars
3755:for all
3689:C′
3486:See also
3352:implies
3056:complete
3025:accepted
3008:, where
2955:, and a
2472:)=1 and
2456:}, with
2408:the set
2295:the set
481:Examples
4214:Decider
4188:Regular
4155:Indexed
4113:Regular
4080:Indexed
3662:, with
3658:) >
3504:extend
3296:Closure
3084:reduced
1630:
1382:grammar
1339:grammar
1223:by (1)
1078:by (1)
1016:by (4)
960:by (2)
897:by (3)
37:strings
4266:Finite
4198:Finite
4043:Type-3
4034:Type-2
4016:Type-1
4010:Type-0
3916:LETHAL
3910:Timbuk
3904:Grappa
3851:
3651:height
3312:is an
3284:, ...
2494:}, and
2361:}, and
1350:String
1335:String
473:, the
426:, and
377:),...,
359:)) →
213:, and
140:),...,
4224:PTIME
3879:arXiv
3864:arXiv
3523:Notes
3384:,...,
3364:,...,
3255:false
3243:false
3231:false
3189:false
3177:false
3135:false
3027:, or
2876:by 2
2772:by 0
2728:by 1
2675:by 4
2622:by 2
2569:))))
2474:Arity
2466:Arity
2458:Arity
2049:(x))
2014:(x))
1979:(x))
1944:(x))
1909:(x))
1874:(x))
1387:rules
1344:rules
1287:false
1247:false
1200:false
1169:false
1102:false
1088:BList
1048:BList
1040:false
986:BList
978:false
945:BList
915:false
882:BList
858:false
811:false
788:BList
762:BList
731:(4).
711:BList
696:BList
661:BList
644:(2),
615:(1),
609:false
593:false
578:BList
563:BList
505:false
399:-ary
350:,...,
288:over
262:over
238:() →
186:-ary
173:,...,
158:)) →
101:arity
95:is a
66:over
3971:and
3928:VATA
3849:ISBN
3836:2014
3750:] ∈
3452:The
3373:) ≡
3281:)))
3269:true
3263:cons
3249:cons
3237:cons
3225:cons
3203:true
3197:cons
3183:cons
3171:cons
3149:true
3143:cons
3129:cons
3116:cons
2873:))))
2833:)))
2725:))))
2672:))))
2619:))))
2372:and
2031:(x))
1996:(x))
1961:(x))
1926:(x))
1891:(x))
1856:(x))
1378:Tree
1364:Tree
1293:true
1281:cons
1261:true
1255:Bool
1241:Bool
1233:cons
1214:true
1208:Bool
1192:cons
1177:true
1161:cons
1118:true
1110:cons
1094:cons
1075:)))
1062:true
1054:cons
1034:Bool
1026:cons
1013:)))
1000:true
992:cons
970:cons
937:true
931:Bool
923:cons
907:cons
874:true
866:cons
850:cons
827:true
819:cons
803:cons
785:and
782:Bool
772:and
742:cons
717:cons
686:Bool
680:cons
638:true
632:Bool
622:true
603:Bool
575:= {
557:Bool
554:= {
529:cons
523:cons
511:true
494:and
453:NFTA
445:DFTA
226:For
3732:).
3607:doi
3427:if
3275:nil
3215:))
3209:nil
3155:nil
3074:to
3062:is
2945:nil
2911:nil
2868:nil
2828:nil
2798:⇒
2789:nil
2764:nil
2720:nil
2667:nil
2614:nil
2564:nil
2516:nil
2479:nil
2453:nil
2401:nil
2384:110
2379:nil
2075:nil
1837:nil
1826:nil
1325:(D)
1320:(C)
1315:(B)
1310:(A)
1250:),
1126:nil
1070:nil
1043:),
1008:nil
957:))
951:nil
940:),
894:))
888:nil
840:))
835:nil
667:nil
651:nil
566:},
517:nil
502:={
471:S2S
103:),
4314::
3967::
3701:=
3601:.
3449:.
3440:∈
3436:⇔
3432:∈
3400:∈
3342:≡
3324:≡
3278:)
3258:,
3218:,
3212:)
3192:,
3164:,
3161:)
3158:)
3138:,
3106:.
3023:)
2464:)=
2450:,
2446:,
2439:},
2430:,
2421:,
2337:},
2333:,
2326:},
2317:,
2308:,
2257:)
2227:)
2197:)
2167:)
2137:)
2107:)
1796:=
1780:δ(
1767:=
1751:δ(
1738:=
1722:δ(
1709:=
1693:δ(
1680:=
1664:δ(
1651:=
1635:δ(
1451:ε
1427:6
1422:5
1417:4
1412:3
1407:2
1402:1
1397:0
1264:)
1236:(
1228:⇒
1220:)
1217:)
1203:,
1195:(
1187:⇒
1182:)
1172:,
1164:(
1146:.
1121:,
1113:(
1105:,
1097:(
1083:⇒
1065:,
1057:(
1029:(
1021:⇒
1003:,
995:(
981:,
973:(
965:⇒
954:)
926:(
918:,
910:(
902:⇒
891:)
877:,
869:(
861:,
853:(
845:⇒
830:,
822:(
814:,
806:(
724:,x
720:(x
703:))
699:(x
693:),
689:(x
581:},
540:,
536:,
421:∈
412:,
408:,
404:∈
319:⊆
300:,
296:,
284:A
281:.
250:→
208:∈
199:,
195:,
191:∈
113:⊆
78:,
74:,
62:A
46:.
23:A
4159:—
4117:—
4084:—
4049:—
4046:—
4040:—
4037:—
4031:—
4028:—
4025:—
4022:—
4019:—
4013:—
3957:e
3950:t
3943:v
3887:.
3881::
3872:.
3866::
3857:.
3838:.
3769:C
3765:n
3761:C
3757:n
3752:L
3748:C
3730:t
3722:C
3718:t
3714:C
3709:C
3705:]
3703:C
3699:t
3694:u
3684:C
3672:t
3668:L
3664:k
3660:k
3656:t
3654:(
3613:.
3609::
3508:.
3477:L
3474:≡
3467:L
3461:L
3447:C
3442:L
3438:C
3434:L
3430:C
3424:v
3420:L
3417:≡
3415:u
3410:L
3402:F
3398:f
3393:)
3390:n
3386:v
3382:1
3379:v
3377:(
3375:f
3370:n
3366:u
3362:1
3359:u
3357:(
3355:f
3348:n
3344:v
3339:n
3335:u
3329:1
3326:v
3322:1
3319:u
3310:F
3272:,
3266:(
3252:(
3246:,
3240:(
3234:,
3228:(
3206:,
3200:(
3186:(
3180:,
3174:(
3152:,
3146:(
3132:(
3111:k
3104:L
3100:L
3096:t
3080:t
3078:(
3076:q
3072:t
3068:t
3060:q
3037:A
3033:A
3021:A
3019:(
3017:L
3010:q
3006:t
3002:t
3000:(
2998:q
2994:t
2990:q
2986:t
2984:(
2982:q
2978:t
2974:t
2942:(
2940:0
2938:(
2936:1
2931:0
2928:S
2906:(
2903:2
2900:S
2895:(
2893:0
2887:(
2885:1
2881:⇒
2861:(
2859:0
2855:(
2852:1
2849:S
2844:(
2842:1
2838:⇒
2821:(
2819:0
2813:(
2811:1
2807:(
2804:0
2801:S
2786:(
2784:0
2782:(
2780:1
2757:(
2755:0
2749:(
2747:1
2741:(
2739:1
2733:⇒
2715:(
2712:0
2709:S
2704:(
2702:0
2696:(
2694:1
2688:(
2686:1
2680:⇒
2660:(
2658:0
2654:(
2651:0
2648:S
2643:(
2641:1
2635:(
2633:1
2627:⇒
2607:(
2605:0
2599:(
2597:1
2593:(
2590:1
2587:S
2582:(
2580:1
2574:⇒
2557:(
2555:0
2549:(
2547:1
2541:(
2539:1
2535:(
2532:0
2529:S
2513:(
2511:0
2509:(
2507:1
2505:(
2503:1
2491:0
2488:S
2476:(
2470:1
2468:(
2462:0
2460:(
2448:1
2444:0
2436:2
2433:S
2427:1
2424:S
2418:0
2415:S
2410:Q
2398:(
2396:0
2394:(
2392:1
2390:(
2388:1
2374:1
2370:0
2358:0
2355:S
2349:,
2346:0
2343:S
2335:1
2331:0
2323:2
2320:S
2314:1
2311:S
2305:0
2302:S
2297:Q
2254:2
2251:S
2248:(
2246:1
2242:→
2237:2
2234:S
2224:1
2221:S
2218:(
2216:0
2212:→
2207:2
2204:S
2194:0
2191:S
2188:(
2186:1
2182:→
2177:1
2174:S
2164:2
2161:S
2158:(
2156:0
2152:→
2147:1
2144:S
2134:1
2131:S
2128:(
2126:1
2122:→
2117:0
2114:S
2104:0
2101:S
2098:(
2096:0
2092:→
2087:0
2084:S
2070:→
2065:0
2062:S
2046:2
2043:S
2040:(
2038:1
2034:→
2029:1
2027:(
2024:2
2021:S
2011:1
2008:S
2005:(
2003:0
1999:→
1994:0
1992:(
1989:2
1986:S
1976:0
1973:S
1970:(
1968:1
1964:→
1959:1
1957:(
1954:1
1951:S
1941:2
1938:S
1935:(
1933:0
1929:→
1924:0
1922:(
1919:1
1916:S
1906:1
1903:S
1900:(
1898:1
1894:→
1889:1
1887:(
1884:0
1881:S
1871:0
1868:S
1865:(
1863:0
1859:→
1854:0
1852:(
1849:0
1846:S
1832:→
1829:)
1823:(
1820:0
1817:S
1802:2
1799:S
1793:)
1791:1
1789:,
1786:2
1783:S
1773:1
1770:S
1764:)
1762:0
1760:,
1757:2
1754:S
1744:0
1741:S
1735:)
1733:1
1731:,
1728:1
1725:S
1715:2
1712:S
1706:)
1704:0
1702:,
1699:1
1696:S
1686:1
1683:S
1677:)
1675:1
1673:,
1670:0
1667:S
1657:0
1654:S
1648:)
1646:0
1644:,
1641:0
1638:S
1617:2
1614:S
1610:1
1606:→
1601:2
1598:S
1589:1
1586:S
1582:0
1578:→
1573:2
1570:S
1561:0
1558:S
1554:1
1550:→
1545:1
1542:S
1533:2
1530:S
1526:0
1522:→
1517:1
1514:S
1505:1
1502:S
1498:1
1494:→
1489:0
1486:S
1477:0
1474:S
1470:0
1466:→
1461:0
1458:S
1448:→
1443:0
1440:S
1290:,
1284:(
1258:(
1244:(
1211:(
1091:(
1051:(
1037:(
989:(
948:(
934:(
885:(
777:2
774:x
770:1
767:x
757:2
754:x
752:,
750:1
747:x
745:(
726:2
722:1
714:(
706:→
701:2
691:1
683:(
670:)
664:(
656:→
641:)
635:(
627:→
612:)
606:(
598:→
572:f
568:Q
560:,
552:Q
546:f
542:Q
538:F
534:Q
520:,
514:,
508:,
500:F
496:Q
492:F
451:(
432:i
428:x
423:Q
418:i
414:q
410:q
406:F
402:f
397:n
392:n
388:x
386:(
383:n
379:q
375:1
372:x
370:(
368:1
365:q
363:(
361:f
356:n
352:x
348:1
345:x
343:(
341:f
339:(
337:q
331:f
327:Q
321:Q
316:i
312:Q
306:i
302:Q
298:F
294:Q
290:F
277:f
273:Q
268:Q
264:F
256:f
254:(
252:q
248:f
244:f
242:(
240:q
236:f
232:f
228:n
219:i
215:x
210:Q
205:i
201:q
197:q
193:F
189:f
184:n
179:n
175:x
171:1
168:x
166:(
164:f
162:(
160:q
155:n
151:x
149:(
146:n
142:q
138:1
135:x
133:(
131:1
128:q
126:(
124:f
115:Q
110:f
106:Q
93:F
89:Q
84:f
80:Q
76:F
72:Q
68:F
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
