article

Finite graph automata for linear and boundary graph languages

Authors:

F. J. Brandenburg,

K. SkodinisAuthors Info & Claims

Theoretical Computer Science, Volume 332, Issue 1-3

Pages 199 - 232

https://doi.org/10.1016/j.tcs.2004.09.040

Published: 28 February 2005 Publication History

Abstract

Graph grammars can be regarded as a generalization of context-free grammars from strings to graphs. Over the past 30 years a rich theory of graph grammars and their languages has been developed. However, there are no graph automata. There is no duality between generative and recognizing devices, as it is known for the Chomsky hierarchy of formal languages.Here we introduce graph automata as devices for the recognition of sets of undirected node labelled graphs. A graph automaton consists of a finite state control, a finite set of instructions, and a collection of heads or guards. It reads an input graph in a systematic way and performs a graph search directed by the instructions. As our main results we show that finite graph automata recognize exactly the set of graph languages generated by linear NCE graph grammars and that alternating finite graph automata recognize exactly the languages of boundary graph grammars. Finally, we generalize some automata theoretic properties from string to graph automata, integrate the connectivity of graphs into graph automata, and explain why graph automata cannot be generalized to deal with dynamic edge relabellings and eNCE graph languages.

References

[1]

[1] I.J. Aalbersberg, G. Rozenbyerg, Traces, dependency graphs and DNLC grammars, Discrete Appl. Math. 11 (1985) 299-306.

[2]

[2] P. Beame, A. Borodin, P. Raghavan, W.L. Ruzzo, M. Tompa, Time-space tradeoffs for undirected graph traversal by graph automata, Inform. Comput. 130 (1996) 101-129.

Digital Library

[3]

[3] D. Bienstock, Graph searching, path-width, tree width and related problems (a survey), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 5, 1991, pp. 33-49.

[4]

[4] D. Bienstock, P. Seymour, Monotonicity in graph searching, J. Algorithms 12 (1991) 239-245.

Digital Library

[5]

[5] F.J. Brandenburg, On polynomial time graph grammars, in: R. Cori, M. Wirsing (Eds.), Proc. STACS 88, Lecture Notes in Computer Science, Vol. 294, Springer, Berlin, 1988, pp. 227-236.

Digital Library

[6]

[6] F.J. Brandenburg, K. Skodinis, Graph automata for linear graph languages, in: J. Cuny et al. (Eds.), Proc. Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, Vol. 1073, Springer, Berlin, 1996, pp. 336-350.

Digital Library

[7]

[7] A.K. Chandra, D. Kozen, L.J. Stockmeyer, Alternation, J. Assoc. Comput. Mach. 28 (1981) 114-131.

Digital Library

[8]

[8] S.H. Cook, C.W. Rackoff, Space lower bounds for maze threadability on restricted machines, SIAM J. Comput. 9 (1980) 636-652.

[9]

[9] T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, 1990.

Digital Library

[10]

[10] B. Courcelle, J. Engelfriet, G. Rozenberg, Handle-rewriting hypergraph grammars, J. Comput. System Sci. 46 (1993) 218-246.

Digital Library

[11]

[11] B. Courcelle, An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Theor. Comput. Sci. 55 (1987) 141-181.

[12]

[12] B. Courcelle, Monadic second-order definable graph transductions: a survey, Theor. Comput. Sci. 126 (1994) 53-75.

Digital Library

[13]

[13] B. Courcelle, The expression of graph properties and graph transformations in monadic second-order logic, in: G. Rozenberg (Ed.), Handbook of Graph Grammars and Computing by Graph Transformations, Vol. 1, World Scientific, Singapore, 1997, pp. 313-400.

Digital Library

[14]

[14] A. Ehrenfeucht, M.G. Main, G. Rozenberg, Restrictions on NLC graph grammars, Theor. Comput. Sci. 31 (1984) 211-223.

[15]

[15] J. Ellis, I. Sudborough, J. Turner, The vertex separation and search number of a graph, Inform. Comput. 113 (1994) 50-79.

Digital Library

[16]

[16] J. Engelfriet, Context-free NCE graph grammars, in: J. Csirik, J. Demetrovics, E Gécseg (Eds.), Fundamentals of Computation Theory, Lecture Notes in Computer Science, Vol. 380, Springer, Berlin, 1989, pp 148-161.

Digital Library

[17]

[17] J. Engelfriet, Context-free graph grammars, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vol. 3, Springer, Berlin, 1997, pp. 125-213.

Digital Library

[18]

[18] J. Engelfriet, L. Heyker, G. Leih, Context-free graph languages of bounded degree are generated by apex graph grammars, Acta Inform. 31 (1994) 341-378.

Digital Library

[19]

