×

Recognizability of graph and pattern languages. (English) Zbl 1089.68052

Summary: Graph language recognizability is defined and investigated by virtue of the syntactic magmoid, analogously with the syntactic monoid of a word language. In this setup, the syntax complexity of a given recognizable graph language can be determined, giving rise to a syntactic classification inside the class of recognizable graph languages.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arnold, A., Dauchet, M.: Théorie des magmoides. I. RAIRO Inform. Théor. 12(3), 235–257 (1978) · Zbl 0391.68037
[2] Arnold, A., Dauchet, M.: Théorie des magmoides. II. RAIRO Inform. Théor. 13(2), 135–154 (1979) · Zbl 0443.68053
[3] Bauderon, M., Courcelle, B.: Graph expressions and graph rewritings. Math. Syst. Theory 20, 83–127 (1987) · Zbl 0641.68115 · doi:10.1007/BF01692060
[4] Bossut, F., Dauchet, M., Warin, B.: A Kleene theorem for a class of planar acyclic graphs. Inform. and Comput. 117, 251–265 (1995) · Zbl 0826.68089 · doi:10.1006/inco.1995.1043
[5] Bell, E.T.: Exponential numbers. Amer. Math. Monthly 41, 411–419 (1934) · Zbl 0010.05401 · doi:10.2307/2300300
[6] Benson, D.B.: The basic algebraic structures in categories of derivations. Inform. and Control 28, 1–29 (1975) · Zbl 0304.68083 · doi:10.1016/S0019-9958(75)90208-9
[7] Bozapalidis, S., Kalampakas, A.: An axiomatization of graphs. Acta Informatica 41, 19–61 (2004) · Zbl 1101.68064 · doi:10.1007/s00236-004-0149-8
[8] Corradini, A., Gadducci, F.: An algebraic presentation of term graphs, via gs-monoidal categories. Appl. Categ. Structures 7(4), 299–331 (1999) · Zbl 0949.68121 · doi:10.1023/A:1008647417502
[9] Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. and Comput. 85, 12–75 (1990) · Zbl 0722.03008
[10] Eilenberg, S.: Automata, Languages and Machines, vol. A. Academic Press (1974) · Zbl 0317.94045
[11] Engelfriet, J., Vereijken, J.J.: Context-free graph grammars and concatenation of graphs. Acta Informatica 34, 773–803 (1997) · Zbl 0896.68092 · doi:10.1007/s002360050106
[12] Engelfriet, J., Schmidt, E.M.: IO and OI I. J. Comput. Syst. Sci. 15(3), 328–353 (1977) · Zbl 0366.68053 · doi:10.1016/S0022-0000(77)80034-2
[13] Gadducci, F., Heckel, R.: An inductive view of graph transformation. Recent Trends in Algebraic Development Techniques (Tarquinia 1997), pp. 223–237. Lecture Notes in Computer Science 1376, Springer (1997) · Zbl 0901.18003
[14] Gibbons, J.: An initial-algebra approach to directed acyclic graphs. Mathematics of program construction (Kloster Irsee, 1995), pp. 282–303. LNCS 947, Springer, Berlin (1995)
[15] Hotz, G.: Eine Algebraisierung des Syntheseproblems von Schaltkreisen. EIK 1, pp. 185–205, 209–231 (1965) · Zbl 0156.25504
[16] Hotz, G.: Eindeutigkeit und Mehrdeutigkeit formaler Sprachen. EIK 2, 235–246 (1966) · Zbl 0177.01702
[17] Kamimura, T., Slutzki, G.: Parallel and two-way automata on directed ordered acyclic graphs. Inform. and Control 49, 10–51 (1981) · Zbl 0482.68051 · doi:10.1016/S0019-9958(81)90438-1
[18] MacLane, S.: Categories for the Working Mathematician. Springer Verlag (1971) · Zbl 0705.18001
[19] Mezei, J., Wright, J.: Algebraic automata and context-free sets. Inform. and Control 11, 3–29 (1967) · Zbl 0155.34301 · doi:10.1016/S0019-9958(67)90353-1
[20] Perrin, D.: (Chapter 1) Finite Auomata. Handbook of Theoretical Computer Science. In: van Leeuwen, J. (ed.), Vol. B, MIT Press (1990)
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.