54 citations · 95 across the 24 of their papers we have counts for
18 papers · 1 filter
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…
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…
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…
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…
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…
Parametrized Universality Problems for One-Counter Nets
Shaull Almagor, Udi Boker, Piotr Hofman +1
We study the language universality problem for One-Counter Nets, also known as 1-dimensional Vector Addition Systems with States (1-VASS), parameterized either with an initial coun…
Weak Cost Register Automata are Still Powerful
Shaull Almagor, Michaël Cadilhac, Filip Mazowiecki +1
We consider one of the weakest variants of cost register automata over a tropical semiring, namely copyless cost register automata over with updates using and i…
Minimizing Expected Cost Under Hard Boolean Constraints, with Applications to Quantitative Synthesis
Shaull Almagor, Orna Kupferman, Yaron Velner
In Boolean synthesis, we are given an LTL specification, and the goal is to construct a transducer that realizes it against an adversarial environment. Often, a specification conta…