[19] J. Engelfriet, G. Leih, Linear graph grammars: power and complexity, Inform. Comput. 81 (1989) 88-121.

Digital Library

[20]

[20] J. Engelfriet, G. Leih, Complexity of boundary graph languages, RAIRO Theor. Inform. Appl. 24 (1990) 267-274.

[21]

[21] J. Engelfriet, G. Leih, G. Rozenberg, Apex graph grammars and attribute grammars, Acta Inform. 25 (1988) 537-571.

Digital Library

[22]

[22] J. Engelfriet, G. Leih, E. Welzl, Boundary graph grammars with dynamic edge relabelling, J. Comput. System Sci. 40 (1990) 307-345.

Digital Library

[23]

[23] J. Engelfriet, G. Rozenberg, A comparison of boundary graph grammars and context-free hypergraph grammars, Inform. Comput. 84 (1990) 163-206.

Digital Library

[24]

[24] J. Engelfriet, G. Rozenberg, Graph grammars based on node rewriting: an introduction to NLC graph grammars, in: H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.), Proc. Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, Vol. 532, Springer, Berlin, 1991, pp. 12-23.

Digital Library

[25]

[25] J. Engelfriet, G. Rozenberg, Node replacement graph grammars, in: G. Rozenberg (Ed.), Handbook of Graph Grammars and Computing by Graph Transformations, Vol. 1, World Scientific, Singapore, 1997, pp. 1-94.

Digital Library

[26]

[26] M. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.

Digital Library

[27]

[27] F. Gécseg, M. Steinby, Tree Automata, Akadémiai Kiadó, Budapest, 1984.

[28]

[28] J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, MA, 1979.

Digital Library

[29]

[29] D. Janssens, G. Rozenberg, On the structure of node-label-controlled graph languages, Inform. Sci. 20 (1980) 191-216.

[30]

[30] D. Janssens, G. Rozenberg, Restrictions, extensions, and variations of NLC grammars, Inform. Sci. 20 (1980) 217-244.

[31]

[31] D. Janssens, G. Rozenberg, Decision problems for node label controlled graph grammars, J. Comput. System Sci. 22 (1981) 144-177.

[32]

[32] D. Janssens, G. Rozenberg, Graph grammars with neighbourhood-controlled embedding, Theor. Comput. Sci. 21 (1982) 55-74.

[33]

[33] N.G. Kinnersley, The vertex separation number of a graph equals its path-width, Inform. Proc. Lett. 42 (1992) 345-350.

Digital Library

[34]

[34] L. Kirousis, C. Papadimitriou, Interval graphs and searching, Discrete Math. 55 (1985) 181-184.

[35]

[35] L. Kirousis, C. Papadimitriou, Searching and pebbling, Theor. Comput. Sci. 47 (1986) 205-218.

Digital Library

[36]

[36] A. LaPaugh, Recontamination does not help to search a graph, J. Assoc. Comput. Mach. 40 (1993) 224-245.

Digital Library

[37]

[37] T. Lengauer, E. Wanke, Efficient solution of connectivity problems on hierarchically defined graphs, SIAM J. Comput. 17 (1988) 1063-1080.

Digital Library

[38]

[38] Lewis, C. Papadimitriou, Symmetric space-bounded computation, Theoret. Comput. Sci. 19 (1982) 161-187.

[39]

[39] 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.

Digital Library

[40]

[40] M. Nagl, Formal languages of labelled graphs, Computing 16 (1976) 113-137.

[41]

[41] C. Papadimitriou, Computational Complexity, Addison-Wesley, Reading, MA, 1994.

[42]

[42] T. Parsons, Pursuit-evasion in a graph, in: Y. Alavi, D. Lick (Eds.), Theory and Applications of Graphs, Springer, New York/Berlin, 1976, pp. 426-441.

[43]

[43] E. Remila, Fundamental study--recognition of graphs by automata, Theor. Comput. Sci. 136 (1994) 291-332.

Digital Library

[44]

[44] A. Rosenfeld, D. Milgram, Web automata and web grammars, Mach. Intell. 7 (1972) 307-324.

[45]

[45] G. Rozenberg (Ed.), Handbook of Graph Grammars and Computing by Graph Transformations, Vol. 1, World Scientific, Singapore, 1997.

Digital Library

[46]

[46] G. Rozenberg, E. Welzl, Boundary NLC graph grammars--basic definitions, normal forms and complexity, Inform. Control 69 (1986) 136-167.

Digital Library

[47]

[47] G. Rozenberg, E. Welzl, Graph theoretic closure properties of the family of boundary NLC graph languages, Acta Inform. 23 (1986) 289-309.

Digital Library

[48]

[48] W.L. Ruzzo, Tree-size bounded alternation, J. Comput. System Sci. 21 (1980) 218-235.

