순차 동력학 시스템

순차적 동적 시스템(SDS)은 그래프 동적 시스템의 한 종류다. 그것들은 고전적인 셀룰러 오토마타 같은 많은 측면을 일반화하는 이산 동적 시스템이며, 그래프를 통해 비동기 프로세스를 연구하기 위한 프레임워크를 제공한다. SDS의 분석은 조합학, 추상 대수학, 그래프 이론, 동적 시스템 및 확률 이론의 기법을 사용한다.

정의

SDS는 다음 구성 요소로 구성된다.

• 정점 집합 v[Y] = {1,2, ..., n}인 유한 그래프 Y. 상황에 따라 그래프를 지시하거나 방향을 바꿀 수 있다.
• 유한 집합 K에서 가져온 Y의 각 꼭지점 i에 대한 상태_v x 시스템 상태는 n-투플 x = (x₁₂, x, ... , x_n), x[i]는 Y에서 i의 1-근접점(일부 고정 순서)에 있는 정점과 관련된 상태로 구성된 튜플이다.
• 각 꼭지점 i에 대한 꼭지점 함수_i f. 정점 함수는 Y에서 i의 1-근접과 관련된 상태를 기준으로 시간 t의 정점 i 상태를 시간 t + 1의 정점 상태로 매핑한다.
• v[Y] 위에₁ w₂ = (w, w, ... , w_m)라는 단어.

에 의해 정점함수로 구성된 Y-로컬 맵 F를_i 도입하는 것이 편리하다.

${\displaystyle F_{i}(x)=(x_{1},x_{2},\ldots,x_{i-1},f_{i}(x[i]),x_{i+1},\ldots,x_{n}\;}$

w라는 단어는 순차적 동적 시스템 맵 F: Kⁿ → K를ⁿ 도출하기 위해 Y-로컬 맵을 구성하는 순서를 지정한다.

${\displaystyle [F_{Y},w]=F_{w(m)}\circ F_{w(m-1)}\circdots \circ F_{w(2)\circdots \circdots \circus F_{w(1)}.}$

업데이트 순서가 순열인 경우, 이 점을 강조하기 위해 순열 SDS를 자주 언급한다. 지도 F: Kⁿ → K를ⁿ 가진 순차적 동적 시스템과 연관된 위상 공간은 정점 집합ⁿ K와 방향 에지(x, F(x))를 가진 유한 지시 그래프다. 위상 공간의 구조는 그래프 Y, 정점 함수(f_i), 업데이트 _i순서 w의 속성에 의해 관리된다. SDS 연구의 많은 부분은 시스템 구성 요소의 구조에 기초하여 위상 공간 특성을 유추하고자 한다.

예

Y가 정점이 {1,2,3}인 그래프와 K = {0,1}의 정점 상태를 가진 비방향 에지 {1,2}, {1,3} 및 {2,3}(삼각형 또는 3-원)인 경우를 고려해 보십시오. 정점 함수의 경우 부울 산술에 의해 정의된 대칭, 부울 함수 nor : K³ → K nor (x,y,z) = (1+x)(1+y)(1+z)를 사용한다. 따라서 함수나 값 1을 반환하는 경우는 모든 인수가 0일 때뿐이다. 업데이트 시퀀스로 w = (1,2,3)를 선택하십시오. t = 0의 초기 시스템 상태(0,0,0)에서 시작하여 t=1의 정점 상태를 nor (0,0,0) = 1로 계산한다. t=1의 정점 2 상태는 nor (1,0,0)=0. t=1의 정점 상태를 즉시 t=1의 정점 상태를 사용한다. 다음으로 정점 3의 상태를 t=1에서 nor (1,0,0) = 0으로 얻는다. 이렇게 하면 업데이트 순서가 완료되고, Nor-SDS 맵이 시스템 상태(0,0,0)를 (1,0,0)로 전송한다고 결론짓는다. 시스템 상태(1,0,0)는 SDS 맵을 적용하여 (0,1,0)에 매핑된다.

참고 항목

• 그래프역학계
• 부울 네트워크
• 유전자 규제망
• 동적 베이시안 네트워크
• 페트리 그물

참조

• Henning S. Mortveit, Christian M. Reidys (2008). An Introduction to Sequential Dynamical Systems. Springer. ISBN 978-0387306544.
• 순차동력시스템의 전신 및 순열존재 문제
• 유전적 순차 동력학 시스템