MENÜ MENÜ  

cover

On the Complexity of Pumping

Christian Rauch
Logos Oekobuch

ISBN 978-3-8325-5942-7
206 Seiten, Erscheinungsjahr: 2025
Preis: 41.50 €
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.

Keywords:
  • formal language theory
  • automata theory
  • minimal pumping constants
  • finite-state devices
  • visibly pushdown languages

Kaufoptionen

41.50 €
Versandkostenfrei innerhalb Deutschlands

40.00 €
51.50 €
55.50 €

(D) = innerhalb Deutschlands
(W) = außerhalb Deutschlands

*Sie können das eBook (PDF) entweder einzeln herunterladen oder in Kombination mit dem gedruckten Buch (eBundle) erwerben. Der Erwerb beider Optionen wird über PayPal abgerechnet - zur Nutzung muss aber kein PayPal-Account angelegt werden. Mit dem Erwerb des eBooks bzw. eBundles akzeptieren Sie unsere Lizenzbedingungen für eBooks.

Bei Interesse an Multiuser- oder Campus-Lizenzen (MyLibrary) füllen Sie bitte das Formular aus oder schreiben Sie eine email an order@logos-verlag.de


Wollen auch Sie Ihre Dissertation veröffentlichen?