Key points are not available for this paper at this time.
그래프 언어의 한 클래스는 단일 변량 제2 차 논리(MSO)로 정의 가능하며, 이는 MSO 공식의 모델 집합으로 구성될 때에만 해당한다. 또한, 각 집합의 그래프의 트리 너비에 대한 계산 가능한 경계가 존재하면, 만족 가능성 및 함의 문제는 Courcelle의 정리에 의해 결정 가능하다. 이는 다른 그래프 논리를 MSO와 비교하는 동기를 부여한다. 본 논문에서는 각 정점 시퀀스가 주어진 레이블을 가진 단 하나의 엣지에만 연결된 간단한 하이퍼 그래프를 설명하는 관계의 분리 논리(SLR)의 MSO 정의 가능성을 고려한다. 우리의 논리 SLR은 존재적으로 수량화된 분리된 논리곱 관계 및 술어 원자의 재귀적 정의로 구성된 유도 술어를 사용한다. 이 논문의 주요 기여는 제한된 트리 너비의 그래프 집합을 설명하는 SLR의 표현력이 풍부한 조각이며, 이는 또한 MSO로 효과적으로 변환될 수 있다.
Bueri 외 (Sun,) 이 질문을 연구하였다.