Negated String Containment is Decidable
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F26%3A0198408" target="_blank" >RIV/00216305:26230/26:0198408 - isvavai.cz</a>
Result on the web
<a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.56" target="_blank" >https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.56</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2025.56" target="_blank" >10.4230/LIPIcs.MFCS.2025.56</a>
Alternative languages
Result language
angličtina
Original language name
Negated String Containment is Decidable
Original language description
We provide a positive answer to a long-standing open question of the decidability of the not-contains string predicate. Not-contains is practically relevant, for instance in symbolic execution of string manipulating programs. Particularly, we show that the predicate ¬Contains(x₁ … x_n, y₁ … y_m), where x₁ … x_n and y₁ … y_m are sequences of string variables constrained by regular languages, is decidable. Decidability of a not-contains predicate combined with chain-free word equations and regular membership constraints follows.
Czech name
—
Czech description
—
Classification
Type
O - Miscellaneous
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)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů