Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-26T23:28:27.819Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  28 March 2014

Jürgen Dassow  and
Stefan Rudolf
Jürgen Dassow
Affiliation:
Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, PSF 4120, 39016 Magdeburg, Germany. [email protected]
Stefan Rudolf
Affiliation:
Fliederweg 7b, 65527 Niedernhausen, Germany
Get access

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.

Keywords

Lindenmayer systemscontrolled derivations
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 48 , Issue 1: Non-Classical Models of Automata and Applications (NCMA 2012) , January 2014 , pp. 127 - 147
Copyright
© EDP Sciences 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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.
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.
Čulik II, K. and Maurer, H.A., 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. Google Scholar
Dassow, J., Subregularly controlled derivations: the context-free case. Rostocker Mathematisches Kolloquium 34 (1988) 61–70. Google Scholar
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.
J. Dassow, Subregularly controlled derivations: restrictions by syntactic parameters. Where Math., Comput. Sci., Linguistics and Biology Meet. Kluwer Academic Publishers (2001) 51–61.
Dassow, J., Contextual grammars with subregular choice. Fundamenta Informaticae 64 (2005) 109–118. Google Scholar
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.
Dassow, J. and Fest, U., On regulated L systems. Rostock. Math. Kolloq. 25 (1984) 99–118. Google Scholar
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.
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.
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.
J. Dassow and Gh. Păun. Regulated Rrewriting in Formal Language Theory. Springer-Verlag, Berlin (1989).
J. Dassow and St. Rudolf, Conditional Lindenmayer systems with subregular conditions: the extended case (Submitted).
Dassow, J., Stiebe, R. and Truthe, B., Two collapsing hierarchies of subregularly tree controlled languages. Theoretical Comput. Sci. 410 (2009) 3261–3271. Google Scholar
Dassow, J., Stiebe, R. and Truthe, B., Generative capacity of subregularly tree controlled grammars. Int. J. Foundations Comput. Sci. 21 (2010) 723–740. Google Scholar
Dassow, J. and Truthe, B., On networks of evolutionary processors with filters accepted by two-state-automata. Fundamenta Informaticae 113 (2011) 1–14. Google Scholar
Fris, I., Grammars with partial ordering. Information and Control 12 (1968) 415–425. Google Scholar
Ginsburg, S. and Spanier, E.H., Control sets on grammars. Math. Syst. Theory 2 (1968) 159–177. Google Scholar
F. Gécseg and I. Peak, Algebraic Theory of Automata. Academiai kiado, Budapest (1972).
Gill, A. and Kou, L.T., Multiple-entry finite automata. J. Comput. Syst. Sci. 9 (1974) 1–19. Google Scholar
Han, Y.-S., Salomaa, K. and Wood, D., Nondeterministic state complexity of basic operations for prefix-suffix-free regular languages. Fundamenta Informaticae 90 (2009) 93–106. Google Scholar
Havel, I.M., The theory of regular events II. Kybernetika 5 (1969) 520–544. Google Scholar
Istrail, S., Gramatici contextuale cu selectiva regulata. Stud. Cerc. Mat. 30 (1978) 287–294. Google Scholar
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.
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.
Marcus, S., Contextual grammars. Revue Roum. Math. Pures Appl. 14 (1969) 1525–1534. Google Scholar
C. Martín-Vide and V. Mitrana, Networks of Evolutionary Processors: Results and Perspectives, in Molecular Computational Models: Unconventional Approaches (2005) 78–114.
R. McNaughton and S. Papert, Counter-Free Languages. M.I.T. Press (1971).
Perles, M., Rabin, M.M. and Shamir, E., The theory of definite automata. IEEE Trans. Electronic Comput. 12 (1963) 233–243. Google Scholar
G. Păun, Marcus Contextual Grammars. Kluwer Publ. House, Doordrecht (1998).
G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press, New York (1980).
G. Rozenberg and A. Salomaa, Handbook of Formal Languages. Springer-Verlag, Berlin (1997).
Rozenberg, G. and von Solms, S.H., Priorities on context conditions in rewriting systems. Inform. Sci. 14 (1978) 15–51. Google Scholar
A. Salomaa, Formal Languages. Academic Press, New York (1973).
H.J. Shyr, Free Monoids and Languages. Hon Min Book Co., Taichung, Taiwan (1991).
Shyr, H.J. and Thierrin, G., Ordered automata and associated languages. Tamkang J. Math. 5 (1974) 9–20. Google Scholar
P.H. Starke, Abstrakte Automaten. Deutscher Verlag der Wissenschaften, Berlin (1969).
B. Wiedemann, Vergleich der Leistungsfähigkeit endlicher determinierter Automaten. Diplomarbeit, Universität Rostock (1978).