Open Daily: 10am - 10pm | Alley door pickup 10am - 7pm 3038 Hennepin Ave Minneapolis, MN
612-822-4611

  • Open Daily: 10am - 10pm
    Alley-side Pickup: 10am - 7pm

    3038 Hennepin Ave Minneapolis, MN
    612-822-4611

Open Daily: 10am - 10pm | Alley-side Pickup: 10am - 7pm
3038 Hennepin Ave Minneapolis, MN
612-822-4611
On the Complexity of Pumping

On the Complexity of Pumping

Rauch, Christian

Paperback

General ComputersGeneral Mathematics

Currently unavailable to order

ISBN10: 3832559426
ISBN13: 9783832559427
Publisher: Logos Verlag Berlin
Published: Jul 21 2025
Pages: 206
Weight: 0.85
Language: English
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.

Also from

Rauch, Christian

View All

Also in

General Computers

View All