./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version a046e57d Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 776d32abf1ae3b62e7ad4a02cd7c02c0cc6433852a1fe73b7d30c6e216da832a --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-mul-div-a046e57-m [2024-10-12 18:51:51,136 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-12 18:51:51,198 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-12 18:51:51,203 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-12 18:51:51,203 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-12 18:51:51,231 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-12 18:51:51,232 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-12 18:51:51,232 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-12 18:51:51,233 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-12 18:51:51,233 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-12 18:51:51,233 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-12 18:51:51,234 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-12 18:51:51,234 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-12 18:51:51,235 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-12 18:51:51,235 INFO L153 SettingsManager]: * Use SBE=true [2024-10-12 18:51:51,235 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-12 18:51:51,236 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-12 18:51:51,236 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-12 18:51:51,236 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-12 18:51:51,237 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-12 18:51:51,237 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-12 18:51:51,238 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-12 18:51:51,238 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-12 18:51:51,238 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-12 18:51:51,239 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-12 18:51:51,239 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-12 18:51:51,239 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-12 18:51:51,240 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-12 18:51:51,240 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-12 18:51:51,240 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-12 18:51:51,241 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-12 18:51:51,241 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-12 18:51:51,241 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-12 18:51:51,242 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-12 18:51:51,242 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-12 18:51:51,242 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-12 18:51:51,243 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-12 18:51:51,243 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-12 18:51:51,243 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-12 18:51:51,243 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-12 18:51:51,244 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-12 18:51:51,246 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-12 18:51:51,246 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 776d32abf1ae3b62e7ad4a02cd7c02c0cc6433852a1fe73b7d30c6e216da832a [2024-10-12 18:51:51,471 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-12 18:51:51,493 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-12 18:51:51,496 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-12 18:51:51,498 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-12 18:51:51,498 INFO L274 PluginConnector]: CDTParser initialized [2024-10-12 18:51:51,499 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c [2024-10-12 18:51:52,903 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-12 18:51:53,083 INFO L384 CDTParser]: Found 1 translation units. [2024-10-12 18:51:53,084 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c [2024-10-12 18:51:53,091 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d2b8c4aeb/f6f9db2a113a45ac910338630aae1294/FLAG3a53d9dda [2024-10-12 18:51:53,102 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d2b8c4aeb/f6f9db2a113a45ac910338630aae1294 [2024-10-12 18:51:53,103 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-12 18:51:53,105 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-12 18:51:53,106 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-12 18:51:53,106 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-12 18:51:53,111 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-12 18:51:53,112 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,113 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4c28726c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53, skipping insertion in model container [2024-10-12 18:51:53,113 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,134 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-12 18:51:53,297 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c[490,503] [2024-10-12 18:51:53,315 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-12 18:51:53,322 INFO L200 MainTranslator]: Completed pre-run [2024-10-12 18:51:53,333 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c[490,503] [2024-10-12 18:51:53,341 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-12 18:51:53,366 INFO L204 MainTranslator]: Completed translation [2024-10-12 18:51:53,366 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53 WrapperNode [2024-10-12 18:51:53,366 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-12 18:51:53,367 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-12 18:51:53,368 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-12 18:51:53,368 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-12 18:51:53,375 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,380 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,410 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 83 [2024-10-12 18:51:53,410 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-12 18:51:53,411 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-12 18:51:53,411 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-12 18:51:53,411 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-12 18:51:53,431 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,432 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,436 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,447 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-10-12 18:51:53,448 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,448 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,451 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,454 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,455 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,456 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,457 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-12 18:51:53,458 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-12 18:51:53,458 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-12 18:51:53,458 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-12 18:51:53,459 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53" (1/1) ... [2024-10-12 18:51:53,466 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-12 18:51:53,477 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:51:53,493 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-10-12 18:51:53,496 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-10-12 18:51:53,540 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-12 18:51:53,541 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-10-12 18:51:53,541 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-10-12 18:51:53,541 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-12 18:51:53,541 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-12 18:51:53,541 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-12 18:51:53,541 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-12 18:51:53,542 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-12 18:51:53,611 INFO L238 CfgBuilder]: Building ICFG [2024-10-12 18:51:53,614 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-12 18:51:53,806 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-10-12 18:51:53,809 INFO L287 CfgBuilder]: Performing block encoding [2024-10-12 18:51:53,837 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-12 18:51:53,838 INFO L314 CfgBuilder]: Removed 3 assume(true) statements. [2024-10-12 18:51:53,838 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 06:51:53 BoogieIcfgContainer [2024-10-12 18:51:53,838 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-12 18:51:53,841 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-12 18:51:53,841 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-12 18:51:53,844 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-12 18:51:53,845 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.10 06:51:53" (1/3) ... [2024-10-12 18:51:53,846 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@76f9aec6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.10 06:51:53, skipping insertion in model container [2024-10-12 18:51:53,846 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:51:53" (2/3) ... [2024-10-12 18:51:53,847 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@76f9aec6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.10 06:51:53, skipping insertion in model container [2024-10-12 18:51:53,847 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 06:51:53" (3/3) ... [2024-10-12 18:51:53,848 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound10.c [2024-10-12 18:51:53,864 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-12 18:51:53,865 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-12 18:51:53,937 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-12 18:51:53,945 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@5fbef35c, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-12 18:51:53,945 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-12 18:51:53,949 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 19 states have (on average 1.631578947368421) internal successors, (31), 20 states have internal predecessors, (31), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-10-12 18:51:53,956 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-10-12 18:51:53,956 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:53,957 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:53,957 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:53,963 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:53,963 INFO L85 PathProgramCache]: Analyzing trace with hash 67099435, now seen corresponding path program 1 times [2024-10-12 18:51:53,971 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:53,972 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1399654985] [2024-10-12 18:51:53,972 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:53,972 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:54,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:54,113 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:51:54,116 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:54,124 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-12 18:51:54,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:54,132 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:51:54,133 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:54,138 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:51:54,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:54,149 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-12 18:51:54,149 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:51:54,150 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1399654985] [2024-10-12 18:51:54,150 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1399654985] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:51:54,150 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:51:54,151 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-12 18:51:54,152 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [787376898] [2024-10-12 18:51:54,152 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:51:54,155 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-12 18:51:54,155 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:51:54,171 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-12 18:51:54,171 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-12 18:51:54,173 INFO L87 Difference]: Start difference. First operand has 32 states, 19 states have (on average 1.631578947368421) internal successors, (31), 20 states have internal predecessors, (31), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-12 18:51:54,199 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:51:54,199 INFO L93 Difference]: Finished difference Result 62 states and 104 transitions. [2024-10-12 18:51:54,204 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-12 18:51:54,206 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2024-10-12 18:51:54,206 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:51:54,212 INFO L225 Difference]: With dead ends: 62 [2024-10-12 18:51:54,212 INFO L226 Difference]: Without dead ends: 30 [2024-10-12 18:51:54,216 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-12 18:51:54,220 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 39 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:51:54,222 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 39 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:51:54,236 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2024-10-12 18:51:54,252 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2024-10-12 18:51:54,254 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-10-12 18:51:54,255 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2024-10-12 18:51:54,257 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 28 [2024-10-12 18:51:54,257 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:51:54,257 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2024-10-12 18:51:54,257 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-12 18:51:54,258 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2024-10-12 18:51:54,259 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-10-12 18:51:54,259 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:54,259 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:54,260 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-12 18:51:54,260 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:54,260 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:54,260 INFO L85 PathProgramCache]: Analyzing trace with hash -1772608446, now seen corresponding path program 1 times [2024-10-12 18:51:54,261 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:54,261 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1892968824] [2024-10-12 18:51:54,261 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:54,261 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:54,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:54,481 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:51:54,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:54,490 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-12 18:51:54,494 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:54,497 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:51:54,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:54,510 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:51:54,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:54,567 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-12 18:51:54,568 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:51:54,568 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1892968824] [2024-10-12 18:51:54,568 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1892968824] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:51:54,568 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:51:54,569 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-12 18:51:54,569 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1942036258] [2024-10-12 18:51:54,569 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:51:54,570 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-12 18:51:54,571 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:51:54,572 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-12 18:51:54,573 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-10-12 18:51:54,574 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:51:54,704 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:51:54,705 INFO L93 Difference]: Finished difference Result 49 states and 64 transitions. [2024-10-12 18:51:54,706 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-12 18:51:54,706 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2024-10-12 18:51:54,707 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:51:54,708 INFO L225 Difference]: With dead ends: 49 [2024-10-12 18:51:54,708 INFO L226 Difference]: Without dead ends: 42 [2024-10-12 18:51:54,709 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-10-12 18:51:54,712 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 30 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:51:54,713 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 116 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:51:54,714 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-10-12 18:51:54,726 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 32. [2024-10-12 18:51:54,727 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-10-12 18:51:54,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2024-10-12 18:51:54,730 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 29 [2024-10-12 18:51:54,730 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:51:54,730 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2024-10-12 18:51:54,730 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:51:54,731 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2024-10-12 18:51:54,732 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-10-12 18:51:54,732 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:54,732 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:54,733 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-12 18:51:54,733 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:54,733 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:54,734 INFO L85 PathProgramCache]: Analyzing trace with hash -1072684582, now seen corresponding path program 1 times [2024-10-12 18:51:54,734 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:54,734 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1383087845] [2024-10-12 18:51:54,734 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:54,734 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:54,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:51:54,774 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [688313356] [2024-10-12 18:51:54,775 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:54,775 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:54,775 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:51:54,777 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:51:54,779 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-10-12 18:51:54,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:54,848 INFO L255 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-12 18:51:54,855 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:51:55,023 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-12 18:51:55,024 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-12 18:51:55,025 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:51:55,027 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1383087845] [2024-10-12 18:51:55,028 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:51:55,028 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [688313356] [2024-10-12 18:51:55,028 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [688313356] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:51:55,028 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:51:55,028 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-12 18:51:55,028 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [917529405] [2024-10-12 18:51:55,029 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:51:55,029 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 18:51:55,029 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:51:55,030 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 18:51:55,030 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-12 18:51:55,030 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:51:55,105 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:51:55,105 INFO L93 Difference]: Finished difference Result 48 states and 62 transitions. [2024-10-12 18:51:55,106 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-12 18:51:55,106 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2024-10-12 18:51:55,107 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:51:55,107 INFO L225 Difference]: With dead ends: 48 [2024-10-12 18:51:55,108 INFO L226 Difference]: Without dead ends: 46 [2024-10-12 18:51:55,108 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-12 18:51:55,109 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 7 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 127 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:51:55,109 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 127 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:51:55,110 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-10-12 18:51:55,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 45. [2024-10-12 18:51:55,123 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 28 states have (on average 1.2142857142857142) internal successors, (34), 29 states have internal predecessors, (34), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-10-12 18:51:55,124 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 59 transitions. [2024-10-12 18:51:55,124 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 59 transitions. Word has length 32 [2024-10-12 18:51:55,124 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:51:55,125 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 59 transitions. [2024-10-12 18:51:55,125 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:51:55,125 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 59 transitions. [2024-10-12 18:51:55,126 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-10-12 18:51:55,126 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:55,126 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:55,141 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-12 18:51:55,330 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:55,331 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:55,331 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:55,331 INFO L85 PathProgramCache]: Analyzing trace with hash 581538888, now seen corresponding path program 1 times [2024-10-12 18:51:55,331 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:55,331 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1907574523] [2024-10-12 18:51:55,332 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:55,332 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:55,351 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:55,471 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:51:55,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:55,475 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-12 18:51:55,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:55,478 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:51:55,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:55,511 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:51:55,513 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:55,517 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-12 18:51:55,517 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:51:55,518 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1907574523] [2024-10-12 18:51:55,519 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1907574523] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:51:55,519 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1002856668] [2024-10-12 18:51:55,519 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:55,520 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:55,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:51:55,522 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:51:55,524 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-10-12 18:51:55,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:55,576 INFO L255 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-12 18:51:55,578 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:51:55,618 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-12 18:51:55,622 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:51:55,704 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-12 18:51:55,704 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1002856668] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:51:55,704 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:51:55,705 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2024-10-12 18:51:55,705 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [194562275] [2024-10-12 18:51:55,705 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:51:55,705 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-10-12 18:51:55,706 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:51:55,707 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-10-12 18:51:55,707 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-10-12 18:51:55,708 INFO L87 Difference]: Start difference. First operand 45 states and 59 transitions. Second operand has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-12 18:51:55,880 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:51:55,883 INFO L93 Difference]: Finished difference Result 98 states and 138 transitions. [2024-10-12 18:51:55,883 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-12 18:51:55,883 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 34 [2024-10-12 18:51:55,884 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:51:55,885 INFO L225 Difference]: With dead ends: 98 [2024-10-12 18:51:55,885 INFO L226 Difference]: Without dead ends: 91 [2024-10-12 18:51:55,886 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 70 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2024-10-12 18:51:55,886 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 60 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 113 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 223 SdHoareTripleChecker+Invalid, 140 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 113 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:51:55,888 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 223 Invalid, 140 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 113 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:51:55,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2024-10-12 18:51:55,904 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 66. [2024-10-12 18:51:55,905 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 45 states have (on average 1.2666666666666666) internal successors, (57), 46 states have internal predecessors, (57), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-10-12 18:51:55,906 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 90 transitions. [2024-10-12 18:51:55,906 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 90 transitions. Word has length 34 [2024-10-12 18:51:55,907 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:51:55,907 INFO L471 AbstractCegarLoop]: Abstraction has 66 states and 90 transitions. [2024-10-12 18:51:55,907 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-12 18:51:55,907 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 90 transitions. [2024-10-12 18:51:55,908 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-10-12 18:51:55,908 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:55,908 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:55,923 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-10-12 18:51:56,112 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2024-10-12 18:51:56,113 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:56,114 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:56,114 INFO L85 PathProgramCache]: Analyzing trace with hash -1534715754, now seen corresponding path program 1 times [2024-10-12 18:51:56,114 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:56,114 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1235046486] [2024-10-12 18:51:56,114 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:56,115 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:56,131 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:51:56,134 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [679359492] [2024-10-12 18:51:56,134 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:56,135 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:56,135 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:51:56,136 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:51:56,139 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-10-12 18:51:56,182 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:56,183 INFO L255 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-12 18:51:56,185 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:51:56,255 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-12 18:51:56,255 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-12 18:51:56,255 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:51:56,256 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1235046486] [2024-10-12 18:51:56,256 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:51:56,256 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [679359492] [2024-10-12 18:51:56,256 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [679359492] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:51:56,256 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:51:56,256 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-12 18:51:56,256 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [885975730] [2024-10-12 18:51:56,256 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:51:56,256 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 18:51:56,257 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:51:56,257 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 18:51:56,257 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-12 18:51:56,257 INFO L87 Difference]: Start difference. First operand 66 states and 90 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-12 18:51:56,331 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:51:56,332 INFO L93 Difference]: Finished difference Result 74 states and 97 transitions. [2024-10-12 18:51:56,332 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-12 18:51:56,332 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 37 [2024-10-12 18:51:56,333 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:51:56,333 INFO L225 Difference]: With dead ends: 74 [2024-10-12 18:51:56,333 INFO L226 Difference]: Without dead ends: 72 [2024-10-12 18:51:56,334 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-12 18:51:56,335 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 7 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:51:56,335 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 124 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:51:56,336 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2024-10-12 18:51:56,352 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 70. [2024-10-12 18:51:56,354 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 48 states have (on average 1.25) internal successors, (60), 49 states have internal predecessors, (60), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-10-12 18:51:56,354 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 93 transitions. [2024-10-12 18:51:56,355 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 93 transitions. Word has length 37 [2024-10-12 18:51:56,355 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:51:56,356 INFO L471 AbstractCegarLoop]: Abstraction has 70 states and 93 transitions. [2024-10-12 18:51:56,357 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-12 18:51:56,357 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 93 transitions. [2024-10-12 18:51:56,357 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-10-12 18:51:56,357 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:56,358 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:56,375 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-10-12 18:51:56,558 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:56,559 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:56,559 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:56,559 INFO L85 PathProgramCache]: Analyzing trace with hash -1190433772, now seen corresponding path program 1 times [2024-10-12 18:51:56,559 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:56,559 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1293214717] [2024-10-12 18:51:56,559 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:56,560 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:56,571 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:51:56,572 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1210689862] [2024-10-12 18:51:56,572 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:56,572 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:56,572 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:51:56,574 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:51:56,575 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-10-12 18:51:56,621 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:56,622 INFO L255 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-10-12 18:51:56,624 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:51:56,747 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-12 18:51:56,747 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:51:56,841 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-12 18:51:56,842 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:51:56,842 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1293214717] [2024-10-12 18:51:56,842 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:51:56,842 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1210689862] [2024-10-12 18:51:56,842 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1210689862] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:51:56,842 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 18:51:56,843 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 9 [2024-10-12 18:51:56,843 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [786240789] [2024-10-12 18:51:56,843 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 18:51:56,843 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-10-12 18:51:56,844 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:51:56,845 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-10-12 18:51:56,845 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-10-12 18:51:56,845 INFO L87 Difference]: Start difference. First operand 70 states and 93 transitions. Second operand has 9 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 8 states have internal predecessors, (30), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:51:56,995 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:51:56,996 INFO L93 Difference]: Finished difference Result 106 states and 142 transitions. [2024-10-12 18:51:56,996 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-12 18:51:56,996 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 8 states have internal predecessors, (30), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 37 [2024-10-12 18:51:56,997 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:51:56,999 INFO L225 Difference]: With dead ends: 106 [2024-10-12 18:51:56,999 INFO L226 Difference]: Without dead ends: 104 [2024-10-12 18:51:56,999 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 63 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2024-10-12 18:51:57,000 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 30 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 197 SdHoareTripleChecker+Invalid, 89 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:51:57,000 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 197 Invalid, 89 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:51:57,002 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2024-10-12 18:51:57,026 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 100. [2024-10-12 18:51:57,027 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 69 states have (on average 1.2608695652173914) internal successors, (87), 70 states have internal predecessors, (87), 25 states have call successors, (25), 5 states have call predecessors, (25), 5 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2024-10-12 18:51:57,028 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 136 transitions. [2024-10-12 18:51:57,029 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 136 transitions. Word has length 37 [2024-10-12 18:51:57,029 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:51:57,029 INFO L471 AbstractCegarLoop]: Abstraction has 100 states and 136 transitions. [2024-10-12 18:51:57,030 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 8 states have internal predecessors, (30), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:51:57,030 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 136 transitions. [2024-10-12 18:51:57,030 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-10-12 18:51:57,031 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:57,031 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:57,048 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-12 18:51:57,234 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:57,235 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:57,235 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:57,235 INFO L85 PathProgramCache]: Analyzing trace with hash 1246105370, now seen corresponding path program 1 times [2024-10-12 18:51:57,235 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:57,235 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1792166526] [2024-10-12 18:51:57,236 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:57,236 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:57,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:51:57,252 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [565015254] [2024-10-12 18:51:57,252 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:57,252 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:57,252 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:51:57,254 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:51:57,256 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-10-12 18:51:57,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:57,299 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 18:51:57,301 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:51:57,346 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-12 18:51:57,347 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-12 18:51:57,347 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:51:57,347 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1792166526] [2024-10-12 18:51:57,347 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:51:57,347 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [565015254] [2024-10-12 18:51:57,347 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [565015254] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:51:57,348 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:51:57,348 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-12 18:51:57,348 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [619769332] [2024-10-12 18:51:57,348 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:51:57,349 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 18:51:57,349 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:51:57,349 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 18:51:57,349 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-12 18:51:57,350 INFO L87 Difference]: Start difference. First operand 100 states and 136 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-12 18:51:57,415 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:51:57,415 INFO L93 Difference]: Finished difference Result 146 states and 208 transitions. [2024-10-12 18:51:57,415 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-12 18:51:57,415 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 42 [2024-10-12 18:51:57,416 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:51:57,436 INFO L225 Difference]: With dead ends: 146 [2024-10-12 18:51:57,437 INFO L226 Difference]: Without dead ends: 144 [2024-10-12 18:51:57,438 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-12 18:51:57,439 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 6 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:51:57,439 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 117 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:51:57,440 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 144 states. [2024-10-12 18:51:57,468 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 144 to 138. [2024-10-12 18:51:57,468 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 86 states have (on average 1.2906976744186047) internal successors, (111), 87 states have internal predecessors, (111), 45 states have call successors, (45), 6 states have call predecessors, (45), 6 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-10-12 18:51:57,470 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 200 transitions. [2024-10-12 18:51:57,471 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 200 transitions. Word has length 42 [2024-10-12 18:51:57,471 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:51:57,471 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 200 transitions. [2024-10-12 18:51:57,471 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-12 18:51:57,472 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 200 transitions. [2024-10-12 18:51:57,472 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-10-12 18:51:57,472 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:57,473 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:57,489 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-10-12 18:51:57,673 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:57,674 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:57,675 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:57,675 INFO L85 PathProgramCache]: Analyzing trace with hash -1174265188, now seen corresponding path program 1 times [2024-10-12 18:51:57,675 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:57,675 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1506592418] [2024-10-12 18:51:57,675 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:57,675 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:57,687 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:51:57,692 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1939949022] [2024-10-12 18:51:57,692 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:57,692 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:57,692 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:51:57,694 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:51:57,695 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-10-12 18:51:57,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:57,749 INFO L255 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-10-12 18:51:57,751 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:51:57,904 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-12 18:51:57,907 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:51:57,970 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:51:57,970 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1506592418] [2024-10-12 18:51:57,970 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:51:57,970 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1939949022] [2024-10-12 18:51:57,970 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1939949022] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:51:57,971 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-12 18:51:57,971 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2024-10-12 18:51:57,971 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [149580320] [2024-10-12 18:51:57,971 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-12 18:51:57,971 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-12 18:51:57,971 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:51:57,972 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-12 18:51:57,972 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-10-12 18:51:57,972 INFO L87 Difference]: Start difference. First operand 138 states and 200 transitions. Second operand has 7 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-12 18:51:58,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:51:58,125 INFO L93 Difference]: Finished difference Result 151 states and 211 transitions. [2024-10-12 18:51:58,125 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-12 18:51:58,126 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 42 [2024-10-12 18:51:58,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:51:58,128 INFO L225 Difference]: With dead ends: 151 [2024-10-12 18:51:58,128 INFO L226 Difference]: Without dead ends: 149 [2024-10-12 18:51:58,129 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 38 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2024-10-12 18:51:58,130 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 26 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 112 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 200 SdHoareTripleChecker+Invalid, 123 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 112 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:51:58,131 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 200 Invalid, 123 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 112 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:51:58,132 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2024-10-12 18:51:58,158 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 146. [2024-10-12 18:51:58,159 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 146 states, 92 states have (on average 1.2717391304347827) internal successors, (117), 93 states have internal predecessors, (117), 45 states have call successors, (45), 8 states have call predecessors, (45), 8 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-10-12 18:51:58,160 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 206 transitions. [2024-10-12 18:51:58,161 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 206 transitions. Word has length 42 [2024-10-12 18:51:58,161 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:51:58,161 INFO L471 AbstractCegarLoop]: Abstraction has 146 states and 206 transitions. [2024-10-12 18:51:58,161 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-12 18:51:58,161 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 206 transitions. [2024-10-12 18:51:58,162 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-10-12 18:51:58,162 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:58,162 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:58,180 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-10-12 18:51:58,363 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:58,363 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:58,363 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:58,364 INFO L85 PathProgramCache]: Analyzing trace with hash -829983206, now seen corresponding path program 2 times [2024-10-12 18:51:58,364 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:58,364 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [753159050] [2024-10-12 18:51:58,364 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:58,364 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:58,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:58,412 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:51:58,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:58,415 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-12 18:51:58,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:58,416 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:51:58,417 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:58,418 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:51:58,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:58,420 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-12 18:51:58,420 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:51:58,420 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [753159050] [2024-10-12 18:51:58,420 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [753159050] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:51:58,420 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:51:58,420 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-12 18:51:58,420 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [846951194] [2024-10-12 18:51:58,420 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:51:58,421 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 18:51:58,421 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:51:58,421 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 18:51:58,421 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-12 18:51:58,421 INFO L87 Difference]: Start difference. First operand 146 states and 206 transitions. Second operand has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:51:58,523 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:51:58,523 INFO L93 Difference]: Finished difference Result 185 states and 258 transitions. [2024-10-12 18:51:58,523 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-12 18:51:58,523 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 42 [2024-10-12 18:51:58,524 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:51:58,525 INFO L225 Difference]: With dead ends: 185 [2024-10-12 18:51:58,525 INFO L226 Difference]: Without dead ends: 129 [2024-10-12 18:51:58,526 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2024-10-12 18:51:58,527 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 18 mSDsluCounter, 108 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 155 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:51:58,527 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 155 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:51:58,528 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2024-10-12 18:51:58,546 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 121. [2024-10-12 18:51:58,546 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 75 states have (on average 1.2133333333333334) internal successors, (91), 76 states have internal predecessors, (91), 37 states have call successors, (37), 8 states have call predecessors, (37), 8 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2024-10-12 18:51:58,547 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 164 transitions. [2024-10-12 18:51:58,548 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 164 transitions. Word has length 42 [2024-10-12 18:51:58,548 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:51:58,548 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 164 transitions. [2024-10-12 18:51:58,548 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:51:58,548 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 164 transitions. [2024-10-12 18:51:58,549 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-10-12 18:51:58,549 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:58,549 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:58,549 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2024-10-12 18:51:58,549 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:58,550 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:58,550 INFO L85 PathProgramCache]: Analyzing trace with hash 225223382, now seen corresponding path program 1 times [2024-10-12 18:51:58,550 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:58,550 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2128993611] [2024-10-12 18:51:58,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:58,550 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:58,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:51:58,560 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [288706739] [2024-10-12 18:51:58,561 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:58,561 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:58,561 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:51:58,562 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:51:58,564 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-10-12 18:51:58,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:58,618 INFO L255 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 18:51:58,619 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:51:58,655 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-10-12 18:51:58,656 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-12 18:51:58,656 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:51:58,656 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2128993611] [2024-10-12 18:51:58,656 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:51:58,656 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [288706739] [2024-10-12 18:51:58,656 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [288706739] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:51:58,657 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:51:58,657 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-12 18:51:58,657 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [419661333] [2024-10-12 18:51:58,657 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:51:58,657 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 18:51:58,657 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:51:58,658 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 18:51:58,658 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-12 18:51:58,658 INFO L87 Difference]: Start difference. First operand 121 states and 164 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-12 18:51:58,726 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:51:58,726 INFO L93 Difference]: Finished difference Result 179 states and 261 transitions. [2024-10-12 18:51:58,726 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-12 18:51:58,727 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 47 [2024-10-12 18:51:58,727 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:51:58,729 INFO L225 Difference]: With dead ends: 179 [2024-10-12 18:51:58,729 INFO L226 Difference]: Without dead ends: 177 [2024-10-12 18:51:58,729 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-12 18:51:58,730 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 4 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:51:58,730 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 125 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:51:58,730 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2024-10-12 18:51:58,758 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 165. [2024-10-12 18:51:58,759 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 165 states, 86 states have (on average 1.186046511627907) internal successors, (102), 95 states have internal predecessors, (102), 69 states have call successors, (69), 9 states have call predecessors, (69), 9 states have return successors, (68), 60 states have call predecessors, (68), 68 states have call successors, (68) [2024-10-12 18:51:58,760 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 239 transitions. [2024-10-12 18:51:58,761 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 239 transitions. Word has length 47 [2024-10-12 18:51:58,761 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:51:58,761 INFO L471 AbstractCegarLoop]: Abstraction has 165 states and 239 transitions. [2024-10-12 18:51:58,761 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-12 18:51:58,761 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 239 transitions. [2024-10-12 18:51:58,762 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-10-12 18:51:58,762 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:58,763 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:58,778 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-10-12 18:51:58,963 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:58,963 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:58,964 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:58,964 INFO L85 PathProgramCache]: Analyzing trace with hash 371933676, now seen corresponding path program 1 times [2024-10-12 18:51:58,964 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:58,964 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1232035639] [2024-10-12 18:51:58,964 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:58,965 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:58,980 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:51:58,981 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1978475038] [2024-10-12 18:51:58,981 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:58,981 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:58,982 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:51:58,983 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:51:58,988 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-10-12 18:51:59,053 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:59,055 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-10-12 18:51:59,060 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:51:59,756 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 14 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-12 18:51:59,756 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:01,035 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-12 18:52:01,036 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:01,036 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1232035639] [2024-10-12 18:52:01,036 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:52:01,036 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1978475038] [2024-10-12 18:52:01,036 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1978475038] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:01,037 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 18:52:01,037 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-10-12 18:52:01,037 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [561282935] [2024-10-12 18:52:01,037 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:01,038 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-10-12 18:52:01,038 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:01,038 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-10-12 18:52:01,038 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2024-10-12 18:52:01,039 INFO L87 Difference]: Start difference. First operand 165 states and 239 transitions. Second operand has 23 states, 21 states have (on average 2.0) internal successors, (42), 20 states have internal predecessors, (42), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-10-12 18:52:04,107 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:04,107 INFO L93 Difference]: Finished difference Result 444 states and 664 transitions. [2024-10-12 18:52:04,108 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2024-10-12 18:52:04,108 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 2.0) internal successors, (42), 20 states have internal predecessors, (42), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 59 [2024-10-12 18:52:04,108 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:04,112 INFO L225 Difference]: With dead ends: 444 [2024-10-12 18:52:04,112 INFO L226 Difference]: Without dead ends: 341 [2024-10-12 18:52:04,113 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 95 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 429 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=398, Invalid=1672, Unknown=0, NotChecked=0, Total=2070 [2024-10-12 18:52:04,114 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 161 mSDsluCounter, 396 mSDsCounter, 0 mSdLazyCounter, 649 mSolverCounterSat, 125 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 169 SdHoareTripleChecker+Valid, 424 SdHoareTripleChecker+Invalid, 774 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 125 IncrementalHoareTripleChecker+Valid, 649 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:04,114 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [169 Valid, 424 Invalid, 774 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [125 Valid, 649 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2024-10-12 18:52:04,115 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 341 states. [2024-10-12 18:52:04,218 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 341 to 255. [2024-10-12 18:52:04,218 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 255 states, 149 states have (on average 1.2080536912751678) internal successors, (180), 156 states have internal predecessors, (180), 93 states have call successors, (93), 12 states have call predecessors, (93), 12 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-10-12 18:52:04,220 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 255 states to 255 states and 365 transitions. [2024-10-12 18:52:04,224 INFO L78 Accepts]: Start accepts. Automaton has 255 states and 365 transitions. Word has length 59 [2024-10-12 18:52:04,224 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:04,224 INFO L471 AbstractCegarLoop]: Abstraction has 255 states and 365 transitions. [2024-10-12 18:52:04,224 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 2.0) internal successors, (42), 20 states have internal predecessors, (42), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-10-12 18:52:04,224 INFO L276 IsEmpty]: Start isEmpty. Operand 255 states and 365 transitions. [2024-10-12 18:52:04,225 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2024-10-12 18:52:04,225 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:04,225 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:04,238 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-10-12 18:52:04,429 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-10-12 18:52:04,430 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:04,430 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:04,430 INFO L85 PathProgramCache]: Analyzing trace with hash -1835197705, now seen corresponding path program 1 times [2024-10-12 18:52:04,430 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:04,430 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2052493686] [2024-10-12 18:52:04,430 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:04,431 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:04,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:52:04,445 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [613517280] [2024-10-12 18:52:04,445 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:04,445 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:04,445 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:04,447 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:04,452 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-10-12 18:52:04,505 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:04,506 INFO L255 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-10-12 18:52:04,508 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:04,580 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 108 trivial. 0 not checked. [2024-10-12 18:52:04,580 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:04,657 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2024-10-12 18:52:04,657 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:04,657 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2052493686] [2024-10-12 18:52:04,658 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:52:04,658 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [613517280] [2024-10-12 18:52:04,658 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [613517280] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-12 18:52:04,658 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-12 18:52:04,658 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-10-12 18:52:04,658 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1683312826] [2024-10-12 18:52:04,658 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:52:04,659 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 18:52:04,659 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:04,659 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 18:52:04,660 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-10-12 18:52:04,660 INFO L87 Difference]: Start difference. First operand 255 states and 365 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-10-12 18:52:04,796 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:04,796 INFO L93 Difference]: Finished difference Result 261 states and 370 transitions. [2024-10-12 18:52:04,797 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-12 18:52:04,797 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 69 [2024-10-12 18:52:04,797 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:04,799 INFO L225 Difference]: With dead ends: 261 [2024-10-12 18:52:04,799 INFO L226 Difference]: Without dead ends: 259 [2024-10-12 18:52:04,799 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 129 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-10-12 18:52:04,800 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 4 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:04,800 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 120 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:52:04,801 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states. [2024-10-12 18:52:04,886 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 259. [2024-10-12 18:52:04,886 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 259 states, 152 states have (on average 1.2039473684210527) internal successors, (183), 159 states have internal predecessors, (183), 93 states have call successors, (93), 13 states have call predecessors, (93), 13 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-10-12 18:52:04,888 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 259 states to 259 states and 368 transitions. [2024-10-12 18:52:04,888 INFO L78 Accepts]: Start accepts. Automaton has 259 states and 368 transitions. Word has length 69 [2024-10-12 18:52:04,889 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:04,889 INFO L471 AbstractCegarLoop]: Abstraction has 259 states and 368 transitions. [2024-10-12 18:52:04,889 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-10-12 18:52:04,889 INFO L276 IsEmpty]: Start isEmpty. Operand 259 states and 368 transitions. [2024-10-12 18:52:04,890 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-10-12 18:52:04,890 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:04,893 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:04,908 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-10-12 18:52:05,096 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:05,097 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:05,097 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:05,097 INFO L85 PathProgramCache]: Analyzing trace with hash 791958698, now seen corresponding path program 1 times [2024-10-12 18:52:05,097 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:05,097 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [380965236] [2024-10-12 18:52:05,097 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:05,097 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:05,120 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:52:05,122 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1985052037] [2024-10-12 18:52:05,123 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:05,123 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:05,123 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:05,125 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:05,126 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-10-12 18:52:05,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:05,198 INFO L255 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 50 conjuncts are in the unsatisfiable core [2024-10-12 18:52:05,200 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:05,672 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 16 proven. 31 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-10-12 18:52:05,673 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:05,854 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2024-10-12 18:52:05,854 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:05,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [380965236] [2024-10-12 18:52:05,854 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:52:05,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1985052037] [2024-10-12 18:52:05,854 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1985052037] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:05,855 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 18:52:05,855 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2024-10-12 18:52:05,855 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2098462117] [2024-10-12 18:52:05,855 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:05,855 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-10-12 18:52:05,855 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:05,856 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-10-12 18:52:05,856 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2024-10-12 18:52:05,856 INFO L87 Difference]: Start difference. First operand 259 states and 368 transitions. Second operand has 22 states, 22 states have (on average 2.727272727272727) internal successors, (60), 19 states have internal predecessors, (60), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-10-12 18:52:09,109 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:09,109 INFO L93 Difference]: Finished difference Result 321 states and 458 transitions. [2024-10-12 18:52:09,110 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-10-12 18:52:09,110 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.727272727272727) internal successors, (60), 19 states have internal predecessors, (60), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 67 [2024-10-12 18:52:09,110 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:09,112 INFO L225 Difference]: With dead ends: 321 [2024-10-12 18:52:09,112 INFO L226 Difference]: Without dead ends: 319 [2024-10-12 18:52:09,113 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 121 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 193 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=190, Invalid=932, Unknown=0, NotChecked=0, Total=1122 [2024-10-12 18:52:09,114 INFO L432 NwaCegarLoop]: 50 mSDtfsCounter, 99 mSDsluCounter, 436 mSDsCounter, 0 mSdLazyCounter, 638 mSolverCounterSat, 84 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 486 SdHoareTripleChecker+Invalid, 722 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 84 IncrementalHoareTripleChecker+Valid, 638 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:09,114 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [101 Valid, 486 Invalid, 722 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [84 Valid, 638 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2024-10-12 18:52:09,115 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 319 states. [2024-10-12 18:52:09,196 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 319 to 267. [2024-10-12 18:52:09,197 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 267 states, 158 states have (on average 1.1962025316455696) internal successors, (189), 165 states have internal predecessors, (189), 93 states have call successors, (93), 15 states have call predecessors, (93), 15 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-10-12 18:52:09,198 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 267 states to 267 states and 374 transitions. [2024-10-12 18:52:09,198 INFO L78 Accepts]: Start accepts. Automaton has 267 states and 374 transitions. Word has length 67 [2024-10-12 18:52:09,199 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:09,199 INFO L471 AbstractCegarLoop]: Abstraction has 267 states and 374 transitions. [2024-10-12 18:52:09,199 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.727272727272727) internal successors, (60), 19 states have internal predecessors, (60), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-10-12 18:52:09,199 INFO L276 IsEmpty]: Start isEmpty. Operand 267 states and 374 transitions. [2024-10-12 18:52:09,199 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-10-12 18:52:09,199 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:09,200 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:09,214 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-10-12 18:52:09,403 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-10-12 18:52:09,403 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:09,404 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:09,404 INFO L85 PathProgramCache]: Analyzing trace with hash 1365578820, now seen corresponding path program 2 times [2024-10-12 18:52:09,404 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:09,404 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1229528855] [2024-10-12 18:52:09,404 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:09,404 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:09,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:09,481 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:09,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:09,483 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-12 18:52:09,484 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:09,485 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:52:09,487 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:09,487 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:52:09,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:09,489 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-10-12 18:52:09,491 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:09,493 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-12 18:52:09,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:09,497 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-10-12 18:52:09,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:09,500 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 48 [2024-10-12 18:52:09,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:09,503 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 58 [2024-10-12 18:52:09,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:09,505 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2024-10-12 18:52:09,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:09,509 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2024-10-12 18:52:09,509 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:09,509 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1229528855] [2024-10-12 18:52:09,509 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1229528855] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:52:09,509 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:52:09,510 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-12 18:52:09,510 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [448929215] [2024-10-12 18:52:09,510 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:52:09,510 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 18:52:09,510 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:09,511 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 18:52:09,511 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-12 18:52:09,512 INFO L87 Difference]: Start difference. First operand 267 states and 374 transitions. Second operand has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-10-12 18:52:09,648 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:09,648 INFO L93 Difference]: Finished difference Result 458 states and 644 transitions. [2024-10-12 18:52:09,648 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-12 18:52:09,649 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 72 [2024-10-12 18:52:09,649 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:09,651 INFO L225 Difference]: With dead ends: 458 [2024-10-12 18:52:09,651 INFO L226 Difference]: Without dead ends: 288 [2024-10-12 18:52:09,651 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-12 18:52:09,652 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 1 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 45 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:09,652 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 116 Invalid, 45 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:52:09,653 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 288 states. [2024-10-12 18:52:09,750 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 288 to 276. [2024-10-12 18:52:09,751 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 276 states, 167 states have (on average 1.1976047904191616) internal successors, (200), 168 states have internal predecessors, (200), 93 states have call successors, (93), 15 states have call predecessors, (93), 15 states have return successors, (92), 92 states have call predecessors, (92), 92 states have call successors, (92) [2024-10-12 18:52:09,754 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 276 states to 276 states and 385 transitions. [2024-10-12 18:52:09,755 INFO L78 Accepts]: Start accepts. Automaton has 276 states and 385 transitions. Word has length 72 [2024-10-12 18:52:09,755 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:09,755 INFO L471 AbstractCegarLoop]: Abstraction has 276 states and 385 transitions. [2024-10-12 18:52:09,755 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-10-12 18:52:09,755 INFO L276 IsEmpty]: Start isEmpty. Operand 276 states and 385 transitions. [2024-10-12 18:52:09,756 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-10-12 18:52:09,756 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:09,756 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:09,756 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13 [2024-10-12 18:52:09,756 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:09,757 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:09,757 INFO L85 PathProgramCache]: Analyzing trace with hash -1054791738, now seen corresponding path program 3 times [2024-10-12 18:52:09,757 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:09,757 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1885419061] [2024-10-12 18:52:09,757 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:09,757 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:09,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:52:09,777 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2060780497] [2024-10-12 18:52:09,777 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-12 18:52:09,777 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:09,777 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:09,779 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:09,780 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-10-12 18:52:09,848 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-10-12 18:52:09,848 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-12 18:52:09,850 INFO L255 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-10-12 18:52:09,852 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:10,342 INFO L134 CoverageAnalysis]: Checked inductivity of 96 backedges. 10 proven. 22 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2024-10-12 18:52:10,343 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:11,520 INFO L134 CoverageAnalysis]: Checked inductivity of 96 backedges. 14 proven. 18 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2024-10-12 18:52:11,521 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:11,521 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1885419061] [2024-10-12 18:52:11,521 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:52:11,521 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2060780497] [2024-10-12 18:52:11,521 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2060780497] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:11,521 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 18:52:11,521 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2024-10-12 18:52:11,522 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1604997068] [2024-10-12 18:52:11,522 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:11,522 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-10-12 18:52:11,522 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:11,523 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-10-12 18:52:11,523 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=375, Unknown=0, NotChecked=0, Total=462 [2024-10-12 18:52:11,523 INFO L87 Difference]: Start difference. First operand 276 states and 385 transitions. Second operand has 22 states, 22 states have (on average 2.409090909090909) internal successors, (53), 21 states have internal predecessors, (53), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2024-10-12 18:52:14,662 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:14,662 INFO L93 Difference]: Finished difference Result 413 states and 571 transitions. [2024-10-12 18:52:14,662 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2024-10-12 18:52:14,663 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.409090909090909) internal successors, (53), 21 states have internal predecessors, (53), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) Word has length 72 [2024-10-12 18:52:14,663 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:14,665 INFO L225 Difference]: With dead ends: 413 [2024-10-12 18:52:14,665 INFO L226 Difference]: Without dead ends: 411 [2024-10-12 18:52:14,666 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 167 GetRequests, 120 SyntacticMatches, 2 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 432 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=472, Invalid=1690, Unknown=0, NotChecked=0, Total=2162 [2024-10-12 18:52:14,667 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 182 mSDsluCounter, 369 mSDsCounter, 0 mSdLazyCounter, 557 mSolverCounterSat, 155 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 182 SdHoareTripleChecker+Valid, 412 SdHoareTripleChecker+Invalid, 712 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 155 IncrementalHoareTripleChecker+Valid, 557 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:14,667 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [182 Valid, 412 Invalid, 712 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [155 Valid, 557 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2024-10-12 18:52:14,668 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 411 states. [2024-10-12 18:52:14,803 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 411 to 354. [2024-10-12 18:52:14,804 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 354 states, 216 states have (on average 1.1944444444444444) internal successors, (258), 217 states have internal predecessors, (258), 117 states have call successors, (117), 20 states have call predecessors, (117), 20 states have return successors, (116), 116 states have call predecessors, (116), 116 states have call successors, (116) [2024-10-12 18:52:14,805 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 354 states to 354 states and 491 transitions. [2024-10-12 18:52:14,806 INFO L78 Accepts]: Start accepts. Automaton has 354 states and 491 transitions. Word has length 72 [2024-10-12 18:52:14,806 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:14,806 INFO L471 AbstractCegarLoop]: Abstraction has 354 states and 491 transitions. [2024-10-12 18:52:14,806 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.409090909090909) internal successors, (53), 21 states have internal predecessors, (53), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2024-10-12 18:52:14,806 INFO L276 IsEmpty]: Start isEmpty. Operand 354 states and 491 transitions. [2024-10-12 18:52:14,807 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2024-10-12 18:52:14,807 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:14,807 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:14,820 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-10-12 18:52:15,008 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-10-12 18:52:15,008 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:15,008 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:15,008 INFO L85 PathProgramCache]: Analyzing trace with hash 807741843, now seen corresponding path program 1 times [2024-10-12 18:52:15,008 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:15,009 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [339300507] [2024-10-12 18:52:15,009 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:15,009 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:15,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:52:15,031 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1509835094] [2024-10-12 18:52:15,032 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:15,032 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:15,032 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:15,033 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:15,035 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-10-12 18:52:15,096 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:15,097 INFO L255 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 64 conjuncts are in the unsatisfiable core [2024-10-12 18:52:15,099 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:16,169 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 36 proven. 29 refuted. 0 times theorem prover too weak. 106 trivial. 0 not checked. [2024-10-12 18:52:16,170 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:17,508 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:17,509 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [339300507] [2024-10-12 18:52:17,509 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:52:17,509 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1509835094] [2024-10-12 18:52:17,509 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1509835094] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:52:17,509 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-12 18:52:17,509 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2024-10-12 18:52:17,509 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [593659001] [2024-10-12 18:52:17,509 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:17,510 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-10-12 18:52:17,510 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:17,510 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-12 18:52:17,510 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=664, Unknown=0, NotChecked=0, Total=756 [2024-10-12 18:52:17,511 INFO L87 Difference]: Start difference. First operand 354 states and 491 transitions. Second operand has 21 states, 20 states have (on average 1.85) internal successors, (37), 19 states have internal predecessors, (37), 6 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2024-10-12 18:52:19,274 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:19,274 INFO L93 Difference]: Finished difference Result 433 states and 599 transitions. [2024-10-12 18:52:19,275 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-10-12 18:52:19,275 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 1.85) internal successors, (37), 19 states have internal predecessors, (37), 6 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) Word has length 86 [2024-10-12 18:52:19,275 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:19,278 INFO L225 Difference]: With dead ends: 433 [2024-10-12 18:52:19,278 INFO L226 Difference]: Without dead ends: 426 [2024-10-12 18:52:19,279 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 81 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 253 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=165, Invalid=1167, Unknown=0, NotChecked=0, Total=1332 [2024-10-12 18:52:19,279 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 81 mSDsluCounter, 655 mSDsCounter, 0 mSdLazyCounter, 962 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 97 SdHoareTripleChecker+Valid, 704 SdHoareTripleChecker+Invalid, 1020 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 962 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:19,279 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [97 Valid, 704 Invalid, 1020 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 962 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2024-10-12 18:52:19,281 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 426 states. [2024-10-12 18:52:19,495 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 426 to 406. [2024-10-12 18:52:19,495 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 406 states, 242 states have (on average 1.2024793388429753) internal successors, (291), 243 states have internal predecessors, (291), 141 states have call successors, (141), 22 states have call predecessors, (141), 22 states have return successors, (140), 140 states have call predecessors, (140), 140 states have call successors, (140) [2024-10-12 18:52:19,498 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 406 states to 406 states and 572 transitions. [2024-10-12 18:52:19,499 INFO L78 Accepts]: Start accepts. Automaton has 406 states and 572 transitions. Word has length 86 [2024-10-12 18:52:19,499 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:19,499 INFO L471 AbstractCegarLoop]: Abstraction has 406 states and 572 transitions. [2024-10-12 18:52:19,499 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 1.85) internal successors, (37), 19 states have internal predecessors, (37), 6 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2024-10-12 18:52:19,499 INFO L276 IsEmpty]: Start isEmpty. Operand 406 states and 572 transitions. [2024-10-12 18:52:19,500 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2024-10-12 18:52:19,501 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:19,501 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:19,518 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-10-12 18:52:19,701 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-10-12 18:52:19,702 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:19,703 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:19,703 INFO L85 PathProgramCache]: Analyzing trace with hash -945949089, now seen corresponding path program 1 times [2024-10-12 18:52:19,703 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:19,703 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [536356257] [2024-10-12 18:52:19,704 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:19,704 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:19,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:52:19,725 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [632848820] [2024-10-12 18:52:19,725 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:19,725 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:19,726 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:19,727 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:19,729 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-10-12 18:52:19,783 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:19,785 INFO L255 TraceCheckSpWp]: Trace formula consists of 203 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-10-12 18:52:19,786 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:20,087 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 26 proven. 19 refuted. 0 times theorem prover too weak. 195 trivial. 0 not checked. [2024-10-12 18:52:20,087 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:20,605 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 22 proven. 14 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2024-10-12 18:52:20,605 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:20,606 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [536356257] [2024-10-12 18:52:20,606 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:52:20,606 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [632848820] [2024-10-12 18:52:20,606 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [632848820] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:20,606 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 18:52:20,606 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 10] total 22 [2024-10-12 18:52:20,606 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1959373759] [2024-10-12 18:52:20,606 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:20,606 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-10-12 18:52:20,606 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:20,607 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-10-12 18:52:20,607 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=373, Unknown=0, NotChecked=0, Total=462 [2024-10-12 18:52:20,607 INFO L87 Difference]: Start difference. First operand 406 states and 572 transitions. Second operand has 22 states, 22 states have (on average 1.9090909090909092) internal successors, (42), 19 states have internal predecessors, (42), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-10-12 18:52:23,020 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:23,020 INFO L93 Difference]: Finished difference Result 956 states and 1503 transitions. [2024-10-12 18:52:23,020 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2024-10-12 18:52:23,021 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 1.9090909090909092) internal successors, (42), 19 states have internal predecessors, (42), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 89 [2024-10-12 18:52:23,021 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:23,026 INFO L225 Difference]: With dead ends: 956 [2024-10-12 18:52:23,026 INFO L226 Difference]: Without dead ends: 954 [2024-10-12 18:52:23,027 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 204 GetRequests, 157 SyntacticMatches, 0 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 561 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=528, Invalid=1824, Unknown=0, NotChecked=0, Total=2352 [2024-10-12 18:52:23,028 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 146 mSDsluCounter, 365 mSDsCounter, 0 mSdLazyCounter, 391 mSolverCounterSat, 120 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 150 SdHoareTripleChecker+Valid, 407 SdHoareTripleChecker+Invalid, 511 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 120 IncrementalHoareTripleChecker+Valid, 391 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:23,028 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [150 Valid, 407 Invalid, 511 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [120 Valid, 391 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-10-12 18:52:23,029 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 954 states. [2024-10-12 18:52:23,519 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 954 to 788. [2024-10-12 18:52:23,520 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 788 states, 397 states have (on average 1.2896725440806045) internal successors, (512), 398 states have internal predecessors, (512), 365 states have call successors, (365), 25 states have call predecessors, (365), 25 states have return successors, (364), 364 states have call predecessors, (364), 364 states have call successors, (364) [2024-10-12 18:52:23,524 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 788 states to 788 states and 1241 transitions. [2024-10-12 18:52:23,525 INFO L78 Accepts]: Start accepts. Automaton has 788 states and 1241 transitions. Word has length 89 [2024-10-12 18:52:23,525 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:23,526 INFO L471 AbstractCegarLoop]: Abstraction has 788 states and 1241 transitions. [2024-10-12 18:52:23,526 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 1.9090909090909092) internal successors, (42), 19 states have internal predecessors, (42), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-10-12 18:52:23,526 INFO L276 IsEmpty]: Start isEmpty. Operand 788 states and 1241 transitions. [2024-10-12 18:52:23,527 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2024-10-12 18:52:23,527 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:23,527 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:23,541 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2024-10-12 18:52:23,731 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-10-12 18:52:23,732 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:23,732 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:23,732 INFO L85 PathProgramCache]: Analyzing trace with hash 928647649, now seen corresponding path program 1 times [2024-10-12 18:52:23,732 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:23,732 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [881083374] [2024-10-12 18:52:23,732 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:23,732 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:23,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:52:23,755 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [489047000] [2024-10-12 18:52:23,755 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:23,755 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:23,756 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:23,759 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:23,761 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-10-12 18:52:23,820 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:23,821 INFO L255 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-10-12 18:52:23,823 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:24,430 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 24 proven. 23 refuted. 0 times theorem prover too weak. 159 trivial. 0 not checked. [2024-10-12 18:52:24,430 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:25,740 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 18 proven. 20 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-10-12 18:52:25,740 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:25,740 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [881083374] [2024-10-12 18:52:25,741 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:52:25,741 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [489047000] [2024-10-12 18:52:25,741 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [489047000] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:25,741 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 18:52:25,741 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-10-12 18:52:25,741 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [657077953] [2024-10-12 18:52:25,741 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:25,741 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-10-12 18:52:25,741 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:25,742 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-10-12 18:52:25,742 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=426, Unknown=0, NotChecked=0, Total=506 [2024-10-12 18:52:25,742 INFO L87 Difference]: Start difference. First operand 788 states and 1241 transitions. Second operand has 23 states, 23 states have (on average 2.260869565217391) internal successors, (52), 20 states have internal predecessors, (52), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-10-12 18:52:35,149 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:35,149 INFO L93 Difference]: Finished difference Result 1099 states and 1720 transitions. [2024-10-12 18:52:35,149 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2024-10-12 18:52:35,150 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.260869565217391) internal successors, (52), 20 states have internal predecessors, (52), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 89 [2024-10-12 18:52:35,150 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:35,156 INFO L225 Difference]: With dead ends: 1099 [2024-10-12 18:52:35,156 INFO L226 Difference]: Without dead ends: 1097 [2024-10-12 18:52:35,158 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 213 GetRequests, 155 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 766 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=711, Invalid=2829, Unknown=0, NotChecked=0, Total=3540 [2024-10-12 18:52:35,158 INFO L432 NwaCegarLoop]: 50 mSDtfsCounter, 163 mSDsluCounter, 619 mSDsCounter, 0 mSdLazyCounter, 871 mSolverCounterSat, 171 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 163 SdHoareTripleChecker+Valid, 669 SdHoareTripleChecker+Invalid, 1042 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 171 IncrementalHoareTripleChecker+Valid, 871 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:35,158 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [163 Valid, 669 Invalid, 1042 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [171 Valid, 871 Invalid, 0 Unknown, 0 Unchecked, 4.0s Time] [2024-10-12 18:52:35,159 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1097 states. [2024-10-12 18:52:35,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1097 to 1001. [2024-10-12 18:52:35,840 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1001 states, 508 states have (on average 1.297244094488189) internal successors, (659), 509 states have internal predecessors, (659), 461 states have call successors, (461), 31 states have call predecessors, (461), 31 states have return successors, (460), 460 states have call predecessors, (460), 460 states have call successors, (460) [2024-10-12 18:52:35,845 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1001 states to 1001 states and 1580 transitions. [2024-10-12 18:52:35,847 INFO L78 Accepts]: Start accepts. Automaton has 1001 states and 1580 transitions. Word has length 89 [2024-10-12 18:52:35,847 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:35,847 INFO L471 AbstractCegarLoop]: Abstraction has 1001 states and 1580 transitions. [2024-10-12 18:52:35,847 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.260869565217391) internal successors, (52), 20 states have internal predecessors, (52), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-10-12 18:52:35,847 INFO L276 IsEmpty]: Start isEmpty. Operand 1001 states and 1580 transitions. [2024-10-12 18:52:35,849 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2024-10-12 18:52:35,850 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:35,851 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:35,868 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-10-12 18:52:36,051 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable17,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:36,051 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:36,052 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:36,052 INFO L85 PathProgramCache]: Analyzing trace with hash -842150628, now seen corresponding path program 2 times [2024-10-12 18:52:36,052 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:36,052 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1552288677] [2024-10-12 18:52:36,052 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:36,052 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:36,068 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:36,223 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:36,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:36,226 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-12 18:52:36,230 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:36,232 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:52:36,232 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:36,237 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:52:36,238 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:36,239 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-10-12 18:52:36,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:36,244 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-12 18:52:36,245 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:36,247 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-10-12 18:52:36,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:36,251 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 48 [2024-10-12 18:52:36,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:36,253 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2024-10-12 18:52:36,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:36,257 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 68 [2024-10-12 18:52:36,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:36,260 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 73 [2024-10-12 18:52:36,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:36,269 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-10-12 18:52:36,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:36,274 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-10-12 18:52:36,275 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:36,276 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1552288677] [2024-10-12 18:52:36,276 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1552288677] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:52:36,277 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [372746617] [2024-10-12 18:52:36,277 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-12 18:52:36,277 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:36,277 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:36,279 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:36,282 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-10-12 18:52:36,343 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-12 18:52:36,343 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-12 18:52:36,344 INFO L255 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-12 18:52:36,346 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:36,393 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-10-12 18:52:36,393 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:36,491 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-10-12 18:52:36,492 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [372746617] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:36,492 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:52:36,492 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 11 [2024-10-12 18:52:36,492 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [153447747] [2024-10-12 18:52:36,492 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:36,492 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-10-12 18:52:36,492 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:36,493 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-10-12 18:52:36,493 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=89, Unknown=0, NotChecked=0, Total=110 [2024-10-12 18:52:36,493 INFO L87 Difference]: Start difference. First operand 1001 states and 1580 transitions. Second operand has 11 states, 11 states have (on average 3.4545454545454546) internal successors, (38), 11 states have internal predecessors, (38), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-10-12 18:52:37,563 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:37,564 INFO L93 Difference]: Finished difference Result 1104 states and 1735 transitions. [2024-10-12 18:52:37,564 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-10-12 18:52:37,564 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.4545454545454546) internal successors, (38), 11 states have internal predecessors, (38), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 94 [2024-10-12 18:52:37,564 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:37,570 INFO L225 Difference]: With dead ends: 1104 [2024-10-12 18:52:37,570 INFO L226 Difference]: Without dead ends: 1097 [2024-10-12 18:52:37,571 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 240 GetRequests, 209 SyntacticMatches, 8 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 96 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=141, Invalid=459, Unknown=0, NotChecked=0, Total=600 [2024-10-12 18:52:37,571 INFO L432 NwaCegarLoop]: 57 mSDtfsCounter, 66 mSDsluCounter, 323 mSDsCounter, 0 mSdLazyCounter, 255 mSolverCounterSat, 57 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 70 SdHoareTripleChecker+Valid, 380 SdHoareTripleChecker+Invalid, 312 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 57 IncrementalHoareTripleChecker+Valid, 255 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:37,572 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [70 Valid, 380 Invalid, 312 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [57 Valid, 255 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-12 18:52:37,573 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1097 states. [2024-10-12 18:52:38,328 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1097 to 870. [2024-10-12 18:52:38,330 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 870 states, 432 states have (on average 1.3055555555555556) internal successors, (564), 433 states have internal predecessors, (564), 409 states have call successors, (409), 28 states have call predecessors, (409), 28 states have return successors, (408), 408 states have call predecessors, (408), 408 states have call successors, (408) [2024-10-12 18:52:38,336 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 870 states to 870 states and 1381 transitions. [2024-10-12 18:52:38,339 INFO L78 Accepts]: Start accepts. Automaton has 870 states and 1381 transitions. Word has length 94 [2024-10-12 18:52:38,339 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:38,339 INFO L471 AbstractCegarLoop]: Abstraction has 870 states and 1381 transitions. [2024-10-12 18:52:38,340 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.4545454545454546) internal successors, (38), 11 states have internal predecessors, (38), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-10-12 18:52:38,340 INFO L276 IsEmpty]: Start isEmpty. Operand 870 states and 1381 transitions. [2024-10-12 18:52:38,342 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2024-10-12 18:52:38,342 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:38,342 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:38,357 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2024-10-12 18:52:38,542 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:38,543 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:38,543 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:38,544 INFO L85 PathProgramCache]: Analyzing trace with hash -1840332690, now seen corresponding path program 2 times [2024-10-12 18:52:38,544 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:38,544 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2076809329] [2024-10-12 18:52:38,544 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:38,544 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:38,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:52:38,576 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1941434454] [2024-10-12 18:52:38,576 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-12 18:52:38,576 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:38,576 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:38,584 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:38,585 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-10-12 18:52:38,673 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-12 18:52:38,673 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-12 18:52:38,675 INFO L255 TraceCheckSpWp]: Trace formula consists of 237 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-10-12 18:52:38,677 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:39,281 INFO L134 CoverageAnalysis]: Checked inductivity of 334 backedges. 24 proven. 22 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-10-12 18:52:39,281 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:41,045 INFO L134 CoverageAnalysis]: Checked inductivity of 334 backedges. 24 proven. 22 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-10-12 18:52:41,046 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:41,046 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2076809329] [2024-10-12 18:52:41,046 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:52:41,046 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1941434454] [2024-10-12 18:52:41,046 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1941434454] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:41,046 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 18:52:41,046 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2024-10-12 18:52:41,046 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1040937590] [2024-10-12 18:52:41,046 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:41,047 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-10-12 18:52:41,047 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:41,047 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-10-12 18:52:41,047 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=381, Unknown=0, NotChecked=0, Total=462 [2024-10-12 18:52:41,048 INFO L87 Difference]: Start difference. First operand 870 states and 1381 transitions. Second operand has 22 states, 20 states have (on average 2.25) internal successors, (45), 21 states have internal predecessors, (45), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-10-12 18:52:48,335 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:48,335 INFO L93 Difference]: Finished difference Result 1066 states and 1664 transitions. [2024-10-12 18:52:48,336 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2024-10-12 18:52:48,336 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 2.25) internal successors, (45), 21 states have internal predecessors, (45), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 103 [2024-10-12 18:52:48,336 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:48,342 INFO L225 Difference]: With dead ends: 1066 [2024-10-12 18:52:48,342 INFO L226 Difference]: Without dead ends: 1058 [2024-10-12 18:52:48,344 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 251 GetRequests, 182 SyntacticMatches, 2 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1247 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=994, Invalid=3698, Unknown=0, NotChecked=0, Total=4692 [2024-10-12 18:52:48,345 INFO L432 NwaCegarLoop]: 66 mSDtfsCounter, 198 mSDsluCounter, 674 mSDsCounter, 0 mSdLazyCounter, 907 mSolverCounterSat, 208 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 198 SdHoareTripleChecker+Valid, 740 SdHoareTripleChecker+Invalid, 1115 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 208 IncrementalHoareTripleChecker+Valid, 907 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:48,345 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [198 Valid, 740 Invalid, 1115 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [208 Valid, 907 Invalid, 0 Unknown, 0 Unchecked, 2.2s Time] [2024-10-12 18:52:48,346 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1058 states. [2024-10-12 18:52:49,115 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1058 to 1027. [2024-10-12 18:52:49,117 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1027 states, 520 states have (on average 1.301923076923077) internal successors, (677), 521 states have internal predecessors, (677), 473 states have call successors, (473), 33 states have call predecessors, (473), 33 states have return successors, (472), 472 states have call predecessors, (472), 472 states have call successors, (472) [2024-10-12 18:52:49,121 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1027 states to 1027 states and 1622 transitions. [2024-10-12 18:52:49,122 INFO L78 Accepts]: Start accepts. Automaton has 1027 states and 1622 transitions. Word has length 103 [2024-10-12 18:52:49,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:49,123 INFO L471 AbstractCegarLoop]: Abstraction has 1027 states and 1622 transitions. [2024-10-12 18:52:49,123 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 2.25) internal successors, (45), 21 states have internal predecessors, (45), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-10-12 18:52:49,123 INFO L276 IsEmpty]: Start isEmpty. Operand 1027 states and 1622 transitions. [2024-10-12 18:52:49,125 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-10-12 18:52:49,125 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:49,125 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:49,133 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-10-12 18:52:49,326 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:49,326 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:49,326 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:49,326 INFO L85 PathProgramCache]: Analyzing trace with hash -1341117113, now seen corresponding path program 3 times [2024-10-12 18:52:49,326 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:49,326 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [265710321] [2024-10-12 18:52:49,327 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:49,327 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:49,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:52:49,349 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [155188743] [2024-10-12 18:52:49,349 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-12 18:52:49,350 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:49,350 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:49,351 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:49,353 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-10-12 18:52:49,456 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-10-12 18:52:49,456 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-12 18:52:49,459 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 53 conjuncts are in the unsatisfiable core [2024-10-12 18:52:49,462 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:50,065 INFO L134 CoverageAnalysis]: Checked inductivity of 339 backedges. 24 proven. 27 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-10-12 18:52:50,066 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:51,408 INFO L134 CoverageAnalysis]: Checked inductivity of 339 backedges. 24 proven. 27 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-10-12 18:52:51,409 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:51,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [265710321] [2024-10-12 18:52:51,409 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:52:51,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [155188743] [2024-10-12 18:52:51,409 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [155188743] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:51,409 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 18:52:51,409 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2024-10-12 18:52:51,409 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1979275646] [2024-10-12 18:52:51,409 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:51,409 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-10-12 18:52:51,410 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:51,410 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-10-12 18:52:51,410 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=384, Unknown=0, NotChecked=0, Total=462 [2024-10-12 18:52:51,410 INFO L87 Difference]: Start difference. First operand 1027 states and 1622 transitions. Second operand has 22 states, 20 states have (on average 2.55) internal successors, (51), 21 states have internal predecessors, (51), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-10-12 18:52:58,153 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:58,153 INFO L93 Difference]: Finished difference Result 1318 states and 2067 transitions. [2024-10-12 18:52:58,153 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2024-10-12 18:52:58,154 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 2.55) internal successors, (51), 21 states have internal predecessors, (51), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 106 [2024-10-12 18:52:58,154 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:58,160 INFO L225 Difference]: With dead ends: 1318 [2024-10-12 18:52:58,161 INFO L226 Difference]: Without dead ends: 1310 [2024-10-12 18:52:58,162 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 243 GetRequests, 188 SyntacticMatches, 2 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 673 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=579, Invalid=2391, Unknown=0, NotChecked=0, Total=2970 [2024-10-12 18:52:58,162 INFO L432 NwaCegarLoop]: 54 mSDtfsCounter, 213 mSDsluCounter, 740 mSDsCounter, 0 mSdLazyCounter, 911 mSolverCounterSat, 210 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 225 SdHoareTripleChecker+Valid, 794 SdHoareTripleChecker+Invalid, 1121 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 210 IncrementalHoareTripleChecker+Valid, 911 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.3s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:58,163 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [225 Valid, 794 Invalid, 1121 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [210 Valid, 911 Invalid, 0 Unknown, 0 Unchecked, 2.3s Time] [2024-10-12 18:52:58,164 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1310 states. [2024-10-12 18:52:59,107 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1310 to 1126. [2024-10-12 18:52:59,109 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1126 states, 567 states have (on average 1.3015873015873016) internal successors, (738), 568 states have internal predecessors, (738), 521 states have call successors, (521), 37 states have call predecessors, (521), 37 states have return successors, (520), 520 states have call predecessors, (520), 520 states have call successors, (520) [2024-10-12 18:52:59,112 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1126 states to 1126 states and 1779 transitions. [2024-10-12 18:52:59,114 INFO L78 Accepts]: Start accepts. Automaton has 1126 states and 1779 transitions. Word has length 106 [2024-10-12 18:52:59,114 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:59,114 INFO L471 AbstractCegarLoop]: Abstraction has 1126 states and 1779 transitions. [2024-10-12 18:52:59,115 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 2.55) internal successors, (51), 21 states have internal predecessors, (51), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-10-12 18:52:59,115 INFO L276 IsEmpty]: Start isEmpty. Operand 1126 states and 1779 transitions. [2024-10-12 18:52:59,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2024-10-12 18:52:59,116 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:59,116 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:59,124 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2024-10-12 18:52:59,317 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:59,317 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:59,317 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:59,318 INFO L85 PathProgramCache]: Analyzing trace with hash 951323959, now seen corresponding path program 4 times [2024-10-12 18:52:59,318 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:59,318 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1669555292] [2024-10-12 18:52:59,318 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:59,318 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:59,338 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:52:59,339 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [836825030] [2024-10-12 18:52:59,339 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-10-12 18:52:59,339 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:59,339 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:59,341 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:59,343 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-10-12 18:52:59,418 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-10-12 18:52:59,418 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-12 18:52:59,420 INFO L255 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 77 conjuncts are in the unsatisfiable core [2024-10-12 18:52:59,422 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:53:00,453 INFO L134 CoverageAnalysis]: Checked inductivity of 350 backedges. 56 proven. 48 refuted. 0 times theorem prover too weak. 246 trivial. 0 not checked. [2024-10-12 18:53:00,453 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:53:04,606 INFO L134 CoverageAnalysis]: Checked inductivity of 350 backedges. 50 proven. 45 refuted. 0 times theorem prover too weak. 255 trivial. 0 not checked. [2024-10-12 18:53:04,607 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:53:04,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1669555292] [2024-10-12 18:53:04,607 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:53:04,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [836825030] [2024-10-12 18:53:04,607 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [836825030] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:53:04,607 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 18:53:04,607 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 19] total 39 [2024-10-12 18:53:04,607 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1373431035] [2024-10-12 18:53:04,607 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 18:53:04,608 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 39 states [2024-10-12 18:53:04,608 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:53:04,608 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2024-10-12 18:53:04,609 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=185, Invalid=1297, Unknown=0, NotChecked=0, Total=1482 [2024-10-12 18:53:04,609 INFO L87 Difference]: Start difference. First operand 1126 states and 1779 transitions. Second operand has 39 states, 37 states have (on average 1.9189189189189189) internal successors, (71), 37 states have internal predecessors, (71), 12 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 10 states have call predecessors, (30), 10 states have call successors, (30) [2024-10-12 18:53:12,523 WARN L286 SmtUtils]: Spent 6.14s on a formula simplification that was a NOOP. DAG size: 110 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-10-12 18:53:14,440 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.35s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-12 18:53:19,272 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers []