Parallel probabilistic searching and sorting algorithms

 Access to full text

 Full (PDF)

1. M.A. Ajzerman, Logika, automaty, algoгitmy (Logic, Automata, Aîgorithms - in Czech), Academia, Prague 1971. (1971) 
2. C Calude, Theories oí Computational Complexity, North Holland, Amsterdam 1988. (1988) MR0919945
3. M. Davis, Computability and Unsolvability, McGraw-Hill, New York 1958. (1958) Zbl0080.00902MR0124208
4. Z. Manna, Mathematical Theory of Computation, McGraw-Hill, New York 1974. Czech tгanslation: SNTL, Prague 1981. (1974) Zbl0353.68066MR0400771
5. J. Mikloško, V. E. Kotov, Algorithms, Software and Hardware of Parallel Computers, Springer-Verlag, Berlin and Veda, Bratislava 1984. (1984) MR0785364
6. H. Rogers, Theory oî Recursive Functions and Efïective Computability, McGraw-Hill, New York 1967. Russian translation: Mir, Moseow 1972. (1967) MR0224462
7. K. Wagner, G. Wechsung, Computational Complexity, VEB Deutscher Verlag der Wissenschaften, Berlin 1986. (1986) Zbl0584.68062MR0831432
8. V. Černý, Fyzikálne aspekty v matematickej informatike (Physical aspects in mathematical informatics - in SІovak), SOFSEM 1987, pp. 81-103. (1987) 
9. M. Davis, Computability and Unsolvability, McGraw-Hill, New York 1958. (1958) Zbl0080.00902MR0124208
10. W. Feller, An Introduction to ProbabШty Theory and its Applications, I, II, J. Wiley and Sons, New York 1957 (vol.I, 2nd edition), 1966 (vol. II). Russian translation: Mir, Moscow 1964, 1967. (1957) 
11. P. Halmos, Measure Theory, Van Nostrand, London, 1968. (1968) MR0033869
12. I. Kramosil, Paralelní pravděpodobnostní algoritmy jako prezentace nového paradigmatu ve znalostních systémech (Parallel probabilistic algorithms as presentation of new paradigma in knowledge systems - in Czech), In: Uplatnění expertníeh - znalostních systémů ve stavebnictví, Prague 1987, pp. 6 - 23. (1987) 
13. I. Кramosil, Extremum-searching hierarchicaí paralłel probabiíistic algorithms, Kybernetika (Prague) 24 (1988), 2, pp. 110-121. (1988) MR0942378
14. M. Loève, Probability Theory, Van Nostrand, Princeton, 1955. Russian translation: IIL, Moscow, 1962. (1955) MR0140129
15. A. Rényi, Teorie pravděpodobnosti (Probability Theory - in Czech), Academia, Prague 1972. (1972) MR0350789
16. J. Štěpán, Teorie pravděpodobnosti - matematické základy (Probabilíty Theory - Mathematical Foundations - in Czech), Academia, Prague 1987. (1987) 
17. V. A. Uspenskij, A. L. Semenov, What are the gains of the theory of algorithms - basic development connected with the concept of aígorithm and with its application in mathematics, In: Algorithm in Modern Mathematics and its Appîications - Proceedings of the Symposium, Urgench 1979, pp. 100-234. (1979) 
18. I. Kramosil, Hierarchické paralelní pravděpodobnostní algorithmy (Hierarchical Paralle Probabilistic Algorithms - in Czech), Res. Rep. No. 1409, Institute of Information Theory and Automation 1986. (1986) 
19. I. Kramosil, Extremum-searching hierarchical parallel probabilistic algorithms, Kybernetika 24 (1988), 2, 110-121. (1988) Zbl0647.68061MR0942378
20. W. Feller, An Introduction to Probability Theory and its Applications I, II, J. Wiley and Sons, New York, 1957 (vol. I, 2nd edition), 1966 (vol. II). Russian transíation: Mir, Moscovv, 1964, 1967. (1957) MR0243559
21. I. Kramosil, Statistical verification procedures for propositional caiculus, Computers and Artificial Intelligence 2, (1983), 3, 235-258. (1983) 
22. I. Kramosil, J. Šindelář, Computational complexity of probabilistic searching algorithms over Herbrand universes, Computers and Artifìcial Intelligence 4 (1985), 2, 97-110. (1985) 
23. W. Feller, An Introduction to Probability Theory and Its Applications I, II, J. Wiley and Sons, New York 1957 (vol. I, 2nd edition), 1966 (vol. II). Russian translation: Mir, Moscow 1964, 1967. (1957) MR0243559
24. A. V. Aho J. E. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading 1974. Russian translation: Mir, Moscow 1979. (1974) MR0538444
25. H. Barringer, 10.1007/3-540-15239-3_16, (Lecture Notes in Computer Science 191.) Springer-Verlag, Berlin-Heidelberg-New York 1985. (191.) MR0794130DOI10.1007/3-540-15239-3_16
26. W. Feller, An Introduction to Probability Theory and its Applications I., II, J. Wiley and Sons, New York 1957 (vol. I, 2nd edition), 1966 (vol. II). Russian translation: Mir, Moscow 1964, 1967. (1957) MR0243559
27. I. Kramosil, Parallel probabilistic ordering algorithms with a simple conflict control strategy, In: Aplikace umele inteligence AI 88, Prague 1988, pp. 39-46. (1988) 
28. J. Miklosko, V. E. Kotov, Algorithms, Software and Hardware of Parallel Computers, Springer-Verlag, Berlin-Heidelberg-New York and Veda, Bratislava 1984. (1984) Zbl0594.68003MR0785364
29. J. H. Reif, 10.1137/0213004, SIAM J. Comput. 13 (1984), 1, 46-56. (1984) Zbl0558.68038MR0731026DOI10.1137/0213004
30. R. Reischuk, A fast probabilistic parallel sorting algorithm, In: 22nd IEEE Symp. on Foundat. of Comp. Sci., Nashwille, Tennessee 1981. (1981) 
31. R. Reischuk, 10.1137/0214030, SIAM J. Comput. 14 (1985), 2, 396-409. (1985) Zbl0578.68040MR0784745DOI10.1137/0214030
32. I. Kramosil, Hierarchies of parallel probabilistic searching algorithms with possible data access conflicts, Problems Control Inform. Theory 7^(1989), 6, 381 - 395. (1989) Zbl0796.68067MR1029470
33. I. Kramosil, A simulation of partial stochastic co-operation in parallel probabilistic searching algorithms, In: Artificial Intelligence and Information-Control Systems of Robots 89 - Proceedings of the conference held at Strbske Pleso, 6.- 10. 11. 1989 (I. Plander, ed.), North Holland, Amsterdam 1989, pp. 159-162. (1989) 
34. S. G. Akl, Parallel Sorting Algorithms, Academic Press, Orlando 1985. (1985) Zbl0657.68070MR0807771
35. Y. Azar, U. Vishkin, 10.1137/0216032, S.AM J. Comput. 16 (1987), 3, 458-464. (1987) Zbl0654.68070MR0889402DOI10.1137/0216032
36. P. Bachman, Phan-Mink-Dung, Nondeterministic computations - structure and axioms. Elektron, Informationsverarb. Kybernet. 22 (1986), 5-6, pp. 243-261. (1986) MR0855528
37. G. Bobrow, A. Collins (eds.), Representation and Understanding, Academic Press, New York 1975. (1975) Zbl0332.68007
38. D. J. Boxma, 10.1080/15326348508807011, Comm. Statist. Stochastic Models 1 (1985), 2, 209-220. (1985) Zbl0605.68023MR0836608DOI10.1080/15326348508807011
39. M. Broy, 10.1016/0304-3975(85)90027-1, Theoret. Comput. Sci. 36 (1985), 1, 1- 19. (1985) Zbl0567.68024MR0792637DOI10.1016/0304-3975(85)90027-1
40. M. Broy, 10.1016/0304-3975(86)90040-X, Theoret. Comput. Sci. 45 (1986), 1, 1-61. (1986) Zbl0601.68022MR0865966DOI10.1016/0304-3975(86)90040-X
41. C. L. Chang, R. T. C. Lee, Symbolic Logic and Mechanical Theorem Proving, Academic Press, New York-London 1974 (Russian translation: Mir, Moscow 1982). (1974) 
42. A. Church, Introduction to Mathematical Logic I, Princeton Univ. Press, Princeton, New Jersey 1956 (Russian translation: ILL, Moscow 1960). (1956) Zbl0073.24301MR0010511
43. R. Davis, D. B. Lenat, Knowledge-Based Systems in Artificial Intelligence, McGraw-Hill, New York 1982. (1982) Zbl0479.68093
44. J. Gill, 10.1137/0206049, SIAM J. Comput. 6 (1977), 4, 675-695. (1977) Zbl0366.02024MR0464691DOI10.1137/0206049
45. M. Karmarkar R. M. Karp G. S. Lueker, A. M. Odlyzko, 10.2307/3214002, J. Appl. Probab. 23 (1986), 3, 626-645. (1986) MR0855370DOI10.2307/3214002
46. G. A. P. Kindervater, J. K. Lenstra, An introduction to parallelism in combinatorial optimization, In: Parallel Computers and Computations, CWI Syllabi 9, Math. Centrum Amsterdam, 1985, pp. 163-184. (1985) MR0834184
47. L. Kronsjó, Computational Complexity of Sequential and Parallel Algorithms, J. Wiley and Sons, Chichester 1985. (1985) MR0835710
48. L. Kučera, Kombinatorické algoritmy , (Combinatorial Algorithms - in Czech). SNTL, Prague 1983. (1983) 
49. M. Luby, 10.1137/0215074, SIAM J. Comput. 15 (1986), 4, 1036- 1053. (1986) Zbl0619.68058MR0861369DOI10.1137/0215074
50. Z. Manna, R. Waldinger, 10.1145/4904.4905, J. Assoc. Comput. Mach. 33 (1986), 1, 1-59. (1986) Zbl0637.68103MR0820098DOI10.1145/4904.4905
51. A. N. Maslov, Verojatnostnyje mašiny Turinga i rekursivnyje funkcii, (Probabilistic Turing machines and recursive functions - in Russian). Dokl. Akad. Nauk SSSR 203 (1972), 5, 1018-1020. (1972) 
52. D. Mitra, 10.1137/0214072, SIAM J. Comput. 14 (1985), 4, 1030-1051. (1985) Zbl0582.68062MR0807898DOI10.1137/0214072
53. Parallelnaja obrabotka informacii, vol. 2, (Parallel Information Processing - a collection of papers - in Russian). Nauková dumka, Kijev 1985. (1985) 
54. Sborník: Expertní systémy - principy, realizace, využití, (Proceedings: Expert Systems - principles, realizations, applications, V. Zdráhal, V. Mařík, eds.). ČSVTS FEL ČVUT, Prague 1984. (1984) 
55. Sborník, Metody umělé inteligence a expertní systémy, (Proceedings: Methods of Artificial Intelligence and Expert Systems, Z. Zdráhal, V. Mařík, eds.). ČSVTS FEL ČVUT, Prague 1985. (1985) 
56. J. R. Shoenfield, Mathematical Logic, Addison-Wesley, Reading 1967 (Russian translation: Nauka, Moscow 1975). (1967) Zbl0155.01102MR0225631
57. J. R. Smith, 10.1137/0215058, SIAM J. Comput. 75 (1986), 3, 814-830. (1986) MR0850425DOI10.1137/0215058
58. J. Sztrik, A probability model for priority processor-shared multiprogrammed computer systems, Acta Cybernet. 7 (1986), 3, 329-340. (1986) Zbl0587.68035MR0829312
59. Wang Hao, A Survey of Symbolic Logic, North-Holland, Amsterdam and China Press, Peking 1962. (1962) 
60. D. A. Watermann, L. Hayes-Roth (eds.), Pattern-Directed Interference Systems, Academic Press, New York 1978. (1978) MR0471483
61. G. Winskel, Category theory and models for parallel computations, In: Category Theory and Computer Programming (Lecture Notes in Comp. Sci. 240), Springer-Verlag, Berlin-Heidelberg-New York 1987, pp. 266-281. (1987) MR0875694
62. M. Zaionc, Nondeterministic programs definable in typed lambda-calculus, Fundam. Informaticae 8 (1985), 1, 63-72. (1985) Zbl0579.68022MR0794566