Benchmark
non-incremental/QF_S/20250403-pcp-string/pcp-3-4-hard/unsolved_pcp_instance_116.smt2
Benchmarks encoding PCP[3,4] that were considered hard to solve by the paper
'Creating Difficult Instances of the Post Correspondence Problem'. Most were solved later with different
techniques like Parikh Automata and Model Checking but String Solvers have not been tested.
Most benchmarks expected to be unsat.
Publication: Creating Difficult Instances of the Post Correspondence Problem, Further Tackling Post Correspondence Problem and
Proof Generation
| Benchmark |
|---|
| Size | 1962 |
| Compressed Size | 755 |
| License |
Creative Commons Attribution 4.0 International
(CC-BY-4.0)
|
| Category | industrial |
| First Occurrence | 2025-08-11 |
| Generated By | Oliver Markgraf |
| Generated On | 2025-04-03 00:00:00 |
| Generator | — |
| Dolmen OK | 1 |
| strict Dolmen OK | 1 |
| check-sat calls | 1 |
| Status | unknown |
| Inferred Status | None |
| Size | 1954 |
| Compressed Size | 755 |
| Max. Term Depth | 4 |
| Asserts | 16 |
| Declared Functions | 0 |
| Declared Constants | 17 |
| Declared Sorts | 0 |
| Defined Functions | 0 |
| Defined Recursive Functions | 0 |
| Defined Sorts | 0 |
| Constants | 0 |
| Declared Datatypes | 0 |
Symbols
= | 15 |
str.replace_all | 6 |
str.to_re | 3 |
re.+ | 1 |
re.union | 1 |
str.in_re | 1 |
| | | |
Evaluations
| Evaluation |
Rating |
Solver |
Variant |
Result |
Wallclock |
CPU Time |
|
SMT-COMP 2025
|
0.83 (1/6) |
cvc5 |
cvc5 |
unknown ❌
|
1201.79006
|
1201.07157
|
| |
OSTRICH |
OSTRICH |
unknown ❌
|
1201.39187
|
1254.69442
|
| |
Z3alpha |
Z3-alpha |
unknown ❌
|
0.39023
|
0.28073
|
| |
Z3 |
Z3-alpha-base |
unknown ❌
|
0.31241
|
0.18467
|
| |
|
Z3-Noodler-base |
unknown ❌
|
0.30303
|
0.17411
|
| |
Z3-Noodler |
Z3-Noodler |
unknown ❌
|
0.28090
|
0.16046
|
| |
|
Z3-Noodler-Mocha-base |
unknown ❌
|
0.30800
|
0.18526
|
| |
Z3-Noodler-Mocha |
Z3-Noodler-Mocha |
unsat ✅
|
0.27726
|
0.15746
|