Regular Languages, Tree Width, and Courcelle's Theorem: An Introduction - Softcover

Inhaltsangabe

"Regular Languages, Tree Width, and Courcelle'sTheorem" provides an introduction to Courcelle'sTheorem, a theorem about the complexityof deciding whether a finite mathematical structuresatisfies a given logical formula. In thisconnection, further topics covered in the bookinclude theinterplay of logic and regular languages (e.g.Büchi's Theorem) and the graph theoretical conceptof tree width, a measure of the similarity of agraph to a tree.The text assumes no previous mathematical knowledgeof the reader other than some basic acquaintancewith the concept of regular languages.

Die Inhaltsangabe kann sich auf eine andere Ausgabe dieses Titels beziehen.