Discrete algorithmic processes: real time, parallelism, complexity, languages

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Рұқсат ақылы немесе тек жазылушылар үшін

Аннотация

Models and languages for descriptions and control of real time execution of discrete algorithmic processes are considered in the paper. Processes are divided into two groups: free and of real time processes. New operations for composition of parallel processes and language for their descriptions are proposed. The methods of parallel processes complexity evaluation are introduced.

Толық мәтін

Рұқсат жабық

Авторлар туралы

V. Kutepov

National Research University “Moscow Power Engineering Institute”

Хат алмасуға жауапты Автор.
Email: kutepov@appmat.ru
Ресей, Moscow

Әдебиет тізімі

  1. Agha G., Mason I., Smith S. Talcott C. Towards a Theory of Actor Computations// Third International Conf. on Concurrency Theory (CONCUR ‘92). Springer-Verlag, 1992. P. 565–579.
  2. Вальковский В.А., Котов В.Е., Марчук А.Г., Миренков Н.Н. Элементы параллельного программирования // Радио и связь. 1983. 240 c.
  3. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984. 264 c.
  4. Keller R.M. Parallel Program Schemata and Maximal Parallelism // J. ACM. 1973. V.20. № 3. P. 514–537.
  5. Milner R. A Calculus of Communicating Systems // Lecture Notes in Computer Science. Springer-Verlag, 1980. P. 184.
  6. Хоар Ч. Взаимодействующие параллельные процессы. М.: Мир, 1992. 184 с.
  7. Кутепов В.П., Фальк В.Н. Функциональные системы: теоретический и практический аспекты // Кибернетика. 1979. № 1. С. 45–58.
  8. Кутепов В.П. Модели и языки для описания параллельных процессов // Изв. РАН. ТиСУ. 2018. № 3. С. 116–127.
  9. Хьюз К., Хьюз Т. Параллельное и распределенное программирование с использованием С++. М.: Вильямс, 2004. 667 с.
  10. Cesarini F., Thompson S. ERLANG Programming: a Concurrent Approach to Software Development. Sebastopol, California, O’Reilly Media, 2009. 496 p.
  11. Кутепов В.П., Шамаль П.Н. Реализация языка функционального параллельного программирования FPTL на многоядерных компьютерах // Изв. РАН. ТиСУ. № 3. С. 46–60.
  12. Кутепов В.П., Зубов М.И. Реализация и экспериментальное исследование эффективности упреждающего параллелизма // Вестн. МЭИ. 2019. № 4. C. 119–126.
  13. Кутепов В.П., Ефанов А.А. Параллельные процессы и программы: модели, языки, реализация на системах // Программные продукты и системы. 2020. Т. 33. № 3. С. 375–384.
  14. Кутепов В.П. Интеллектуальное управление процессами и загруженностью в вычислительных системах // Изв. РАН. ТиСУ. 2007. № 5. С. 58–73.
  15. Бражникова Ю.Н., Горицкий Ю.А., Кутепов В.П., Панков Н.А. Исследование методов прогнозирования загруженности компьютеров и компьютерных систем // Программные продукты и системы. 2015. № 2. С. 135–146.
  16. Кутепов В.П., Фальк В.Н. Алгоритмические параллельные процессы и их сложность // Вестн. МЭИ. 2020. № 3. С. 102–110.
  17. Apt K. Formal Justification of a Proof System for Communicating Sequential Process // J. ACM. 1983. V. 30. № 1. P. 197–216.
  18. Pnueli A. Temporal Logic of Programs // Proc. 18-th IEEE Sympos. of Foundation of Computer Science. Tel Aviv, Israel, 1977. P. 46–57.
  19. Lamport L. The Temporal Logic of Actions // ACM Transactions on Programming Languages. 1993. V. 7. № 3. P. 1–52.
  20. Stanford Encyclopedia of Philosophy. Temporal Logic. 2019. Р. 1–17. https://plato.stanford.edu/entries/logic-temporal/
  21. Allen J.F. Maintaining Knowledge About Temporal Intervals // Communications of ACM. 2010. V. 26. № 11. P. 832–843.
  22. Orgun M., Wadge W. Theory and Practice of Temporal Logic Programming // J. Logic Programming. 1992. V. 13. P. 413–440.
  23. Buchi J.R. On a Decision Method in Restricted Second Order Arithmetic // Proc. Intern. Congr. Logic, Method and Philos., Sci. Stanford University, 1960. P. 1–12.
  24. Vardi M.Y., Wolper P. Reasoning About Infinite Computations // Information and Computation. 1994. V. 115. № 1. P. 1–37.
  25. Finger M., Gabbay Dov. Adding a Temporal Dimension to a Logic System // J. Logic, Language and Information. 1992. V. 1. P. 203–233.
  26. Gabbay P., Pnueli A., Shelah S., Stavi J. On the Temporal Analysis of Fairness // The ACM Sympos. on Principles of Programming Languages. Las Vegas, 1980. P. 163–173.
  27. Клини С. Введение в метаматематику. М.: Из-во иностр. лит., 1957. 520 c.

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML
Жүктеу
2. Fig. 1. Timing diagram of absolutely parallel calculation of the value of the function 𝐹(X).

Жүктеу (65KB)
Метадеректер
3. Fig. 2. Process execution trace.

Жүктеу (68KB)
Метадеректер
4. Fig. 3. All process execution traces  X10*(p1→a1)*X11.

Жүктеу (95KB)
Метадеректер

© Russian Academy of Sciences, 2025