3 results
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 in the i-th position of the run is divided by $\lambda^i$, where the discount factor $\lambda$ is a fixed rational number […]
Published on February 13, 2014
Milad Aghajohari ; Guy Avni ; Thomas A. Henzinger.
In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner of the game. Such games are central in formal methods since they model the interaction between a non-terminating system and its environment. In bidding games the players […]
Published on February 3, 2021
Krishnendu Chatterjee ; Thomas A. Henzinger ; Rasmus Ibsen-Jensen ; Jan Otop.
The edit distance between two words $w_1, w_2$ is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform $w_1$ to $w_2$. The edit distance generalizes to languages $\mathcal{L}_1, \mathcal{L}_2$, where the edit distance from $\mathcal{L}_1$ to […]
Published on September 13, 2017