Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-23T03:51:14.819Z Has data issue: false hasContentIssue false
  • English
  • Français

Formal graph languages of shape

Published online by Cambridge University Press:  27 February 2009

Patrick A. Fitzhorn
Patrick A. Fitzhorn
Affiliation:
Department of Mechanical Engineering, Colorado State University, Fort Collins, CO 80523, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

The study of languages of shape is rich and interesting. One can develop formal grammars whose languages are non-realizable shape (nonsense objects), as well as grammars whose languages are classes of realizable shape. This paper develops several graph-based multi-dimensional languages that are complete in the physical solids. Thus, realizable shape is a language.

Type
Research Article
Information
AI EDAM , Volume 4 , Issue 3 , August 1990 , pp. 151 - 163
Copyright
Copyright © Cambridge University Press 1990

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abe, N., Mizumoto, M., Toyoda, J. and Tanaka, K. 1973. Web grammars and several graphs. Journal of Computer Systems Science, 7, 37–65.CrossRefGoogle Scholar
Baer, A., Eastman, C. and Henrion, M. 1979. Geometric modeling: A survey. Computer-aided Design, 11, 253–272.CrossRefGoogle Scholar
Braid, I., Hillyard, R. and Stroud, I. 1980. Stepwise construction of polyhedra in geometric modeling. In: Brodie, K. (Ed.). Mathematical Methods in Computer Graphics and Design. London: Academic Press.Google Scholar
Brainerd, W. 1969. Tree-generating regular systems. Information Control, 14, 217–231.CrossRefGoogle Scholar
Chiyokura, H. and Kimura, F. 1985. A method of representing the solid design process. IEEE Computer Graphics and Applications, 5(3), 32–41.CrossRefGoogle Scholar
Chomsky, N. 1957. Syntactic Structures. Atlantic Highlands, NJ: Humanities Press.CrossRefGoogle Scholar
Feder, J. 1971. Plex languages. Information Sciences 3, 225–241.CrossRefGoogle Scholar
Gonzalez, R. and Thomason, M. 1978. Syntactic Pattern Recognition. Reading, MA: Addison-Wesley.Google Scholar
Levy, L. and Yueh, K. 1978. On labelled graph grammars. Computing, 20, 109–125.CrossRefGoogle Scholar
Lin, W. and Fu, K. 1984. A syntactic approach to 3-D object representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6, 351–364.CrossRefGoogle ScholarPubMed
Mantyla, M. 1982. An inversion algorithm for geometric models. Computer Graphics, 16(3), 51–60.CrossRefGoogle Scholar
Mantyla, M. 1984. A note on the modeling space of Euler operators. Computer Vision, Graphics, and Image Processing, 26, 45–60.CrossRefGoogle Scholar
Mantyla, M. and Sulonen, R. 1982. GWB: A solid modeler with Euler operators. IEEE Computer Graphics and Applications, 2, 17–32.CrossRefGoogle Scholar
Montanari, U. 1970. Separable graphs, planar graphs and web grammars. Information Control, 16, 243–267.CrossRefGoogle Scholar
Nagl, M. 1976. Formal languages of labelled graphs. Computing, 16, 113–137.CrossRefGoogle Scholar
Nagl, M. 1979. A tutorial and bibliographical survey on graph grammars. In: Ehrig, H., Claus, V. and Rozenberg, G. (Eds). Graph Grammars and their Applications to CS and Biology. Berlin: Springer.Google Scholar
Pfaltz, J. 1972. Web grammars and picture descriptions. Computer Graphics and Image Processing, 1, 193–220.CrossRefGoogle Scholar
Requicha, A. A. G. 1980. Representations of rigid solids: Theory, methods and systems. ACM Computing Surveys, 12, 437–464.CrossRefGoogle Scholar
Rosenfeld, A. and Milgram, D. 1972. Web automata and web grammars. In: Meltzer, B. and Michie, D. (Eds) Machine Intelligence 7. New York: John Wiley.Google Scholar
Stiny, G. and March, L. 1981. Design machines. Environment and Planning B8, 245–255.CrossRefGoogle Scholar
Uesu, T. 1979. A complete system of grammars for plane graphs. Tsukuba Journal of Mathematics, 3(1), 129–160.CrossRefGoogle Scholar
Wilson, P. 1985. Euler formulas and geometric modelling. IEEE Computer Graphics and Applications, 5, 24–36.CrossRefGoogle Scholar