Inference of bounded L systems with polymorphic P systems
Tóm tắt
In this paper, we are going to solve the inference problem of bounded L systems, namely such L systems which work on filaments having length up to a fixed size. We will show that these bounded L systems have considerable computational power as they can simulate linear-bounded automata. To carry out the inference, we are going to construct a specific polymorphic P system with target indication, which can reproduce the transitions of the examined bounded L system, and which is of size
$$O(n|G|^4)$$
, where G is the alphabet of the bounded L system with n as the maximal size of the filaments.
Tài liệu tham khảo
Alhazov A, Ivanov S, Rogozhin Y. Polymorphic P systems. In: Gheorge M, Hinze T, Păun G, Rosenberg G, Salomaa A, editors. Membrane computing, vol. 6501., Lecture Notes in Computer ScienceBerlin: Springer; 2011. p. 81–94.
Alhazov A, Freund R, Ivanov S. Polymorphic P systems: a survey. IMCS Bull. 2016;2:79–102.
Ben-Naoum F. A survey on L-system inference. INFOCOMP J Comput Sci. 2009;8(3):29–39.
Bulletin of the International Membrane Computing Society (IMCS). http://membranecomputing.net/IMCSBulletin/index.php
Feliciangeli H, Herman GT. Algorithms for producing grammars from sample derivations: a common problem of formal language theory and developmental biology. J. Comput. Syst. Sci. 1973;7:97–118.
Heinz J, Sempere JM, editors. Topics in grammatical inference. Berlin: Springer; 2016.
Herman GT. Computing ability of a developmental model for filamentous organisms. J Theor Biol. 1969;25:421–35.
Higuera C. Grammatical inference: learning automata and grammars. Cambridge: Cambridge University Press; 2010.
Kozen DC. Automata and computability. Berlin: Springer; 1997.
Kuroda SY. Classes of languages and linear-bounded automata. Inf Control. 1964;7:207–23.
Landweber PS. Three theorems on phrase structure grammars of type 1. Inf Control. 1963;6:131–6.
Lindenmayer A. Mathematical models for cellular interaction in development. J Theor Biol. 1968;18:280–315.
Myhill J. Linear bounded automata. WADD Tech. Note No. 60-165. Ohio: Wright–Patterson Air Force Base; 1960.
Păun G. Computing with membranes. TUCS Report 208 (1998). J Comput Syst Sci. 2000;61(1):108–43.
Păun G. Membrane computing. An introduction. Berlin: Springer; 2002.
Păun G, Rozenberg G, Salomaa A, editors. The Oxford handbook of membrane computing. Oxford: Oxford University Press; 2010.
Rozenberg G, Salomaa A. L Systems. Berlin: Springer; 1974.
Rozenberg G, Salomaa A. The mathematical theory of L systems. London: Academic Press; 1980.
Rozenberg G, Salomaa A. The book of L. Berlin: Springer; 1986.
Rozenberg G, Salomaa A, editors. Lindenmayer systems: impacts on theoretical computer science, computer graphics, and developmental biology. Berlin: Springer; 1992.
Sempere JM, García P. Grammatical inference: theoretical results and applications. In: 10th International colloquium, ICGI 2010, Valencia; 2010.
The P systems website. http://ppage.psystems.eu/