128:
32:
73:
674:
Program ranksort declare n: integer, A,R: array of integer initially n = 15 # <|| i : 0 <= i < n :: A, R = rand() % 100, i > assign <|| i : 0 <= i < n :: R := <+ j : 0 <= j < n and (A < A or (A =
555:
Program bubblesort declare n: integer, A: array of integer initially n = 20 # <|| i : 0 <= i and i < n :: A = rand() % 100 > assign <# k : 0 <= k < 2 :: <|| i : i % 2 = k and 0 <= i < n - 1 ::
925:
Program shortestpath2 declare n: integer, D: array of integer initially n = 10 # <|| i,j : 0 <= i < n and 0 <= j < n :: D = rand() % 10 > assign <|| i,j : 0 <= i < n and 0 <= j < n :: D := min(D,
795:
Program shortestpath declare n,k: integer, D: array of integer initially n = 10 # k = 0 # <|| i,j : 0 <= i < n and 0 <= j < n :: D = rand() % 100 > assign <|| i,j : 0 <= i < n and 0 <= j < n ::
285:
way until statements cease to cause changes during execution. This allows for programs to run indefinitely, such as auto-pilot or power plant safety systems, as well as programs that would normally terminate (which here converge to a
920:
839:
597:
875:
790:
754:
669:
633:
478:
91:
718:
507:
442:
413:
1046:
1017:
546:
991:
971:
947:
45:
1074:
192:
164:
229:
211:
109:
59:
51:
149:
142:
171:
178:
299:
684:
282:
160:
675:
A and j < i)) :: 1 > > # <|| i : 0 <= i < n :: A] := A > end
138:
278:
880:
287:
20:
802:
688:
185:
567:
844:
759:
723:
638:
602:
447:
274:
386:
the array by comparing adjacent numbers, and swapping them if they are in the wrong order. Using
694:
483:
418:
389:
1022:
996:
519:
976:
956:
932:
799:
We can do this even faster. The following programs computes all pairs shortest path in
246:
1068:
250:
383:
127:
19:
This article is about the 1988 theoretical language. For other uses, see
796:
D := min(D, D + D) > || k := k + 1 if k < n - 1 end
16:
Theoretical programming language for describing concurrent computations
330:, where x and y are chosen randomly among the values that satisfy
926:<min k : 0 <= k < n :: D + D >) > end
556:
A, A := A, A if A > A > > end
306:. A statement can consist of multiple assignments, of the form
691:
algorithm, we include intermediate nodes iteratively, and get
121:
66:
25:
87:
1025:
999:
979:
959:
935:
883:
847:
805:
762:
726:
697:
641:
605:
570:
522:
486:
450:
421:
392:
82:
may be too technical for most readers to understand
1040:
1011:
985:
965:
941:
914:
869:
833:
784:
748:
712:
663:
627:
591:
540:
501:
472:
436:
407:
257:. It is a theoretical language which focuses on
953:contains the length of the shortest path from
8:
535:
523:
60:Learn how and when to remove these messages
1024:
998:
978:
958:
934:
894:
882:
858:
846:
816:
804:
773:
761:
737:
725:
696:
652:
640:
616:
604:
569:
521:
485:
461:
449:
420:
391:
312:a := x || b := y || c := z
245:is a programming language constructed by
230:Learn how and when to remove this message
212:Learn how and when to remove this message
110:Learn how and when to remove this message
94:, without removing the technical details.
1057:K. Mani Chandy and Jayadev Misra (1988)
480:expected work. The reason you only have
148:Please improve this article by adding
1059:Parallel Program Design: A Foundation
273:. The language contains no method of
255:Parallel Program Design: A Foundation
92:make it understandable to non-experts
7:
915:{\displaystyle \Theta (n^{3}\log n)}
834:{\displaystyle \Theta (\log ^{2}n)}
1075:Experimental programming languages
884:
848:
806:
763:
727:
698:
642:
606:
571:
487:
451:
422:
393:
14:
161:"UNITY" programming language
41:This article has multiple issues.
548:. This can be fixed by flipping
126:
71:
30:
1019:. In the next round, of length
592:{\displaystyle \Theta (\log n)}
516:is always chosen randomly from
354:is executed simultaneously for
49:or discuss these issues on the
909:
887:
870:{\displaystyle \Theta (n^{3})}
864:
851:
828:
809:
785:{\displaystyle \Theta (n^{3})}
779:
766:
749:{\displaystyle \Theta (n^{2})}
743:
730:
707:
701:
664:{\displaystyle \Theta (n^{2})}
658:
645:
628:{\displaystyle \Theta (n^{2})}
622:
609:
599:time with rank-sort. You need
586:
574:
496:
490:
473:{\displaystyle \Theta (n^{2})}
467:
454:
431:
425:
402:
396:
1:
150:secondary or tertiary sources
1091:
713:{\displaystyle \Theta (n)}
502:{\displaystyle \Theta (n)}
437:{\displaystyle \Theta (n)}
408:{\displaystyle \Theta (n)}
18:
1041:{\displaystyle 0\dots 2r}
316:quantified statement list
1012:{\displaystyle 0\dots r}
685:Floyd–Warshall algorithm
679:Floyd–Warshall algorithm
541:{\displaystyle \{0,1\}}
302:, and are separated by
1042:
1013:
987:
967:
943:
916:
871:
835:
786:
750:
714:
665:
629:
593:
542:
503:
474:
438:
409:
314:. You can also have a
137:relies excessively on
1043:
1014:
988:
968:
944:
917:
872:
836:
787:
751:
715:
666:
630:
594:
543:
504:
475:
439:
410:
336:quantified assignment
1023:
997:
977:
957:
933:
881:
845:
803:
760:
724:
695:
639:
603:
568:
520:
484:
448:
419:
390:
635:processors, and do
308:a,b,c := x,y,z
298:All statements are
1038:
1009:
983:
963:
939:
912:
867:
831:
782:
746:
710:
661:
625:
589:
538:
499:
470:
434:
405:
340:<|| x,y :
986:{\displaystyle j}
966:{\displaystyle i}
942:{\displaystyle r}
320:<# x,y :
240:
239:
232:
222:
221:
214:
196:
120:
119:
112:
64:
1082:
1047:
1045:
1044:
1039:
1018:
1016:
1015:
1010:
992:
990:
989:
984:
972:
970:
969:
964:
952:
948:
946:
945:
940:
921:
919:
918:
913:
899:
898:
876:
874:
873:
868:
863:
862:
840:
838:
837:
832:
821:
820:
791:
789:
788:
783:
778:
777:
755:
753:
752:
747:
742:
741:
719:
717:
716:
711:
670:
668:
667:
662:
657:
656:
634:
632:
631:
626:
621:
620:
598:
596:
595:
590:
564:You can sort in
551:
547:
545:
544:
539:
515:
508:
506:
505:
500:
479:
477:
476:
471:
466:
465:
443:
441:
440:
435:
414:
412:
411:
406:
365:
361:
349:
329:
313:
309:
305:
283:nondeterministic
235:
228:
217:
210:
206:
203:
197:
195:
154:
130:
122:
115:
108:
104:
101:
95:
75:
74:
67:
56:
34:
33:
26:
21:Unity § Software
1090:
1089:
1085:
1084:
1083:
1081:
1080:
1079:
1065:
1064:
1054:
1021:
1020:
995:
994:
975:
974:
955:
954:
950:
931:
930:
927:
890:
879:
878:
877:processors and
854:
843:
842:
812:
801:
800:
797:
769:
758:
757:
756:processors and
733:
722:
721:
693:
692:
681:
676:
648:
637:
636:
612:
601:
600:
566:
565:
562:
557:
549:
518:
517:
513:
482:
481:
457:
446:
445:
444:processors and
417:
416:
415:expected time,
388:
387:
381:
376:
363:
359:
339:
338:is similar. In
319:
311:
307:
303:
296:
253:for their book
236:
225:
224:
223:
218:
207:
201:
198:
155:
153:
147:
143:primary sources
131:
116:
105:
99:
96:
88:help improve it
85:
76:
72:
35:
31:
24:
17:
12:
11:
5:
1088:
1086:
1078:
1077:
1067:
1066:
1063:
1062:
1053:
1050:
1037:
1034:
1031:
1028:
1008:
1005:
1002:
982:
962:
938:
924:
911:
908:
905:
902:
897:
893:
889:
886:
866:
861:
857:
853:
850:
830:
827:
824:
819:
815:
811:
808:
794:
781:
776:
772:
768:
765:
745:
740:
736:
732:
729:
709:
706:
703:
700:
680:
677:
673:
660:
655:
651:
647:
644:
624:
619:
615:
611:
608:
588:
585:
582:
579:
576:
573:
561:
558:
554:
537:
534:
531:
528:
525:
512:time, is that
498:
495:
492:
489:
469:
464:
460:
456:
453:
433:
430:
427:
424:
404:
401:
398:
395:
380:
377:
375:
372:
295:
292:
277:, and program
247:K. Mani Chandy
238:
237:
220:
219:
134:
132:
125:
118:
117:
100:September 2011
79:
77:
70:
65:
39:
38:
36:
29:
15:
13:
10:
9:
6:
4:
3:
2:
1087:
1076:
1073:
1072:
1070:
1060:
1056:
1055:
1051:
1049:
1048:, and so on.
1035:
1032:
1029:
1026:
1006:
1003:
1000:
980:
960:
936:
923:
906:
903:
900:
895:
891:
859:
855:
825:
822:
817:
813:
793:
774:
770:
738:
734:
704:
690:
689:shortest path
686:
678:
672:
653:
649:
617:
613:
583:
580:
577:
559:
553:
532:
529:
526:
511:
493:
462:
458:
428:
399:
385:
378:
373:
371:
369:
366:that satisfy
357:
353:
347:
343:
337:
333:
327:
323:
317:
301:
293:
291:
289:
284:
280:
276:
272:
268:
264:
261:, instead of
260:
256:
252:
251:Jayadev Misra
248:
244:
234:
231:
216:
213:
205:
194:
191:
187:
184:
180:
177:
173:
170:
166:
163: –
162:
158:
157:Find sources:
151:
145:
144:
140:
135:This article
133:
129:
124:
123:
114:
111:
103:
93:
89:
83:
80:This article
78:
69:
68:
63:
61:
54:
53:
48:
47:
42:
37:
28:
27:
22:
1058:
929:After round
928:
841:time, using
798:
720:time, using
682:
563:
509:
382:
367:
355:
351:
345:
341:
335:
331:
325:
321:
315:
297:
275:flow control
270:
266:
262:
258:
254:
242:
241:
226:
208:
199:
189:
182:
175:
168:
156:
136:
106:
97:
81:
57:
50:
44:
43:Please help
40:
384:Bubble sort
379:Bubble sort
300:assignments
294:Description
288:fixed point
1052:References
993:of length
687:all pairs
683:Using the
552:manually.
368:expression
342:expression
332:expression
322:expression
279:statements
172:newspapers
139:references
46:improve it
1030:…
1004:…
904:
885:Θ
849:Θ
823:
807:Θ
764:Θ
728:Θ
699:Θ
643:Θ
607:Θ
581:
572:Θ
560:Rank-sort
488:Θ
452:Θ
423:Θ
394:Θ
358:pairs of
352:statement
346:statement
344: ::
326:statement
324: ::
281:run in a
202:July 2019
52:talk page
1069:Category
510:expected
374:Examples
186:scholar
86:Please
922:work.
792:work.
671:work.
188:
181:
174:
167:
159:
310:, or
263:where
243:UNITY
193:JSTOR
179:books
362:and
348:>
334:. A
328:>
267:when
259:what
249:and
165:news
973:to
901:log
814:log
578:log
356:all
290:).
271:how
269:or
141:to
90:to
1071::
949:,
370:.
350:,
318:,
265:,
152:.
55:.
1061:.
1036:r
1033:2
1027:0
1007:r
1001:0
981:j
961:i
951:D
937:r
910:)
907:n
896:3
892:n
888:(
865:)
860:3
856:n
852:(
829:)
826:n
818:2
810:(
780:)
775:3
771:n
767:(
744:)
739:2
735:n
731:(
708:)
705:n
702:(
659:)
654:2
650:n
646:(
623:)
618:2
614:n
610:(
587:)
584:n
575:(
550:k
536:}
533:1
530:,
527:0
524:{
514:k
497:)
494:n
491:(
468:)
463:2
459:n
455:(
432:)
429:n
426:(
403:)
400:n
397:(
364:y
360:x
304:#
233:)
227:(
215:)
209:(
204:)
200:(
190:·
183:·
176:·
169:·
146:.
113:)
107:(
102:)
98:(
84:.
62:)
58:(
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.