On the Descriptional and Algorithmic Complexity of Regular Languages

Autor Gruber, Hermann
Buchtitel On the Descriptional and Algorithmic Complexity of Regular Languages
VerlagHarland media
ISBN-13 978-3-938363-62-1
Seitenzahl 210
Verkaufspreis 45.90 €
Buchformat 21x14,8 (DIN A5)
Cover Softcover
Veröffentlichung 01/2010

Buch / Bücher

Hermann Gruber addresses basic questions in formal language theory, regarding the succinctness of description of languages by means of finite automata and regular expressions.

These questions are studied from two different viewpoints. The first is descriptional complexity, which amounts to comparing the sizes of minimal descriptions. The second viewpoint is algorithmic complexity, which leads to efficiently finding such small descriptions.

This monograph guidelines the reader through current research in the field and provides original solutions to several challenging research problems, including a classical open question dating back to the 1970s. The author uses a variety of proof methods, which are a blend of formal language theory, extremal combinatorics, communication complexity, circuit lower bounds, as well as the structure theory of graphs and digraphs.

The book addresses researchers and professionals interested in discrete mathematics and theoretical computer science, especially automata theory.

Copyright 1996-2023
Dr. Peter E. Harland
Ernst-Thälmann-Str. 16
07747 Jena