uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
A New SAT Encoding of Earley Parsing
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology.
2015 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

While the Boolean satisfiability problem (SAT) lies in NP, prodigious work in SAT solvers has allowed for its use in modeling a multitude of practical problems. Stating a problem in SAT can be cumbersome though and so the demand for SAT encodings arises, providing a means to formulate problems or parts of problems in a more intuitive environment. Several algorithms have been proposed in the past to encode context-free grammars as SAT formulae, allowing for the comprehensive construction of many interesting constraints such as at-most k constraints or such ones pertaining to language syntax. In 2011 a new algorithm was proposed, differing from previous ones in it being based on Earley parsing instead of CYK parsing. Although it performed well for interesting groups of grammars it was later found to behave incorrectly for certain inputs. This thesis discusses the flaws in said algorithm, presents a revision of it and argues for the altered algorithm's correctness. The alterations come with a price, however, and both the running time and output size complexities suffer more-than-quadratic blowup. Since no empirical tests have been performed as of yet, it is still unclear what impact this blowup will have on practical instances.

Place, publisher, year, edition, pages
2015. , 42 p.
IT, 15004
Keyword [en]
Context Free Grammers, SAT.
National Category
Engineering and Technology
URN: urn:nbn:se:uu:diva-244520OAI: oai:DiVA.org:uu-244520DiVA: diva2:788985
Educational program
Bachelor Programme in Computer Science
Available from: 2015-02-17 Created: 2015-02-17 Last updated: 2015-09-15Bibliographically approved

Open Access in DiVA

fulltext(624 kB)268 downloads
File information
File name FULLTEXT01.pdfFile size 624 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Information Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 268 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 622 hits
ReferencesLink to record
Permanent link

Direct link