摘要: Labelled graphs of bounded degree, with numbers assigned to the arcs at each node, are called d-graphs. A class generalized automata, cellular d-graph in which intercell connections define a d-graph, is introduced. It can be shown that automaton measure various properties its underlying graph; detect graph or subgraph isomorphism; and recognize basic types graphs. Most these tasks performed time proportional diameter given graph. Closure languages also briefly discussed.
springer.com
sci-hub.se 参考文章(17)
Leslie Michael Goldschlager, Synchronous parallel computation. ,(1978)
Ronald C. Read, Claude Berge, Graph theory and computing ,(1972)
P. Rosenstiehl, J.R. Fiksel, A. Holliger, INTELLIGENT GRAPHS: NETWORKS OF FINITE AUTOMATA CAPABLE OF SOLVING GRAPH PROBLEMS Graph Theory and Computing. pp. 219- 265 ,(1972) , 10.1016/B978-1-4832-3187-7.50019-2
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
J. P. Mylopoulos, T. Pavlidis, On the Topological Properties of Quantized Spaces, I. The Notion of Dimension Journal of the ACM. ,vol. 18, pp. 239- 246 ,(1971) , 10.1145/321637.321644
Juris Hartmanis, Janos Simon, On the power of multiplication in random access machines 15th Annual Symposium on Switching and Automata Theory (swat 1974). pp. 13- 23 ,(1974) , 10.1109/SWAT.1974.20
Stephen A. Cook, Robert A. Reckhow, Time bounded random access machines Journal of Computer and System Sciences. ,vol. 7, pp. 354- 375 ,(1973) , 10.1016/S0022-0000(73)80029-7
Leslie M. Goldschlager, A unified approach to models of synchronous parallel machines symposium on the theory of computing. pp. 89- 94 ,(1978) , 10.1145/800133.804336
Azriel Rosenfeld, Networks of Automata: Some Applications IEEE Transactions on Systems, Man, and Cybernetics. ,vol. SMC-5, pp. 380- 383 ,(1975) , 10.1109/TSMC.1975.5408418
Dexter Kozen, On parallelism in turing machines 17th Annual Symposium on Foundations of Computer Science (sfcs 1976). pp. 89- 97 ,(1976) , 10.1109/SFCS.1976.20