Zobrazeno 1 - 10
of 88
pro vyhledávání: '"Boker, Udi"'
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 attracted particular attention for its applications in synthesis problems. An
Externí odkaz:
http://arxiv.org/abs/2407.08620
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 require several paths to satisfy properties in a synchronous manner, e.g., t
Externí odkaz:
http://arxiv.org/abs/2308.03308
Autor:
Boker, Udi, Hefetz, Guy
Discounting the influence of future events is a key paradigm in economics and it is widely used in computer-science models, such as games, Markov decision processes (MDPs), reinforcement learning, and automata. While a single game or MDP may allow fo
Externí odkaz:
http://arxiv.org/abs/2307.08780
Safety and liveness stand as fundamental concepts in formal languages, playing a key role in verification. The safety-liveness classification of boolean properties characterizes whether a given property can be falsified by observing a finite prefix o
Externí odkaz:
http://arxiv.org/abs/2307.06016
Autor:
Boker, Udi, Hefetz, Guy
Publikováno v:
proceedings of FoSSaCS. pp. 371-391 (2023)
We look into the problems of comparing nondeterministic discounted-sum automata on finite and infinite words. That is, the problems of checking for automata $A$ and $B$ whether or not it holds that for all words $w$, $A(w)=B(w), A(w) \leq B(w)$, or $
Externí odkaz:
http://arxiv.org/abs/2301.04086
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 LTL is not. In particular, there is no known elementary bound on the com
Externí odkaz:
http://arxiv.org/abs/2201.10267
Autor:
Boker, Udi, Lehtinen, Karoliina
Publikováno v:
Logical Methods in Computer Science, Volume 19, Issue 4 (November 3, 2023) lmcs:9922
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 properties, history-deterministic automata are useful in solving games
Externí odkaz:
http://arxiv.org/abs/2110.14308
Autor:
Boker, Udi, Lehtinen, Karoliina
Automata models between determinism and nondeterminism/alternations can retain some of the algorithmic properties of deterministic automata while enjoying some of the expressiveness and succinctness of nondeterminism. We study three closely related s
Externí odkaz:
http://arxiv.org/abs/2110.14238
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, without knowledge of the suffix of the input word still to be read. We sh
Externí odkaz:
http://arxiv.org/abs/2009.14437
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 counter value, or with an upper bound on the allowed counter value during
Externí odkaz:
http://arxiv.org/abs/2005.03435