Anzeige
Erschienen in:
1998 | OriginalPaper | Buchkapitel
Descriptive Complexity and Model Checking
verfasst von : Neil Immerman
Erschienen in: Foundations of Software Technology and Theoretical Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Descriptive Complexity [I98] is an approach to complexity that measures the richness of a language or sentence needed to describe a given property. There is a profound relationship between the traditional computational complexity of a problem and the descriptive complexity of the problem. In this setting, the finite object being worked on is treated as a logical structure. Thus descriptive complexity is part of finite model theory [EF95].