Dr Jonni Virtema
School of Computer Science
Lecturer in Verification
Member of the Foundations of Computation research group
J.T.Virtema@sheffield.ac.uk
Regent Court (DCS)
Full contact details
Dr Jonni Virtema
School of Computer Science
Regent Court (DCS)
211 Portobello
Sheffield
S1 4DP
School of Computer Science
Regent Court (DCS)
211 Portobello
Sheffield
S1 4DP
- Profile
-
Jonni is a Lecturer in Verification at the Department of Computer Science. Before joining, in September 2021, he held research positions as a PI or a hired postdoc in a series of projects funded by the German Research Foundation (DFG), the Japan Society for the Promotion of Science (JSPS), the Research Foundation – Flanders (FWO), and the Academy of Finland (AKA).
Jonni received his MSc (2008) and PhD (2014) in mathematics from the University of Tampere, Finland. In 2020, he received the title of a Docent in Mathematical Logic from the University of Helsinki, Finland. His research interests originate from the general fields of finite model theory and logic in computer science. His research themes revolve around the interplay between expressivity and complexity of different logical formalisms, and in logical characterisations of complexity classes.
- Research interests
-
Dr Jonni Virtema's research interests include: finite model theory, logic in computer science, logics for dependence and independence, modal logics, logics for verification, logical foundations of neural networks, logical foundations of quantum information theory, computational complexity, and logics with team semantics.
- Publications
-
Show: Featured publications All publications
Featured publications
Journal articles
- Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals. Annals of Pure and Applied Logic. View this article in WRRO
- Descriptive complexity of deterministic polylogarithmic time and space. Journal of Computer and System Sciences, 119, 145-163.
Conference proceedings papers
- Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions. THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 11 (pp 12278-12285)
- Unified foundations of team semantics via semirings. Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, KR 2023 (pp 75-85). Rhodes, Greece, 2 September 2023 - 2 September 2023. View this article in WRRO
- Temporal Team Semantics Revisited. Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
- Linear-time temporal logic with team semantics: expressivity and complexity. 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021), Vol. 213. Virtual Conference, 15 December 2021 - 17 December 2021. View this article in WRRO
- Descriptive complexity of real computation and probabilistic independence logic. Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science
- Weak models of distributed computing, with connections to modal logic. Proceedings of the 2012 ACM symposium on Principles of distributed computing - PODC '12, 16 July 2012 - 18 July 2012.
- Complexity of Two-Variable Dependence Logic and IF-Logic. 2011 IEEE 26th Annual Symposium on Logic in Computer Science, 21 June 2011 - 24 June 2011.
All publications
Journal articles
- Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals. Annals of Pure and Applied Logic. View this article in WRRO
- Descriptive complexity of deterministic polylogarithmic time and space. Journal of Computer and System Sciences, 119, 145-163.
- Polyteam semantics. Journal of Logic and Computation, 30(8), 1541-1566.
- Model checking and validity in propositional and modal inclusion logics. Journal of Logic and Computation, 29(5), 605-630.
- Characterising modal definability of team-based logics via the universal modality. Annals of Pure and Applied Logic, 170(9), 1100-1127.
- Approximation and dependence via multiteam semantics. Annals of Mathematics and Artificial Intelligence, 83(3-4), 297-320.
- Complexity of propositional logics in team semantic. ACM Transactions on Computational Logic, 19(1).
- Boolean dependence logic and partially-ordered connectives. Journal of Computer and System Sciences, 88, 103-125.
- Complexity of validity for propositional dependence logics. Information and Computation, 253, 224-236.
- Weak models of distributed computing, with connections to modal logic. Distributed Computing, 28(1), 31-53.
- Complexity of two-variable dependence logic and IF-logic. Information and Computation, 239, 237-253.
- Undecidable first-order theories of affine geometries. Logical Methods in Computer Science, 9(4).
Conference proceedings papers
- A Remark on the Expressivity of Asynchronous TeamLTL and HyperLTL. Foundations of Information and Knowledge Systems, 13th International Symposium, FoIKS 2024, Sheffield, UK, April 8–11, 2024, Proceedings, Vol. 14589 (pp 275-286)
- Computing Repairs Under Functional and Inclusion Dependencies via Argumentation. Foundations of Information and Knowledge Systems, 13th International Symposium, FoIKS 2024, Sheffield, UK, April 8–11, 2024, Proceedings, Vol. 14589 (pp 23-42)
- Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions. THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 11 (pp 12278-12285)
- Unified foundations of team semantics via semirings. Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, KR 2023 (pp 75-85). Rhodes, Greece, 2 September 2023 - 2 September 2023. View this article in WRRO
- Temporal Team Semantics Revisited. Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
- Linear-time temporal logic with team semantics: expressivity and complexity. 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021), Vol. 213. Virtual Conference, 15 December 2021 - 17 December 2021. View this article in WRRO
- Tractability Frontiers in Probabilistic Team Semantics and Existential Second-Order Logic over the Reals. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12678 LNAI (pp 262-278)
- On the complexity of horn and krom fragments of second-order boolean logic. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 183
- Descriptive complexity of real computation and probabilistic independence logic. Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science
- Fully Generic Queries: Open Problems and Some Partial Answers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 11815 LNCS (pp 20-31)
- Descriptive Complexity of Deterministic Polylogarithmic Time. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 11541 LNCS (pp 208-222)
- Facets of Distribution Identities in Probabilistic Team Semantics. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 11468 LNAI (pp 304-320)
- Team semantics for the specification and verification of hyperproperties. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 117
- Expressivity within second-order transitive-closure logic. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 119
- Probabilistic team semantics. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 10833 LNCS (pp 186-206)
- Polyteam semantics. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 10703 LNCS (pp 190-210)
- Model checking and validity in propositional and modal inclusion logics. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 83
- On quantified propositional logics and the exponential time hierarchy. Electronic Proceedings in Theoretical Computer Science, EPTCS, Vol. 226 (pp 198-212)
- Decidability of predicate logics with team semantics. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 58
- A team based variant of CTL. Proceedings of the International Workshop on Temporal Representation and Reasoning, Vol. 2016-January (pp 140-149)
- Characterizing relative frame definability in team semantics via the universal modality. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 9803 LNCS (pp 392-409)
- Approximation and dependence via multiteam semantics. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 9616 (pp 271-291)
- Axiomatizing propositional dependence logics. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 41 (pp 292-307)
- Characterizing frame definability in team semantics via the universal modality. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 9160 (pp 140-155)
- Complexity of propositional independence and inclusion logic. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 9234 (pp 269-280)
- Complexity of validity for propositional dependence logics. Electronic Proceedings in Theoretical Computer Science, EPTCS, Vol. 161 (pp 18-31)
- The expressive power of modal dependence logic. Advances in Modal Logic, Vol. 10 (pp 294-312)
- Boolean dependence logic and partially-ordered connectives. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 8071 LNCS (pp 111-125)
- Extended modal dependence logic. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 8071 LNCS (pp 126-137)
- Weak models of distributed computing, with connections to modal logic. Proceedings of the 2012 ACM symposium on Principles of distributed computing - PODC '12, 16 July 2012 - 18 July 2012.
- Undecidable first-order theories of affine geometries. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 16 (pp 470-484)
- Complexity of Two-Variable Dependence Logic and IF-Logic. 2011 IEEE 26th Annual Symposium on Logic in Computer Science, 21 June 2011 - 24 June 2011.
- Expressivity Landscape for Logics with Probabilistic Interventionist Counterfactuals. 32nd EACSL Annual Conference on Computer Science Logic, CSL 2024, February 19-23, 2023, Naples, Italy.
- Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity. 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28-September 1, 2023, Bordeaux, France
- Strongly complete axiomatization for a logic with probabilistic interventionist counterfactuals. Logics in Artificial Intelligence - 18th European Conference, JELIA 2023, Dresden, Germany, September 20-22, 2023, Proceedings.
- Logics with probabilistic team semantics and the Boolean negation. Logics in Artificial Intelligence - 18th European Conference, JELIA 2023, Dresden, Germany, September 20-22, 2023, Proceedings.
- Parameterized Complexity of Propositional Inclusion and Independence Logic. Logic, Language, Information, and Computation - 29th International Workshop, WoLLIC 2023, Halifax, Canada, July 11-14, 2023, Proceedings.
Preprints
- Graph Neural Networks and Arithmetic Circuits.
- Computing Repairs Under Functional and Inclusion Dependencies via
Argumentation.
- A fine-grained framework for database repairs.
- Logics with probabilistic team semantics and the Boolean negation.
- Complexity of Neural Network Training and ETR: Extensions with
Effectively Continuous Functions.
- Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity.
- Strongly complete axiomatization for a logic with probabilistic
interventionist counterfactuals.
- Expressivity Landscape for Logics with Probabilistic Interventionist
Counterfactuals.
- Unified Foundations of Team Semantics via Semirings.
- Temporal Team Semantics Revisited.
- Tractability frontiers in probabilistic team semantics and existential
second-order logic over the reals.
- Linear-time Temporal Logic with Team Semantics: Expressivity and
Complexity.
- On the Complexity of Horn and Krom Fragments of Second-Order Boolean
Logic.
- Descriptive complexity of real computation and probabilistic
independence logic.
- Descriptive Complexity of Deterministic Polylogarithmic Time and Space.
- Facets of Distribution Identities in Probabilistic Team Semantics.
- Expressivity within second-order transitive-closure logic.
- Probabilistic team semantics.
- Team Semantics for the Specification and Verification of Hyperproperties.
- Polyteam Semantics.
- Model Checking and Validity in Propositional and Modal Inclusion Logics.
- Characterizing Relative Frame Definability in Team Semantics via the
Universal Modality.
- Approximation and Dependence via Multiteam Semantics.
- A Team Based Variant of CTL.
- Complexity of Propositional Logics in Team Semantics.
- Characterising Modal Definability of Team-Based Logics via the Universal
Modality.
- Decidability of predicate logics with team semantics.
- Axiomatizing Propositional Dependence Logics.
- Boolean Dependence Logic and Partially-Ordered Connectives.
- Complexity of validity for propositional dependence logics.
- The Expressive Power of Modal Dependence Logic.
- Undecidable First-Order Theories of Affine Geometries.
- Undecidable First-Order Theories of Affine Geometries.
- Weak Models of Distributed Computing, with Connections to Modal Logic.
- Complexity of two-variable Dependence Logic and IF-Logic.
- Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals. Annals of Pure and Applied Logic. View this article in WRRO
- Grants
-
Current Grants
Logical approach to quantum mechanics and contextuality, DFG, 09/2021 - 10/2020, £160,711, as PI