Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Allow String in TermCompiler #130

Open
wants to merge 1 commit into
base: master
Choose a base branch
from
Open

Conversation

serras
Copy link

@serras serras commented Aug 18, 2021

No description provided.

@serras
Copy link
Author

serras commented Aug 23, 2021

@jhoenicke I found that without this change there's no way to use a logical formula containing a constant string, not even the simplest (= x "hello").

@jhoenicke
Copy link
Member

I think this is unsound without any String reasoning. E.g., with this change, SMTInterpol will also say that (and (= x "hello") (= x "good bye")) is satisfiable.

@serras
Copy link
Author

serras commented Aug 23, 2021

I'm happy to devote some time to have this working; is there any place I could look at to bring strings to SMTInterpol?

@jhoenicke
Copy link
Member

Writing a string solver can be quite an involved task. The whole theory is undecidable, so the first step would be to pick a decidable fragment and an algorithm for this fragment. Here is a survey on techniques of string solving: https://arxiv.org/pdf/2002.02376.pdf

If you want to work on a solver, I can help you to integrate it in SMTInterpol.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants