프리픽스 순서

수학, 특히 순서론에서, 접두사 순서 집합은 연속적인 진행과 연속적인 분기의 가능성을 도입함으로써 나무의 직관적인 개념을 일반화한다.자연 프리픽스 순서는 시간(전체 순서 집합)에서 일부 위상 공간까지의 함수 집합으로 동적 시스템을 고려할 때 자주 발생합니다.이 경우 세트의 요소는 보통 시스템의 실행이라고 불립니다.

이름 프리픽스 순서는 단어의 프리픽스 순서에서 유래합니다.이것은 특수한 종류의 서브스트링 관계이며, 그 이산적인 문자 때문에 트리가 됩니다.

형식적 정의

프리픽스 순서는 집합 P에 대한 2진수 관계 "θ"로, 반대칭, 전이, 반사 및 하향 합계입니다.즉, P의 모든 a, b 및 c에 대해 다음과 같습니다.

a δ a(유동성)
a ≤ b 및 b ≤ a이면 a = b (대칭성);
a b b 및 b c c일 경우 a c c (비활성)
a and c 및 b c c일 경우 a or b 또는 b a a(전체적으로는)입니다.

프리픽스 순서간의 함수

부분 순서 사이에 순서 유지 함수를 고려하는 것이 일반적이지만, 프리픽스 순서 사이에 가장 중요한 함수 유형은 소위 이력 보존 함수입니다.프리픽스 순서 집합 P의 경우, 포인트 p'P의 이력은 (정의상 완전 순서) 집합 p- = {qq q ≤ p}입니다.프리픽스 순서 P와 Q 사이의 함수 f : P → Q는 모든 p'P에 대해 f(p-) = f(p)-가 검출된 경우에만 이력 보존됩니다.마찬가지로, 점 ppP의 미래는 (순서대로) 집합 p+ = {q p q q q q } q}이며, 모든 ppP에 대해 f(p+) = f(p)+를 찾을 경우 f는 미래 보존됩니다.

모든 역사 보존 기능 및 모든 미래 보존 기능도 질서 보존 기능이지만, 그 반대도 아닙니다.동적 시스템 이론에서, 역사 보존 지도는 한 시스템에서의 행동이 다른 시스템에서의 행동의 정제라는 직관을 포착합니다.더욱이, 역사와 미래 보존 투영인 함수는 시스템 간의 이중 시뮬레이션 개념을 포착하고, 따라서 주어진 정교함이 사양에 대해 정확하다는 직관을 포착한다.

이력 보존 함수의 범위는 항상 프리픽스 클로즈드 서브셋입니다.여기서 서브셋S p P는 prefix 클로즈드입니다.t p S 및 s t S가 있는 모든 s, t p P에 대해 prefix 클로즈드입니다.

제품과 조합

역사를 보존하는 지도를 접두어 순서의 범주에서 형태소로 받아들인 것은 데카르트 곱이 항상 접두어 순서는 아니기 때문에 두 순서의 데카르트 곱이 아닌 곱의 개념을 낳는다.대신에, 원래의 프리픽스 순서의 임의의 인터리빙이 발생합니다.두 개의 접두사 순서의 결합은 부분 순서와 마찬가지로 분리된 결합입니다.

동형사상

모든 생물 이력 보존 함수는 순서 동형사상입니다.또한 주어진 프리픽스 순서 집합 P에 대해 집합 P-θ {p-pθ P}를 구성하면 이 집합이 부분집합 관계 θ에 의해 순서화된 프리픽스임을 알 수 있으며, 나아가 함수 max : P- → P는 동형사상이며, 여기서 max(S)는 p의 순서에서 최대 요소 조건인 각 집합 SθP에 대해 반환된다.

레퍼런스

Cuijpers, Pieter (2013). "Prefix Orders as a General Model of Dynamics" (PDF). Proceedings of the 9th International Workshop on Developments in Computational Models (DCM). pp. 25–29.
Cuijpers, Pieter (2013). "The Categorical Limit of a Sequence of Dynamical Systems". EPTCS 120 : Proceedings EXPRESS/SOS 2013. pp. 78–92. doi:10.4204/EPTCS.120.7.
Ferlez, James; Cleaveland, Rance; Marcus, Steve (2014). "Generalized Synchronization Trees". LLNCS 8412: Proceedings of FOSSACS'14. pp. 304–319. doi:10.1007/978-3-642-54830-7_20.

Search