Complexity of the interpretability logic IL

Autor: Luka Mikec, Mladen Vuković, Fedor Pakhomov
Jazyk: angličtina
Rok vydání: 2019
Předmět:
Discrete mathematics
Computer Science::Computer Science and Game Theory
Logic
Computer science
010102 general mathematics
Computer Science::Neural and Evolutionary Computation
Mathematics - Logic
02 engineering and technology
03F45 (primary)
03D15 (secondary)
Decision problem
Computer Science::Computational Complexity
interpretability logic
Veltman semantics
decidability
complexity
PSPACE
01 natural sciences
Interpretability logic
interpretability logic
PSPACE-completeness
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Fragment (logic)
Computer Science::Logic in Computer Science
0202 electrical engineering
electronic engineering
information engineering
FOS: Mathematics
020201 artificial intelligence & image processing
0101 mathematics
Logic (math.LO)
Computer Science::Formal Languages and Automata Theory
PSPACE
Popis: We show that the decision problem for the basic system of interpretability logic IL is PSPACE-complete. For this purpose we present an algorithm which uses polynomial space with respect to the complexity of a given formula. The existence of such algorithm, together with the previously known PSPACE hardness of the closed fragment of IL, implies PSPACE-completeness.
Comment: 7 pages
Databáze: OpenAIRE
Externí odkaz: