Kokkinis, Ioannis
(2016).
*
The Complexity of Non-Iterated Probabilistic Justification Logic.
*
In:
Gyssens, Marc; Simari, Guillermo
(eds.)
Foundations of Information and Knowledge Systems - 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings. Lecture Notes in Computer Science: Vol. 9616 (pp. 292-310).
Cham: Springer
10.1007/978-3-319-30024-5_16

Text
chp%3A10.1007%2F978-3-319-30024-5_16.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (537kB) | Request a copy |

The logic PJ is a probabilistic logic defined by adding (noniterated) probability operators to the basic justification logic J. In this paper we establish upper and lower bounds for the complexity of the derivability problem in the logic PJ. The main result of the paper is that the complexity of the derivability problem in PJ remains the same as the complexity of the derivability problem in the underlying logic J, which is π[p/2] -complete. This implies that the probability operators do not increase the complexity of the logic, although they arguably enrich the expressiveness of the language.

Item Type: | Book Section (Book Chapter) |
---|---|

Division/Institute: | 08 Faculty of Science > Institute of Computer Science (INF) 08 Faculty of Science > Institute of Computer Science (INF) > Logic and Theory Group (LTG) |

UniBE Contributor: | Kokkinis, Ioannis |

Subjects: | 000 Computer science, knowledge & systems 500 Science > 510 Mathematics |

ISSN: | 0302-9743 |

ISBN: | 978-3-319-30023-8 |

Series: | Lecture Notes in Computer Science |

Publisher: | Springer |

Language: | English |

Submitter: | Lukas Jaun |

Date Deposited: | 09 May 2016 16:01 |

Last Modified: | 20 Mar 2017 13:49 |

Publisher DOI: | 10.1007/978-3-319-30024-5_16 |

BORIS DOI: | 10.7892/boris.79973 |

URI: | http://boris.unibe.ch/id/eprint/79973 |