Detail publikace

Solving Not-Substring Constraint with Flat Abstraction

ABDULLA Parosh A., ATIG Mohamed F., BUI Phi Diep, HOLÍK Lukáš, CHEN Yu-Fang a WU Zhilin. Solving Not-Substring Constraint with Flat Abstraction. In: Programming Languages and Systems - 19th Asian Symposium, APLAS 2021, Chicago, IL, USA, October 17-18, 2021, Proceedings. 13008. Berlín: Springer International Publishing, 2021, s. 305-320. ISBN 978-3-030-89051-3. Dostupné z: https://doi.org/10.1007/978-3-030-89051-3\_17
Název česky
Řešení ne-podřetězcového omezení pomocí ploché abstrakce
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Abdulla Parosh A. (Uppsala)
Atig Mohamed F. (Uppsala)
Bui Phi Diep (Uppsala)
Holík Lukáš, doc. Mgr., Ph.D. (UITS FIT VUT)
Chen Yu-Fang (ASIN)
Wu Zhilin (UCAS)
URL
Klíčová slova

CEGAR, omezení řetězců, řetězce

Abstrakt

Ne-podřetězec patří současně mezi nejméně podporované omezení řetězců a existující solvery využívají jen relativně hrubé heuristiky. Avšak ne-podřetězce se vyskytují relativně často v praktických příkladech a jsou užitečné při kódování jiný typů omezení. V tomto článku jsme navrhli systematický způsob řešení ne-podřetězců s použitím zjemňující abstrakce pomocí protipříkladů založené na ploché abstrakci. V takovémto rámci je doména retězcových proměnných omezena na ploché jazyky a následně všechny omezení můžou být vyjádřeny jako formule lineární aritmetiky. Prokázali jsme, že omezení ne-podřetězců můžou být efektivně zploštěné a poskytli jsme experimentální důkazy, že navržené řešení pro ne-podřetězce je konkurenceschopné.

Rok
2021
Strany
305-320
Sborník
Programming Languages and Systems - 19th Asian Symposium, APLAS 2021, Chicago, IL, USA, October 17-18, 2021, Proceedings
Řada
13008
Konference
19th Asian Symposium on Programming Languages and Systems -- APLAS'21, Chicago, US
ISBN
978-3-030-89051-3
Vydavatel
Springer International Publishing
Místo
Berlín, DE
DOI
10.1007/978-3-030-89051-3_17
UT WoS
000783821500017
EID Scopus
2-s2.0-85118186762
BibTeX 
@INPROCEEDINGS{FITPUB12676,
   author = "A. Parosh Abdulla and F. Mohamed Atig and Diep Phi Bui and Luk\'{a}\v{s} Hol\'{i}k and Yu-Fang Chen and Zhilin Wu",
   title = "Solving Not-Substring Constraint with Flat Abstraction",
   pages = "305--320",
   booktitle = "Programming Languages and Systems - 19th Asian Symposium, APLAS 2021, Chicago, IL, USA, October 17-18, 2021, Proceedings",
   series = "13008",
   year = 2021,
   location = "Berl\'{i}n, DE",
   publisher = "Springer International Publishing",
   ISBN = "978-3-030-89051-3",
   doi = "10.1007/978-3-030-89051-3\_17",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12676"
}
Nahoru