4 citations · 11 across the 11 of their papers we have counts for
15 papers
Finite Satisfiability of Two-Variable Logic with Arbitrarily Many Successors
Artur Jeż, Jakub Michaliszyn, Piotr Witkowski
We study finite satisfiability of two-variable first-order logic over structures equipped with an arbitrary finite number of independent successor relations of linear orders. The n…
Undecidability of Reachability for Constraint Automata
Jakub Michaliszyn
We prove that reachability for constraint automata over finite binary words is undecidable. Eight registers suffice, with conjunctive guards using only equality, proper prefix, pro…
EntroPrefill: Renyi-Guided Context Pruning with Conditional Stability Guarantees for Retrieval-Augmented Generation
Inbasekaran S
Mid-prefill pruning can reduce the sequence processed by deeper transformer layers, but attention concentration alone does not certify that discarded context is dispensable. We for…
Deterministic Weighted Automata under Partial Observability
Jakub Michaliszyn, Jan Otop
Weighted automata is a basic tool for specification in quantitative verification, which allows to express quantitative features of analysed systems such as resource consumption. Qu…
"Most of" leads to undecidability: Failure of adding frequencies to LTL
Bartosz Bednarczyk, Jakub Michaliszyn
Linear Temporal Logic (LTL) interpreted on finite traces is a robust specification framework popular in formal verification. However, despite the high interest in the logic in rece…
Modular Path Queries with Arithmetic
Jakub Michaliszyn, Jan Otop, Piotr Wieczorek
We propose a new approach to querying graph databases. Our approach balances competing goals of expressive power, language clarity and computational complexity. A distinctive featu…
Non-deterministic weighted automata evaluated over Markov chains
Jakub Michaliszyn, Jan Otop
We present the first study of non-deterministic weighted automata under probabilistic semantics. In this semantics words are random events, generated by a Markov chain, and functio…
Approximate Learning of Limit-Average Automata
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-ave…
Elementary Multimodal Logics
Jakub Michaliszyn
We study multimodal logics over universally first-order definable classes of frames. We show that even for bimodal logics, there are universal Horn formulas that define set of fram…
Average Stack Cost of Buechi Pushdown Automata
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 cost…
Querying Best Paths in Graph Databases
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 c…
Model Checking Epistemic Halpern-Shoham Logic Extended with Regular Expressions
Alessio Lomuscio, Jakub Michaliszyn
The Epistemic Halpern-Shoham logic (EHS) is a temporal-epistemic logic that combines the interval operators of the Halpern-Shoham logic with epistemic modalities. The semantics of…
On Injective Embeddings of Tree Patterns
Jakub Michaliszyn, Anca Muscholl, Sławek Staworko +2
We study three different kinds of embeddings of tree patterns: weakly-injective, ancestor-preserving, and lca-preserving. While each of them is often referred to as injective embed…
The Last Paper on the Halpern-Shoham Interval Temporal Logic
Jerzy Marcinkowski, Jakub Michaliszyn
The Halpern-Shoham logic is a modal logic of time intervals. Some effort has been put in last ten years to classify fragments of this beautiful logic with respect to decidability o…
The cost of being co-Buchi is nonlinear
Jerzy Marcinkowski, Jakub Michaliszyn
It is well known, and easy to see, that not each nondeterministic Buchi automaton on infinite words can be simulated by a nondeterministic co-Buchi automaton. We show that in the c…