| Title:
|
Parallel probabilistic searching and sorting algorithms (English) |
| Author:
|
Kramosil, Ivan |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
26 |
| Issue:
|
7 |
| Year:
|
1990 |
| Pages:
|
1-93 |
| . |
| Category:
|
math |
| . |
| MSC:
|
60K99 |
| MSC:
|
68P10 |
| MSC:
|
68P15 |
| MSC:
|
68Q22 |
| MSC:
|
68W15 |
| idZBL:
|
Zbl 0727.68021 |
| idMR:
|
MR1089358 |
| Note:
|
Supplement to Volume 26 (1990) of journal Kybernetika (English) |
| . |
| Date available:
|
2009-09-24T18:22:27Z |
| Last updated:
|
2013-11-20 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/124173 |
| . |
| Reference:
|
[1] M.A. Ajzerman: Logika, automaty, algoгitmy (Logic, Automata, Aîgorithms - in Czech).Academia, Prague 1971. |
| Reference:
|
[2] C Calude: Theories oí Computational Complexity.North Holland, Amsterdam 1988. MR 0919945 |
| Reference:
|
[3] M. Davis: Computability and Unsolvability.McGraw-Hill, New York 1958. Zbl 0080.00902, MR 0124208 |
| Reference:
|
[4] Z. Manna: Mathematical Theory of Computation.McGraw-Hill, New York 1974. Czech tгanslation: SNTL, Prague 1981. Zbl 0353.68066, MR 0400771 |
| Reference:
|
[5] J. Mikloško, V. E. Kotov: Algorithms, Software and Hardware of Parallel Computers.Springer-Verlag, Berlin and Veda, Bratislava 1984. MR 0785364 |
| Reference:
|
[6] H. Rogers: Theory oî Recursive Functions and Efïective Computability.McGraw-Hill, New York 1967. Russian translation: Mir, Moseow 1972. MR 0224462 |
| Reference:
|
[7] K. Wagner, G. Wechsung: Computational Complexity.VEB Deutscher Verlag der Wissenschaften, Berlin 1986. Zbl 0584.68062, MR 0831432 |
| Reference:
|
[1] V. Černý: Fyzikálne aspekty v matematickej informatike (Physical aspects in mathematical informatics - in SІovak).SOFSEM 1987, pp. 81-103. |
| Reference:
|
[2] M. Davis: Computability and Unsolvability.McGraw-Hill, New York 1958. Zbl 0080.00902, MR 0124208 |
| Reference:
|
[3] 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. |
| Reference:
|
[4] P. Halmos: Measure Theory.Van Nostrand, London, 1968. MR 0033869 |
| Reference:
|
[5] 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. |
| Reference:
|
[6] I. Кramosil: Extremum-searching hierarchicaí paralłel probabiíistic algorithms.Kybernetika (Prague) 24 (1988), 2, pp. 110-121. MR 0942378 |
| Reference:
|
[7] M. Loève: Probability Theory.Van Nostrand, Princeton, 1955. Russian translation: IIL, Moscow, 1962. MR 0140129 |
| Reference:
|
[8] A. Rényi: Teorie pravděpodobnosti (Probability Theory - in Czech).Academia, Prague 1972. MR 0350789 |
| Reference:
|
[9] J. Štěpán: Teorie pravděpodobnosti - matematické základy (Probabilíty Theory - Mathematical Foundations - in Czech).Academia, Prague 1987. |
| Reference:
|
[10] 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. |
| Reference:
|
[1] I. Kramosil: Hierarchické paralelní pravděpodobnostní algorithmy (Hierarchical Paralle Probabilistic Algorithms - in Czech).Res. Rep. No. 1409, Institute of Information Theory and Automation 1986. |
| Reference:
|
[2] I. Kramosil: Extremum-searching hierarchical parallel probabilistic algorithms.Kybernetika 24 (1988), 2, 110-121. Zbl 0647.68061, MR 0942378 |
| Reference:
|
[1] 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. MR 0243559 |
| Reference:
|
[2] I. Kramosil: Statistical verification procedures for propositional caiculus.Computers and Artificial Intelligence 2, (1983), 3, 235-258. |
| Reference:
|
[3] I. Kramosil, J. Šindelář: Computational complexity of probabilistic searching algorithms over Herbrand universes.Computers and Artifìcial Intelligence 4 (1985), 2, 97-110. |
| Reference:
|
[1] 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. MR 0243559 |
| Reference:
|
[1] 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. MR 0538444 |
| Reference:
|
[2] H. Barringer: A Survey of Verification Techniques for Parallel Programs.(Lecture Notes in Computer Science 191.) Springer-Verlag, Berlin-Heidelberg-New York 1985. MR 0794130, 10.1007/3-540-15239-3_16 |
| Reference:
|
[3] 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. MR 0243559 |
| Reference:
|
[4] I. Kramosil: Parallel probabilistic ordering algorithms with a simple conflict control strategy.In: Aplikace umele inteligence AI 88, Prague 1988, pp. 39-46. |
| Reference:
|
[5] J. Miklosko, V. E. Kotov: Algorithms, Software and Hardware of Parallel Computers.Springer-Verlag, Berlin-Heidelberg-New York and Veda, Bratislava 1984. Zbl 0594.68003, MR 0785364 |
| Reference:
|
[6] J. H. Reif: On synchronous parallel computations with independent probabilistic choice.SIAM J. Comput. 13 (1984), 1, 46-56. Zbl 0558.68038, MR 0731026, 10.1137/0213004 |
| Reference:
|
[7] R. Reischuk: A fast probabilistic parallel sorting algorithm.In: 22nd IEEE Symp. on Foundat. of Comp. Sci., Nashwille, Tennessee 1981. |
| Reference:
|
[8] R. Reischuk: Probabilistic parallel algorithms for sorting and selection.SIAM J. Comput. 14 (1985), 2, 396-409. Zbl 0578.68040, MR 0784745, 10.1137/0214030 |
| Reference:
|
[1] I. Kramosil: Hierarchies of parallel probabilistic searching algorithms with possible data access conflicts.Problems Control Inform. Theory 7^(1989), 6, 381 - 395. Zbl 0796.68067, MR 1029470 |
| Reference:
|
[2] 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. |
| Reference:
|
[1] S. G. Akl: Parallel Sorting Algorithms.Academic Press, Orlando 1985. Zbl 0657.68070, MR 0807771 |
| Reference:
|
[2] Y. Azar, U. Vishkin: Tight comparison bounds on the complexity of parallel sorting.S.AM J. Comput. 16 (1987), 3, 458-464. Zbl 0654.68070, MR 0889402, 10.1137/0216032 |
| Reference:
|
[3] P. Bachman, Phan-Mink-Dung: Nondeterministic computations - structure and axioms. Elektron.Informationsverarb. Kybernet. 22 (1986), 5-6, pp. 243-261. MR 0855528 |
| Reference:
|
[4] G. Bobrow, A. Collins (eds.): Representation and Understanding.Academic Press, New York 1975. Zbl 0332.68007 |
| Reference:
|
[5] D. J. Boxma: A probabilistic analysis of multiprocessor list scheduling: the Erlang case.Comm. Statist. Stochastic Models 1 (1985), 2, 209-220. Zbl 0605.68023, MR 0836608, 10.1080/15326348508807011 |
| Reference:
|
[6] M. Broy: On the Herbrand-Kleene universe for nondeterministic computations.Theoret. Comput. Sci. 36 (1985), 1, 1- 19. Zbl 0567.68024, MR 0792637, 10.1016/0304-3975(85)90027-1 |
| Reference:
|
[7] M. Broy: A theory for nondeterminism, parallelism, communication, and concurrency.Theoret. Comput. Sci. 45 (1986), 1, 1-61. Zbl 0601.68022, MR 0865966, 10.1016/0304-3975(86)90040-X |
| Reference:
|
[8] C. L. Chang, R. T. C. Lee: Symbolic Logic and Mechanical Theorem Proving.Academic Press, New York-London 1974 (Russian translation: Mir, Moscow 1982). |
| Reference:
|
[9] A. Church: Introduction to Mathematical Logic I.Princeton Univ. Press, Princeton, New Jersey 1956 (Russian translation: ILL, Moscow 1960). Zbl 0073.24301, MR 0010511 |
| Reference:
|
[10] R. Davis, D. B. Lenat: Knowledge-Based Systems in Artificial Intelligence.McGraw-Hill, New York 1982. Zbl 0479.68093 |
| Reference:
|
[11] J. Gill: Computational complexity of probabilistic Turing machines.SIAM J. Comput. 6 (1977), 4, 675-695. Zbl 0366.02024, MR 0464691, 10.1137/0206049 |
| Reference:
|
[12] M. Karmarkar R. M. Karp G. S. Lueker, A. M. Odlyzko: Probabilistic analysis of optimum partitioning.J. Appl. Probab. 23 (1986), 3, 626-645. MR 0855370, 10.2307/3214002 |
| Reference:
|
[13] 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. MR 0834184 |
| Reference:
|
[14] L. Kronsjó: Computational Complexity of Sequential and Parallel Algorithms.J. Wiley and Sons, Chichester 1985. MR 0835710 |
| Reference:
|
[15] L. Kučera: Kombinatorické algoritmy.(Combinatorial Algorithms - in Czech). SNTL, Prague 1983. |
| Reference:
|
[16] M. Luby: A simple parallel algorithm for the maximal independent set problem.SIAM J. Comput. 15 (1986), 4, 1036- 1053. Zbl 0619.68058, MR 0861369, 10.1137/0215074 |
| Reference:
|
[17] Z. Manna, R. Waldinger: Special relations in automated deduction.J. Assoc. Comput. Mach. 33 (1986), 1, 1-59. Zbl 0637.68103, MR 0820098, 10.1145/4904.4905 |
| Reference:
|
[18] 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. |
| Reference:
|
[19] D. Mitra: Probabilistic models and asymptotic results for concurrent processing with exclusive and non-exclusive locks.SIAM J. Comput. 14 (1985), 4, 1030-1051. Zbl 0582.68062, MR 0807898, 10.1137/0214072 |
| Reference:
|
[20]
: Parallelnaja obrabotka informacii, vol. 2.(Parallel Information Processing - a collection of papers - in Russian). Nauková dumka, Kijev 1985. |
| Reference:
|
[21]
: 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. |
| Reference:
|
[22] 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. |
| Reference:
|
[23] J. R. Shoenfield: Mathematical Logic.Addison-Wesley, Reading 1967 (Russian translation: Nauka, Moscow 1975). Zbl 0155.01102, MR 0225631 |
| Reference:
|
[24] J. R. Smith: Parallel algorithms for depth-first searches - planar graphs.SIAM J. Comput. 75 (1986), 3, 814-830. MR 0850425, 10.1137/0215058 |
| Reference:
|
[25] J. Sztrik: A probability model for priority processor-shared multiprogrammed computer systems.Acta Cybernet. 7 (1986), 3, 329-340. Zbl 0587.68035, MR 0829312 |
| Reference:
|
[26] Wang Hao: A Survey of Symbolic Logic.North-Holland, Amsterdam and China Press, Peking 1962. |
| Reference:
|
[27] D. A. Watermann, L. Hayes-Roth (eds.): Pattern-Directed Interference Systems.Academic Press, New York 1978. MR 0471483 |
| Reference:
|
[28] 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. MR 0875694 |
| Reference:
|
[29] M. Zaionc: Nondeterministic programs definable in typed lambda-calculus.Fundam. Informaticae 8 (1985), 1, 63-72. Zbl 0579.68022, MR 0794566 |
| . |
