Conditional Lindenmayer systems with subregular conditions: The non-extended case

Jürgen Dassow; Stefan Rudolf

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

  • Volume: 48, Issue: 1, page 127-147
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Dassow, Jürgen, and Rudolf, Stefan. "Conditional Lindenmayer systems with subregular conditions: The non-extended case." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.1 (2014): 127-147. <http://eudml.org/doc/273073>.

@article{Dassow2014,
abstract = {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.},
author = {Dassow, Jürgen, Rudolf, Stefan},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {Lindenmayer systems; controlled derivations},
language = {eng},
number = {1},
pages = {127-147},
publisher = {EDP-Sciences},
title = {Conditional Lindenmayer systems with subregular conditions: The non-extended case},
url = {http://eudml.org/doc/273073},
volume = {48},
year = {2014},
}

TY - JOUR
AU - Dassow, Jürgen
AU - Rudolf, Stefan
TI - Conditional Lindenmayer systems with subregular conditions: The non-extended case
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2014
PB - EDP-Sciences
VL - 48
IS - 1
SP - 127
EP - 147
AB - 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.
LA - eng
KW - Lindenmayer systems; controlled derivations
UR - http://eudml.org/doc/273073
ER -

References

top
  1. [1] J. Castellanos, C. Martín-Vide, V. Mitrana and J.M. Sempere, 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. Zbl0982.68767
  2. [2] E. Csuhaj-Varjú and A. Salomaa, Networks of Parallel Language Processors. New Trends in Formal Languages. Vol. 1218 of Lect. Notes Comput. Sci. Springer-Verlag, Berlin (1997) 299–318. Zbl1054.68084MR1605238
  3. [3] K. Čulik II and H.A. Maurer, 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. Zbl0363.68108MR464718
  4. [4] J. Dassow, Subregularly controlled derivations: the context-free case. Rostocker Mathematisches Kolloquium34 (1988) 61–70. Zbl0651.68096MR968639
  5. [5] J. Dassow, 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. MR1914749
  6. [6] J. Dassow, Subregularly controlled derivations: restrictions by syntactic parameters. Where Math., Comput. Sci., Linguistics and Biology Meet. Kluwer Academic Publishers (2001) 51–61. Zbl1007.68090MR1890680
  7. [7] J. Dassow, Contextual grammars with subregular choice. Fundamenta Informaticae64 (2005) 109–118. Zbl1102.68041MR2347547
  8. [8] J. Dassow, 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. Zbl1183.68324MR2553622
  9. [9] J. Dassow and U. Fest, On regulated L systems. Rostock. Math. Kolloq.25 (1984) 99–118. Zbl0565.68067MR763680
  10. [10] J. Dassow and H. Hornig, Conditional grammars with subregular conditions, in Proc. Internat. Conf. Words, Languages and Combinatorics II. World Scientific, Singapore (1994) 71–86. Zbl0875.68610MR1351280
  11. [11] J. Dassow, F. Manea and B. Truthe, 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. Zbl1230.68125
  12. [12] J. Dassow, F. Manea and B. Truthe, 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. Zbl05934411MR2910372
  13. [13] J. Dassow and Gh. Păun. Regulated Rrewriting in Formal Language Theory. Springer-Verlag, Berlin (1989). Zbl0697.68067MR1067543
  14. [14] J. Dassow and St. Rudolf, Conditional Lindenmayer systems with subregular conditions: the extended case (Submitted). Zbl06333645
  15. [15] J. Dassow, R. Stiebe and B. Truthe, Two collapsing hierarchies of subregularly tree controlled languages. Theoretical Comput. Sci.410 (2009) 3261–3271. Zbl1176.68102MR2546881
  16. [16] J. Dassow, R. Stiebe and B. Truthe, Generative capacity of subregularly tree controlled grammars. Int. J. Foundations Comput. Sci.21 (2010) 723–740. Zbl1207.68173MR2728321
  17. [17] J. Dassow and B. Truthe, On networks of evolutionary processors with filters accepted by two-state-automata. Fundamenta Informaticae113 (2011) 1–14. Zbl1263.68098MR2918604
  18. [18] I. Fris, Grammars with partial ordering. Information and Control12 (1968) 415–425. Zbl0172.30002MR243952
  19. [19] S. Ginsburg and E.H. Spanier, Control sets on grammars. Math. Syst. Theory2 (1968) 159–177. Zbl0157.33604MR235936
  20. [20] F. Gécseg and I. Peak, Algebraic Theory of Automata. Academiai kiado, Budapest (1972). Zbl0246.94029MR332374
  21. [21] A. Gill and L.T. Kou, Multiple-entry finite automata. J. Comput. Syst. Sci.9 (1974) 1–19. Zbl0285.94030MR351666
  22. [22] Y.-S. Han, K. Salomaa and D. Wood, Nondeterministic state complexity of basic operations for prefix-suffix-free regular languages. Fundamenta Informaticae90 (2009) 93–106. Zbl1161.68534MR2494605
  23. [23] I.M. Havel, The theory of regular events II. Kybernetika5 (1969) 520–544. Zbl0184.28703MR256787
  24. [24] S. Istrail, Gramatici contextuale cu selectiva regulata. Stud. Cerc. Mat.30 (1978) 287–294. MR500803
  25. [25] F. Manea and B. Truthe, 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. Zbl1230.68125
  26. [26] F. Manea and B. Truthe, 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. Zbl1304.68112MR2993347
  27. [27] S. Marcus, Contextual grammars. Revue Roum. Math. Pures Appl.14 (1969) 1525–1534. Zbl0193.32401MR262026
  28. [28] C. Martín-Vide and V. Mitrana, Networks of Evolutionary Processors: Results and Perspectives, in Molecular Computational Models: Unconventional Approaches (2005) 78–114. Zbl1060.68046
  29. [29] R. McNaughton and S. Papert, Counter-Free Languages. M.I.T. Press (1971). Zbl0232.94024MR371538
  30. [30] M. Perles, M.M. Rabin and E. Shamir, The theory of definite automata. IEEE Trans. Electronic Comput.12 (1963) 233–243. Zbl0158.01002MR153518
  31. [31] G. Păun, Marcus Contextual Grammars. Kluwer Publ. House, Doordrecht (1998). Zbl0965.68037
  32. [32] G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press, New York (1980). Zbl0508.68031MR561711
  33. [33] G. Rozenberg and A. Salomaa, Handbook of Formal Languages. Springer-Verlag, Berlin (1997). Zbl0866.68057
  34. [34] G. Rozenberg and S.H. von Solms, Priorities on context conditions in rewriting systems. Inform. Sci.14 (1978) 15–51. Zbl0416.68066MR538667
  35. [35] A. Salomaa, Formal Languages. Academic Press, New York (1973). Zbl0686.68003MR438755
  36. [36] H.J. Shyr, Free Monoids and Languages. Hon Min Book Co., Taichung, Taiwan (1991). Zbl0746.20050MR1090325
  37. [37] H.J. Shyr and G. Thierrin, Ordered automata and associated languages. Tamkang J. Math.5 (1974) 9–20. Zbl0302.68069MR366563
  38. [38] P.H. Starke, Abstrakte Automaten. Deutscher Verlag der Wissenschaften, Berlin (1969). Zbl0182.02102MR276016
  39. [39] B. Wiedemann, Vergleich der Leistungsfähigkeit endlicher determinierter Automaten. Diplomarbeit, Universität Rostock (1978). 

NotesEmbed ?

top

You must be logged in to post comments.