Witness words reveal limits of regular language pumping lemmas
Witness Languages for Pumping Lemmata
Formal Languages and Automata Theory
Summary
Some languages have a rule called a pumping lemma that helps understand their structure, but figuring out the smallest 'pumping length' is tricky. The authors study special words called witnesses that show when pumping by that smallest length fails. They introduce a new way to measure language complexity called scattered factor distance, linking it to these critical lengths. They also show that deciding if one language matches the witness words of another is a computationally hard problem.
What this means in practice
- •For formal language engineers: Determine the minimal pumping constants to optimize language processing algorithms handling regular languages.
- •For automated verification teams: Use witness language characterizations to identify cases where regular language-based system models fail standard pumping assumptions.
A theory result. No direct application yet.
Authors
Pamela Fleischmann, Annika Huch, Christian Rauch
Abstract
In 2022 Dassow and Jecker started investigations on the operational complexity of the pumping constant w.r.t.~two pumping lemmata. Since then, the research on pumping lemmata emerged to several variants for regular as well as context-free languages. Within this work, we further investigate the \emph{witnesses} of regular languages (firstly introduced by Rauch) w.r.t.~different pumping lemmata: For a language $L$ and a minimal pumping constant $K$, a \emph{witness} of a language is a word that cannot be \emph{pumped} by $K$ w.r.t.~the given pumping lemma. Here, the pumping constant is minimal if for all smaller numbers, the pumping lemma condition is not satisfied. Alongside combinatorial investigations on (unary) witness languages, we introduce and study the measure of scattered factor distance, which is related to minimal pumping constants. We present bounds on minimal pumping constants by the scattered factor distance and show that deciding, given two regular languages, whether one of them is equal to the witness language of the second is \coNP-complete.