1,553 papers · page 33 of 78
In this paper, we propose a novel algorithm to learn a Buchi automaton from a teacher who knows an \(\omega \)-regular language. The algorithm is based on learning a formalism named family of DFAs (FDFAs) recently proposed by Angluin and Fisman [10]. The main catch is that we use…
We introduce ARES, an efficient approximation algorithm for generating optimal plans action sequences that take an initial state of a Markov Decision Process MDP to a state whose cost is below a specified convergence threshold. ARES uses Particle Swarm Optimization, with adaptive…
Abstract elided by the publisher.
Abstract elided by the publisher.
We prove that certain formulations of program synthesis and reachability are equivalent. Specifically, our constructive proof shows the reductions between the template-based synthesis problem, which generates a program in a pre-specified form, and the reachability problem, which …
Abstract elided by the publisher.
Abstract elided by the publisher.
Abstract elided by the publisher.
Abstract elided by the publisher.
Abstract elided by the publisher.
Abstract elided by the publisher.
Optimization Modulo Theories $$\text {OMT}$$ is an extension of SMT which allows for finding models that optimize given objectives. Partial weighted MaxSMT---or equivalently $$\text {OMT}$$ with Pseudo-Boolean objective functions, $$\text {OMT+PB}$$ --- is a very-relevant strict …
What properties about the internals of a program explain the possible differences in its overall running time for different inputs? In this paper, we propose a formal framework for considering this question we dub trace-set discrimination. We show that even though the algorithmic…
Abstract elided by the publisher.
In an algorithmic complexity attack, a malicious party takes advantage of the worst-case behavior of an algorithm to cause denial-of-service. A prominent algorithmic complexity attack is regular expression denial-of-service (ReDoS), in which the attacker exploits a vulnerable reg…
Abstract elided by the publisher.
We present an efficient algorithm to reduce the size of nondeterministic tree automata, while retaining their language. It is based on new transition pruning techniques, and quotienting of the state space w.r.t. suitable equivalences. It uses criteria based on combinations of dow…
Abstract elided by the publisher.
Abstract elided by the publisher.
We propose an abstract-interpretation-based analysis for recurrent sets. A recurrent set is a set of states from which the execution of a program cannot or might not as in our case escape. A recurrent set is a part of a program's non-termination proof that needs to be complemente…