27 citations · 69 across the 15 of their papers we have counts for
16 papers · 1 filter
The Target Discounted-Sum Problem
Udi Boker, Thomas A. Henzinger, Jan Otop
The target discounted-sum problem is the following: Given a rational discount factor and three rational values , and , does there exist a finite or an infinite sequ…
History-Determinism vs Fair Simulation
Udi Boker, Thomas A. Henzinger, Karoliina Lehtinen +1
An automaton is history-deterministic if its nondeterminism can be resolved on the fly, only using the prefix of the word read so far. This mild form of nondeterminism has attracte…
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…
Safety and Liveness of Quantitative Properties and Automata
Udi Boker, Thomas A. Henzinger, Nicolas Mazzocchi +1
Safety and liveness stand as fundamental concepts in formal languages, playing a key role in verification. The safety-liveness classification of boolean properties characterizes wh…
On the Comparison of Discounted-Sum Automata with Multiple Discount Factors
Udi Boker, Guy Hefetz
We look into the problems of comparing nondeterministic discounted-sum automata on finite and infinite words. That is, the problems of checking for automata and whether or…
On the Translation of Automata to Linear Temporal Logic
Udi Boker, Karoliina Lehtinen, Salomon Sickert
While the complexity of translating future linear temporal logic (LTL) into automata on infinite words is well-understood, the size increase involved in turning automata back to LT…
History Determinism vs. Good for Gameness in Quantitative Automata
Udi Boker, Karoliina Lehtinen
Automata models between determinism and nondeterminism/alternations can retain some of the algorithmic properties of deterministic automata while enjoying some of the expressivenes…
Token Games and History-Deterministic Quantitative-Automata
Udi Boker, Karoliina Lehtinen
A nondeterministic automaton is history-deterministic if its nondeterminism can be resolved by only considering the prefix of the word read so far. Due to their good compositional…
On the Succinctness of Alternating Parity Good-for-Games Automata
Udi Boker, Denis Kuperberg, Karoliina Lehtinen +1
We study alternating parity good-for-games (GFG) automata, i.e., alternating parity automata where both conjunctive and disjunctive choices can be resolved in an online manner, wit…
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…
On Succinctness and Recognisability of Alternating Good-for-Games Automata
Udi Boker, Denis Kuperberg, Karoliina Lehtinen +1
We study alternating good-for-games (GFG) automata, i.e., alternating automata where both conjunctive and disjunctive choices can be resolved in an online manner, without knowledge…
Good for Games Automata: From Nondeterminism to Alternation
Udi Boker, Karoliina Lehtinen
A word automaton recognizing a language is good for games (GFG) if its composition with any game with winning condition preserves the game's winner. While all deterministic…
Register Games
Karoliina Lehtinen, Udi Boker
The complexity of parity games is a long standing open problem that saw a major breakthrough in 2017 when two quasi-polynomial algorithms were published. This article presents a th…
How Deterministic are Good-For-Games Automata?
Udi Boker, Orna Kupferman, Michał Skrzypczak
In GFG automata, it is possible to resolve nondeterminism in a way that only depends on the past and still accepts all the words in the language. The motivation for GFG automata co…
Families of DFAs as Acceptors of -Regular Languages
Dana Angluin, Udi Boker, Dana Fisman
Families of DFAs (FDFAs) provide an alternative formalism for recognizing -regular languages. The motivation for introducing them was a desired correlation between the automaton…
Exact and Approximate Determinization of Discounted-Sum Automata
Udi Boker, Thomas A. Henzinger
A discounted-sum automaton (NDA) is a nondeterministic finite automaton with edge weights, valuing a run by the discounted sum of visited edge weights. More precisely, the weight i…