CFGL의 형식화와 연결성 결정을 위한 병렬 알고리즘

여러가지 제약 조건하의 문맥 자유 그래프 언어(CFGL) 상에서 우리는 연결성 문제의 복잡도를 분석한다. 문맥 자유 그래프를 일반 형식 언어 형태로 표현하고 이것을 다시 그래프로 유도하는 규칙들을 보이고 튜링 변환기를 통한 문맥 자유 그래프 언어의 연결성 결정 시간인 DEXPTIME을 DLOGTIME으로 줄일 수 있는 Mesh of tree상에서의 효율적인 병렬 알고리즘을 제안한다. 우리의 결과는 NETWORK,CAD,VLSI등의 공학 설계에 많은 도움을 줄 것이다.