36 citations · 111 across the 11 of their papers we have counts for
11 papers
Some Complexity Results for Stateful Network Verification
Kalev Alpernas, Aurojit Panda, Alexander Rabinovich +4
In modern networks, forwarding of packets often depends on the history of previously transmitted traffic. Such networks contain stateful middleboxes, whose forwarding behaviour dep…
Ambiguity Hierarchy of Regular Infinite Tree Languages
Alexander Rabinovich, Doron Tiferet
An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is k-ambiguous (for k > 0) if for every input it has at most k accepting compu…
A Proof of Stavi's Theorem
Alexander Rabinovich
Kamp's theorem established the expressive equivalence of the temporal logic with Until and Since and the First-Order Monadic Logic of Order (FOMLO) over the Dedekind-complete time…
A Proof of Kamp's theorem
Alexander Rabinovich
We provide a simple proof of Kamp's theorem.
The Complexity of Multi-Mean-Payoff and Multi-Energy Games
Yaron Velner, Krishnendu Chatterjee, Laurent Doyen +3
In mean-payoff games, the objective of the protagonist is to ensure that the limit average of an infinite sequence of numeric weights is nonnegative. In energy games, the objective…
Decidable Expansions of Labelled Linear Orderings
Alexis Bes, Alexander Rabinovich
Consider a linear ordering equipped with a finite sequence of monadic predicates. If the ordering contains an interval of order type ωor -ω, and the monadic second-order theory of…