Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
3 results

Edit Distance for Pushdown Automata

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&nbsp;[&hellip;]
Published on September 13, 2017

Quantitative Automata under Probabilistic Semantics

Krishnendu Chatterjee ; Thomas A. Henzinger ; Jan Otop.
Automata with monitor counters, where the transitions do not depend on counter values, and nested weighted automata are two expressive automata-theoretic frameworks for quantitative properties. For a well-studied and wide class of quantitative functions, we establish that automata with monitor&nbsp;[&hellip;]
Published on August 13, 2019

Modular Path Queries with Arithmetic

Jakub Michaliszyn ; Jan Otop ; Piotr Wieczorek.
We propose a new approach to querying graph databases. Our approach balances competing goals of expressive power, language clarity and computational complexity. A distinctive feature of our approach is the ability to express properties of minimal (e.g. shortest) and maximal (e.g. most valuable)&nbsp;[&hellip;]
Published on September 20, 2021

  • < Previous
  • 1
  • Next >