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.

Sign up for GitHub

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

Jump to bottom

to_int: axioms for number equations #124

Merged
merged 9 commits into from
Feb 25, 2024
Merged

to_int: axioms for number equations #124

merged 9 commits into from
Feb 25, 2024

Conversation

vhavlena
Copy link
Collaborator

@vhavlena vhavlena commented Feb 21, 2024 •
edited
Loading

This PR introduces optimizations generating axioms for length (in)equations and constant conversions.

@vhavlena
Copy link
Collaborator Author

Results from full_str_int

# of formulae: 16968
###################################################################################
####                                   Table 1                                 ####
###################################################################################
| method                     |    max |     mean |   median |   std. dev |   TO+MO+ERR |   unknowns |
|----------------------------|--------|----------|----------|------------|-------------|------------|
| z3-noodler-a0d4232-2cddb2f | 118.25 | 0.759949 |     0.01 |    5.35528 |         767 |        266 |
| cvc5-1.0.8                 |  82.08 | 0.309905 |     0.03 |    1.18924 |           0 |          0 |
| z3-4.12.2                  | 118.32 | 1.44806  |     0.04 |    7.81162 |         234 |          0 |
| z3-noodler-bdb7f83-2cddb2f |  84.32 | 0.225197 |     0.01 |    1.77001 |         715 |        895 |

stringfuzz

# of formulae: 11618
###################################################################################
####                                   Table 1                                 ####
###################################################################################
| method                     |    max |      mean |   median |   std. dev |   TO+MO+ERR |   unknowns |
|----------------------------|--------|-----------|----------|------------|-------------|------------|
| z3-noodler-a0d4232-2cddb2f |  15.96 | 0.0263197 |     0.01 |   0.164309 |           9 |          4 |
| cvc5-1.0.8                 | 119.36 | 2.60648   |     0.02 |  12.8104   |        1066 |          0 |
| z3-4.12.2                  | 117.71 | 4.13847   |     0.04 |  14.3598   |         386 |          0 |
| z3-noodler-bdb7f83-2cddb2f |   6.71 | 0.0269098 |     0.01 |   0.114551 |           4 |         42 |

on all benchmarks:

# of formulae: 99940
###################################################################################
####                                   Table 1                                 ####
###################################################################################
| method                     |    max |     mean |   median |   std. dev |   TO+MO+ERR |   unknowns |
|----------------------------|--------|----------|----------|------------|-------------|------------|
| z3-noodler-a0d4232-2cddb2f | 118.25 | 0.220081 |     0.02 |    2.66574 |        1312 |        688 |
| cvc5-1.0.8                 | 119.36 | 0.47966  |     0.02 |    4.78767 |        1723 |          2 |
| z3-4.12.2                  | 119.29 | 1.48291  |     0.04 |    8.11438 |        2857 |        123 |
| z3-noodler-bdb7f83-2cddb2f | 119.02 | 0.132023 |     0.02 |    1.69187 |        1258 |       1355 |
  • kaluza is a bit worse (~10 TOs), otherwise it is comparable/same

@vhavlena vhavlena marked this pull request as ready for review February 23, 2024 13:54
@vhavlena vhavlena requested a review from jurajsic February 23, 2024 13:54
jurajsic
jurajsic approved these changes Feb 23, 2024
View reviewed changes
Copy link
Member

@jurajsic jurajsic left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good!

src/smt/theory_str_noodler/theory_str_noodler.cpp
Comment on lines +2353 to +2359
for(int i = 0; i < val; i++) {
if(re == nullptr) {
re = m_util_s.re.mk_full_char(nullptr);
} else {
re = m_util_s.re.mk_concat(re, m_util_s.re.mk_full_char(nullptr));
}
}
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

this could be also mk_loop, right?

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Loop is imo <=. For equality we need exactly n.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

But you can put mk_loop(str, val, val) no? Or is there no minimum?

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ok, you are right.

src/smt/theory_str_noodler/theory_str_noodler.cpp Outdated Show resolved Hide resolved
@vhavlena
Copy link
Collaborator Author

@jurajsic Just let me know if you are happy with the changes and I can merge it then.

@jurajsic
Copy link
Member

Yeah i think you can

@vhavlena vhavlena merged commit 3d31687 into devel Feb 25, 2024
@vhavlena vhavlena deleted the to-int-eq branch February 25, 2024 15:29
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@jurajsic jurajsic jurajsic approved these changes

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@vhavlena @jurajsic