Jakub Michaliszyn

University of Wrocław

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Jan Otop

University of Wrocław

Alessio Lomuscio

Imperial College London

Emanuel Kieroński

University of Wrocław

Jerzy Marcinkowski

University of Wrocław

Piotr Wieczorek

University of Wrocław

Piotr Witkowski

University of Wrocław

Ian Pratt‐Hartmann

University of Manchester

Bartosz Bednarczyk

Institute of Computer Science

Lidia Tendera

University of Opole

Anca Muscholl

Institut Polytechnique de Bordeaux

Cooperative Institutions

University of Wrocław

Institute of Computer Science

University of Opole

Czech Academy of Sciences, Institute of Computer Science

Institute of Mathematics

Centre National de la Recherche Scientifique

Université Paris Cité

Laboratoire d'Informatique Algorithmique: Fondements et Applications

Max Planck Institute for Informatics

Imperial College London

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

Querying Best Paths in Graph Databases

arXiv (Cornell University) (2017)

Jakub Michaliszyn Jan Otop Piotr Wieczorek

Querying graph databases has recently received much attention. We propose a new approach to this problem, which balances competing goals of expressive power, language clarity and computational complexity. A distinctive feature of our approach is the ability to express properties of minimal (e.g. shortest) and maximal (e.g. most valuable) paths satisfying given criteria. To express complex properties in a modular way, we introduce labelling-generating ontologies. The resulting formalism is computationally attractive -- queries can be answered in non-deterministic logarithmic space in the size of the database.

Expressive power

CLARITY

Formalism (music)

10.48550/arxiv.1710.04419

Cite

Citations (1)

Decidable Elementary Modal Logics

Jakub Michaliszyn Jan Otop

In this paper, the modal logic over classes of structures definable by universal first-order Horn formulas is studied. We show that the satisfiability problems for that logics are decidable, confirming the conjecture from [E. Hemaspaandra and H. Schnoor, On the Complexity of Elementary Modal Logics, STACS 08]. We provide a full classification of logics defined by universal first-order Horn formulas, with respect to the complexity of satisfiability of modal logic over the classes of frames they define. It appears, that except for the trivial case of inconsistent formulas for which the problem is in P, local satisfiability is either NP-complete or PSPACE-complete, and global satisfiability is NP-complete, PSPACE-complete, or EXPTIME-complete. While our results holds even if we allow to use equality, we show that inequality leads to undecidability.

Satisfiability

EXPTIME

Boolean satisfiability problem

10.1109/lics.2012.59

Cite

Citations (8)

Deterministic Weighted Automata Under Partial Observability

Lecture notes in computer science (2023)

Jakub Michaliszyn Jan Otop

Observability

10.1007/978-3-031-43619-2_52

Cite

Citations (1)

Approximate Learning of Limit-Average Automata

arXiv (Cornell University) (2019)

Jakub Michaliszyn Jan Otop

Limit-average automata are weighted automata on infinite words that use average to aggregate the weights seen in infinite runs. We study approximate learning problems for limit-average automata in two settings: passive and active. In the passive learning case, we show that limit-average automata are not PAC-learnable as samples must be of exponential-size to provide (with good probability) enough details to learn an automaton. We also show that the problem of finding an automaton that fits a given sample is NP-complete. In the active learning case, we show that limit-average automata can be learned almost-exactly, i.e., we can learn in polynomial time an automaton that is consistent with the target automaton on almost all words. On the other hand, we show that the problem of learning an automaton that approximates the target automaton (with perhaps fewer states) is NP-complete. The abovementioned results are shown for the uniform distribution on words. We briefly discuss learning over different distributions.

Learning Automata

10.48550/arxiv.1906.11104

Cite

Citations (1)

Non-deterministic weighted automata evaluated over Markov chains

Journal of Computer and System Sciences (2019)

Jakub Michaliszyn Jan Otop

Probabilistic automaton

10.1016/j.jcss.2019.10.001

Cite

Citations (3)

Finite Satisfiability of Modal Logic over Horn~Definable Classes of Frames.

Advances in Modal Logic (2012)

Jakub Michaliszyn Emanuel Kieroński

Modal logic plays an important role in various areas of computer science, including verification and knowledge representation. In many practical applications it is natural to consider some restrictions of classes of admissible frames. Traditionally classes of frames are defined by modal axioms. However, many important classes of frames, e.g. the class of transitive frames or the class of Euclidean frames, can be defined in a more natural way by first-order formulas. In a recent paper it was proved that the satisfiability problem for modal logic over the class of frames defined by a universally quantified, first-order Horn formula is decidable. In this paper we show that also the finite satisfiability problem for modal logic over such classes is decidable.

Satisfiability

Horn clause

Source

Cite

Citations (1)

Average Stack Cost of Büchi Pushdown Automata

arXiv (Cornell University) (2018)

Jakub Michaliszyn Jan Otop

We study the average stack cost of Buechi pushdown automata (Buechi PDA). We associate a non-negative price with each stack symbol and define the cost of a stack as the sum of costs of all its elements. We introduce and study the average stack cost problem (ASC), which asks whether there exists an accepting run of a given Buechi PDA such that the long-run average of stack costs is below some given threshold. The ASC problem generalises mean-payoff objective and can be use to express quantitative properties of pushdown systems. In particular, we can compute the average response time using the ASC problem. We show that the ASC problem can be solved in polynomial time.

Pushdown automaton

Deterministic pushdown automaton

Embedded pushdown automaton

Call stack

10.4230/lipics.fsttcs.2017.42

Cite

Citations (1)

Querying data graphs with arithmetical regular expressions

International Joint Conference on Artificial Intelligence (2016)

Maciej Grabon Jakub Michaliszyn Jan Otop Piotr Wieczorek

We propose a query language LARE for graphs whose edges are labelled by a finite alphabet and nodes store unbounded data values. LARE is based on a variant of regular expressions with memory. Queries of LARE can compare quantities of memorised graph nodes and their neighbourhoods. These features allow us to express a number of natural properties, while keeping the data complexity (with a query fixed) in non-deterministic logarithmic space. We establish an algorithm that works efficiently not only with LARE, but also with a wider language defined using effective relational conditions, another formalism we propose.

Arithmetic function

Formalism (music)

Regular expression

Regular language

Source

Cite

Citations (1)

An epistemic Halpern-Shoham logic

International Joint Conference on Artificial Intelligence (2013)

Alessio Lomuscio Jakub Michaliszyn

We define a family of epistemic extensions of Halpern-Shoham logic for reasoning about temporal-epistemic properties of multi-agent systems. We exemplify their use and study the complexity of their model checking problem. We show a range of results ranging from PTIME to PSPACE-hard depending on the logic considered.

Source

Cite

Citations (52)

Modal Logics Definable by Universal Three-Variable Formulas

Foundations of Software Technology and Theoretical Computer Science (2011)

Emanuel Kieroński Jakub Michaliszyn Jan Otop

We consider the satisfiability problem for modal logic over classes of structures definable by universal first-order formulas with three variables. We exhibit a simple formula for which the problem is undecidable. This improves an earlier result in which nine variables were used. We also show that for classes defined by three-variable, universal Horn formulas the problem is decidable. This subsumes decidability results for many natural modal logics, including T, B, K4, S4, S5.

Undecidable problem

Satisfiability

Boolean satisfiability problem

Modal operator

10.4230/lipics.fsttcs.2011.264

Cite

Citations (5)