Abstract
In classic formal language and automata theory, grammars and automata were modeling classic computing devices. Such devices were “centralized” — the computation was accomplished by one “central” agent. Hence in classic formal language theory a language is generated by one grammar or recognized by one automaton. In modern computer science distributed computation plays major role. Analyzing such computations in computer networks, distributed data bases, etc., leads to notions such as distribution, parallelism, concurrency, and communication. The theory of grammar systems was developed as a grammatical model for distributed computation where these notions could be defined and analyzed.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Abraham, Compound and serial grammars, Inform. Control, 20 (1972), 432–438.
L. M. Adleman, On constructing a molecular computer, Manuscript in circulation, January 1995.
D. Angluin, Finding patterns common to a set of strings, Journal of Computer and System Sciences, 21 (1980), 46–62.
A. Atanasiu, V. Mitrana, The modular grammars, Intern. J. Computer Math., 30 (1989), 101–122.
H. Bordihn, H. Fernau, Accepting grammars with regulation, Intern. J. Computer Math., 53 (1994), 1–18.
H. Bordihn, H. Fernau, M. Hölzer, Accepting grammar systems, Computers and AI, 1996.
W. Bucher, K. Culik H, H. A. Maurer, D. Wotschke, Concise description of finite languages, Theor. Computer Sci., 14 (1981), 227–246.
L. Cai, The computational complexity of PCGS with regular components, Proc. of Developments in Language Theory Conf., Magdeburg, 1995, 209–219.
L. Cai, The computational complexity of PCGS with linear components, Computers and AI,15, 2–3 (1996), 199–210..
C. Calude, Gh. Nun, Global syntax and semantics for recursively enumerable languages, Fundamenta Informaticae, 42 (1981), 254–254.
E. Csuhaj-Varju, Some remarks on cooperating grammar systems, In Proc. Conf. Aut. Lang. Progr. Syst. (I. Peak, F. Gecseg, eds. ), Budapest, 1986, 75–86.
E. Csuhaj-Varju, Cooperating grammar systems. Power and parameters, LNCS 812, Springer-Verlag, Berlin, 1994, 67–84.
E. Csuhaj-Varju, Grammar systems: a multi-agent framework for natural language generation, in [109], 63–78.
E. Csuhaj-Varju, Eco-grammar systems: recent results and perspectives, in [111], 79–103.
E. Csuhaj-Varju, J. Dassow, On cooperating distributed grammar systems, J. Inform. Process. Cybern., EIK, 26 (1990), 49–63.
E. Csuhaj-Varju, J. Dassow, J. Kelemen, Gh. Pâun, Stratified grammar systems, Computers and AI, 13 (1994), 409–422.
E. Csuhaj-Varju, J. Dassow, J. Kelemen, Gh. Pâun, Grammar Systems. A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, London, 1994.
E. Csuhaj-Varju, J. Dassow, V. Mitrana, G. Pâun, Cooperation in grammar systems: similarity, universality, timing, Cybernetica, 4 (1993), 271–282.
E. Csuhaj-Varju, J. Dassow, Gh. Pâun, Dynamically controlled cooperating distributed grammar systems, Information Sci., 69 (1993), 1–25.
E. Csuhaj-Varju, L. Kari, Gh. Pâun, Test tube distributed systems based on splicing, Computers and AI, 15, 23 (1996), 211–232.
E. Csuhaj-Varju, J. Kelemen, Cooperating grammar systems: a syntactical framework for the blackboard model of problem solving, In Proc. Conf. Artificial Intelligence and Information-Control Systems of Robots, ’ 89 ( I. Plander, ed.), North-Holland, Amsterdam 1989, 121–127.
E. Csuhaj-Varju, J. Kelemen, On the power of cooperation: a regular representation of r.e. languages, Theor. Computer Sci., 81 (1991), 305–310.
E. Csuhaj-Varju, J. Kelemen, A. Kelemenova, Gh. Pâun, Eco-grammar systems: A preview, in Cybernetics and Systems 94 ( R. Trappl, ed.), World Sci. Publ., Singapore, 1994, 941–949.
E. Csuhaj-Varju, J. Kelemen, A. Kelemenova, Gh. Pâun, Eco-grammar systems: A grammatical framework for life-like interactions, Artificial Life, 31 (1996), 1–28.
E. Csuhaj-Varju, J. Kelemen, Gh. Pâun, Grammar systems with WAVE-like communication, Computers and AI, 1996.
E. Csuhaj-Varju, Gh. Pâun, A. Salomaa, Conditional tabled eco-grammar systems, in [111], 227–239.
E. Csuhaj-Varju, Gh. Pâun, A. Salomaa, Conditional tabled eco-grammar systems versus (E)TOL systems, JUCS, 15 (1995), 248–264.
K. Culik II, T. Harju, Splicing semigroups of dominoes and DNA, Discrete Appl. Math., 31 (1991), 261–277.
J. Dassow, Cooperating distributed grammar systems with hypothesis languages, J. Exper. Th. AI, 3 (1991), 11–16.
J. Dassow, A remark on cooperating distributed grammar systems controlled by graphs, Wiss. Z. der TU Magdeburg, 35 (1991), 4–6.
J. Dassow, An example of an eco-grammar system: a can collecting robot, in [111], 240–244.
J. Dassow, J. Kelemen, Cooperating distributed grammar systems: a link between formal languages and artificial intelligence, Bulletin of EATCS, 45 (1991), 131–145.
J. Dassow, J. Kelemen, Gh. Pâun, On parallelism in colonies, Cybernetics and Systems, 24 (1993), 37–49.
J. Dassow, V. Mihalache, Eco-grammar systems, matrix grammars and EOL systems, in [111], 210–226.
J. Dassow, V. Mitrana, Splicing grammar systems, Computers and AI, 15, 23 (1996), 109–122.
J. Dassow, V. Mitrana, Cooperating distributed pushdown automata systems, submitted, 1995.
J. Dassow, V. Mitrana, Deterministic pushdown automata systems, submitted, 1995.
J. Dassow, V. Mitrana, “Call by name” and “call by value” in cooperating distributed grammar systems, Ann. Univ. Buc., Matern.-Inform. Series, 45, 1 (1996), 29–40.
J. Dassow, V. Mitrana, Fairness in grammar systems, submitted, 1995.
J. Dassow, V. Mitrana, Gh. Pâun, Szilard languages associated to cooperating distributed grammar systems, Stud. Cercet. Mat., 45, 5 (1993), 403–413.
J. Dassow, Gh. Pâun, Regulated Rewriting in Formal Language Theory, Springer-Verlag, Berlin, Heidelberg, 1989.
J. Dassow, Gh. Nun, Cooperating distributed grammar systems with registers, Found. Control Engineering, 15 (1990), 19–38.
J. Dassow, Gh. Pâun, On the succinctness of descriptions of context-free languages by cooperating distributed grammar systems, Computers and AI, 10 (1991), 513–527.
J. Dassow, Gh. Pâun, On some variants of cooperating distributed grammar systems, Stud. Cercet. Mat., 42, 2 (1990), 153–165.
J. Dassow, Gh. Pâun, St. Skalla, On the size of components of cooperating grammar systems, LNCS 812, Springer-Verlag, Berlin, 1994, 325–343.
S. Dumitrescu, CD and PC grammar systems, PHD Thesis, Univ. of Bucharest, Faculty of Mathematics, 1996.
S. Dumitrescu, Non-returning parallel communicating grammar systems can be simulated by returning systems, Theor. Computer Sci.,to appear.
S. Dumitrescu, Gh. Pâun, On the power of parallel communicating grammar systems with right-linear components, submitted, 1995.
S. Dumitrescu, Gh. Nun, A. Salomaa, Pattern languages versus parallel communicating grammar systems, Intern. J. Found, Computer Sci.,to appear.
L. Errico, WAVE: An Overview of the Model and the Language, CSRG, Dept. Electronic and Electr. Eng., Univ. of Surrey, UK, 1993.
L. Errico, C. Jesshope, Towards a new architecture for symbolic processing, In Proc. Con f. Artificial Intelligence and Information-Control Systems of Robots ‘84 ( I. Plander, ed.), World Sci. Publ., Singapore, 1994, 31–40.
J. D. Farmer, A. d’A Belin, Artificial Life: the coming evolution,in Proc. in Cellebration of Muray Gell-Man’s 60th Birthday,Cambridge Univ. Press., Cambridge, 1990.
H. Fernau, M. Holzer, H. Bordihn, Accepting multi-agent systems: the case of CD grammar systems, Computers and AI, 15, 23 (1996), 123–140.
R. Freund, Multi-level eco-array grammars, in [111], 175–201.
R. Freund, L. Kari, Gh. Pâun, DNA computing based on splicing: the existence of universal computers, submitted, 1995.
R. Freund, Gh. [’Ann, A variant of team cooperation in grammar systems, JUGS, 1, 3 (1995), 105–130.
R. Freund, Gh. PAun, C. M. Procopiuc, O. Procopiuc, Parallel communicating grammar systems with context-sensitive components, in [111], 166–174.
G. Georgescu, The generative power of small grammar systems, in [111], 152165.
G. Georgescu, A sufficient condition for the regularity of PCGS languages, J. Automata, Languages, Combinatorics,to appear.
J. Gruska, Descriptional complexity of context-free languages, Proc. MFCS 73, High Tatras, 1973, 71–84.
D. Hauschild, M. Jantzen, Petri nets algorithms in the theory of matrix grammars, Acta Informatica, 31 (1994), 719–728.
W. D. Hillis, The Connection Machine. The MIT Press, Cambridge, Mass., 1985.
T. Head, Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors, Bull. Math. Biology, 49 (1987), 737–759.
J. Hromkovic, Descriptional and computational complexity measures for distributive generation of languages, in Proc. of Developments in Language Theory Conf., Magdeburg, 1995.
J. Hromkovic, J. Kari, L. Kari, Some hierarchies for the communicating complexity measures of cooperating grammar systems, Theor. Computer Sci., 127 (1994), 123–147.
J. Hromkovic, J. Kari, L. Kari, D. Pardubska, Two lower bounds on distributive generation of languages, Proc. MFCS 94, LNCS 841, Springer-Verlag, Berlin, 1994, 423–432.
J. Hromkovic, D. Wierzchula, On nondeterministic linear time, real time and parallel communicating grammar systems, in [109], 184–190.
L. Ilie, Collapsing hierarchies in parallel communicating grammar systems with communication by command, Computers and AI,15, 23 (1996), 173184.
L. Ilie, A. Salomaa, 2-testability and relabeling produce everything, submitted, 1995.
C. M. Ionescu, O. Procopiuc, Bounded communication in parallel communicating grammar systems, J. Inform. Process. Cybern., EIK, 30 (1994), 97–110.
L. Kari, A. Mateescu, Gh. PAun, A. Salomaa, Teams in cooperating grammar systems, J. Exper. Th. AI, 7 (1995), 347–359.
J. Kari, L. Sântean, The impact of the number of cooperating grammars on the generative power, Theor. Computer Sci., 98 (1992), 621–633.
J. Kelemen, A. Kelemenova, A subsumption architecture for generative symbol systems, in Cybernetics and Systems Research 92 ( R. Trappl, ed.), World Sci. Publ., Singapore, 1992, 1529–1536.
J. Kelemen, R. Miichova, Bibliography of grammar systems, Bulletin of EATCS, 49 (1992), 210–218.
A. Kelemenova, E. Csuhaj-Varju, Languages of colonies, Theo r. Computer Sci., 134 (1994), 119–130.
A. Kelemenova, J. Kelemen, From colonies to eco-grammar systems. An overview, LNCS 812, Springer-Verlag, Berlin, 1994, 213–231.
C. Langton, Artificial life, in Artificial Life ( C. Langton, ed.), Santa Fe Institute Studies in the Sciences of Complexity, Addison Wesley Publ., 1989.
R. J. Lipton, Speeding up computations via molecular biology, Manuscript in circulation, December 1994.
M. Malita, Gh. Stefan, The eco-chip: a physical support for artificial life systems, in [111], 260–275.
A. Mateescu, A survey of teams in cooperating distributed grammar systems, in [111], 137–151.
A. Mateescu, Teams in cooperating distributed grammar systems; an overview, Proc. Decentralized Intelligent and Multi-Agent Systems, DIMAS ‘85, Cracow, 1995, 309–323.
R. Meersman, G. Rozenberg, Cooperating grammar systems, Proc. MFCS ‘78, LNCS 64, Springer-Verlag, Berlin, 1978, 364–374.
R. Meersman, G. Rozenberg, D. Vermeir, Cooperating grammar systems, Techn. Report, 78–12, Univ. Antwerp, Dept. of Math., 1978.
M. Middendorf, Supersequences, runs and CD grammar systems, in Developments in Theoretical Computer Science ( J. Dassow, A. Kelemenova, eds.), Gordon and Breach, London, 1994, 101–113.
V. Mihalache, Matrix grammars versus parallel communicating grammar systems, in [109], 293–318.
V. Mihalache, Extended conditional tabled eco-grammar systems, J. Inform. Processing Cybern., 30, 4 (1994), 213–229.
V Mihalache, General Artificial Intelligence systems as eco-grammar systems, in [111], 245–259.
V. Mihalache, On parallel communicating grammar systems with context-free components, in [113], 258–270.
V. Mihalache, Szilard languages associated to parallel communicating grammar systems, Proc. of Developments in Language Theory Conf., Magdeburg, 1995, 247–256.
V. Mihalache, On the generative capacity of parallel communicating grammar systems with regular components, Computers and AI, 15, 23 (1996), 155–172.
V. Mihalache, Terminal versus nonterminal symbols in parallel communicating grammar systems, Rev. Rouen. Math. Pures Appl., 1996.
V. Mihalache, Variants of parallel communicating grammar systems, Mathematical Linguistics Conf., Tarragona, 1996.
V. Mihalache, Parallel communicating grammar systems with query words, Ann. Univ. Buc., Matem.-Inform. Series, 45, 1 (1996), 81–92.
Grammargsm Pairs, Ann. Univ. Buc., Ser. Matem.-Inform., 39, 40 (1992), 64–71.
V. Mitrana, Hybrid cooperating distributed grammar systems, Computers and AI, 2 (1993), 83–88.
V. Mitrana, Eco-pattern systems, in [111], 202–209.
V. Mitrana, Similarity in grammar systems, Fundamenta Informaticae, 24 (1995), 251–257.
V. Mitrana, Gh. Pâun, G. Rozenberg, Structuring grammar systems by priorities and hierarchies, Acta Cybernetica, 11 (1994), 189–204.
P. H. Nii, Blackboard systems, In The Handbook of AI, vol. 4 ( A. Barr, P. R. Cohen, E. A. Feigenbaum, eds.), Addison-Wesley, Reading, Mass., 1989.
D. Pardubska, On the power of communication structure for distributive generation of languages, In Developments in Language Theory ( G. Rozenberg, A. Salomaa, eds.), World Sci. Publ., Singapore, 1994, 90–101.
D. Pardubska, Communication complexity hierarchies for distributive generation of languages, Fundamenta Informaticae,to appear.
Gh. Pâun, A new type of generative device: valence grammars, Rev. Rouen. Math. Pures Appl., 25, 6 (1980), 911–924.
Gh. Pâun, Parallel communicating grammar systems: the context-free case, Found. Control Engineering, 14, 1 (1989), 39–50.
Gh. Nun, On the power of synchronization in parallel communicating grammar systems, Stud. Cerc. Matem., 41, 3 (1989), 191–197.
Gh. Nun, Non-centralized parallel communicating grammar systems, Bulletin of EATCS, 40 (1990), 257–264.
Gh. Pâun, On the syntactic complexity of parallel communicating grammar systems, Kybernetika, 28 (1992), 155–166.
Gh. Nun, Parallel communicating systems of L systems, in Lindenmayer systems. Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology ( G. Rozenberg, A. Salomaa, eds.), Springer-Verlag, Berlin, 1992, 405–418.
Gh. Nun, On the synchronization in parallel communicating grammar systems, Acta Informatica, 30 (1993), 351–367.
Gh. Nun (ed.), Mathematical Aspects of Natural and Formal Languages, World Sci. Publ., Singapore, 1994.
Gh. Nun, On the generative capacity of colonies, Kybernetika, 31 (1995), 83–97.
Gh. Nun (ed.), Artificial Life. Grammatical Models, The Black Sea Univ. Press, Bucharest, 1995.
Gh. Nun, On the generative capacity of hybrid CD grammar systems, J. Inform. Process. Cybern., EIK, 30, 4 (1994), 231–244.
Gh. Pâun (ed.), Mathematical Linguistics and Related Topics, The Publ. House of the Romanian Academy, Bucharest, 1995.
Gh. Nun, Grammar systems: A grammatical approach to distribution and cooperation, Proc. ICALP ‘85 Conf., LNCS, 944 (1995), 429–443.
Gh. Pâun, Generating languages in a distributed way: grammar systems, XIth Congress on Natural and Formal Languages, Tortosa, 1995, 45–67.
Gh. Nun, Parallel comunicating grammar systems. A survey, XIth Congress on Natural and Formal Languages, Tortosa, 1995, 257–283.
Gh. Pâun, On the splicing operation, Discrete Appl. Math., 70 (1996), 57–79.
Gh. Nun, Regular extended H systems are computationally universal, J. Automata, Languages, Combinatorics, 11 (1996), 27–36.
Gh. Nun On the power of the splicing operation, Intern. J. Computer Math., 59 (1995), 27–35.
Gh. Pâun, L. Polkowski, A. Skowron, Parallel communicating grammar systems with negotiation, Fundamenta Informaticae, 1996.
Gh. Nun, G. Rozenberg, Prescribed teams of grammars, Acta Informatica, 31 (1994), 525–537.
Gh. Nun, G. Rozenberg, A. Salomaa, Computing by splicing, Intern. J. Computer Sci., 1996, 168, 2 (1996), 321–336.
Gh. Nun, A. Salomaa, S. Vicolov, On the generative capacity of parallel communicating grammar systems, Intern. J. Computer Math., 45 (1992), 4959.
Gh. Nun, L. Sântean, Parallel communicating grammar systems: the regular case, Ann. Univ. Bue. Ser. Matem.-Inform., 38 (1989), 55–63.
Gh. Nun, L. Sântean, Further remarks about parallel communicating grammar systems, Intern. J. Computer Math., 34 (1990), 187–203.
D. Pixton, Regularity of splicing languages, Discrete Appl. Math., 1995, 69 (1996), 101–124.
O. Procopiuc, C. M. Ionescu, F. L. Tiplea, Parallel communicating grammar systems: the context-sensitive case, Intern. J. Computer Math, 49 (1993), 145–156.
G. Rozenberg, K. Ruohonen, A. Salomaa, Developmental systems with fragmentation, Intern. J. Computer Math., 5 (1976), 177–191.
G. Rozenberg, A. Salomaa, The Mathematical Theory of L Systems, Academic Press, New York, 1980.
A. Salomaa, Formal Languages, Academic Press, New York, 1973.
L. Sântean, Parallel communicating systems, Bulletin of EATCS, 42 (1990), 160–171.
P. S. Sapaty, The WAVE Paradigm, Internal Report 17/92, Dept. Informatics, University of Karlsruhe, 1992.
S. Skalla, On the number of active nonterminals of cooperating distributed grammar systems, in Artificial Intelligence and Information-Control Systems of Robots 94 ( I. Plander, ed.), World Sci. Publ., Singapore, 1994, 367–374.
A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc., Ser. 2, 42 (1936), 230–265.
F. L. Tiplea, C. Ene, A coverability structure for parallel communicating grammar systems, J. Inform. Process. Cybern., EIK, 29 (1993), 303–315.
F. L. Tiplea, C. Ene, C. M. Ionescu, O. Procopiuc, Some decision problems for parallel communicating grammar systems, Theor. Computer Sci., 134 (1994), 365–385.
F. L. Tiplea, O. Procopiuc, C. M. Procopiuc, C. Ene, On the power and complexity of parallel communicating grammar systems, in [111], 53–78.
G. Vaszil, Parallel communicating grammar systems without a master, Computers and AI, 15, 23 (1996), 185–198.
G. Vaszil, The simulation of a non-returning parallel communicating grammar system with a returning system in case of linear component grammars, submitted, 1995.
S. Vicolov, Non-centralized parallel grammar systems, Stud. Cercet. Matera., 44 (1992), 455–462.
D. Wâtjen, On cooperating distributed limited OL systems, J. Inform. Process. Cybern. EIK, 29 (1993), 129–142.
Connection Machine Model CM-2 Technical Summary, Thinking Machines Corporation, Cambridge, Mass., 1987.
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Dassow, J., Păun, G., Rozenberg, G. (1997). Grammar Systems. In: Rozenberg, G., Salomaa, A. (eds) Handbook of Formal Languages. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-07675-0_4
Download citation
DOI: https://doi.org/10.1007/978-3-662-07675-0_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-08230-6
Online ISBN: 978-3-662-07675-0
eBook Packages: Springer Book Archive