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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Flatten and Conquer: A Framework for Efficient Analysis of String Constraints
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Show others and affiliations
2017 (English)In: SIGPLAN notices, ISSN 0362-1340, E-ISSN 1558-1160, Vol. 52, no 6, p. 602-617Article in journal (Refereed) Published
Abstract [en]

We describe a uniform and efficient framework for checking the satisfiability of a large class of string constraints. The framework is based on the observation that both satisfiability and unsatisfiability of common constraints can be demonstrated through witnesses with simple patterns. These patterns are captured using flat automata each of which consists of a sequence of simple loops. We build a Counter-Example Guided Abstraction Refinement (CEGAR) framework which contains both an under-and an over-approximation module. The flow of information between the modules allows to increase the precision in an automatic manner. We have implemented the framework as a tool and performed extensive experimentation that demonstrates both the generality and efficiency of our method.

Place, publisher, year, edition, pages
2017. Vol. 52, no 6, p. 602-617
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:uu:diva-328181DOI: 10.1145/3062341.3062384ISI: 000414334200041ISBN: 978-1-4503-4988-8 (print)OAI: oai:DiVA.org:uu-328181DiVA, id: diva2:1134273
Conference
38th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). Barcelona, June 18-23, 2017
Available from: 2017-08-18 Created: 2017-08-18 Last updated: 2018-03-20Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Abdulla, Parosh AzizAtig, Mohamed FaouziBui, Phi DiepRümmer, Philipp

Search in DiVA

By author/editor
Abdulla, Parosh AzizAtig, Mohamed FaouziBui, Phi DiepRümmer, Philipp
By organisation
Computer Systems
In the same journal
SIGPLAN notices
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 456 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf