54 citations · 95 across the 24 of their papers we have counts for
38 papers
Analyzing the Interaction of Optimal Strategies in Mean-Payoff Bidding Games
Shaull Almagor, Guy Avni, Julian Ewaied
A common assumption when designing an agent in a multi-agent system is that the other agents behave adversarially. This allows a designer to obtain the strongest guarantees when th…
Representing One Letter Weighted Automata Over the Tropical Semiring
Shaull Almagor, Ismaël Jecker, Filip Mazowiecki +3
We consider weighted automata over the tropical semiring . Recently, it was shown that determinisation is decidable; in this paper we focus on the comple…
A Factorization Theorem for Forest Algebras
Shaull Almagor, Michaël Cadilhac, Asaf Shoham
Simon's factorization theorem is a celebrated tool in algebraic automata theory, providing bounded-depth decompositions of words with respect to morphisms into finite semigroups. W…
A Complexity Bound for Determinisation of Min-Plus Weighted Automata
Shaull Almagor, Guy Arbel, Sarai Sheinvald
The determinisation problem for min-plus (tropical) weighted automata was recently shown to be decidable. However, the proof is purely existential, relying on several non-construct…
Stress-Testing Causal Claims via Cardinality Repairs
Yarden Gabbay, Haoquan Guan, Shaull Almagor +3
Causal analyses derived from observational data underpin high-stakes decisions in domains such as healthcare, public policy, and economics. Yet such conclusions can be surprisingly…
Unambiguisability and Register Minimisation of Min-Plus Models
Shaull Almagor, Guy Arbel, Sarai Sheinvald
We study the unambiguisability problem for min-plus (tropical) weighted automata (WFAs), and the counter-minimisation problem for tropical Cost Register Automata (CRAs), which are…
Box-Reachability in Vector Addition Systems
Shaull Almagor, Itay Hasson, Michał Pilipczuk +1
We consider a variant of reachability in Vector Addition Systems (VAS) dubbed \emph{box reachability}, whereby a vector is box-reachable from in a VAS i…
Determinization of Min-Plus Weighted Automata is Decidable
Shaull Almagor, Guy Arbel, Sarai Sheinvald
We show that the determinization problem for min-plus (tropical) weighted automata is decidable, thus resolving this long-standing open problem. In doing so, we develop a new toolb…
Robin Hood Reachability Bidding Games
Shaull Almagor, Guy Avni, Neta Dafni
Two-player graph games are a fundamental model for reasoning about the interaction of agents. These games are played between two players who move a token along a graph. In bidding…
Two-Way One-Counter Nets Revisited
Shaull Almagor, Michaël Cadilhac, Asaf Yeshurun
One Counter Nets (OCNs) are finite-state automata equipped with a counter that cannot become negative, but cannot be explicitly tested for zero. Their close connection to various o…
Quantitative Semantics for Jumping Automata
Shaull Almagor, Neta Dafni, Ishai Salgado
Jumping automata are finite automata that read their input in a non-sequential manner, by allowing a reading head to ``jump'' between positions on the input, consuming a permutatio…
Determinization of Integral Discounted-Sum Automata is Decidable
Shaull Almagor, Neta Dafni
Nondeterministic Discounted-Sum Automata (NDAs) are nondeterministic finite automata equipped with a discounting factor , and whose transitions are labelled by weights. The va…
Synchronized CTL over One-Counter Automata
Shaull Almagor, Daniel Assa, Udi Boker
We consider the model-checking problem of Synchronized Computation-Tree Logic (CTL+Sync) over One-Counter Automata (OCAs). CTL+Sync augments CTL with temporal operators that requir…
Dimension-Minimality and Primality of Counter Nets
Shaull Almagor, Guy Avni, Henry Sinclair-Banks +1
A -Counter Net (-CN) is a finite-state automaton equipped with integer counters that are not allowed to become negative, but do not have explicit zero tests. This languag…
Introducing Delays in Multi-Agent Path Finding
Justin Kottinger, Tzvika Geft, Shaull Almagor +2
We consider a Multi-Agent Path Finding (MAPF) setting where agents have been assigned a plan, but during its execution some agents are delayed. Instead of replanning from scratch w…
Jumping Automata over Infinite Words
Shaull Almagor, Omer Yizhaq
Jumping automata are finite automata that read their input in a non-consecutive manner, disregarding the order of the letters in the word. We introduce and study jumping automata o…
The Geometry of Reachability in Continuous Vector Addition Systems with States
Shaull Almagor, Arka Ghosh, Tim Leys +1
We study the geometry of reachability sets of continuous vector addition systems with states (VASS). In particular we establish that they are almost Minkowski sums of convex cones…
Concurrent Games with Multiple Topologies
Shaull Almagor, Shai Guendelman
Concurrent multi-player games with -regular objectives are a standard model for systems that consist of several interacting components, each with its own objective. The standard…
Conflict-based Search for Multi-Robot Motion Planning with Kinodynamic Constraints
Justin Kottinger, Shaull Almagor, Morteza Lahijanian
Multi-robot motion planning (MRMP) is the fundamental problem of finding non-colliding trajectories for multiple robots acting in an environment, under kinodynamic constraints. Due…
Conflict-Based Search for Explainable Multi-Agent Path Finding
Justin Kottinger, Shaull Almagor, Morteza Lahijanian
In the Multi-Agent Path Finding (MAPF) problem, the goal is to find non-colliding paths for agents in an environment, such that each agent reaches its goal from its initial locatio…
Determinization of One-Counter Nets
Shaull Almagor, Asaf Yeshurun
One-Counter Nets (OCNs) are finite-state automata equipped with a counter that is not allowed to become negative, but does not have zero tests. Their simplicity and close connectio…
Good-Enough Synthesis
Shaull Almagor, Orna Kupferman
In the classical synthesis problem, we are given an LTL formula ψover sets of input and output signals, and we synthesize a system T that realizes ψ: with every input sequences x,…
Simulation by Rounds of Letter-to-Letter Transducers
Antonio Abu Nassar, Shaull Almagor
Letter-to-letter transducers are a standard formalism for modeling reactive systems. Often, two transducers that model similar systems differ locally from one another, by behaving…
Deciding -Regular Properties on Linear Recurrence Sequences
Shaull Almagor, Toghrul Karimov, Edon Kelmendi +2
We consider the problem of deciding -regular properties on infinite traces produced by linear loops. Here we think of a given loop as producing a single infinite trace that enco…