Problém dosažitelnosti - Reachability problem

Dosažitelnost je základní problém, který se objevuje v několika různých kontextech: konečný a nekonečnýStát souběžné systémy, výpočetní modely jako mobilní automaty a Petriho sítě, programová analýza, diskrétní a spojité systémy časově kritické systémy, hybridní systémy, přepisovací systémy, pravděpodobnostní a parametrické systémy a otevřené systémy modelováno jako hry.[1]

Obecně problém dosažitelnosti lze formulovat následovně:

Vzhledem k výpočetnímu (potenciálně nekonečnému stavu) systému se sadou povolených pravidel nebo transformací rozhodněte, zda je určitý stav systému dosažitelný z daného počátečního stavu systému.

Varianty problému dosažitelnosti mohou vyplývat z dalších omezení počátečního nebo konečného stavu, zvláštního požadavku na cesty dosažitelnosti i pro iterativní dosažitelnost nebo změna otázek na analýzu vítězných strategií v nekonečných hrách nebo nevyhnutelnost nějaké dynamiky.

Typicky pro popis pevného systému daný v nějaké formě (redukční pravidla, soustavy rovnic, logické vzorce atd.) problém dosažitelnosti spočívá v kontrole, zda lze dosáhnout dané sady cílových stavů počínaje pevnou sadou počátečních stavů. Sada cílových stavů může být zastoupena explicitně nebo prostřednictvím nějakého implicitního vyjádření (např. Soustava rovnic, sada minimálních prvků s ohledem na nějaké uspořádání na stavech). Sofistikované kvantitativní a kvalitativní vlastnosti lze často omezit na základní otázky dosažitelnosti. Rozhodnutelnost a hranice složitosti, algoritmická řešení a efektivní heuristika jsou v této souvislosti všechny důležité aspekty, které je třeba vzít v úvahu. Algoritmická řešení jsou často založena na různých kombinacích průzkumných strategií, symbolických manipulacích množin stavů, vlastnostech rozkladu nebo redukci na lineární programování problémy a často z nich mají prospěch aproximace, abstrakce, zrychlení a extrapolační heuristika. Řešení ad hoc i řešení založená na obecném účelu řešitelé omezení a dedukční motory se často kombinují, aby se vyvážila účinnost a flexibilita.

Varianty problémů s dosažitelností

Otevřené problémy

Mezinárodní konference o problémech dosažitelnosti (RP)

Série Mezinárodní konference o problémech dosažitelnosti, dříve známá jako Workshop o problémech dosažitelnosti, je každoroční akademická konference, která sdružuje výzkumné pracovníky z různých oborů a prostředí zajímajících se o problémy dosažitelnosti, které se objevují v algebraických strukturách, výpočetních modelech, hybridních systémech, nekonečných hrách, logice a ověřování. Workshop se snaží zaplnit mezeru mezi výsledky získanými v různých oborech, ale sdílením společné matematické struktury nebo koncepčních obtíží.

Reference

  1. ^ Giorgio Delzanno, Igor Potapov (Eds.): Problémy s dosažitelností - 5. mezinárodní workshop, RP 2011, Janov, Itálie, 28. – 30. Září 2011. Sborník. Přednášky z informatiky 6945, Springer 2011, ISBN  978-3-642-24287-8