Biến đổi đa tập hợp tuần tự và song song tối đa: khả năng đảo ngược và tính xác định

Springer Science and Business Media LLC - Tập 11 - Trang 95-106 - 2011
Artiom Alhazov1,2, Rudolf Freund3, Kenichi Morita1
1FCS, Department of Information Engineering, Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima, Japan
2Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Chişinău, Moldova
3Faculty of Informatics, Vienna University of Technology, Vienna, Austria

Tóm tắt

Chúng tôi nghiên cứu khía cạnh đảo ngược và tính xác định, cũng như các phiên bản mạnh mẽ của các thuộc tính này trong các hệ thống xử lý đa tập hợp tuần tự và hệ thống song song tối đa, từ góc độ tính toán. Trong trường hợp tuần tự, các tiêu chí cú pháp được thiết lập cho cả tính xác định mạnh và tính đảo ngược mạnh. Trong trường hợp song song, một tiêu chí được thiết lập cho tính xác định mạnh, trong khi tính đảo ngược mạnh được chỉ ra là có thể quyết định. Trong trường hợp tuần tự, không có sự kiểm soát, cả bốn lớp—xác định, xác định mạnh, có thể đảo ngược, có thể đảo ngược mạnh—đều không phổ quát, trong khi trong trường hợp song song, các hệ thống xác định là phổ quát. Khi cho phép chất ức chế, lớp đầu tiên và lớp thứ ba trở thành phổ quát trong cả hai mô hình, trong khi với các độ ưu tiên, tất cả chúng đều là phổ quát. Trong trường hợp song song tối đa, các hệ thống xác định mạnh với cả chất thúc đẩy và chất ức chế là phổ quát. Chúng tôi cũng trình bày một vài kết quả và giả thuyết cụ thể hơn.

Từ khóa

#đảo ngược #tính xác định #hệ thống xử lý đa tập hợp #song song tối đa #tính toán

Tài liệu tham khảo

Alhazov A, Freund R, Morita K (2010) Reversibility and determinism in sequential multiset rewriting. In: Calude CS, Hagiya M, Morita K, Rozenberg G, Timmis J (eds) Unconventional computation 2010, Tokyo. Lecture notes in computer science, vol 6079. Springer, New York, pp 21–31 Alhazov A, Morita K (2010) On reversibility and determinism in P systems. In: Păun G, Pérez-Jiménez MJ, Riscos-Núñez A, Rozenberg G, Salomaa A (eds) Membrane computing, 10th international workshop, WMC 2009, Curtea de Argeş, revised selected and invited papers. Lecture notes in computer science, vol 5957. pp 158–168 Bennett CH (1973) Logical reversibility of computation. IBM J Res Dev 17:525–532 Calude CS, Păun Gh (2004) Bio-steps beyond Turing. BioSystems 77:175–194 Dassow J, Păun Gh (1989) Regulated rewriting in formal language theory. In: EATCS monographs in theoretical computer science, vol 18. Springer, New York Fredkin E, Toffoli T (1982) Conservative logic. Int J Theor Phys 21:219–253 Freund R, Ibarra OH, Păun Gh, Yen H-C (2005) Matrix Languages, Register Machines, Vector Addition Systems. In: Gutiérrez-Naranjo MA, Riscos-Núñez A, Romero-Campero FJ, Sburlan D (eds) RGNC report 01/2005. Third brainstorming week on membrane computing. University of Seville, Fénix Editora, Sevilla, pp 155–168 Ibarra OH (2011) On strong reversibility in P systems and related problems. Int J Found Comput Sci 22(1):7–14 Leporati A, Zandron C, Mauri G (2006) Reversible P systems to simulate Fredkin circuits. Fundam Inform 74(4):529–548 Minsky ML (1969) Computation: finite and infinite machines. Prentice-Hall, Englewood Cliffs Morita K (1996) Universality of a reversible two-counter machine. Theor Comput Sci 168:303–320 Morita K (2001) A simple reversible logic element and cellular automata for reversible computing. In: Margenstern M, Rogozhin Yu (eds) Proceedings of 3rd international conference on machines, computations, and universality. Lecture notes in computer science, vol 2055. Springer, New York. pp 102–113 Morita K (2007) Simple universal one-dimensional reversible cellular automata. J Cell Autom 2:159–165 Morita K, Nishihara N, Yamamoto Y, Zhang Zh (1997) A hierarchy of uniquely parsable grammar classes and deterministic acceptors. Acta Inform 34(5):389–410 Morita K, Yamaguchi Y (2007) A universal reversible turing machine. In: Proceedings of 5th international conference on machines, computations, and universality. Lecture notes in computer science, vol 4664. Springer, New York, pp 90–98 Păun Gh (2002) Membrane computing. An Introduction. Springer, Berlin P Systems Webpage. http://ppage.psystems.eu/