Abstract
We introduce graph automata as devices for the recognition of linear graph languages. A graph automaton is the canonical extension of a finite state automaton recognizing a set of connected labeled graphs. It consists of a finite state control and a collection of heads, which search the input graph. In a move the graph automaton reads a new subgraph, checks some consistency conditions, changes states and moves some of its heads beyond the read subgraph. It proceeds such that the set of currently visited edges is an edge-separator between the visited and the yet undiscovered part of the input graph. Hence, the graph automaton realizes a graph searching strategy. Our main result states that finite graph automata recognize exactly the set of graph languages generated by connected linear NCE graph grammars.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Bienstock, P. Seymour. Monotonicity in graph searching. J. Algorithms 12 (1991), 239–245.
F.J. Brandenburg. Designing graph drawings by layout graph grammars. Proc. Workshop on Graph Drawing 94, LNCS 894 (1995), 416–427.
B. Courcelle. Graph rewriting: an algebraic and logic approach. Handbook of Theoretical Computer Science, Elsevier, Amsterdam, (1990) 193–242.
H. Ehrig, H.J. Kreowski, G. Rozenberg. Proc. 4. Workshop on Graph Grammars and Their Application to Computer Science, LNCS 532 (1991).
J. Engelfriet. Context-free NCE graph grammars. Proc. FCT 89, LNCS 380 (1989), 148–161.
J. Engelfriet, G. Leih. Linear graph grammars: power and complexity. Inform. Com-put. 81 (1989), 88–121.
F. Gécseg, M. Steinby. Tree Automata. Akadémiai Kiadó, Budapest (1984).
T. Hickl. Rechtwinkliges Layout von hierarchisch strukturierten Graphen. Dissertation, Universität Passau (1994).
D. Janssens, G. Rozenberg, E. Welzl. The bounded degree problem for NLC graph grammars is decidable. J. Comput. System Sci. 33 (1986), 415–422.
M. Kaul. Practical applications of precedence graph grammars. Proc. 3. Workshop on Graph Grammars and their Application to Computer Science, LNCS 291 (1987), 326–342.
A.S. LaPaugh. Recontamination does not help to search a graph. J. Assoc. Comput. Mach. 40 (1993), 224–245.
N. Megiddo, S.L. Hakimi, M. R. Garey, D.S. Johnson, C.H. Papadimitriou. The complexity of searching a graph. J. Assoc. Comput. Mach. 35 (1988), 18–44.
M. Nagl. Graph Grammatiken. Vieweg, Braunschweig (1979).
J.L. Pfaltz, A. Rosenfeld. Web Grammars. Proc. Joint Intern. Conference on Artificial Intelligence, Washington, D.C., (1969), 609–619.
E. Remila. Fundamental study — Recognition of graphs by automata. Theor. Comput. Sci. 136 (1994), 291–332.
A. Rosenfeld, D.L. Milgram. Web automata and web grammars. Machine Intelligence 7 (1972), 307–324.
G. Rozenberg, E. Welzl. Boundary NLC graph grammars-Basic definitions, normal forms and complexity. Inform. Control 69 (1986), 136–167.
A. Wu, R. Rosenfeld. Cellular graph automata I. Inform. Control 42 (1979), 305–329.
A. Wu, R. Rosenfeld. Cellular graph automata II. Inform. Control 42 (1979), 330–353.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brandenburg, F.J., Skodinis, K. (1996). Graph automata for linear graph languages. In: Cuny, J., Ehrig, H., Engels, G., Rozenberg, G. (eds) Graph Grammars and Their Application to Computer Science. Graph Grammars 1994. Lecture Notes in Computer Science, vol 1073. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61228-9_97
Download citation
DOI: https://doi.org/10.1007/3-540-61228-9_97
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61228-5
Online ISBN: 978-3-540-68388-9
eBook Packages: Springer Book Archive