Termination Time of Vector Addition Systems with States /
Vector Addition Systems with States (VASS) jsou důležitým modelem pro souběžné procesy, paralelní programy a parametrizované systémy. Mohou být také použity jako model programů za účelem získání odhadů na času a/nebo prostor, které tyto programy mohou vyžadovat. V této dizertační práci se zaměřujeme...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Angličtina |
| Vydáno: |
2022
|
| Témata: | |
| On-line přístup: | https://is.muni.cz/th/d9zyd/ |
| LEADER | 05148ctm a22007337i 4500 | ||
|---|---|---|---|
| 001 | MUB01006507908 | ||
| 003 | CZ BrMU | ||
| 005 | 20240523142524.0 | ||
| 008 | 220915s2022 xr ||||| |||||||||||eng d | ||
| STA | |a POSLANO DO SKCR |b 2023-04-17 | ||
| 035 | |a (ISMU-VSKP)292120 | ||
| 040 | |a BOD114 |b cze |d BOD018 |e rda | ||
| 072 | 7 | |a 519.1/.8 |x Kombinatorika. Teorie grafů. Matematická statistika. Operační výzkum. Matematické modelování |2 Konspekt |9 13 | |
| 072 | 7 | |a 004.4/.6 |x Programování. Software |2 Konspekt |9 23 | |
| 080 | |a 519.6 |2 MRF | ||
| 080 | |a (043.3) |2 MRF | ||
| 080 | |a 004.42.032.24 |2 MRF | ||
| 080 | |a 004.925.8 |2 MRF | ||
| 080 | |a 004.421 |2 MRF | ||
| 100 | 1 | |a Velan, Dominik |% UČO 393839 |* [absolvent FI MU] |4 dis | |
| 242 | 1 | 0 | |a Termination Time of Vector Addition Systems with States |y eng |
| 245 | 1 | 0 | |a Termination Time of Vector Addition Systems with States / |c Dominik Velan |
| 264 | 0 | |c 2022 | |
| 300 | |a vii, 160 stran : |b ilustrace | ||
| 336 | |a text |b txt |2 rdacontent | ||
| 337 | |a bez média |b n |2 rdamedia | ||
| 338 | |a svazek |b nc |2 rdacarrier | ||
| 500 | |a Vedoucí práce: Tomáš Brázdil | ||
| 502 | |a Dizertace (Ph.D.)--Masarykova univerzita, Fakulta informatiky, 2022 | ||
| 520 | 2 | |a Vector Addition Systems with States (VASS) jsou důležitým modelem pro souběžné procesy, paralelní programy a parametrizované systémy. Mohou být také použity jako model programů za účelem získání odhadů na času a/nebo prostor, které tyto programy mohou vyžadovat. V této dizertační práci se zaměřujeme na získání odhadů na dobu terminace VASS a jejich rozšíření, zejména stochastické rozšíření a hry na VASS, přičemž klademe důraz na lineární dobu terminace. Uvažujeme obě krajní varianty nedeterminismu, andělskou a démonickou. Andělský (démonický) nedeterminismus je vyřešen co největším snížením (zvýšením) doby terminace. Výsledky naší práce jsou následující. Pro démonické VASS představíme polynomiální algoritmus, který rozhoduje, zda je terminace lineární. Ukážeme, že pokud doba terminace není lineární, je alespoň kvadratická. Také ukážeme, že každý VASS, který má lineárně ohraničené čítače buď neterminuje, nebo má polynomiální dobu terminace, kde nejnižší stupeň polynomu ohraničující dob |% cze | |
| 520 | 2 | 9 | |a Vector Addition Systems with States (VASS) are a fundamental model for concurrent processes, parallel programs, and parametrised systems. They can be also used as models of programs for obtaining bounds on the time and/or space needed by the program. In this thesis, we focus on determining the bounds on the termination time of VASS and their extensions, namely VASS MDPs and VASS games, with an emphasis on the linear termination. We consider both angelic and demonic nondeterminism. Here, the angelic (demonic) nondeterminism is resolved by lowering (increasing) the termination time as much as possible. Our contributions are as follows. For demonic VASS, we give a polynomial time algorithm for deciding whether it has linear termination complexity. We show that if the termination complexity is not linear then it is at least quadratic. We show that every VASS with linearly bounded counters is either non-terminating or it has a polynomial termination time where the degree of the polynomial |9 eng |
| 650 | 0 | 7 | |a paralelní programování |7 ph115669 |2 czenas |
| 650 | 0 | 7 | |a parametrické modelování |7 ph156637 |2 czenas |
| 650 | 0 | 7 | |a asymptotické metody |7 ph471323 |2 czenas |
| 650 | 0 | 7 | |a lineární terminace |2 CZ-BrMU |
| 650 | 0 | 7 | |a algoritmy (programování) |7 ph131788 |2 czenas |
| 650 | 0 | 9 | |a parallel programming |2 eczenas |
| 650 | 0 | 9 | |a parametric modeling |2 eczenas |
| 650 | 0 | 9 | |a asymptotic methods |2 eczenas |
| 650 | 0 | 9 | |a linear termination |2 eCZ-BrMU |
| 650 | 0 | 9 | |a computer algorithms |2 eczenas |
| 655 | 7 | |a disertace |7 fd132024 |2 czenas | |
| 655 | 9 | |a dissertations |2 eczenas | |
| 658 | |a Informatika |b Fundamenty informatiky |c FI D-INF DIFI (DIFI) |2 CZ-BrMU | ||
| 700 | 1 | |a Brázdil, Tomáš, |d 1979- |7 mub2013776804 |% UČO 4074 |4 ths | |
| 710 | 2 | |a Masarykova univerzita. |b Katedra strojového učení a zpracování dat |4 dgg | |
| 856 | 4 | 1 | |u https://is.muni.cz/th/d9zyd/ |
| CAT | |c 20220915 |l MUB01 |h 0422 | ||
| CAT | |a POSPEL |b 02 |c 20221019 |l MUB01 |h 2324 | ||
| CAT | |a VESELA |b 02 |c 20230109 |l MUB01 |h 1410 | ||
| CAT | |a POSPEL |b 02 |c 20230313 |l MUB01 |h 1622 | ||
| CAT | |c 20230417 |l MUB01 |h 1117 | ||
| CAT | |a POSPEL |b 02 |c 20230612 |l MUB01 |h 0019 | ||
| CAT | |a POSPEL |b 02 |c 20230629 |l MUB01 |h 0036 | ||
| CAT | |a POSPEL |b 02 |c 20240318 |l MUB01 |h 2141 | ||
| CAT | |a REPISOVA |b 02 |c 20240405 |l MUB01 |h 1604 | ||
| CAT | |a VESELAX |b 02 |c 20240523 |l MUB01 |h 1423 | ||
| CAT | |a VESELAX |b 02 |c 20240523 |l MUB01 |h 1424 | ||
| CAT | |a VESELAX |b 02 |c 20240523 |l MUB01 |h 1425 | ||
| CAT | |a POSPEL |b 02 |c 20251119 |l MUB01 |h 2001 | ||
| LOW | |a POSLANO DO SKCR |b 2023-04-17 | ||
| 994 | - | 1 | |l MUB01 |l MUB01 |m VYSPR |1 FI |a Fakulta informatiky |2 SKLAD |b sklad |3 Diz. práce 2021 |5 42005D2738 |8 20230109 |f 72 |f Týdenní |r 20230109 |
| AVA | |a INF50 |b FI |c sklad |d Diz. práce 2021 |e available |t K dispozici |f 1 |g 0 |h N |i 0 |j SKLAD | ||