國立虎尾科技大學 |

Knowledge Compilation for Solving Computationally Hard Problems.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Knowledge Compilation for Solving Computationally Hard Problems./
Author:	Oztok, Umut.
Description:	1 online resource (208 pages)
Notes:	Source: Dissertation Abstracts International, Volume: 79-04(E), Section: B.
Contained By:	Dissertation Abstracts International79-04B(E).
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9780355386769

Knowledge Compilation for Solving Computationally Hard Problems.
Oztok, Umut.

Knowledge Compilation for Solving Computationally Hard Problems. - 1 online resource (208 pages)

Source: Dissertation Abstracts International, Volume: 79-04(E), Section: B.

Thesis (Ph.D.)

Includes bibliographical references

Knowledge compilation is concerned with compiling problems encoded in some input language into some tractable, output language, with the goal of allowing one to solve such problems efficiently if the compilation is successful. This paradigm was originally motivated by the need to push much of the computational overhead into an offline compilation phase, which can then be amortized over a large number of queries in an online computation phase. In this dissertation, we study various new approaches to enhance the offline compilation phase, both theoretically and practically. We also study knowledge compilation from a perspective where it is employed as a general methodology for computation instead of just a paradigm that is concerned with the offline/online divide.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9780355386769Subjects--Topical Terms:

573171
Computer science.
Index Terms--Genre/Form:

554714
Electronic books.

Knowledge Compilation for Solving Computationally Hard Problems.
LDR:03056ntm a2200361Ki 4500 001 910845
005 20180517112612.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9780355386769
035 $a (MiAaPQ)AAI10637258
035 $a (MiAaPQ)ucla:16218
035 $a AAI10637258
040 $a MiAaPQ $b eng $c MiAaPQ
099 $a TUL $f hyy $c available through World Wide Web
100 1 $a Oztok, Umut. $3 1182329
245 1 0 $a Knowledge Compilation for Solving Computationally Hard Problems.
264 0 $c 2017
300 $a 1 online resource (208 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 79-04(E), Section: B.
500 $a Adviser: Adnan Darwiche.
502 $a Thesis (Ph.D.) $c University of California, Los Angeles $d 2017.
504 $a Includes bibliographical references
520 $a Knowledge compilation is concerned with compiling problems encoded in some input language into some tractable, output language, with the goal of allowing one to solve such problems efficiently if the compilation is successful. This paradigm was originally motivated by the need to push much of the computational overhead into an offline compilation phase, which can then be amortized over a large number of queries in an online computation phase. In this dissertation, we study various new approaches to enhance the offline compilation phase, both theoretically and practically. We also study knowledge compilation from a perspective where it is employed as a general methodology for computation instead of just a paradigm that is concerned with the offline/online divide.
520 $a In particular, we introduce a hierarchy of complexity parameters to bound the sizes of compiled representations. These new parameters are based on incorporating the logical content of the input representations, as opposed to existing parameters (e.g., treewidth) that are only based on the structure of the input. Our results improve some of the best known upper bounds on the compilation of influential representations, such as DNNFs, SDDs, and OBDDs. Moreover, we develop two new practical compilation algorithms for the DNNF and SDD languages, leading to orders of magnitude faster compilations. Finally, we study solving Beyond-NP problems using knowledge compilation, while particularly extending the reach of knowledge compilation to tackling problems in the highly intractable complexity class PPPP. Our results show the applicability of knowledge compilers as black-box tools for solving Beyond-NP problems, similar to the use of SAT solvers for solving NP-complete problems.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
650 4 $a Artificial intelligence. $3 559380
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
690 $a 0800
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of California, Los Angeles. $b Computer Science. $3 1180947
773 0 $t Dissertation Abstracts International $g 79-04B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10637258 $z click for full text (PQDT)