Sekventiellt dynamiskt system
Sekventiella dynamiska system ( SDS ) är en klass av dynamiska grafsystem . De är diskreta dynamiska system som generaliserar många aspekter av till exempel klassiska cellulära automater , och de tillhandahåller ett ramverk för att studera asynkrona processer över grafer . Analysen av SDS:er använder sig av tekniker från kombinatorik , abstrakt algebra , grafteori , dynamiska system och sannolikhetsteori .
Definition
En SDS är uppbyggd av följande komponenter:
- En finit graf Y med vertexuppsättning v[ Y ] = {1,2, ... , n}. Beroende på sammanhanget kan grafen vara riktad eller oriktad.
- Ett tillstånd x v för varje hörn i av Y taget från en finit mängd K . Systemtillståndet är n -tuppeln x = ( x 1 , x 2 , ... , x n ), och x [ i ] är tupeln som består av tillstånden som är associerade med hörnen i 1-grannskapet av i i Y (i viss ordning).
- En vertexfunktion f i för varje vertex i . vertexfunktionen mappar tillståndet för vertex i vid tidpunkten t till vertextillståndet vid tidpunkten t + 1 baserat på tillstånden som är associerade med 1-grannskapet av i i Y .
- Ett ord w = ( w 1 , w 2 , ..., w m ) över v [ Y ].
Det är bekvämt att introducera de Y -lokala kartorna Fi konstruerade från vertexfunktionerna av
![F_{i}(x)=(x_{1},x_{2},\ldots ,x_{{i-1}},f_{i}(x[i]),x_{{i+1}},\ldots ,x_{n})\;.](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0297cda06442aa0a2bb3a1835cf94c5e8011fba)
Ordet w specificerar sekvensen i vilken de Y -lokala kartorna är sammansatta för att härleda den sekventiella dynamiska systemkartan F : K n → K n as
![[F_{Y},w]=F_{{w(m)}}\circ F_{{w(m-1)}}\circ \cdots \circ F_{{w(2)}}\circ F_{{w(1)}}\;.](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca42ec3794afcdf858b2c72b17b1c5d18f8c90cc)
Om uppdateringssekvensen är en permutation talar man ofta om en permutation SDS för att betona denna punkt. Fasutrymmet associerat med ett sekventiellt dynamiskt system med kartan F : K n → K n är den finita riktade grafen med vertexuppsättning K n och riktade kanter ( x , F ( x )). Strukturen av fasutrymmet styrs av egenskaperna hos grafen Y , vertexfunktionerna ( f i ) i och uppdateringssekvensen w . En stor del av SDS-forskningen syftar till att härleda fasutrymmesegenskaper baserat på strukturen hos systembeståndsdelarna.
Exempel
Betrakta fallet där Y är grafen med vertexuppsättning {1,2,3} och oriktade kanter {1,2}, {1,3} och {2,3} (en triangel eller 3-cirkel) med vertextillstånd från K = {0,1}. För vertexfunktioner använd den symmetriska, booleska funktionen eller : K 3 → K definierad av nor( x , y , z ) = (1+ x )(1+ y )(1+ z ) med boolesk aritmetik. Det enda fallet där funktionen inte heller returnerar värdet 1 är när alla argument är 0. Välj w = (1,2,3) som uppdateringssekvens. Utgående från det initiala systemtillståndet (0,0,0) vid tidpunkten t = 0 beräknar man tillståndet för vertex 1 vid tidpunkten t =1 som nor(0,0,0) = 1. Tillståndet för vertex 2 vid tidpunkten t =1 är nor(1,0,0) = 0. Observera att tillståndet för vertex 1 vid tidpunkten t =1 används omedelbart. Därefter erhåller man tillståndet för vertex 3 vid tidpunkten t =1 som nor(1,0,0) = 0. Detta slutför uppdateringssekvensen och man drar slutsatsen att Nor-SDS-kartan skickar systemtillståndet (0,0,0 (1,0,0). Systemtillståndet (1,0,0) mappas i sin tur till (0,1,0) genom en tillämpning av SDS-kartan.
Se även
- Grafiskt dynamiskt system
- booleskt nätverk
- Generellt nätverk
- Dynamiskt Bayesianskt nätverk
- Petri nät
- Henning S. Mortveit, Christian M. Reidys (2008). En introduktion till sekventiella dynamiska system . Springer. ISBN 978-0387306544 .
- Föregångare och permutationsexistensproblem för sekventiella dynamiska system
- Genetiska sekventiella dynamiska system