On the Complexity of Pumping
By (author) Christian Rauch
Paperback (Published)
(July 2025)
ISBN: 9783832559427
8.27 x 11.65 inches
Price: $63.00
Out of 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
Punning in Odd or Elegant Constructions in Jeremiah
The Convergence of Linguistics, Rhetoric, and Textuality in the Hebrew Text of Jeremiah
Language, Semantics, and Cognition in Ancient Egypt and Beyond
Proceedings of the International Conference, Yale University, April 16-18, 2021
Volume 14
Linguistic Fragmentation and Cultural Inclusion in the Middle Ages
Translation, Plurilingualism, Multilingualism
Volume 22
Treatise on Biblical Rhetoric
Second Complete English Edition. Translation of the Third Revised and Enlarged Edition
Volume 52
Varietate delectamur
Multifarious Approaches to Synchronic and Diachronic Variation in Latin: Selected Papers from the 14th International Colloquium on Late and Vulgar Latin (Ghent, 2022)
Volume 1
Argumentation, Persuasion und Manipulation in Medientexten und -diskursen
Beitrage zur kontrastiven Medienlinguistik
Volume 20
Aspektmarkierung im Mittelhochdeutschen
Untersuchungen zur prafixgesteuerten Perfektivierung und verbalen Paarigkeit
Der spatmittelalterliche Kanzleibrief in Nurnberg
Zur Beschreibung von historischem Textmusterwissen
