2변수 논리학
Two-variable logic수학논리와 컴퓨터과학에서 2변수 논리는 공식을 두 개의 다른 변수만으로 쓸 수 있는 1차 논리학의 단편이다.[1]이 파편은 보통 기능 기호 없이 연구된다.null
결정성
만족도, 유한 만족도 등 2변수 논리에 관한 몇 가지 중요한 문제들은 해독이 가능하다.[2]이 결과는 특정 서술 로직과 같은 2변수 논리 조각의 결정성에 대한 결과를 일반화하지만, 2변수 논리 일부 조각은 만족도 문제에 대해 계산 복잡성이 훨씬 낮다.null
이와는 대조적으로 기능 기호가 없는 1차 논리학의 3변수 단편에서는 만족을 알 수 없다.[3]null
정량자 계수
함수 기호가 없는 1차 로직의 2변수 파편은 계수 정량자가 추가되어도 해독이 불가능해 고유 [4]정량화가 가능한 것으로 알려져 있다.높은 수치 값에 대한 정량자를 계산하는 것은 그 논리에서는 표현할 수 없기 때문에 이것은 더 강력한 결과물이다.null
Counting quantifiers actually improve the expressiveness of finite-variable logics as they allow to say that there is a node with neighbors, namely . Without counting quantifiers variables are같은 공식에 필요한.null
Weisfeiler-Leman 알고리즘 연결
2변수 논리와 Weisfeiler-Leman(또는 색상 정제) 알고리즘 사이에는 강한 연관성이 있다.두 개의 그래프를 볼 때, 두 의 가동일한 C 2 {\ C} 유형을 갖는 경우에만, 즉 계산과 함께 동일한 공식을 2변수 논리로 만족하는 경우, 어떤 두 개의 노드가든 색상 정제에서 동일한 안정적인 색상을 갖는다.[5]null
참조
- ^ 엘. 헨킨.한정된 수의 기호만을 포함하는 논리 시스템, 보고서, 몬트리올 대학교, 1967년 수학부
- ^ E. Grael, P.G. Kolaitis 및 M. Vardi, 2변수 1차 순서 로직의 의사결정 문제, 기호 로직의 회보, 제3권, 제1권(1997년 3월), 페이지 53-69.
- ^ A. S. Kahr, Edward F.무어와 하오 왕.Entscheidungsproblem 그들의 ∀ ∀ ∀ 사례로 축소, 1962년 그들의 ∀ ∀ 공식은 단지 세 변수만을 사용한다는 점에 주목했다.
- ^ E. 그래델,오토와 E.Rosen. 계산이 있는 2변수 논리학(Two-Variable Logic with Counting)은 1997년 제12차 IEEE 컴퓨터 과학 논리학 심포지엄의 진행으로 결정된다.
- ^ 그로헤, 마틴."변수 로직은 서술적 복잡성 이론으로 마무리하십시오."기호 논리 4.4(1998)의 게시판: 345-398.