Flatten and conquer: a framework for efficient analysis of string constraints
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F17%3APU127288" target="_blank" >RIV/00216305:26230/17:PU127288 - isvavai.cz</a>
Result on the web
<a href="https://dl.acm.org/citation.cfm?doid=3062341.3062384" target="_blank" >https://dl.acm.org/citation.cfm?doid=3062341.3062384</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3062341.3062384" target="_blank" >10.1145/3062341.3062384</a>
Alternative languages
Result language
angličtina
Original language name
Flatten and conquer: a framework for efficient analysis of string constraints
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation
ISBN
978-1-4503-4988-8
ISSN
—
e-ISSN
—
Number of pages
16
Pages from-to
602-617
Publisher name
Association for Computing Machinery
Place of publication
New York
Event location
Barcelona
Event date
Jun 18, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000414334200041