Zobrazeno 1 - 10
of 69
pro vyhledávání: '"Juha Kontinen"'
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 226, Iss Proc. GandALF 2016, Pp 198-212 (2016)
We study quantified propositional logics from the complexity theoretic point of view. First we introduce alternating dependency quantified boolean formulae (ADQBF) which generalize both quantified and dependency quantified boolean formulae. We show t
Externí odkaz:
https://doaj.org/article/27d696fcf69d4b1e8fd5f1ece7e74c3a
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 193, Iss Proc. GandALF 2015, Pp 73-85 (2015)
We study the data complexity of model-checking for logics with team semantics. For dependence and independence logic, we completely characterize the tractability/intractability frontier of data complexity of both quantifier-free and quantified formul
Externí odkaz:
https://doaj.org/article/ba033f5d90404de5bb697432fce2b8c9
Publikováno v:
Logical Methods in Computer Science, Vol Volume 10, Issue 3 (2014)
In this paper we study the expressive power of Horn-formulae in dependence logic and show that they can express NP-complete problems. Therefore we define an even smaller fragment D-Horn* and show that over finite successor structures it captures the
Externí odkaz:
https://doaj.org/article/72ca468483ab4f468485baebe0749bdb
Autor:
Juha Kontinen, Heribert Vollmer
Publikováno v:
Logical Methods in Computer Science, Vol Volume 6, Issue 3 (2010)
We study logics defined in terms of second-order monadic monoidal and groupoidal quantifiers. These are generalized quantifiers defined by monoid and groupoid word-problems, equivalently, by regular and context-free languages. We give a computational
Externí odkaz:
https://doaj.org/article/8a714fc8703740c28aafbf800add9dd0
Autor:
JUHA KONTINEN, FAN YANG
Publikováno v:
The Journal of Symbolic Logic. 88:579-619
In this paper, we introduce a logic based on team semantics, called $\mathbf {FOT} $ , whose expressive power is elementary, i.e., coincides with first-order logic both on the level of sentences and (possibly open) formulas, and we also show that a s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::015197ef570898dd47357fcc79cad8c2
https://doi.org/10.1017/jsl.2022.80
https://doi.org/10.1017/jsl.2022.80
Publikováno v:
Journal of Logic and Computation. 32:1624-1644
In this paper, we investigate the parameterized complexity of model checking for Dependence and Independence logic, which are well studied logics in the area of Team Semantics. We start with a list of nine immediate parameterizations for this problem
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6d3c5b51ceb7e46466dd9e49e159e3a5
https://doi.org/10.1093/logcom/exac070
https://doi.org/10.1093/logcom/exac070
Publikováno v:
Logical Foundations of Computer Science ISBN: 9783030930998
In this paper, we investigate the parameterized complexity of model checking for Dependence Logic which is a well studied logic in the area of Team Semantics. We start with a list of nine immediate parameterizations for this problem, namely: the numb
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fd513c3547afc46bdc1c40b5fcdcd120
http://hdl.handle.net/10138/338066
http://hdl.handle.net/10138/338066
Publikováno v:
Annals of Pure and Applied Logic. 173:103104
We define and study logics in the framework of probabilistic team semantics and over metafinite structures. Our work is paralleled by the recent development of novel axiomatizable and tractable logics in team semantics that are closed under the Boole
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d67273fb00a7787d57fc21df2f0f454b
https://doi.org/10.1016/j.apal.2022.103104
https://doi.org/10.1016/j.apal.2022.103104
Autor:
Juha Kontinen, Max Sandström
Publikováno v:
Logic, Language, Information, and Computation ISBN: 9783030888527
WoLLIC
WoLLIC
In this article we study linear temporal logics with team semantics (\(\mathrm {TeamLTL}\)) that are novel logics for defining hyperproperties. We define Kamp-type translations of these logics into fragments of first-order team logic and second-order
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::40a61415ca41119908c50f065a22dda4
http://arxiv.org/abs/2110.11109
http://arxiv.org/abs/2110.11109
We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. We completely determine the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f81f16b2a12aa71f9a8164c5f0204f32
http://hdl.handle.net/10138/322725
http://hdl.handle.net/10138/322725