Electronic Notes in Theoretical Computer Science · 1995 · 139 citations · 5 references
ComputingComputer ScienceFormal MethodsKnowledge RepresentationSafety EngineeringDirected Acyclic GraphsFormal Language FoundationsGraph AlgorithmsGraph TheoryModel CheckingSpecification LanguagesConsistencyConsistency SemanticsGraph RewritingRule Consistency CheckingRule LanguagesSafety Critical System AnalysisSafety-critical System DesignSafety-critical System Modeling
Consistency conditions describe basic properties of graphs as e.g. the existence or uniqueness of certain elements. A graph grammar is consistent if the start graph satisfies the consistency condition and the rules preserve this property. We propose a general construction that transforms global consistency conditions into preconditions for individual rules. A so-constructed rule is applicable to a consistent graph if and only if the derived graph is consistent, too. The relevance of this result is motivated by an example specification of a safety-critical system that is, a roundabout.
5
John L. Pfaltz, Azriel Rosenfeld · International Joint Conference on Artificial Intelligence · 1969 · 183 citations
Separable graphs, planar graphs and web grammars
Ugo Montanari · Information and Control · 1970 · 82 citations