We consider conditional tabled Lindenmayer sytems without interaction, where each table is associated with a regular set and a table can only be applied to a sentential form which is contained in its associated regular set. We study the effect to the generative power, if we use instead of arbitrary regular languages only finite, nilpotent, monoidal, combinational, definite, ordered, union-free, star-free, strictly locally testable, commutative regular, circular regular, and suffix-closed regular languages. Essentially, we prove that the hierarchy of language families obtained from conditional Lindenmayer systems with subregular conditions is almost identical to the hierarchy of families of subregular languages.
@article{ITA_2014__48_1_127_0,
author = {Dassow, J\"urgen and Rudolf, Stefan},
title = {Conditional Lindenmayer systems with subregular conditions: The non-extended case},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {48},
year = {2014},
pages = {127-147},
doi = {10.1051/ita/2014007},
mrnumber = {3195792},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2014__48_1_127_0}
}
Dassow, Jürgen; Rudolf, Stefan. Conditional Lindenmayer systems with subregular conditions: The non-extended case. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) pp. 127-147. doi : 10.1051/ita/2014007. http://gdmltest.u-ga.fr/item/ITA_2014__48_1_127_0/
[1] , , and , Solving NP-Complete Problems With Networks of Evolutionary Processors. IWANN'01: Proc. of the 6th International Work-Conference on Artificial and Natural Neural Networks. Vol. 2084 of Lect. Notes Comput. Sci. Springer-Verlag, Berlin (2001) 621-628. | Zbl 0982.68767
[2] and , Networks of Parallel Language Processors. New Trends in Formal Languages. Vol. 1218 of Lect. Notes Comput. Sci. Springer-Verlag, Berlin (1997) 299-318. | MR 1605238
[3] and , Tree controlled grammars. Comput. 19 (1977) 129-139. New Trends in Formal Languages - Control, Cooperation, and Combinatorics. Vol.1218 of Lect. Notes Comput. Sci. Springer-Verlag Berlin (1997) 299-318. | MR 464718 | Zbl 0363.68108
[4] , Subregularly controlled derivations: the context-free case. Rostocker Mathematisches Kolloquium 34 (1988) 61-70. | MR 968639 | Zbl 0651.68096
[5] , Conditional grammars with restrictions by syntactic parameters. Words, Semigroups, Transductions, edited by M. Ito, Gh. Păun and Sh. Yu. World Scientific, Singapore (2001) 59-68. | MR 1914749
[6] , Subregularly controlled derivations: restrictions by syntactic parameters. Where Math., Comput. Sci., Linguistics and Biology Meet. Kluwer Academic Publishers (2001) 51-61. | MR 1890680 | Zbl 1007.68090
[7] , Contextual grammars with subregular choice. Fundamenta Informaticae 64 (2005) 109-118. | MR 2347547 | Zbl 1102.68041
[8] , Grammars with commutative, circular, and locally testable conditions. Automata, Formal Languages, and Related Topics - Dedicated to Ferenc Gécseg on the occasion of his 70th birthday. University of Szeged (2009) 27-37. | MR 2553622 | Zbl 1183.68324
[9] and , On regulated L systems. Rostock. Math. Kolloq. 25 (1984) 99-118. | MR 763680 | Zbl 0565.68067
[10] and , Conditional grammars with subregular conditions, in Proc. Internat. Conf. Words, Languages and Combinatorics II. World Scientific, Singapore (1994) 71-86. | MR 1351280 | Zbl 0875.68610
[11] , and , Networks of evolutionary processors with subregular filters, in Languages and Automata Theory and Applications. Vol. 6638 of Lect. Notes Comput. Sci. Springer-Verlag, Berlin (2011) 262-273. | Zbl 1230.68125
[12] , and , On Contextual Grammars with Subregular Selection Languages, in Descriptional Complexity of Formal Systems. Vol. 6808 of Lect. Notes Comput. Sci. Springer-Verlag, Berlin (2011) 135-146. | MR 2910372 | Zbl pre05934411
[13] and . Regulated Rrewriting in Formal Language Theory. Springer-Verlag, Berlin (1989). | MR 1067543 | Zbl 0697.68067
[14] and , Conditional Lindenmayer systems with subregular conditions: the extended case (Submitted). | Zbl pre06333645
[15] , and , Two collapsing hierarchies of subregularly tree controlled languages. Theoretical Comput. Sci. 410 (2009) 3261-3271. | MR 2546881 | Zbl 1176.68102
[16] , and , Generative capacity of subregularly tree controlled grammars. Int. J. Foundations Comput. Sci. 21 (2010) 723-740. | MR 2728321 | Zbl 1207.68173
[17] and , On networks of evolutionary processors with filters accepted by two-state-automata. Fundamenta Informaticae 113 (2011) 1-14. | MR 2918604 | Zbl 1263.68098
[18] , Grammars with partial ordering. Information and Control 12 (1968) 415-425. | MR 243952 | Zbl 0172.30002
[19] and , Control sets on grammars. Math. Syst. Theory 2 (1968) 159-177. | MR 235936 | Zbl 0157.33604
[20] and , Algebraic Theory of Automata. Academiai kiado, Budapest (1972). | MR 332374 | Zbl 0246.94029
[21] and , Multiple-entry finite automata. J. Comput. Syst. Sci. 9 (1974) 1-19. | MR 351666 | Zbl 0285.94030
[22] , and , Nondeterministic state complexity of basic operations for prefix-suffix-free regular languages. Fundamenta Informaticae 90 (2009) 93-106. | MR 2494605 | Zbl 1161.68534
[23] , The theory of regular events II. Kybernetika 5 (1969) 520-544. | MR 256787 | Zbl 0184.28703
[24] , Gramatici contextuale cu selectiva regulata. Stud. Cerc. Mat. 30 (1978) 287-294. | MR 500803
[25] and , Accepting Networks of Evolutionary Processors with Subregular Filters, in Automata and Formal Languages - 13th International Conference AFL 2011. College of Nyíregyháza (2011) 300-314. | Zbl 1230.68125
[26] and , On internal contextual grammars with subregular selection languages, in Descriptional Complexity of Formal Systems. Vol. 7386 of Lect. Notes Comput. Sci. Springer-Verlag, Berlin (2012) 222-235. | MR 2993347 | Zbl pre06101744
[27] , Contextual grammars. Revue Roum. Math. Pures Appl. 14 (1969) 1525-1534. | MR 262026 | Zbl 0193.32401
[28] and , Networks of Evolutionary Processors: Results and Perspectives, in Molecular Computational Models: Unconventional Approaches (2005) 78-114. | Zbl 1060.68046
[29] and , Counter-Free Languages. M.I.T. Press (1971). | MR 371538
[30] , and , The theory of definite automata. IEEE Trans. Electronic Comput. 12 (1963) 233-243. | MR 153518 | Zbl 0158.01002
[31] , Marcus Contextual Grammars. Kluwer Publ. House, Doordrecht (1998). | Zbl 0965.68037
[32] and , The Mathematical Theory of L Systems. Academic Press, New York (1980). | MR 561711 | Zbl 0508.68031
[33] and , Handbook of Formal Languages. Springer-Verlag, Berlin (1997). | Zbl 0866.68057
[34] and , Priorities on context conditions in rewriting systems. Inform. Sci. 14 (1978) 15-51. | MR 538667 | Zbl 0416.68066
[35] , Formal Languages. Academic Press, New York (1973). | MR 438755 | Zbl 0686.68003
[36] , Free Monoids and Languages. Hon Min Book Co., Taichung, Taiwan (1991). | MR 1090325 | Zbl 0746.20050
[37] and , Ordered automata and associated languages. Tamkang J. Math. 5 (1974) 9-20. | MR 366563 | Zbl 0302.68069
[38] , Abstrakte Automaten. Deutscher Verlag der Wissenschaften, Berlin (1969). | MR 276016 | Zbl 0182.02102
[39] , Vergleich der Leistungsfähigkeit endlicher determinierter Automaten. Diplomarbeit, Universität Rostock (1978).