5 papers
Pumping Constants for Infinite Alphabets
Yoav Danieli
It is well known that the pumping lemma for regular languages over finite alphabets does not extend to infinite alphabets. Instead, the generalized version of the pumping lemma for…
The Price of Almost Navigability
Tomer Waizer, Yoav Danieli
Navigability is a fundamental property of graph-based search structures and plays an important role in the analysis of nearest-neighbor algorithms. Informally, a graph is navigable…
Star Complexity of Parikh Images of Languages over Infinite Alphabets
Yoav Danieli
It has been conjectured that the Parikh (commutative) image of every language over an infinite alphabet recognized by an automaton with registers is defined by a rational expressio…
Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More
Mihail Stoian
Despite much research, hard weighted problems still resist super-polynomial improvements over their textbook solution. On the other hand, the unweighted versions of these problems…
A pumping-like lemma for languages over infinite alphabets
Yoav Danieli
We prove a pumping-like lemma for languages accepted by one-register alternating finite-memory automata over an infinite alphabet. Every sufficiently long accepted word has a nonem…