Publication result detail

Solving String Constraints with Approximate Parikh Image

HOLÍKOVÁ, L.; JANKŮ, P.

Original Title

Solving String Constraints with Approximate Parikh Image

English Title

Solving String Constraints with Approximate Parikh Image

Type

Paper in proceedings (conference paper)

Original Abstract

In this paper, we propose a refined version of the Parikh image abstraction of finite automata to resolve string length constraints. We integrate this abstraction into the string solver SLOTH, where on top of handling length constraints, our abstraction is also used to speed-up solving other types of constraints. The experimental results show that our extension of SLOTH has good results on simple benchmarks as well as on complex benchmarks that are real-word combinations of transducer and concatenation constraints.

English abstract

In this paper, we propose a refined version of the Parikh image abstraction of finite automata to resolve string length constraints. We integrate this abstraction into the string solver SLOTH, where on top of handling length constraints, our abstraction is also used to speed-up solving other types of constraints. The experimental results show that our extension of SLOTH has good results on simple benchmarks as well as on complex benchmarks that are real-word combinations of transducer and concatenation constraints.

Keywords

String constraint solving,
Program verification,
Parikh Image,
Alternating Finite Automata,
Decision Procedure

Key words in English

String constraint solving,
Program verification,
Parikh Image,
Alternating Finite Automata,
Decision Procedure

Authors

HOLÍKOVÁ, L.; JANKŮ, P.

RIV year

2021

Released

10.12.2019

Publisher

Springer International Publishing

Location

Heidelberg

ISBN

978-3-030-45092-2

Book

Proceedings of EUROCAST'19

Edition

Lecture Notes in Computer Science

Pages from

1

Pages to

8

Pages count

8

URL

https://www.fit.vut.cz/research/publication/12135/

BibTex

@inproceedings{BUT162295,
  author="Lenka {Holíková} and Petr {Janků}",
  title="Solving String Constraints with Approximate Parikh Image",
  booktitle="Proceedings of EUROCAST'19",
  year="2019",
  series="Lecture Notes in Computer Science",
  pages="1--8",
  publisher="Springer International Publishing",
  address="Heidelberg",
  doi="10.1007/978-3-030-45093-9\{_}59",
  isbn="978-3-030-45092-2",
  url="https://www.fit.vut.cz/research/publication/12135/"
}

Documents

eurocast_janku_turonova