[49]

[49] K. Skodinis, E. Wanke, Emptiness problems of eNCE graph languages, J. Comput. System Sci. 51 (1995) 472-485.

Digital Library

[50]

[50] K. Skodinis, E. Wanke, The bounded degree problem for eNCE graph grammars, Inform. Comput. 135 (1997) 15-35.

Digital Library

[51]

[51] E. Wank, e Algorithms for graph problems on BNLC structured graphs, Inform. Comput. 94 (1991) 93-122.

Digital Library

[52]

[52] A. Wu, R. Rosenfeld, Cellular graph automata I, Inform. Control 42 (1979) 305-329.

[53]

[53] A. Wu, R. Rosenfeld, Cellular graph automata II, Inform. Control 42 (1979) 330-353.

Cited By

de Oliveira Oliveira M(2022)Synthesis and Analysis of Petri Nets from Causal SpecificationsComputer Aided Verification10.1007/978-3-031-13188-2_22(447-467)Online publication date: 7-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-13188-2_22
De Oliveira Oliveira M(2016)Causality in Bounded Petri Nets is MSO DefinableProceedings of the 23rd International Workshop on Logic, Language, Information, and Computation - Volume 980310.1007/978-3-662-52921-8_13(200-214)Online publication date: 16-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-662-52921-8_13
Oliveira Oliveira M(2015)MSO Logic and the Partial Order Semantics of Place/Transition-NetsProceedings of the 12th International Colloquium on Theoretical Aspects of Computing - ICTAC 2015 - Volume 939910.1007/978-3-319-25150-9_22(368-387)Online publication date: 29-Oct-2015
https://dl.acm.org/doi/10.1007/978-3-319-25150-9_22
Show More Cited By

Index Terms

Finite graph automata for linear and boundary graph languages
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph enumeration
  2. Mathematical analysis
    1. Numerical analysis
      1. Computations in finite fields
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

First Order Graph Grammars

In this paper we consider first order context-free, linear, and regular graph grammars and obtain many results similar to those for the corresponding string grammars. We obtain normal forms for context-free and regular graph grammars, simplification ...
Connected graph searching in chordal graphs

Graph searching was introduced by Parson [T. Parson, Pursuit-evasion in a graph, in: Theory and Applications of Graphs, in: Lecture Notes in Mathematics, Springer-Verlag, 1976, pp. 426-441]: given a ''contaminated'' graph G (e.g., a network containing a ...
Parsing and Translation of (Attributed) Expansive Graph Languages for Scene Analysis

In this paper, we suggest a class of (attributed) expansive graph grammars which generate languages contained in a graph family . It turns out that by means of node renumbering using a very effi-cient algorithm, any graph in can be converted into a ...

Reviews

Reviewer: Kamal Lodaya

In the first part of this paper, the authors introduce nondeterministic graph automata that are in close correspondence with linear graph grammars. They then go on to introduce alternating graph automata that relate to boundary graph grammars. Whether the language accepted is empty or finite can be decided as for the corresponding word automata, with the same complexity. Minimization and determinism also follow word automata. The main idea is to divide the input graph into "visited" and "not yet visited" portions, using a transition relation modeled on a graph grammar production that moves the "visited" boundary into the "not visited" area. The ideas presented here are quite intuitive. The authors also explain that their approach does not extend to larger classes of graph grammars; new research may be required to address this.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 332, Issue 1-3

28 February 2005

566 pages

ISSN:0304-3975

Issue’s Table of Contents

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 28 February 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

de Oliveira Oliveira M(2022)Synthesis and Analysis of Petri Nets from Causal SpecificationsComputer Aided Verification10.1007/978-3-031-13188-2_22(447-467)Online publication date: 7-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-13188-2_22
De Oliveira Oliveira M(2016)Causality in Bounded Petri Nets is MSO DefinableProceedings of the 23rd International Workshop on Logic, Language, Information, and Computation - Volume 980310.1007/978-3-662-52921-8_13(200-214)Online publication date: 16-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-662-52921-8_13
Oliveira Oliveira M(2015)MSO Logic and the Partial Order Semantics of Place/Transition-NetsProceedings of the 12th International Colloquium on Theoretical Aspects of Computing - ICTAC 2015 - Volume 939910.1007/978-3-319-25150-9_22(368-387)Online publication date: 29-Oct-2015
https://dl.acm.org/doi/10.1007/978-3-319-25150-9_22
Brandenburg FHerrmann S(2006)Graph searching and search timeProceedings of the 32nd conference on Current Trends in Theory and Practice of Computer Science10.1007/11611257_17(197-206)Online publication date: 21-Jan-2006
https://dl.acm.org/doi/10.1007/11611257_17

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents