Advanced Tools and Methods for Treewidth-Based Problem Solving / Markus Hecher.

Format:

Book

Author/Creator:

Hecher, Markus, author.

Series:

Frontiers in artificial intelligence and applications ; Volume 359.

Frontiers in Artificial Intelligence and Applications Series ; Volume 359

Language:

English

Subjects (All):

Knowledge representation (Information theory).

Artificial intelligence.

Physical Description:

1 online resource (252 pages)

Edition:

First edition.

Place of Publication:

Amsterdam, Netherlands : IOS Press BV, [2022]

Summary:

This book presents advanced tools and methods for problem-solving in the field of artificial intelligence, focusing on the structural parameter treewidth. Authored by Markus Hecher, it is based on his award-winning PhD thesis and aims to establish theoretical and practical frameworks for knowledge and reasoning. The book explores runtime bounds for evaluating Quantified Boolean formulas and logic programs, with implications for computational complexity. It targets an academic audience, especially those interested in artificial intelligence research, offering insights into the efficient application of treewidth beyond the specific problems addressed. Published as part of the 'Frontiers in Artificial Intelligence and Applications' series, it serves as a foundation for further research and development in AI. Generated by AI.

Contents:

Title Page

Preface

Acknowledgements

Abstract

Contents

Introduction

Contributions and Overview

Preliminaries

Graph Theory

Computational Complexity

(Quantified) Boolean Formulas

Answer Set Programming

Tree Decompositions and Treewidth

Labeled Tree Decompositions

Upper Bounds for Using Treewidth

Basics on Dynamic Programming

Dynamic Programming for ASP

Outlook on Dynamic Programming

Decomposition-Guided Reductions

Concept and Definitions

DG Reduction from Tight Asp to Sat

DG Reduction from HCF Asp to Sat

DG Reduction from Asp to Almost Tight Asp

Discussion: Different Ways of Treating Hard Cycles

Lower Bounds by DG Reductions

Lower Bounds for QBFs and Treewidth

Lower Bounds for Asp and Treewidth

A Complexity Landscape for Treewidth

A Methodology for Lower Bounds

Complexity Characterization for Treewidth Generated by AI.

Notes:

Includes bibliographical references.

Description based on publisher supplied metadata and other sources.

Part of the metadata in this record was created by AI, based on the text of the resource.

Description based on print version record.

Other Format:

Print version: Hecher, M. Advanced Tools and Methods for Treewidth-Based Problem Solving

ISBN:

9781643683454

OCLC:

1353820401