×
Rozenberg, G.

On coordinated selective substitutions: Towards a unified theory of grammars and machines. (English) Zbl 0601.68054

Theor. Comput. Sci. 37, 31-50 (1985).
The notion of a coordinated table selective substitution system (a cts system) is introduced. It provides a unifying framework for both grammars and machines (automata) and hence a really broad framework for formal language theory. An extensive number of examples is given which illustrate how a quite considerable number of grammars and automata considered in the literature may be ’naturally’ interpreted as special instances (subclasses of the class) of cts systems.

Cited in 3 Reviews
Cited in 5 Documents

MSC:

68Q45 Formal languages and automata

Keywords:

selector; coordinated table selective substitution system; cts system; formal language
Cite Review PDF
Full Text: DOI

References:

[1] Aalbersberg, I. J.J.; Rozenberg, G., cts system and Petri nets, (Techn. Rept. (1984), Institute of Appl. Math. and Comput. Sci., Univ. of Leiden: Institute of Appl. Math. and Comput. Sci., Univ. of Leiden The Netherlands) · Zbl 0608.68053
[2] (Brauer, W., Net Theory and Applications. Net Theory and Applications, Lecture Notes in Computer Science, 84 (1980), Springer: Springer Berlin/Heidelberg) · Zbl 0434.68040
[3] Büchi, R., Regular canonical systems, Archiv. fur Mathematische Logik und Grundlagenforschung, 6, 91-111 (1964) · Zbl 0129.26102
[4] Campbell, R. H.; Haberman, A. N., The specification of process synchronization by path expressions, (Lecture Notes in Computer Science, 16 (1974), Springer: Springer Berlin/Heidelberg), 89-102 · Zbl 0295.68028
[5] Eilenberg, S., Automata, Languages and Machines (1974), Academic Press: Academic Press London/New York · Zbl 0317.94045
[6] Ginsburg, S., Algebraic and Automata—Theoretic Properties of Formal Languages (1975), North-Holland: North-Holland Amsterdam · Zbl 0325.68002
[7] Ginsburg, S.; Rozenberg, G., T0L schemes and control sets, Information and Control, 27, 109-125 (1974) · Zbl 0294.68027
[8] Goldstine, J., Automata with data storage, (Proc. Conf. on Theoretical Computer Science. Proc. Conf. on Theoretical Computer Science, Waterloo (1977)), 239-246 · Zbl 0416.68044
[9] Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[10] Kleiijn, H. C.M., Selective substitution grammars based on context-free productions, (Ph.D. Thesis (1983), Dept. of Math., Univ. of Leiden: Dept. of Math., Univ. of Leiden The Netherlands)
[11] Kleijn, H. C.M.; Rozenberg, G., Context-free like restrictions on selective rewriting, Theoret. Comput. Sci., 16, 237-269 (1981) · Zbl 0469.68079
[12] Kleijn, H. C.M.; Rozenberg, G., Sequential, continuous and parallel grammars, Information and Control, 48, 221-260 (1981) · Zbl 0469.68080
[13] Kral, J., On multiple grammars, Kybernetika, 5, 60-85 (1969) · Zbl 0175.27703
[14] Mazurkiewicz, A., A complete set of assertations on distributed systems, (Tech. Rept. (1979), Dept. of Comput. Sci., Univ. of Aarhus)
[15] Rozenberg, G., Selective substitution grammars (towards a framework for rewriting systems), Part I: Definitions and examples, Elektron. Informationsverarbeit Kybernetik, 13, 455-463 (1977) · Zbl 0381.68062
[16] Rozenberg, G.; Salomaa, A., The Mathematical Theory of L Systems (1981), Academic Press: Academic Press London/New York · Zbl 0365.68072
[17] Salomaa, A., Formal Languages (1973), Academic Press: Academic Press London/New York · Zbl 0262.68025
[18] Scott, D., Some definitional suggestions for automata theory, J. Comput. System Sci., 1, 187-212 (1967) · Zbl 0164.32103
[19] Wood, D., Properties of \(n\)-parallel finite state languages, Utilitas Mathematica, 4, 103-113 (1973) · Zbl 0279.68063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.