Detail publikačního výsledku

Word Equations in Synergy with Regular Constraints

HAVLENA, V.; CHOCHOLATÝ, D.; LENGÁL, O.; HOLÍK, L.; SÍČ, J.; BLAHOUDEK, F.; CHEN, Y.

Originální název

Word Equations in Synergy with Regular Constraints

Anglický název

Word Equations in Synergy with Regular Constraints

Druh

Stať ve sborníku v databázi WoS či Scopus

Originální abstrakt

We argue that in string solving, word equations and regular constraints are better mixed together than approached separately as in most current string solvers. We propose a fast algorithm, complete for the fragment of chain-free constraints, in which word equations and regular constraints are tightly integrated and exchange information, efficiently pruning the cases generated by each other and limiting possible combinatorial explosion. The algorithm is based on a novel language-based characterisation of satisfiability of word equations with regular constraints. We experimentally show that  our prototype implementation is competitive with the best string solvers and even superior in that it is the fastest on difficult examples and has the least number of timeouts.

Anglický abstrakt

We argue that in string solving, word equations and regular constraints are better mixed together than approached separately as in most current string solvers. We propose a fast algorithm, complete for the fragment of chain-free constraints, in which word equations and regular constraints are tightly integrated and exchange information, efficiently pruning the cases generated by each other and limiting possible combinatorial explosion. The algorithm is based on a novel language-based characterisation of satisfiability of word equations with regular constraints. We experimentally show that  our prototype implementation is competitive with the best string solvers and even superior in that it is the fastest on difficult examples and has the least number of timeouts.

Klíčová slova

Word equations, regular constraints, string solving, finite automata

Klíčová slova v angličtině

Word equations, regular constraints, string solving, finite automata

Autoři

HAVLENA, V.; CHOCHOLATÝ, D.; LENGÁL, O.; HOLÍK, L.; SÍČ, J.; BLAHOUDEK, F.; CHEN, Y.

Rok RIV

2024

Vydáno

06.03.2023

Nakladatel

Springer Verlag

Místo

Lübeck

Kniha

Proceedings of FM'23

ISSN

0302-9743

Periodikum

Lecture Notes in Computer Science

Číslo

14000

Stát

Spolková republika Německo

Strany od

403

Strany do

423

Strany počet

21

BibTex

@inproceedings{BUT185156,
  author="Vojtěch {Havlena} and David {Chocholatý} and Ondřej {Lengál} and Lukáš {Holík} and Juraj {Síč} and František {Blahoudek} and Yu-Fang {Chen}",
  title="Word Equations in Synergy with Regular Constraints",
  booktitle="Proceedings of FM'23",
  year="2023",
  journal="Lecture Notes in Computer Science",
  number="14000",
  pages="403--423",
  publisher="Springer Verlag",
  address="Lübeck",
  doi="10.1007/978-3-031-27481-7\{_}23",
  issn="0302-9743"
}