Exponential improvement of time complexity of model checking for multiagent systems with perfect recall
| Autor: | Natalya Olegovna Garanina |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Model checking
Theoretical computer science Computation tree logic Multi-agent system Data structure Propositional calculus Exponential function TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Exponential growth Computer Science::Logic in Computer Science Time complexity Algorithm Software Mathematics |
| Zdroj: | Programming and Computer Software. 38:294-303 |
| ISSN: | 1608-3261 0361-7688 |
| DOI: | 10.1134/s0361768812060047 |
| Popis: | The model checking algorithm for a combination of the computation tree logic (CTL) and the propositional logic of knowledge (PLK) in multiagent systems with perfect recall is revised. The proposed approach is based on data structures that are exponentially smaller than the structures used in the previous version of this checking algorithm. Thus, the time complexity of this algorithm is exponentially reduced. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink