Grammars on partial graphs

descriptionPublicationkeyboard_double_arrow_right Article 01 Jan 1976 English Publisher:Springer Science and Business Media LLCJournal:Acta Informatica, volume 6, pages 297-316 (issn: 0001-5903, eissn: 1432-0525,

Copyright policy )

Authors: Hans Jürgen Schneider; Hartmut Ehrig;

doi: 10.1007/bf00288659

Grammars on partial graphs

- Summary
- Subjects
- Metrics

Abstract

The concept of Chomsky-grammars is generalized to graph-grammars; the "gluing" of graphs is defined by a pushout-construction. In the present paper, we allow the left-hand and right-hand side of a production to be partial graphs, i.e. graphs in which there may be edges without a source or target node. A necessary and sufficient condition for applicability of productions is given. Furthermore, convex graph-grammars are studied.

Related Organizations

Technical University of Berlin
Germany

Keywords

Graph theory, Categories of machines, automata, Formal languages and automata

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	24
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%