Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-16T15:20:51.918Z Has data issue: false hasContentIssue false
  • English
  • Français

Dynamic labeled 2-structures

Published online by Cambridge University Press:  04 March 2009

A. Ehrenfeucht  and
G. Rozenberg
A. Ehrenfeucht
Affiliation:
Department of Computer Science, University of Colorado at Boulder Boulder, CO 80309, U.S.A.
G. Rozenberg
Affiliation:
Department of Computer Science, University of Colorado at Boulder Boulder, CO 80309, U.S.A. Department of Computer Science, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands
Get access Rights & Permissions [Opens in a new window]

Abstract

The notion of a dynamic labeled 2-structure(dℓ2s) is introduced and investigated. It generalizes the notion of a labeled 2-structure (ℓ2s) (Ehrenfeucht and Rozenberg 1990), by making it possible to change the (label) relationships between the nodes. This is achieved by storing in the nodes of a ℓ2s output and input functions that can change the outgoing and incoming labels, respectively. The notion of a clan, which is central in the theory of ℓ2s's is transferred to the framework of dℓ2s's, and the basic properties of clans of dℓ2s's are investigated.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 4 , Issue 4 , December 1994 , pp. 433 - 455
Copyright
Copyright © Cambridge University Press 1994

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

Birkhoff, G. and Bartee, T. C. (1970) Modern Applied Algebra, McGraw Hill, New York.Google Scholar
Buer, H. and Möring, R. H. (1983) A fast algorithm for the decomposition of graphs and posets. Mathematics of Operations Research 8 170–184.CrossRefGoogle Scholar
Ehrenfeucht, A. and Rozenberg, G. (1990) Theory of 2-structures, parts I and II. Theoretical Computer Science 70 277–342.CrossRefGoogle Scholar
Ehrenfeucht, A. and Rozenberg, G. (1992) Angular 2-structures. Theoretical Computer Science 92 227–248.Google Scholar
Ehrenfeucht, A. and Rozenberg, G. (1993a) T-structures, T-functions and texts. Theoretical Computer Science 116 227–290.Google Scholar
Ehrenfeucht, A. and Rozenberg, G. (1993b) Dynamic labeled 2-structures. Technical Report No. 93–01, Dept. of Computer Science, Leiden University, The Netherlands.Google Scholar
Ehrenfeucht, A. and Rozenberg, G. (1994) Square systems. Fundamenta Informaticae (to appear).CrossRefGoogle Scholar
Ehrenfeucht, A., Harju, T. and Rozenberg, G. (1993) Permutable transformation semigroups. Semigroup Forum 47 123–125.CrossRefGoogle Scholar
Ehrig, H., Kreowski, H.-J. and Rozenberg, G. (eds.) (1991) Graph grammars and their application to computer science. Springer- Verlag Lecture Notes in Computer Science 532.Google Scholar
Engelfriet, J. and Rozenberg, G. (1991) Graph grammars based on node rewriting: an introduction to NLC graph grammars. In Ehrig et al. (1991) 12–23.Google Scholar
Litovsky, I., Metivier, Y. and Sopena, E. (1994) Different local controls for graph relabeling systems. Mathematical Systems Theory (to appear).CrossRefGoogle Scholar
Reisig, W. (1985) Petri Nets, An Introduction, Springer-Verlag.CrossRefGoogle Scholar