./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/prodbin-ll_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 61a67961 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/prodbin-ll_unwindbound10.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 b4ff78c7a05ff12ed3c4b9587e1e659860187fd62fb9ac015e2b63b391c38f88 --- Real Ultimate output --- This is Ultimate 0.2.5-wip.fs.cvc5-61a6796-m [2024-10-14 02:35:41,247 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-14 02:35:41,320 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-14 02:35:41,324 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-14 02:35:41,325 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-14 02:35:41,358 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-14 02:35:41,359 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-14 02:35:41,360 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-14 02:35:41,361 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-14 02:35:41,362 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-14 02:35:41,363 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-14 02:35:41,363 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-14 02:35:41,364 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-14 02:35:41,364 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-14 02:35:41,366 INFO L153 SettingsManager]: * Use SBE=true [2024-10-14 02:35:41,366 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-14 02:35:41,366 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-14 02:35:41,367 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-14 02:35:41,367 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-14 02:35:41,367 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-14 02:35:41,370 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-14 02:35:41,371 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-14 02:35:41,371 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-14 02:35:41,371 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-14 02:35:41,371 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-14 02:35:41,372 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-14 02:35:41,372 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-14 02:35:41,372 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-14 02:35:41,372 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-14 02:35:41,373 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-14 02:35:41,373 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-14 02:35:41,373 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-14 02:35:41,373 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-14 02:35:41,374 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-14 02:35:41,374 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-14 02:35:41,374 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-14 02:35:41,374 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-14 02:35:41,375 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-14 02:35:41,375 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-14 02:35:41,376 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-14 02:35:41,376 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-14 02:35:41,377 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-14 02:35:41,377 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 -> b4ff78c7a05ff12ed3c4b9587e1e659860187fd62fb9ac015e2b63b391c38f88 [2024-10-14 02:35:41,646 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-14 02:35:41,672 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-14 02:35:41,676 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-14 02:35:41,678 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-14 02:35:41,678 INFO L274 PluginConnector]: CDTParser initialized [2024-10-14 02:35:41,680 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound10.c [2024-10-14 02:35:43,173 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-14 02:35:43,370 INFO L384 CDTParser]: Found 1 translation units. [2024-10-14 02:35:43,371 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound10.c [2024-10-14 02:35:43,381 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/19e27d1c1/0d88b0265eae4a88b8cbc6c232c65760/FLAG59e1e403a [2024-10-14 02:35:43,393 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/19e27d1c1/0d88b0265eae4a88b8cbc6c232c65760 [2024-10-14 02:35:43,395 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-14 02:35:43,396 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-14 02:35:43,397 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-14 02:35:43,399 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-14 02:35:43,405 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-14 02:35:43,406 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,407 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@247ab7b2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43, skipping insertion in model container [2024-10-14 02:35:43,407 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,430 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-14 02:35:43,566 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/prodbin-ll_unwindbound10.c[1175,1188] [2024-10-14 02:35:43,582 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-14 02:35:43,590 INFO L200 MainTranslator]: Completed pre-run [2024-10-14 02:35:43,628 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/prodbin-ll_unwindbound10.c[1175,1188] [2024-10-14 02:35:43,641 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-14 02:35:43,667 INFO L204 MainTranslator]: Completed translation [2024-10-14 02:35:43,667 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43 WrapperNode [2024-10-14 02:35:43,667 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-14 02:35:43,668 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-14 02:35:43,668 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-14 02:35:43,669 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-14 02:35:43,690 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,699 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,726 INFO L138 Inliner]: procedures = 14, calls = 10, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 49 [2024-10-14 02:35:43,727 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-14 02:35:43,727 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-14 02:35:43,727 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-14 02:35:43,727 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-14 02:35:43,735 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,736 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,737 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,749 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-14 02:35:43,751 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,751 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,753 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,757 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,761 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,761 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,767 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-14 02:35:43,767 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-14 02:35:43,767 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-14 02:35:43,768 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-14 02:35:43,768 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43" (1/1) ... [2024-10-14 02:35:43,774 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-14 02:35:43,786 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:35:43,801 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-14 02:35:43,804 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-14 02:35:43,851 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-14 02:35:43,851 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-14 02:35:43,851 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-14 02:35:43,852 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-14 02:35:43,852 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-14 02:35:43,852 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-14 02:35:43,915 INFO L238 CfgBuilder]: Building ICFG [2024-10-14 02:35:43,917 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-14 02:35:44,078 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-10-14 02:35:44,078 INFO L287 CfgBuilder]: Performing block encoding [2024-10-14 02:35:44,100 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-14 02:35:44,100 INFO L314 CfgBuilder]: Removed 1 assume(true) statements. [2024-10-14 02:35:44,101 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.10 02:35:44 BoogieIcfgContainer [2024-10-14 02:35:44,101 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-14 02:35:44,103 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-14 02:35:44,103 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-14 02:35:44,106 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-14 02:35:44,106 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.10 02:35:43" (1/3) ... [2024-10-14 02:35:44,107 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5070b12a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.10 02:35:44, skipping insertion in model container [2024-10-14 02:35:44,107 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:35:43" (2/3) ... [2024-10-14 02:35:44,108 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5070b12a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.10 02:35:44, skipping insertion in model container [2024-10-14 02:35:44,108 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.10 02:35:44" (3/3) ... [2024-10-14 02:35:44,109 INFO L112 eAbstractionObserver]: Analyzing ICFG prodbin-ll_unwindbound10.c [2024-10-14 02:35:44,122 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-14 02:35:44,123 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-14 02:35:44,176 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-14 02:35:44,182 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;@148a2c27, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-14 02:35:44,182 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-14 02:35:44,187 INFO L276 IsEmpty]: Start isEmpty. Operand has 18 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 14 states have internal predecessors, (20), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-14 02:35:44,195 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-10-14 02:35:44,195 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:35:44,196 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:35:44,196 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:35:44,200 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:35:44,201 INFO L85 PathProgramCache]: Analyzing trace with hash -818250469, now seen corresponding path program 1 times [2024-10-14 02:35:44,209 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:35:44,210 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1826371738] [2024-10-14 02:35:44,210 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:35:44,211 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:35:44,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:35:44,358 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-14 02:35:44,362 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:35:44,362 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1826371738] [2024-10-14 02:35:44,363 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1826371738] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-14 02:35:44,363 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-14 02:35:44,363 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-14 02:35:44,366 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1361667002] [2024-10-14 02:35:44,367 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-14 02:35:44,371 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-14 02:35:44,372 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:35:44,390 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-14 02:35:44,391 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-14 02:35:44,392 INFO L87 Difference]: Start difference. First operand has 18 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 14 states have internal predecessors, (20), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-14 02:35:44,411 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:35:44,412 INFO L93 Difference]: Finished difference Result 34 states and 47 transitions. [2024-10-14 02:35:44,414 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-14 02:35:44,415 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-10-14 02:35:44,415 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:35:44,422 INFO L225 Difference]: With dead ends: 34 [2024-10-14 02:35:44,422 INFO L226 Difference]: Without dead ends: 16 [2024-10-14 02:35:44,424 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 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-14 02:35:44,427 INFO L432 NwaCegarLoop]: 19 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, 19 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-14 02:35:44,428 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 19 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-14 02:35:44,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2024-10-14 02:35:44,454 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2024-10-14 02:35:44,455 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 12 states have (on average 1.3333333333333333) internal successors, (16), 13 states have internal predecessors, (16), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-14 02:35:44,455 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 19 transitions. [2024-10-14 02:35:44,457 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 19 transitions. Word has length 8 [2024-10-14 02:35:44,457 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:35:44,457 INFO L471 AbstractCegarLoop]: Abstraction has 16 states and 19 transitions. [2024-10-14 02:35:44,458 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-14 02:35:44,458 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 19 transitions. [2024-10-14 02:35:44,458 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-10-14 02:35:44,458 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:35:44,459 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:35:44,459 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-14 02:35:44,459 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:35:44,460 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:35:44,460 INFO L85 PathProgramCache]: Analyzing trace with hash -1011676302, now seen corresponding path program 1 times [2024-10-14 02:35:44,460 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:35:44,460 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [781958927] [2024-10-14 02:35:44,461 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:35:44,461 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:35:44,485 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:35:44,600 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-14 02:35:44,601 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:35:44,601 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [781958927] [2024-10-14 02:35:44,601 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [781958927] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-14 02:35:44,601 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-14 02:35:44,601 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-10-14 02:35:44,601 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [874744906] [2024-10-14 02:35:44,601 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-14 02:35:44,602 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-14 02:35:44,603 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:35:44,607 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-14 02:35:44,607 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-14 02:35:44,608 INFO L87 Difference]: Start difference. First operand 16 states and 19 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-14 02:35:44,629 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:35:44,630 INFO L93 Difference]: Finished difference Result 25 states and 28 transitions. [2024-10-14 02:35:44,630 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-14 02:35:44,630 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-10-14 02:35:44,630 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:35:44,631 INFO L225 Difference]: With dead ends: 25 [2024-10-14 02:35:44,631 INFO L226 Difference]: Without dead ends: 18 [2024-10-14 02:35:44,631 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-14 02:35:44,633 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 0 mSDsluCounter, 29 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-14 02:35:44,633 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-14 02:35:44,634 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2024-10-14 02:35:44,637 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2024-10-14 02:35:44,637 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 15 states have internal predecessors, (18), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-14 02:35:44,638 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 21 transitions. [2024-10-14 02:35:44,638 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 21 transitions. Word has length 9 [2024-10-14 02:35:44,638 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:35:44,638 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 21 transitions. [2024-10-14 02:35:44,638 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-14 02:35:44,639 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 21 transitions. [2024-10-14 02:35:44,639 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-10-14 02:35:44,639 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:35:44,639 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:35:44,640 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-14 02:35:44,640 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:35:44,640 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:35:44,641 INFO L85 PathProgramCache]: Analyzing trace with hash -1009888842, now seen corresponding path program 1 times [2024-10-14 02:35:44,641 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:35:44,641 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1574109411] [2024-10-14 02:35:44,641 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:35:44,641 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:35:44,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:35:44,661 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [885067340] [2024-10-14 02:35:44,661 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:35:44,662 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:35:44,662 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:35:44,664 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-14 02:35:44,666 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-14 02:35:44,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:35:44,714 INFO L255 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-14 02:35:44,722 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:35:44,944 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-14 02:35:44,944 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-14 02:35:44,945 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:35:44,945 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1574109411] [2024-10-14 02:35:44,945 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:35:44,946 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [885067340] [2024-10-14 02:35:44,946 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [885067340] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-14 02:35:44,946 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-14 02:35:44,946 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-14 02:35:44,947 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1225101015] [2024-10-14 02:35:44,947 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-14 02:35:44,947 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-14 02:35:44,947 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:35:44,948 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-14 02:35:44,948 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2024-10-14 02:35:44,949 INFO L87 Difference]: Start difference. First operand 18 states and 21 transitions. Second operand has 7 states, 7 states have (on average 1.1428571428571428) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-14 02:35:45,069 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:35:45,070 INFO L93 Difference]: Finished difference Result 33 states and 38 transitions. [2024-10-14 02:35:45,070 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-14 02:35:45,070 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 1.1428571428571428) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-10-14 02:35:45,071 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:35:45,071 INFO L225 Difference]: With dead ends: 33 [2024-10-14 02:35:45,072 INFO L226 Difference]: Without dead ends: 26 [2024-10-14 02:35:45,072 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-10-14 02:35:45,073 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 16 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 46 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-14 02:35:45,074 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 46 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-14 02:35:45,074 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2024-10-14 02:35:45,078 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 24. [2024-10-14 02:35:45,079 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-14 02:35:45,079 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2024-10-14 02:35:45,080 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 9 [2024-10-14 02:35:45,080 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:35:45,080 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2024-10-14 02:35:45,080 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 1.1428571428571428) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-14 02:35:45,080 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2024-10-14 02:35:45,081 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-10-14 02:35:45,081 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:35:45,081 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:35:45,100 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-14 02:35:45,285 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-14 02:35:45,286 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:35:45,287 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:35:45,287 INFO L85 PathProgramCache]: Analyzing trace with hash 1083966870, now seen corresponding path program 1 times [2024-10-14 02:35:45,287 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:35:45,287 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1910466437] [2024-10-14 02:35:45,287 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:35:45,288 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:35:45,309 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:35:45,480 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-14 02:35:45,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:35:45,498 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-14 02:35:45,502 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:35:45,503 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1910466437] [2024-10-14 02:35:45,503 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1910466437] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:35:45,503 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1198621869] [2024-10-14 02:35:45,503 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:35:45,504 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:35:45,504 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:35:45,506 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-14 02:35:45,507 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-14 02:35:45,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:35:45,552 INFO L255 TraceCheckSpWp]: Trace formula consists of 75 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-10-14 02:35:45,554 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:35:45,606 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-14 02:35:45,606 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:35:45,681 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-14 02:35:45,681 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1198621869] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:35:45,681 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-14 02:35:45,682 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-10-14 02:35:45,682 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2137622784] [2024-10-14 02:35:45,682 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-14 02:35:45,683 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-10-14 02:35:45,683 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:35:45,684 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-10-14 02:35:45,684 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-10-14 02:35:45,685 INFO L87 Difference]: Start difference. First operand 24 states and 27 transitions. Second operand has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-14 02:35:45,775 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:35:45,775 INFO L93 Difference]: Finished difference Result 61 states and 71 transitions. [2024-10-14 02:35:45,775 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-14 02:35:45,776 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 19 [2024-10-14 02:35:45,776 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:35:45,777 INFO L225 Difference]: With dead ends: 61 [2024-10-14 02:35:45,777 INFO L226 Difference]: Without dead ends: 54 [2024-10-14 02:35:45,777 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2024-10-14 02:35:45,779 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 25 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-14 02:35:45,780 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 114 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-14 02:35:45,781 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2024-10-14 02:35:45,787 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 50. [2024-10-14 02:35:45,787 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 38 states have (on average 1.2894736842105263) internal successors, (49), 41 states have internal predecessors, (49), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-14 02:35:45,788 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 60 transitions. [2024-10-14 02:35:45,789 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 60 transitions. Word has length 19 [2024-10-14 02:35:45,789 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:35:45,789 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 60 transitions. [2024-10-14 02:35:45,789 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-14 02:35:45,789 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 60 transitions. [2024-10-14 02:35:45,790 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-10-14 02:35:45,790 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:35:45,790 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:35:45,808 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-14 02:35:45,990 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-14 02:35:45,991 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:35:45,991 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:35:45,991 INFO L85 PathProgramCache]: Analyzing trace with hash 1085754330, now seen corresponding path program 1 times [2024-10-14 02:35:45,992 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:35:45,992 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1796552579] [2024-10-14 02:35:45,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:35:45,992 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:35:46,024 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:35:46,028 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [538280977] [2024-10-14 02:35:46,029 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:35:46,029 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:35:46,029 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:35:46,031 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-14 02:35:46,032 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-14 02:35:46,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:35:46,085 INFO L255 TraceCheckSpWp]: Trace formula consists of 75 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-10-14 02:35:46,087 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:35:46,469 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-14 02:35:46,470 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:35:49,220 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-14 02:35:49,220 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:35:49,220 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1796552579] [2024-10-14 02:35:49,221 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:35:49,221 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [538280977] [2024-10-14 02:35:49,221 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [538280977] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:35:49,221 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-14 02:35:49,221 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 15 [2024-10-14 02:35:49,221 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [342419279] [2024-10-14 02:35:49,222 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-14 02:35:49,222 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-10-14 02:35:49,222 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:35:49,223 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-10-14 02:35:49,223 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2024-10-14 02:35:49,223 INFO L87 Difference]: Start difference. First operand 50 states and 60 transitions. Second operand has 15 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 14 states have internal predecessors, (28), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-14 02:35:49,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:35:49,946 INFO L93 Difference]: Finished difference Result 83 states and 98 transitions. [2024-10-14 02:35:49,948 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-10-14 02:35:49,948 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 14 states have internal predecessors, (28), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 19 [2024-10-14 02:35:49,949 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:35:49,951 INFO L225 Difference]: With dead ends: 83 [2024-10-14 02:35:49,952 INFO L226 Difference]: Without dead ends: 81 [2024-10-14 02:35:49,953 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=64, Invalid=242, Unknown=0, NotChecked=0, Total=306 [2024-10-14 02:35:49,954 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 13 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 116 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 123 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 116 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-10-14 02:35:49,956 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 89 Invalid, 123 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 116 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-10-14 02:35:49,956 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2024-10-14 02:35:49,971 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 79. [2024-10-14 02:35:49,972 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 61 states have (on average 1.2295081967213115) internal successors, (75), 66 states have internal predecessors, (75), 10 states have call successors, (10), 7 states have call predecessors, (10), 7 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-14 02:35:49,973 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 92 transitions. [2024-10-14 02:35:49,973 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 92 transitions. Word has length 19 [2024-10-14 02:35:49,974 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:35:49,974 INFO L471 AbstractCegarLoop]: Abstraction has 79 states and 92 transitions. [2024-10-14 02:35:49,974 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 14 states have internal predecessors, (28), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-14 02:35:49,974 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 92 transitions. [2024-10-14 02:35:49,974 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-10-14 02:35:49,974 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:35:49,975 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:35:49,993 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-14 02:35:50,175 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-14 02:35:50,175 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:35:50,176 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:35:50,176 INFO L85 PathProgramCache]: Analyzing trace with hash 276407704, now seen corresponding path program 1 times [2024-10-14 02:35:50,176 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:35:50,176 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2076323242] [2024-10-14 02:35:50,176 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:35:50,176 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:35:50,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:35:50,192 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1046876883] [2024-10-14 02:35:50,192 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:35:50,192 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:35:50,193 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:35:50,194 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-14 02:35:50,198 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-14 02:35:50,239 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:35:50,240 INFO L255 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-14 02:35:50,242 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:35:50,759 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-14 02:35:50,760 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:35:53,983 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:35:53,983 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2076323242] [2024-10-14 02:35:53,984 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:35:53,984 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1046876883] [2024-10-14 02:35:53,984 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1046876883] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:35:53,984 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-14 02:35:53,984 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2024-10-14 02:35:53,984 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1605095627] [2024-10-14 02:35:53,984 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-14 02:35:53,984 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-10-14 02:35:53,985 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:35:53,985 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-14 02:35:53,986 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=191, Unknown=0, NotChecked=0, Total=240 [2024-10-14 02:35:53,986 INFO L87 Difference]: Start difference. First operand 79 states and 92 transitions. Second operand has 12 states, 12 states have (on average 1.3333333333333333) internal successors, (16), 10 states have internal predecessors, (16), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-14 02:35:55,300 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:35:55,301 INFO L93 Difference]: Finished difference Result 90 states and 102 transitions. [2024-10-14 02:35:55,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-10-14 02:35:55,301 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 1.3333333333333333) internal successors, (16), 10 states have internal predecessors, (16), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 19 [2024-10-14 02:35:55,302 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:35:55,303 INFO L225 Difference]: With dead ends: 90 [2024-10-14 02:35:55,303 INFO L226 Difference]: Without dead ends: 81 [2024-10-14 02:35:55,303 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 12 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=55, Invalid=217, Unknown=0, NotChecked=0, Total=272 [2024-10-14 02:35:55,304 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 17 mSDsluCounter, 65 mSDsCounter, 0 mSdLazyCounter, 137 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 141 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 137 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2024-10-14 02:35:55,304 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 77 Invalid, 141 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 137 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2024-10-14 02:35:55,305 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2024-10-14 02:35:55,325 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 81. [2024-10-14 02:35:55,327 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 63 states have (on average 1.1904761904761905) internal successors, (75), 67 states have internal predecessors, (75), 10 states have call successors, (10), 8 states have call predecessors, (10), 7 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-14 02:35:55,329 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 92 transitions. [2024-10-14 02:35:55,329 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 92 transitions. Word has length 19 [2024-10-14 02:35:55,330 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:35:55,330 INFO L471 AbstractCegarLoop]: Abstraction has 81 states and 92 transitions. [2024-10-14 02:35:55,330 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 1.3333333333333333) internal successors, (16), 10 states have internal predecessors, (16), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-14 02:35:55,330 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 92 transitions. [2024-10-14 02:35:55,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-10-14 02:35:55,331 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:35:55,331 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:35:55,348 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-10-14 02:35:55,531 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-14 02:35:55,531 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:35:55,532 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:35:55,532 INFO L85 PathProgramCache]: Analyzing trace with hash -2037077519, now seen corresponding path program 1 times [2024-10-14 02:35:55,532 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:35:55,532 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [250487736] [2024-10-14 02:35:55,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:35:55,532 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:35:55,562 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:35:55,565 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [787757902] [2024-10-14 02:35:55,567 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:35:55,568 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:35:55,568 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:35:55,570 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-14 02:35:55,571 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-14 02:35:55,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:35:55,613 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-14 02:35:55,615 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:35:55,685 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-14 02:35:55,686 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:35:55,760 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-14 02:35:55,760 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:35:55,760 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [250487736] [2024-10-14 02:35:55,760 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:35:55,760 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [787757902] [2024-10-14 02:35:55,760 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [787757902] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:35:55,760 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-14 02:35:55,760 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 11 [2024-10-14 02:35:55,761 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [250442767] [2024-10-14 02:35:55,761 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-14 02:35:55,761 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-10-14 02:35:55,761 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:35:55,762 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-10-14 02:35:55,762 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-10-14 02:35:55,762 INFO L87 Difference]: Start difference. First operand 81 states and 92 transitions. Second operand has 11 states, 10 states have (on average 2.3) internal successors, (23), 8 states have internal predecessors, (23), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2024-10-14 02:35:55,862 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:35:55,863 INFO L93 Difference]: Finished difference Result 93 states and 103 transitions. [2024-10-14 02:35:55,863 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-14 02:35:55,863 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.3) internal successors, (23), 8 states have internal predecessors, (23), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2024-10-14 02:35:55,864 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:35:55,864 INFO L225 Difference]: With dead ends: 93 [2024-10-14 02:35:55,864 INFO L226 Difference]: Without dead ends: 78 [2024-10-14 02:35:55,865 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2024-10-14 02:35:55,865 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 7 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 78 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 79 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 78 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-14 02:35:55,866 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 73 Invalid, 79 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 78 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-14 02:35:55,866 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2024-10-14 02:35:55,881 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 77. [2024-10-14 02:35:55,882 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 61 states have (on average 1.1475409836065573) internal successors, (70), 64 states have internal predecessors, (70), 8 states have call successors, (8), 7 states have call predecessors, (8), 7 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-14 02:35:55,885 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 85 transitions. [2024-10-14 02:35:55,886 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 85 transitions. Word has length 25 [2024-10-14 02:35:55,886 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:35:55,887 INFO L471 AbstractCegarLoop]: Abstraction has 77 states and 85 transitions. [2024-10-14 02:35:55,887 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.3) internal successors, (23), 8 states have internal predecessors, (23), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2024-10-14 02:35:55,887 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 85 transitions. [2024-10-14 02:35:55,891 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-10-14 02:35:55,891 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:35:55,891 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-10-14 02:35:55,910 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-14 02:35:56,091 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-14 02:35:56,092 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:35:56,093 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:35:56,093 INFO L85 PathProgramCache]: Analyzing trace with hash 1530857210, now seen corresponding path program 2 times [2024-10-14 02:35:56,093 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:35:56,093 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [541469665] [2024-10-14 02:35:56,093 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:35:56,093 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:35:56,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:35:56,112 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1195250477] [2024-10-14 02:35:56,112 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-14 02:35:56,112 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:35:56,113 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:35:56,114 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-14 02:35:56,119 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-14 02:35:56,173 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-14 02:35:56,173 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-14 02:35:56,174 INFO L255 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-10-14 02:35:56,176 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:35:57,454 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 13 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-14 02:35:57,454 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:35:59,649 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 13 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-14 02:35:59,649 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:35:59,649 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [541469665] [2024-10-14 02:35:59,649 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:35:59,650 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1195250477] [2024-10-14 02:35:59,650 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1195250477] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:35:59,650 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-14 02:35:59,650 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 21 [2024-10-14 02:35:59,650 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [759989561] [2024-10-14 02:35:59,650 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-14 02:35:59,650 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-10-14 02:35:59,651 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:35:59,651 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-14 02:35:59,652 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=331, Unknown=0, NotChecked=0, Total=420 [2024-10-14 02:35:59,652 INFO L87 Difference]: Start difference. First operand 77 states and 85 transitions. Second operand has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 20 states have internal predecessors, (41), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-14 02:36:02,017 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:36:02,017 INFO L93 Difference]: Finished difference Result 112 states and 129 transitions. [2024-10-14 02:36:02,018 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-14 02:36:02,018 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 20 states have internal predecessors, (41), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 29 [2024-10-14 02:36:02,018 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:36:02,019 INFO L225 Difference]: With dead ends: 112 [2024-10-14 02:36:02,019 INFO L226 Difference]: Without dead ends: 110 [2024-10-14 02:36:02,020 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 34 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 171 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=182, Invalid=574, Unknown=0, NotChecked=0, Total=756 [2024-10-14 02:36:02,021 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 34 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 185 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 204 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 185 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-10-14 02:36:02,021 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 112 Invalid, 204 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 185 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-10-14 02:36:02,022 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2024-10-14 02:36:02,037 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 108. [2024-10-14 02:36:02,037 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 87 states have (on average 1.160919540229885) internal successors, (101), 90 states have internal predecessors, (101), 12 states have call successors, (12), 8 states have call predecessors, (12), 8 states have return successors, (11), 9 states have call predecessors, (11), 11 states have call successors, (11) [2024-10-14 02:36:02,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 124 transitions. [2024-10-14 02:36:02,038 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 124 transitions. Word has length 29 [2024-10-14 02:36:02,039 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:36:02,039 INFO L471 AbstractCegarLoop]: Abstraction has 108 states and 124 transitions. [2024-10-14 02:36:02,039 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 20 states have internal predecessors, (41), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-14 02:36:02,039 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 124 transitions. [2024-10-14 02:36:02,040 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-10-14 02:36:02,041 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:36:02,041 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1] [2024-10-14 02:36:02,054 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-10-14 02:36:02,244 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-14 02:36:02,245 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:36:02,245 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:36:02,245 INFO L85 PathProgramCache]: Analyzing trace with hash 2036959006, now seen corresponding path program 1 times [2024-10-14 02:36:02,245 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:36:02,245 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [13406614] [2024-10-14 02:36:02,245 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:36:02,246 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:36:02,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:36:02,289 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [432353340] [2024-10-14 02:36:02,290 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:36:02,290 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:36:02,290 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:36:02,292 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-14 02:36:02,294 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-14 02:36:02,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:36:02,348 INFO L255 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-10-14 02:36:02,350 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:36:02,937 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 11 proven. 28 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-14 02:36:02,937 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:36:03,454 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:36:03,455 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [13406614] [2024-10-14 02:36:03,455 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:36:03,455 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [432353340] [2024-10-14 02:36:03,455 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [432353340] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:36:03,455 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-14 02:36:03,455 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2024-10-14 02:36:03,456 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [122383725] [2024-10-14 02:36:03,456 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-14 02:36:03,456 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-10-14 02:36:03,456 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:36:03,457 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-10-14 02:36:03,457 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2024-10-14 02:36:03,457 INFO L87 Difference]: Start difference. First operand 108 states and 124 transitions. Second operand has 14 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 13 states have internal predecessors, (29), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-14 02:36:03,885 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:36:03,885 INFO L93 Difference]: Finished difference Result 118 states and 135 transitions. [2024-10-14 02:36:03,886 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-14 02:36:03,886 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 13 states have internal predecessors, (29), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 39 [2024-10-14 02:36:03,886 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:36:03,888 INFO L225 Difference]: With dead ends: 118 [2024-10-14 02:36:03,888 INFO L226 Difference]: Without dead ends: 116 [2024-10-14 02:36:03,889 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 50 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=62, Invalid=318, Unknown=0, NotChecked=0, Total=380 [2024-10-14 02:36:03,889 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 6 mSDsluCounter, 183 mSDsCounter, 0 mSdLazyCounter, 308 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 203 SdHoareTripleChecker+Invalid, 308 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 308 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-10-14 02:36:03,890 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 203 Invalid, 308 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 308 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-10-14 02:36:03,890 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2024-10-14 02:36:03,914 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 113. [2024-10-14 02:36:03,917 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 90 states have (on average 1.1555555555555554) internal successors, (104), 94 states have internal predecessors, (104), 13 states have call successors, (13), 9 states have call predecessors, (13), 9 states have return successors, (12), 9 states have call predecessors, (12), 12 states have call successors, (12) [2024-10-14 02:36:03,917 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 129 transitions. [2024-10-14 02:36:03,917 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 129 transitions. Word has length 39 [2024-10-14 02:36:03,918 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:36:03,918 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 129 transitions. [2024-10-14 02:36:03,918 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 13 states have internal predecessors, (29), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-14 02:36:03,918 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 129 transitions. [2024-10-14 02:36:03,919 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-10-14 02:36:03,920 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:36:03,920 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:36:03,932 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-10-14 02:36:04,120 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:36:04,121 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:36:04,121 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:36:04,121 INFO L85 PathProgramCache]: Analyzing trace with hash 1536935426, now seen corresponding path program 2 times [2024-10-14 02:36:04,121 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:36:04,121 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1564430479] [2024-10-14 02:36:04,121 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:36:04,121 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:36:04,136 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:36:04,362 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-14 02:36:04,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:36:04,368 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-10-14 02:36:04,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:36:04,376 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-10-14 02:36:04,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:36:04,382 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-10-14 02:36:04,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:36:04,388 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 8 proven. 44 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-14 02:36:04,388 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:36:04,388 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1564430479] [2024-10-14 02:36:04,389 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1564430479] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:36:04,389 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1045112630] [2024-10-14 02:36:04,389 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-14 02:36:04,390 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:36:04,390 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:36:04,391 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-14 02:36:04,393 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-14 02:36:04,444 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-14 02:36:04,445 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-14 02:36:04,448 INFO L255 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-14 02:36:04,450 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:36:04,514 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 8 proven. 68 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-14 02:36:04,514 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:36:04,608 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 8 proven. 44 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-14 02:36:04,608 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1045112630] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:36:04,608 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-14 02:36:04,609 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-10-14 02:36:04,609 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1931752282] [2024-10-14 02:36:04,609 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-14 02:36:04,609 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-14 02:36:04,609 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:36:04,610 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-14 02:36:04,610 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=144, Unknown=0, NotChecked=0, Total=240 [2024-10-14 02:36:04,610 INFO L87 Difference]: Start difference. First operand 113 states and 129 transitions. Second operand has 16 states, 16 states have (on average 4.5625) internal successors, (73), 16 states have internal predecessors, (73), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-10-14 02:36:04,794 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:36:04,794 INFO L93 Difference]: Finished difference Result 293 states and 338 transitions. [2024-10-14 02:36:04,794 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-10-14 02:36:04,795 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 4.5625) internal successors, (73), 16 states have internal predecessors, (73), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) Word has length 49 [2024-10-14 02:36:04,795 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:36:04,798 INFO L225 Difference]: With dead ends: 293 [2024-10-14 02:36:04,799 INFO L226 Difference]: Without dead ends: 286 [2024-10-14 02:36:04,800 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 98 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=196, Invalid=356, Unknown=0, NotChecked=0, Total=552 [2024-10-14 02:36:04,800 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 68 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 61 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-14 02:36:04,800 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [68 Valid, 151 Invalid, 61 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-14 02:36:04,801 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 286 states. [2024-10-14 02:36:04,840 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 286 to 276. [2024-10-14 02:36:04,841 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 276 states, 219 states have (on average 1.1369863013698631) internal successors, (249), 228 states have internal predecessors, (249), 30 states have call successors, (30), 26 states have call predecessors, (30), 26 states have return successors, (29), 21 states have call predecessors, (29), 29 states have call successors, (29) [2024-10-14 02:36:04,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 276 states to 276 states and 308 transitions. [2024-10-14 02:36:04,843 INFO L78 Accepts]: Start accepts. Automaton has 276 states and 308 transitions. Word has length 49 [2024-10-14 02:36:04,843 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:36:04,843 INFO L471 AbstractCegarLoop]: Abstraction has 276 states and 308 transitions. [2024-10-14 02:36:04,843 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 4.5625) internal successors, (73), 16 states have internal predecessors, (73), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-10-14 02:36:04,843 INFO L276 IsEmpty]: Start isEmpty. Operand 276 states and 308 transitions. [2024-10-14 02:36:04,845 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-10-14 02:36:04,847 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:36:04,848 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1] [2024-10-14 02:36:04,864 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-14 02:36:05,051 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,SelfDestructingSolverStorable9 [2024-10-14 02:36:05,052 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:36:05,052 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:36:05,052 INFO L85 PathProgramCache]: Analyzing trace with hash -1264768446, now seen corresponding path program 2 times [2024-10-14 02:36:05,052 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:36:05,052 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [561873668] [2024-10-14 02:36:05,052 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:36:05,052 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:36:05,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:36:05,103 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1256035646] [2024-10-14 02:36:05,103 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-14 02:36:05,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:36:05,104 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:36:05,105 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-14 02:36:05,107 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-14 02:36:05,157 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-14 02:36:05,158 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-14 02:36:05,165 INFO L255 TraceCheckSpWp]: Trace formula consists of 140 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-10-14 02:36:05,167 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:36:06,159 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 10 proven. 55 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-14 02:36:06,159 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:36:32,516 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 37 proven. 25 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-10-14 02:36:32,516 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:36:32,517 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [561873668] [2024-10-14 02:36:32,517 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:36:32,517 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1256035646] [2024-10-14 02:36:32,517 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1256035646] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:36:32,517 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-14 02:36:32,517 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 24 [2024-10-14 02:36:32,517 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [285643071] [2024-10-14 02:36:32,517 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-14 02:36:32,518 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-10-14 02:36:32,518 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:36:32,518 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-10-14 02:36:32,519 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=456, Unknown=1, NotChecked=0, Total=552 [2024-10-14 02:36:32,519 INFO L87 Difference]: Start difference. First operand 276 states and 308 transitions. Second operand has 24 states, 24 states have (on average 2.375) internal successors, (57), 22 states have internal predecessors, (57), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 7 states have call successors, (8) [2024-10-14 02:36:49,216 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.51s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-14 02:37:04,403 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:37:04,403 INFO L93 Difference]: Finished difference Result 397 states and 451 transitions. [2024-10-14 02:37:04,403 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-10-14 02:37:04,404 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 2.375) internal successors, (57), 22 states have internal predecessors, (57), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 7 states have call successors, (8) Word has length 49 [2024-10-14 02:37:04,404 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:37:04,406 INFO L225 Difference]: With dead ends: 397 [2024-10-14 02:37:04,406 INFO L226 Difference]: Without dead ends: 395 [2024-10-14 02:37:04,407 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 76 SyntacticMatches, 2 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 258 ImplicationChecksByTransitivity, 43.7s TimeCoverageRelationStatistics Valid=251, Invalid=1080, Unknown=1, NotChecked=0, Total=1332 [2024-10-14 02:37:04,408 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 27 mSDsluCounter, 208 mSDsCounter, 0 mSdLazyCounter, 336 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 362 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 336 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.6s IncrementalHoareTripleChecker+Time [2024-10-14 02:37:04,408 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 229 Invalid, 362 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 336 Invalid, 0 Unknown, 0 Unchecked, 8.6s Time] [2024-10-14 02:37:04,409 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 395 states. [2024-10-14 02:37:04,445 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 395 to 391. [2024-10-14 02:37:04,446 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 391 states, 312 states have (on average 1.1378205128205128) internal successors, (355), 322 states have internal predecessors, (355), 43 states have call successors, (43), 35 states have call predecessors, (43), 35 states have return successors, (42), 33 states have call predecessors, (42), 42 states have call successors, (42) [2024-10-14 02:37:04,448 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 391 states to 391 states and 440 transitions. [2024-10-14 02:37:04,448 INFO L78 Accepts]: Start accepts. Automaton has 391 states and 440 transitions. Word has length 49 [2024-10-14 02:37:04,449 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:37:04,449 INFO L471 AbstractCegarLoop]: Abstraction has 391 states and 440 transitions. [2024-10-14 02:37:04,449 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 2.375) internal successors, (57), 22 states have internal predecessors, (57), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 7 states have call successors, (8) [2024-10-14 02:37:04,449 INFO L276 IsEmpty]: Start isEmpty. Operand 391 states and 440 transitions. [2024-10-14 02:37:04,450 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-10-14 02:37:04,450 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:37:04,451 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1] [2024-10-14 02:37:04,467 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-14 02:37:04,654 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:37:04,654 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:37:04,655 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:37:04,655 INFO L85 PathProgramCache]: Analyzing trace with hash -1774241536, now seen corresponding path program 3 times [2024-10-14 02:37:04,655 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:37:04,655 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1914041260] [2024-10-14 02:37:04,655 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:37:04,655 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:37:04,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:37:04,682 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1111310212] [2024-10-14 02:37:04,682 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-14 02:37:04,682 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:37:04,682 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:37:04,687 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-14 02:37:04,688 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-14 02:37:04,744 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-10-14 02:37:04,744 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-14 02:37:04,746 INFO L255 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-14 02:37:04,748 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:37:05,470 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 16 proven. 49 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-14 02:37:05,470 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:37:05,804 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:37:05,804 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1914041260] [2024-10-14 02:37:05,804 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:37:05,804 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1111310212] [2024-10-14 02:37:05,804 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1111310212] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:37:05,804 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-14 02:37:05,804 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2024-10-14 02:37:05,805 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [130024003] [2024-10-14 02:37:05,805 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-14 02:37:05,805 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-10-14 02:37:05,805 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:37:05,806 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-10-14 02:37:05,806 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=412, Unknown=0, NotChecked=0, Total=506 [2024-10-14 02:37:05,806 INFO L87 Difference]: Start difference. First operand 391 states and 440 transitions. Second operand has 19 states, 19 states have (on average 1.7894736842105263) internal successors, (34), 18 states have internal predecessors, (34), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-14 02:37:06,740 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:37:06,740 INFO L93 Difference]: Finished difference Result 393 states and 441 transitions. [2024-10-14 02:37:06,740 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-10-14 02:37:06,740 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 1.7894736842105263) internal successors, (34), 18 states have internal predecessors, (34), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 49 [2024-10-14 02:37:06,740 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:37:06,742 INFO L225 Difference]: With dead ends: 393 [2024-10-14 02:37:06,742 INFO L226 Difference]: Without dead ends: 391 [2024-10-14 02:37:06,745 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 35 SyntacticMatches, 2 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 311 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=245, Invalid=877, Unknown=0, NotChecked=0, Total=1122 [2024-10-14 02:37:06,746 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 33 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 199 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 210 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 199 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-14 02:37:06,746 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 115 Invalid, 210 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 199 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-14 02:37:06,747 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 391 states. [2024-10-14 02:37:06,787 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 391 to 391. [2024-10-14 02:37:06,788 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 391 states, 312 states have (on average 1.1346153846153846) internal successors, (354), 322 states have internal predecessors, (354), 43 states have call successors, (43), 35 states have call predecessors, (43), 35 states have return successors, (42), 33 states have call predecessors, (42), 42 states have call successors, (42) [2024-10-14 02:37:06,789 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 391 states to 391 states and 439 transitions. [2024-10-14 02:37:06,790 INFO L78 Accepts]: Start accepts. Automaton has 391 states and 439 transitions. Word has length 49 [2024-10-14 02:37:06,790 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:37:06,790 INFO L471 AbstractCegarLoop]: Abstraction has 391 states and 439 transitions. [2024-10-14 02:37:06,791 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 1.7894736842105263) internal successors, (34), 18 states have internal predecessors, (34), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-14 02:37:06,791 INFO L276 IsEmpty]: Start isEmpty. Operand 391 states and 439 transitions. [2024-10-14 02:37:06,792 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-10-14 02:37:06,792 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:37:06,792 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1] [2024-10-14 02:37:06,805 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-14 02:37:06,994 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,SelfDestructingSolverStorable11 [2024-10-14 02:37:06,994 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:37:06,995 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:37:06,995 INFO L85 PathProgramCache]: Analyzing trace with hash -28215198, now seen corresponding path program 4 times [2024-10-14 02:37:06,995 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:37:06,995 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1108296661] [2024-10-14 02:37:06,995 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:37:06,995 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:37:07,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:37:07,016 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1513966443] [2024-10-14 02:37:07,016 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-10-14 02:37:07,016 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:37:07,016 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:37:07,018 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-14 02:37:07,026 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-14 02:37:07,085 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-10-14 02:37:07,085 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-14 02:37:07,086 INFO L255 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 53 conjuncts are in the unsatisfiable core [2024-10-14 02:37:07,089 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:37:13,401 INFO L134 CoverageAnalysis]: Checked inductivity of 125 backedges. 23 proven. 80 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2024-10-14 02:37:13,402 INFO L311 TraceCheckSpWp]: Computing backward predicates...