36:
688:
548:
993:
556:
315:
359:
188:
845:
1061:
478:
786:
741:
499:
858:
57:
79:
1100:
97:
683:{\displaystyle d(w,v)=\inf\{2^{-|x|}\mid x\in \Sigma ^{*}\ {\text{and}}\ x\in {\text{Pref}}(w)\cap {\text{Pref}}(v)\}}
50:
44:
1105:
379:
61:
1019:
of ω-regular language membership is decidable using a Büchi automaton, and fairly straightforward to compute.
1008:
287:
336:
1087:, Volume B: Formal Models and Semantics, pages 133-192. Elsevier Science Publishers, Amsterdam, 1990.
1027:
494:
171:
1065:
815:
1012:
454:
1051:
750:
117:
1047:
1043:
1016:
136:
Let Σ be a set of symbols (not necessarily finite). Following the standard definition from
1080:
137:
109:
93:
720:
1057:
1031:
125:
121:
144:
words over Σ. Every finite word has a length, which is a natural number. Given a word
1094:
1069:
543:{\displaystyle d:\Sigma ^{\omega }\times \Sigma ^{\omega }\rightarrow \mathbb {R} }
490:
714:
318:
190:
to Σ. The set of all infinite words over Σ is denoted Σ. The set of all finite
17:
1023:
988:{\displaystyle d(w,u)\leq 2^{-\min\{m,n\}}\leq 2^{-m}+2^{-n}=d(w,v)+d(v,u)}
168:. The infinite words, or ω-words, can likewise be viewed as functions from
105:
710:
1026:
of a set (called the "atomic propositions") then the ω-language is a
202:
788:. Symmetry is clear. Transitivity follows from the fact that if
1007:
The most widely used subclass of the ω-languages is the set of
29:
423:
set. In other words, for an arbitrarily large natural number
321:
operator on finite-length languages. Given a formal language
1011:, which enjoy the useful property of being recognizable by
329:
is the ω-language of all infinite sequences of words from
1076:, Volume 3, pages 339-387. Springer-Verlag, Berlin, 1997.
1054:". Pure and Applied Mathematics Vol 141, Elsevier, 2004.
120:
of infinite words. Here, ω refers to the first infinite
1052:
Infinite Words: Automata, Semigroups, Logic and Games
861:
818:
753:
723:
559:
502:
457:
339:
290:
174:
213:Some common operations defined on ω-languages are:
194:infinite words over Σ is sometimes written Σ or Σ.
987:
839:
780:
735:
682:
542:
472:
353:
309:
182:
156:can be viewed as a function from the set {0,1,...,
891:
819:
581:
427:, it is always possible to choose some word in
1079:Thomas, W. "Automata on Infinite Objects". In
8:
906:
894:
834:
822:
677:
584:
371:be an ω-word. Then the formal language Pref(
333:; in the functional view, of all functions
934:
918:
887:
860:
817:
752:
722:
663:
646:
632:
623:
603:
595:
591:
558:
536:
535:
526:
513:
501:
459:
458:
456:
341:
340:
338:
301:
289:
262:be a language of finite words only. Then
176:
175:
173:
80:Learn how and when to remove this message
1085:Handbook of Theoretical Computer Science
108:(specifically, an ω-length sequence) of
43:This article includes a list of general
808:have a maximal shared prefix of length
796:have a maximal shared prefix of length
284:As the notation hints, the operation
266:can be concatenated on the left, and
7:
27:Theoretical computer science concept
697:| is interpreted as "the length of
620:
523:
510:
310:{\displaystyle (\cdot )^{\omega }}
49:it lacks sufficient corresponding
25:
354:{\displaystyle \mathbb {N} \to L}
160:−1} → Σ, with the value at
743:then there is no longest prefix
34:
431:, whose length is greater than
392:Given a finite-length language
317:is the infinite version of the
982:
970:
961:
949:
877:
865:
769:
757:
674:
668:
657:
651:
604:
596:
575:
563:
532:
464:
345:
298:
291:
164:giving the symbol at position
1:
489:The set Σ can be made into a
485:Distance between ω-words
1074:Handbook of Formal Languages
274:to yield the new ω-language
183:{\displaystyle \mathbb {N} }
140:theory, Σ is the set of all
98:theoretical computer science
840:{\displaystyle \min\{m,n\}}
1122:
473:{\displaystyle {\vec {L}}}
281:Omega (infinite iteration)
1022:If the language Σ is the
443:. The limit operation on
1009:ω-regular languages
781:{\displaystyle d(w,v)=0}
701:" (number of symbols in
1030:, which are studied in
64:more precise citations.
989:
841:
782:
737:
684:
544:
474:
355:
311:
258:be an ω-language, and
217:Intersection and union
184:
104:is an infinite-length
1101:Theory of computation
990:
842:
783:
738:
685:
545:
493:by definition of the
475:
439:which is a prefix of
356:
312:
185:
1028:linear time property
1003:Important subclasses
859:
855:must be the same so
816:
751:
721:
557:
500:
455:
337:
288:
172:
124:, modeling a set of
736:{\displaystyle w=v}
197:Thus an ω-language
985:
837:
778:
733:
680:
540:
470:
351:
307:
251:Left concatenation
220:Given ω-languages
180:
666:
649:
639:
635:
631:
467:
375:) contains every
132:Formal definition
90:
89:
82:
16:(Redirected from
1113:
1106:Formal languages
1062:ω-Languages
1017:decision problem
994:
992:
991:
986:
942:
941:
926:
925:
910:
909:
846:
844:
843:
838:
787:
785:
784:
779:
742:
740:
739:
734:
689:
687:
686:
681:
667:
664:
650:
647:
637:
636:
633:
629:
628:
627:
609:
608:
607:
599:
549:
547:
546:
541:
539:
531:
530:
518:
517:
479:
477:
476:
471:
469:
468:
460:
418:
360:
358:
357:
352:
344:
316:
314:
313:
308:
306:
305:
270:on the left, to
248:are ω-languages.
247:
237:
189:
187:
186:
181:
179:
85:
78:
74:
71:
65:
60:this article by
51:inline citations
38:
37:
30:
21:
1121:
1120:
1116:
1115:
1114:
1112:
1111:
1110:
1091:
1090:
1081:Jan van Leeuwen
1040:
1005:
930:
914:
883:
857:
856:
814:
813:
812:then the first
749:
748:
719:
718:
619:
587:
555:
554:
522:
509:
498:
497:
487:
453:
452:
447:can be written
409:
408:if and only if
335:
334:
297:
286:
285:
239:
229:
211:
170:
169:
138:formal language
134:
126:natural numbers
94:formal language
86:
75:
69:
66:
56:Please help to
55:
39:
35:
28:
23:
22:
15:
12:
11:
5:
1119:
1117:
1109:
1108:
1103:
1093:
1092:
1089:
1088:
1077:
1055:
1039:
1036:
1032:model checking
1013:Büchi automata
1004:
1001:
984:
981:
978:
975:
972:
969:
966:
963:
960:
957:
954:
951:
948:
945:
940:
937:
933:
929:
924:
921:
917:
913:
908:
905:
902:
899:
896:
893:
890:
886:
882:
879:
876:
873:
870:
867:
864:
847:characters of
836:
833:
830:
827:
824:
821:
777:
774:
771:
768:
765:
762:
759:
756:
732:
729:
726:
691:
690:
679:
676:
673:
670:
662:
659:
656:
653:
645:
642:
626:
622:
618:
615:
612:
606:
602:
598:
594:
590:
586:
583:
580:
577:
574:
571:
568:
565:
562:
538:
534:
529:
525:
521:
516:
512:
508:
505:
486:
483:
482:
481:
466:
463:
390:
387:
365:
362:
350:
347:
343:
304:
300:
296:
293:
282:
279:
252:
249:
218:
210:
207:
178:
133:
130:
122:ordinal number
96:theory within
88:
87:
42:
40:
33:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1118:
1107:
1104:
1102:
1099:
1098:
1096:
1086:
1082:
1078:
1075:
1071:
1067:
1063:
1059:
1056:
1053:
1049:
1045:
1042:
1041:
1037:
1035:
1033:
1029:
1025:
1020:
1018:
1014:
1010:
1002:
1000:
999:is a metric.
998:
979:
976:
973:
967:
964:
958:
955:
952:
946:
943:
938:
935:
931:
927:
922:
919:
915:
911:
903:
900:
897:
888:
884:
880:
874:
871:
868:
862:
854:
850:
831:
828:
825:
811:
807:
803:
799:
795:
791:
775:
772:
766:
763:
760:
754:
746:
730:
727:
724:
716:
713:over sets of
712:
708:
704:
700:
696:
671:
660:
654:
643:
640:
624:
616:
613:
610:
600:
592:
588:
578:
572:
569:
566:
560:
553:
552:
551:
527:
519:
514:
506:
503:
496:
492:
484:
461:
450:
446:
442:
438:
434:
430:
426:
422:
417:
413:
407:
403:
399:
395:
391:
388:
385:
381:
378:
374:
370:
366:
363:
348:
332:
328:
324:
320:
302:
294:
283:
280:
277:
273:
269:
265:
261:
257:
253:
250:
246:
242:
236:
232:
227:
223:
219:
216:
215:
214:
208:
206:
204:
200:
195:
193:
167:
163:
159:
155:
151:
147:
143:
139:
131:
129:
127:
123:
119:
115:
111:
107:
103:
102:infinite word
99:
95:
84:
81:
73:
63:
59:
53:
52:
46:
41:
32:
31:
19:
18:Infinite word
1084:
1073:
1066:G. Rozenberg
1038:Bibliography
1021:
1006:
996:
852:
848:
809:
805:
801:
797:
793:
789:
744:
715:real numbers
706:
702:
698:
694:
692:
491:metric space
488:
448:
444:
440:
436:
432:
428:
424:
420:
415:
411:
405:
401:
397:
396:, an ω-word
393:
383:
376:
372:
368:
330:
326:
322:
275:
271:
267:
263:
259:
255:
244:
240:
234:
230:
225:
221:
212:
201:over Σ is a
198:
196:
191:
165:
161:
157:
153:
149:
145:
141:
135:
113:
101:
91:
76:
70:October 2015
67:
48:
1072:, editors,
1058:Staiger, L.
1015:. Thus the
319:Kleene star
62:introducing
1095:Categories
1083:, editor,
1070:A. Salomaa
1048:Pin, J.-E.
1044:Perrin, D.
400:is in the
209:Operations
148:of length
114:ω-language
45:references
1024:power set
936:−
920:−
912:≤
889:−
881:≤
661:∩
644:∈
625:∗
621:Σ
617:∈
611:∣
593:−
533:→
528:ω
524:Σ
520:×
515:ω
511:Σ
465:→
346:→
303:ω
295:⋅
112:, and an
995:. Hence
421:infinite
364:Prefixes
106:sequence
747:and so
711:infimum
709:is the
705:), and
693:where |
228:, both
110:symbols
58:improve
1064:". In
638:
630:
495:metric
419:is an
380:prefix
377:finite
205:of Σ.
203:subset
142:finite
47:, but
717:. If
410:Pref(
402:limit
389:Limit
116:is a
100:, an
1068:and
1046:and
851:and
804:and
800:and
792:and
665:Pref
648:Pref
550:as:
414:) ∩
367:Let
268:only
254:Let
238:and
224:and
892:min
820:min
707:inf
634:and
582:inf
451:or
437:and
404:of
382:of
192:and
118:set
92:In
1097::
1034:.
435:,
325:,
276:KL
243:∩
233:∪
152:,
128:.
1060:"
1050:"
997:d
983:)
980:u
977:,
974:v
971:(
968:d
965:+
962:)
959:v
956:,
953:w
950:(
947:d
944:=
939:n
932:2
928:+
923:m
916:2
907:}
904:n
901:,
898:m
895:{
885:2
878:)
875:u
872:,
869:w
866:(
863:d
853:u
849:w
835:}
832:n
829:,
826:m
823:{
810:n
806:u
802:v
798:m
794:v
790:w
776:0
773:=
770:)
767:v
764:,
761:w
758:(
755:d
745:x
731:v
728:=
725:w
703:x
699:x
695:x
678:}
675:)
672:v
669:(
658:)
655:w
652:(
641:x
614:x
605:|
601:x
597:|
589:2
585:{
579:=
576:)
573:v
570:,
567:w
564:(
561:d
537:R
507::
504:d
480:.
462:L
449:L
445:L
441:w
433:n
429:L
425:n
416:L
412:w
406:L
398:w
394:L
386:.
384:w
373:w
369:w
361:.
349:L
342:N
331:L
327:L
323:L
299:)
292:(
278:.
272:L
264:K
260:K
256:L
245:M
241:L
235:M
231:L
226:M
222:L
199:L
177:N
166:i
162:i
158:n
154:w
150:n
146:w
83:)
77:(
72:)
68:(
54:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.