More on Language Families with a Decidable Pumping-Problem (Extended Abstract)
摘要
The decidability of the Pumping-Problem—determining if a language given by an automaton or a grammar satisfies a pumping lemma w.r.t. a given pumping constant—exhibits a striking contrast: it is solvable for regular languages, even under context-free pumping constraints, but undecidable for (linear) context-free languages [H. Gruber and M. Holzer and C. Rauch. The Pumping Lemma for Context-Free Languages is Undecidable. DLT 2024, pp. 141–155 ]. This work investigates which subfamilies of context-free languages retain decidability. We first prove that the Pumping-Problem is decidable for k-rated linear languages, a generalization of even linear languages that balances structural regularity with expressive power. As a byproduct of this research we develop an automaton model for k-rated linear languages. Further, we show decidability for well-matched visibly pushdown languages, a subfamily of the well-known visibly pushdown languages (VPL), which attracted a lot of attention, especially in verification, during the last decade.