On the Complexity of Pumping
By (author) Christian Rauch
Paperback (Published)
(July 2025)
ISBN: 9783832559427
8.31 x 11.65 inches
Price: $63.00
In stock
Since the beginning of automata and formal language theory, researchers have studied pumping properties of formal languages in order to gain a better understanding of the computational complexity and the expressive power of various types of language accepting or generating mechanisms. The first part of this monograph studies the descriptional complexity of minimal pumping constants-the smallest value that satisfies a previously fixed pumping lemma-by comparing the constants according to various pumping lemmata. This results in a complete hierarchy of measures for regular languages. The simultaneous regulation of minimal pumping constants and other measures is improved and their operational complexity analyzed. The second part is dedicated to the computational complexity of the Pumping-Problem, that is, for a given grammar G and a value p, to decide whether the language L(G) satisfies a previously fixed pumping lemma w.r.t. the value p. Among other results, we show that the problem is decidable but computationally intractable for all studied pumping lemmata, if the language under consideration is regular, a k-rated linear language or a well-matched visibly pushdown language, and the problem becomes undecidable if the language is (linear) context-free.
- By (author) Christian Rauch
Similar Books
Cahiers de lexicologie
Particules floues — Nouvelles études sur le français et l'espagnol
Volume 128
Des mots aux actes
Traduction épistémique et littéraire. Nouvelles tendances en histoire et didactique
Volume 15
Deutsch als Fremdsprache nach Englisch an chinesischen Hochschulen
Eine empirische Forschung über Lernstrategien zum Wortschatzlernen
Punning in Odd or Elegant Constructions in Jeremiah
The Convergence of Linguistics, Rhetoric, and Textuality in the Hebrew Text of Jeremiah
Lectori vago. Manuscripts, Libraries, and Classical Scholarship from the Middle Ages to the Early Modern Period
Liber amicorum Luc Deitz
Volume 43
Das Alemannische der Rätoroman:innen in Bern
Langfristige Akkommodation bei simultan und früh konsekutiv bilingual aufgewachsenen Personen
