이중 푸시아웃 그래프 다시 쓰기
Double pushout graph rewriting컴퓨터 과학에서 더블 푸시아웃 그래프 재작성(또는 DPO 그래프 재작성)은 그래프 재작성을 위한 수학적인 틀을 말한다.그것은 "그래프 그래머:대수학적 접근법"(1973년).[1]이후 그래프가 아닌 구조를 다시 쓸 수 있도록 허용하고 음의 적용 조건을 처리하는 것이 일반화되었다.[2]
정의
DPO 그래프 변환 시스템(또는 그래프 문법)은 시작 상태인 유한 그래프와 파생 규칙의 역할을 하는 유한 그래프와 그래프 동형성의 범주에서 유한하거나 계수 가능한 레이블링된 범위 집합으로 구성된다.규칙 범위는 일반적으로 단형성으로 구성되지만 세부 사항은 다를 수 있다.[3]
다시 쓰기는 삭제와 추가의 두 단계로 수행된다.
왼쪽에서 사이의 일치가 고정된 후 오른쪽에 없는 노드와 가장자리가 삭제된다.그런 다음 오른손은 접착제로 붙인다.
그래프를 붙이는 것은 사실상 그래프 범주의 푸시아웃 구조로, 삭제는 푸시아웃 보완체를 찾는 것과 같은 것이어서 이름이 붙는다.
사용하다
이중 푸시아웃 그래프 재작성은 일정한 크기와 구성의 패턴을 명시하여 패턴의 일부를 보존할 수 있도록 하여 그래프 변환의 사양을 지정할 수 있다.규칙의 적용은 잠재적으로 결정적이지 않다. 몇 가지 뚜렷한 일치가 가능할 수 있다.이러한 것들은 겹치지 않거나 보존된 항목만 공유할 수 있기 때문에 병렬 독립성이라고 알려진 일종의 동시성을 보여주거나 [4]양립할 수 없는 경우가 있는데, 이 경우 응용프로그램을 순차적으로 실행하거나 다른 응용프로그램을 차단할 수도 있다.
소프트웨어 설계와 프로그래밍을 위한 언어로 사용할 수 있다(대개 그래프보다 풍부한 구조에서 작업하는 변종이 선택된다).사후 대응 문제를 줄일 수 있기 때문에 DPO 그래프 재작성을 위한 종료는 이해할 수 없다.[5]
DPO 그래프 재작성은 페트리 그물의 일반화로 볼 수 있다.[4]
일반화
공리는 DPO 다시 쓰기가 작동하는 범주를 설명하기 위해 모색되어 왔다.한 가지 가능성은 접착제 범주의 개념으로, 이 범주는 또한 많은 폐쇄 특성을 가지고 있다.관련 개념은 HLR 시스템, 준접착 범주 및 -접착 범주, 접착식 HLR 범주 등이다.[6]
접착제 범주와 HLR 시스템의 개념은 관련이 있다(코프로덕트가 있는 접착제 범주는 HLR 시스템이다[7]).
예를 [8]들어 하이퍼그래프, 타이핑된 그래프, 귀속된 그래프 재작성 등은 접착식 HLR 시스템으로 주조될 수 있기 때문에 처리할 수 있다.
메모들
- ^ Hartmut Ehrig; Michael Pfender; Hans-Jürgen Schneider (Oct 1973). "Graph-Grammars: An Algebraic Approach". IEEE Conference Record of 14th Annual Symposium on Switching and Automata Theory (SWAT'08). IEEE. pp. 167–180. doi:10.1109/SWAT.1973.11.
- ^ Hartmut Ehrig; Karsten Ehrig; Annegret Habel; Karl-Heinz Pennemann (2004). "Constraints and Application Conditions: From Graphs to High-Level Structures". In Ehrig H.; Engels G.; Parisi-Presicce F.; Rozenberg G. (eds.). Graph Transformations. ICGT. Lecture Notes in Computer Science. Vol. 3256. Springer. pp. 287–303.
- ^ "Double-pushout graph transformation 재방문", 하벨, 앤그렛과 뮐러, 위르겐과 포동포동, 데틀프, 컴퓨터 과학의 수학 구조, 제11권, 제05권, 페이지 637--688, 2001, 캠브리지 대학교 출판부
- ^ a b "동일 컴퓨팅: 페트리 그물에서 그래프 그래머에 이르기까지", 코라디니, 안드레아, ENTCS, vol. 2, 페이지 56--70, 1995, 엘스비에
- ^ , "그래프 재작성 종료는 불해독" , Detlef Poople, Undomatica Informatataticae, vol. 33, 2, 페이지 201--209, 1998, IOS Press.
- ^ Hartmut Ehrig 및 Annegret Habel과 Julia Padberg 및 Ulrike Prange, "어댑티브 높은 수준의 대체 범주 및 시스템", 2004, Springer
- ^ 소프트웨어 과학 및 연산 구조의 기초에 있는 "어댑티브 범주", Stephen Lack 및 Pawew Sobociński, 페이지 273-288, Springer 2004
- ^ "대수학 그래프 변환의 기초" 하르트무트 에릭, 카르스텐 에릭, 울리케 프란지, 가브리엘 탠처