6533b824fe1ef96bd127feb8

RESEARCH PRODUCT

Graph languages defined by systems of forbidden structures: A survey

Frank WankmüllerVolker Blödel

subject

Discrete mathematicsTheoretical computer scienceA-normal formVoltage graphGraph (abstract data type)Decision problemNull graphForbidden graph characterizationMathematics

description

This paper deals with different ways of defining graph languages. These are the so-called forbidden structures. Some results on decision problems, their complexity, and set theoretic closure properties are scetched. A normal form, the minimal systems, are given. Finally the influence of the different kinds of forbidden structures on the descriptive power of the systems is shown.

yearjournalcountryeditionlanguage
1988-01-01
https://doi.org/10.1007/3-540-19422-3_4