./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/hard-ll_valuebound2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 4a390ef5 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/hard-ll_valuebound2.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 9851f41ad4fb2d0ff96507e8e48f0d2886a8de6481eed845b23377b9fa492b45 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-4a390ef-m [2024-10-24 00:19:48,436 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-24 00:19:48,504 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-24 00:19:48,508 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-24 00:19:48,508 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-24 00:19:48,541 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-24 00:19:48,541 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-24 00:19:48,541 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-24 00:19:48,542 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-24 00:19:48,542 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-24 00:19:48,543 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-24 00:19:48,543 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-24 00:19:48,545 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-24 00:19:48,546 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-24 00:19:48,547 INFO L153 SettingsManager]: * Use SBE=true [2024-10-24 00:19:48,548 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-24 00:19:48,548 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-24 00:19:48,548 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-24 00:19:48,549 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-24 00:19:48,549 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-24 00:19:48,549 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-24 00:19:48,553 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-24 00:19:48,553 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-24 00:19:48,553 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-24 00:19:48,553 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-24 00:19:48,554 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-24 00:19:48,554 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-24 00:19:48,554 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-24 00:19:48,554 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-24 00:19:48,555 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-24 00:19:48,555 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-24 00:19:48,555 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-24 00:19:48,555 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-24 00:19:48,555 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-24 00:19:48,556 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-24 00:19:48,556 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-24 00:19:48,556 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-24 00:19:48,556 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-24 00:19:48,557 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-24 00:19:48,557 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-24 00:19:48,557 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-24 00:19:48,558 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-24 00:19:48,558 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 -> 9851f41ad4fb2d0ff96507e8e48f0d2886a8de6481eed845b23377b9fa492b45 [2024-10-24 00:19:48,832 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-24 00:19:48,860 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-24 00:19:48,863 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-24 00:19:48,864 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-24 00:19:48,865 INFO L274 PluginConnector]: CDTParser initialized [2024-10-24 00:19:48,866 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard-ll_valuebound2.c [2024-10-24 00:19:50,357 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-24 00:19:50,572 INFO L384 CDTParser]: Found 1 translation units. [2024-10-24 00:19:50,572 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard-ll_valuebound2.c [2024-10-24 00:19:50,584 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/881d36d2b/1004d8a7e8f143919c9ed448efed06c9/FLAGff8e3e318 [2024-10-24 00:19:50,931 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/881d36d2b/1004d8a7e8f143919c9ed448efed06c9 [2024-10-24 00:19:50,934 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-24 00:19:50,936 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-24 00:19:50,940 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-24 00:19:50,940 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-24 00:19:50,946 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-24 00:19:50,947 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.10 12:19:50" (1/1) ... [2024-10-24 00:19:50,949 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@20405406 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:50, skipping insertion in model container [2024-10-24 00:19:50,950 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.10 12:19:50" (1/1) ... [2024-10-24 00:19:50,973 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-24 00:19:51,168 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/hard-ll_valuebound2.c[538,551] [2024-10-24 00:19:51,221 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-24 00:19:51,236 INFO L200 MainTranslator]: Completed pre-run [2024-10-24 00:19:51,276 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/hard-ll_valuebound2.c[538,551] [2024-10-24 00:19:51,303 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-24 00:19:51,323 INFO L204 MainTranslator]: Completed translation [2024-10-24 00:19:51,324 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51 WrapperNode [2024-10-24 00:19:51,324 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-24 00:19:51,325 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-24 00:19:51,326 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-24 00:19:51,326 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-24 00:19:51,332 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51" (1/1) ... [2024-10-24 00:19:51,339 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51" (1/1) ... [2024-10-24 00:19:51,357 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 56 [2024-10-24 00:19:51,359 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-24 00:19:51,360 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-24 00:19:51,360 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-24 00:19:51,360 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-24 00:19:51,371 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51" (1/1) ... [2024-10-24 00:19:51,371 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51" (1/1) ... [2024-10-24 00:19:51,377 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51" (1/1) ... [2024-10-24 00:19:51,398 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-24 00:19:51,399 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51" (1/1) ... [2024-10-24 00:19:51,399 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51" (1/1) ... [2024-10-24 00:19:51,403 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51" (1/1) ... [2024-10-24 00:19:51,406 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51" (1/1) ... [2024-10-24 00:19:51,407 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51" (1/1) ... [2024-10-24 00:19:51,408 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51" (1/1) ... [2024-10-24 00:19:51,410 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-24 00:19:51,411 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-24 00:19:51,411 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-24 00:19:51,411 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-24 00:19:51,412 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51" (1/1) ... [2024-10-24 00:19:51,421 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-24 00:19:51,431 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:19:51,448 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-24 00:19:51,453 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-24 00:19:51,499 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-24 00:19:51,500 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-10-24 00:19:51,500 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-10-24 00:19:51,500 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-24 00:19:51,500 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-24 00:19:51,501 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-24 00:19:51,501 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-24 00:19:51,501 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-24 00:19:51,555 INFO L238 CfgBuilder]: Building ICFG [2024-10-24 00:19:51,557 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-24 00:19:51,717 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-10-24 00:19:51,717 INFO L287 CfgBuilder]: Performing block encoding [2024-10-24 00:19:51,742 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-24 00:19:51,743 INFO L314 CfgBuilder]: Removed 2 assume(true) statements. [2024-10-24 00:19:51,743 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 12:19:51 BoogieIcfgContainer [2024-10-24 00:19:51,743 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-24 00:19:51,745 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-24 00:19:51,746 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-24 00:19:51,748 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-24 00:19:51,748 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.10 12:19:50" (1/3) ... [2024-10-24 00:19:51,749 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@58a02731 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.10 12:19:51, skipping insertion in model container [2024-10-24 00:19:51,749 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:19:51" (2/3) ... [2024-10-24 00:19:51,750 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@58a02731 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.10 12:19:51, skipping insertion in model container [2024-10-24 00:19:51,750 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 12:19:51" (3/3) ... [2024-10-24 00:19:51,751 INFO L112 eAbstractionObserver]: Analyzing ICFG hard-ll_valuebound2.c [2024-10-24 00:19:51,766 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-24 00:19:51,766 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-24 00:19:51,817 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-24 00:19:51,823 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;@7cf501e0, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-24 00:19:51,823 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-24 00:19:51,828 INFO L276 IsEmpty]: Start isEmpty. Operand has 30 states, 16 states have (on average 1.625) internal successors, (26), 17 states have internal predecessors, (26), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-10-24 00:19:51,835 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-10-24 00:19:51,835 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:19:51,836 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:19:51,836 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:19:51,842 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:19:51,842 INFO L85 PathProgramCache]: Analyzing trace with hash 760957734, now seen corresponding path program 1 times [2024-10-24 00:19:51,851 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:19:51,852 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1403581809] [2024-10-24 00:19:51,853 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:19:51,853 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:19:51,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:52,044 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:19:52,049 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:52,059 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:19:52,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:52,071 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:19:52,074 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:52,083 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-10-24 00:19:52,083 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:19:52,084 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1403581809] [2024-10-24 00:19:52,084 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1403581809] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:19:52,084 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:19:52,085 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-24 00:19:52,087 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2056605268] [2024-10-24 00:19:52,088 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:19:52,091 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-24 00:19:52,091 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:19:52,110 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-24 00:19:52,111 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-24 00:19:52,113 INFO L87 Difference]: Start difference. First operand has 30 states, 16 states have (on average 1.625) internal successors, (26), 17 states have internal predecessors, (26), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-24 00:19:52,136 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:19:52,136 INFO L93 Difference]: Finished difference Result 58 states and 99 transitions. [2024-10-24 00:19:52,138 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-24 00:19:52,139 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2024-10-24 00:19:52,139 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:19:52,145 INFO L225 Difference]: With dead ends: 58 [2024-10-24 00:19:52,146 INFO L226 Difference]: Without dead ends: 28 [2024-10-24 00:19:52,149 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 11 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-24 00:19:52,153 INFO L432 NwaCegarLoop]: 38 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, 38 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-24 00:19:52,154 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 38 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:19:52,171 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2024-10-24 00:19:52,194 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2024-10-24 00:19:52,196 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 16 states have internal predecessors, (19), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-10-24 00:19:52,198 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 38 transitions. [2024-10-24 00:19:52,199 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 38 transitions. Word has length 23 [2024-10-24 00:19:52,200 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:19:52,200 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 38 transitions. [2024-10-24 00:19:52,202 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-24 00:19:52,202 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 38 transitions. [2024-10-24 00:19:52,203 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-10-24 00:19:52,204 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:19:52,204 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:19:52,204 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-24 00:19:52,205 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:19:52,206 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:19:52,209 INFO L85 PathProgramCache]: Analyzing trace with hash -387749596, now seen corresponding path program 1 times [2024-10-24 00:19:52,209 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:19:52,210 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [64284987] [2024-10-24 00:19:52,210 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:19:52,210 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:19:52,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:52,407 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:19:52,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:52,416 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:19:52,421 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:52,432 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:19:52,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:52,443 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-10-24 00:19:52,447 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:19:52,447 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [64284987] [2024-10-24 00:19:52,448 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [64284987] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:19:52,448 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:19:52,448 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 00:19:52,448 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [997550675] [2024-10-24 00:19:52,448 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:19:52,450 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:19:52,450 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:19:52,451 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:19:52,451 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:19:52,457 INFO L87 Difference]: Start difference. First operand 28 states and 38 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-10-24 00:19:52,537 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:19:52,538 INFO L93 Difference]: Finished difference Result 41 states and 55 transitions. [2024-10-24 00:19:52,538 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:19:52,539 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 23 [2024-10-24 00:19:52,539 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:19:52,540 INFO L225 Difference]: With dead ends: 41 [2024-10-24 00:19:52,540 INFO L226 Difference]: Without dead ends: 39 [2024-10-24 00:19:52,541 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:19:52,542 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 9 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:19:52,543 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 119 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:19:52,544 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2024-10-24 00:19:52,556 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 32. [2024-10-24 00:19:52,556 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-10-24 00:19:52,558 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2024-10-24 00:19:52,558 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 23 [2024-10-24 00:19:52,558 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:19:52,559 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2024-10-24 00:19:52,559 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-10-24 00:19:52,559 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2024-10-24 00:19:52,560 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-10-24 00:19:52,560 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:19:52,560 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:19:52,560 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-24 00:19:52,561 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:19:52,561 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:19:52,561 INFO L85 PathProgramCache]: Analyzing trace with hash -1391236353, now seen corresponding path program 1 times [2024-10-24 00:19:52,562 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:19:52,562 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1308022591] [2024-10-24 00:19:52,562 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:19:52,562 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:19:52,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:52,694 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:19:52,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:52,702 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:19:52,706 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:52,711 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:19:52,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:52,719 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-24 00:19:52,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:52,735 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-10-24 00:19:52,738 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:19:52,739 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1308022591] [2024-10-24 00:19:52,739 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1308022591] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:19:52,739 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:19:52,739 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 00:19:52,739 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1194393757] [2024-10-24 00:19:52,739 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:19:52,740 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:19:52,740 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:19:52,741 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:19:52,741 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:19:52,743 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-24 00:19:52,859 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:19:52,859 INFO L93 Difference]: Finished difference Result 45 states and 58 transitions. [2024-10-24 00:19:52,859 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:19:52,860 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2024-10-24 00:19:52,860 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:19:52,861 INFO L225 Difference]: With dead ends: 45 [2024-10-24 00:19:52,861 INFO L226 Difference]: Without dead ends: 43 [2024-10-24 00:19:52,861 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:19:52,862 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 9 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:19:52,862 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 116 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:19:52,866 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-10-24 00:19:52,881 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 36. [2024-10-24 00:19:52,905 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 22 states have internal predecessors, (25), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-10-24 00:19:52,907 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 44 transitions. [2024-10-24 00:19:52,907 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 44 transitions. Word has length 28 [2024-10-24 00:19:52,907 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:19:52,907 INFO L471 AbstractCegarLoop]: Abstraction has 36 states and 44 transitions. [2024-10-24 00:19:52,907 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-24 00:19:52,908 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 44 transitions. [2024-10-24 00:19:52,908 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-10-24 00:19:52,908 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:19:52,908 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:19:52,909 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-10-24 00:19:52,909 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:19:52,916 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:19:52,916 INFO L85 PathProgramCache]: Analyzing trace with hash 831418820, now seen corresponding path program 1 times [2024-10-24 00:19:52,916 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:19:52,916 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1440171654] [2024-10-24 00:19:52,916 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:19:52,917 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:19:52,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:19:52,956 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [825105087] [2024-10-24 00:19:52,958 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:19:52,958 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:19:52,958 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:19:52,960 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-24 00:19:52,962 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-24 00:19:53,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:53,030 INFO L255 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 00:19:53,039 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:19:53,152 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-10-24 00:19:53,156 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 00:19:53,156 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:19:53,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1440171654] [2024-10-24 00:19:53,157 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:19:53,157 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [825105087] [2024-10-24 00:19:53,157 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [825105087] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:19:53,158 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:19:53,158 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 00:19:53,158 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [444537442] [2024-10-24 00:19:53,158 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:19:53,158 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:19:53,159 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:19:53,159 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:19:53,159 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:19:53,159 INFO L87 Difference]: Start difference. First operand 36 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-24 00:19:53,256 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:19:53,256 INFO L93 Difference]: Finished difference Result 62 states and 81 transitions. [2024-10-24 00:19:53,256 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:19:53,257 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2024-10-24 00:19:53,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:19:53,258 INFO L225 Difference]: With dead ends: 62 [2024-10-24 00:19:53,258 INFO L226 Difference]: Without dead ends: 49 [2024-10-24 00:19:53,259 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:19:53,260 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 5 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:19:53,261 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 117 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:19:53,262 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-10-24 00:19:53,276 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2024-10-24 00:19:53,277 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 29 states have internal predecessors, (33), 15 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2024-10-24 00:19:53,278 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 62 transitions. [2024-10-24 00:19:53,279 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 62 transitions. Word has length 33 [2024-10-24 00:19:53,279 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:19:53,279 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 62 transitions. [2024-10-24 00:19:53,279 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-24 00:19:53,279 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 62 transitions. [2024-10-24 00:19:53,280 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-10-24 00:19:53,280 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:19:53,281 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:19:53,301 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-10-24 00:19:53,481 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:19:53,482 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:19:53,482 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:19:53,483 INFO L85 PathProgramCache]: Analyzing trace with hash -1016562388, now seen corresponding path program 1 times [2024-10-24 00:19:53,483 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:19:53,483 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1990514243] [2024-10-24 00:19:53,483 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:19:53,483 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:19:53,508 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:19:53,509 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1651105451] [2024-10-24 00:19:53,512 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:19:53,513 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:19:53,513 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:19:53,515 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-24 00:19:53,524 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-10-24 00:19:53,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:53,569 INFO L255 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-10-24 00:19:53,571 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:19:53,674 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-10-24 00:19:53,675 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:19:53,893 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-10-24 00:19:53,894 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:19:53,894 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1990514243] [2024-10-24 00:19:53,894 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:19:53,894 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1651105451] [2024-10-24 00:19:53,895 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1651105451] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:19:53,895 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:19:53,895 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-10-24 00:19:53,896 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1469100266] [2024-10-24 00:19:53,896 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:19:53,899 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-10-24 00:19:53,899 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:19:53,900 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-10-24 00:19:53,900 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-10-24 00:19:53,900 INFO L87 Difference]: Start difference. First operand 49 states and 62 transitions. Second operand has 10 states, 10 states have (on average 2.4) internal successors, (24), 9 states have internal predecessors, (24), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2024-10-24 00:19:54,057 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:19:54,058 INFO L93 Difference]: Finished difference Result 64 states and 82 transitions. [2024-10-24 00:19:54,058 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-24 00:19:54,058 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 9 states have internal predecessors, (24), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) Word has length 40 [2024-10-24 00:19:54,059 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:19:54,061 INFO L225 Difference]: With dead ends: 64 [2024-10-24 00:19:54,061 INFO L226 Difference]: Without dead ends: 62 [2024-10-24 00:19:54,061 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 69 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2024-10-24 00:19:54,062 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 15 mSDsluCounter, 137 mSDsCounter, 0 mSdLazyCounter, 129 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 129 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:19:54,064 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 161 Invalid, 136 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 129 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:19:54,065 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2024-10-24 00:19:54,078 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 59. [2024-10-24 00:19:54,080 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 34 states have (on average 1.2058823529411764) internal successors, (41), 36 states have internal predecessors, (41), 18 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2024-10-24 00:19:54,081 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 76 transitions. [2024-10-24 00:19:54,083 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 76 transitions. Word has length 40 [2024-10-24 00:19:54,083 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:19:54,083 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 76 transitions. [2024-10-24 00:19:54,084 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 9 states have internal predecessors, (24), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2024-10-24 00:19:54,084 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 76 transitions. [2024-10-24 00:19:54,085 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-10-24 00:19:54,086 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:19:54,086 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:19:54,103 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-24 00:19:54,290 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:19:54,291 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:19:54,291 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:19:54,291 INFO L85 PathProgramCache]: Analyzing trace with hash -1147651331, now seen corresponding path program 1 times [2024-10-24 00:19:54,291 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:19:54,292 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1902503591] [2024-10-24 00:19:54,292 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:19:54,292 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:19:54,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:19:54,308 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1535333862] [2024-10-24 00:19:54,309 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:19:54,309 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:19:54,309 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:19:54,311 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-24 00:19:54,313 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-24 00:19:54,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:54,364 INFO L255 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-24 00:19:54,367 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:19:54,497 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 10 proven. 4 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-10-24 00:19:54,500 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:19:54,614 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2024-10-24 00:19:54,614 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:19:54,615 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1902503591] [2024-10-24 00:19:54,615 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:19:54,615 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1535333862] [2024-10-24 00:19:54,616 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1535333862] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-24 00:19:54,616 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-24 00:19:54,616 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-10-24 00:19:54,617 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1513104823] [2024-10-24 00:19:54,617 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:19:54,618 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:19:54,618 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:19:54,618 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:19:54,619 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-10-24 00:19:54,619 INFO L87 Difference]: Start difference. First operand 59 states and 76 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-24 00:19:54,726 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:19:54,727 INFO L93 Difference]: Finished difference Result 69 states and 88 transitions. [2024-10-24 00:19:54,727 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:19:54,727 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 50 [2024-10-24 00:19:54,728 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:19:54,730 INFO L225 Difference]: With dead ends: 69 [2024-10-24 00:19:54,732 INFO L226 Difference]: Without dead ends: 67 [2024-10-24 00:19:54,732 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 91 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-10-24 00:19:54,733 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 5 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:19:54,733 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 110 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:19:54,734 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-10-24 00:19:54,751 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 66. [2024-10-24 00:19:54,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 41 states have internal predecessors, (45), 20 states have call successors, (20), 7 states have call predecessors, (20), 7 states have return successors, (19), 17 states have call predecessors, (19), 19 states have call successors, (19) [2024-10-24 00:19:54,753 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 84 transitions. [2024-10-24 00:19:54,753 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 84 transitions. Word has length 50 [2024-10-24 00:19:54,753 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:19:54,753 INFO L471 AbstractCegarLoop]: Abstraction has 66 states and 84 transitions. [2024-10-24 00:19:54,754 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-24 00:19:54,754 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 84 transitions. [2024-10-24 00:19:54,755 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-10-24 00:19:54,755 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:19:54,755 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:19:54,773 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-10-24 00:19:54,956 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:19:54,957 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:19:54,957 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:19:54,957 INFO L85 PathProgramCache]: Analyzing trace with hash 73871321, now seen corresponding path program 1 times [2024-10-24 00:19:54,957 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:19:54,958 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [747503501] [2024-10-24 00:19:54,958 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:19:54,958 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:19:54,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:55,089 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:19:55,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:55,097 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:19:55,098 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:55,100 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:19:55,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:55,105 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-24 00:19:55,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:55,111 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-24 00:19:55,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:55,118 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-24 00:19:55,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:55,128 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-10-24 00:19:55,131 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:55,137 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-10-24 00:19:55,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:55,145 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-10-24 00:19:55,148 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:55,153 INFO L134 CoverageAnalysis]: Checked inductivity of 84 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2024-10-24 00:19:55,154 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:19:55,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [747503501] [2024-10-24 00:19:55,154 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [747503501] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:19:55,155 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:19:55,155 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 00:19:55,155 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1999507467] [2024-10-24 00:19:55,155 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:19:55,156 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:19:55,156 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:19:55,157 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:19:55,157 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:19:55,157 INFO L87 Difference]: Start difference. First operand 66 states and 84 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-10-24 00:19:55,223 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:19:55,223 INFO L93 Difference]: Finished difference Result 74 states and 92 transitions. [2024-10-24 00:19:55,224 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:19:55,224 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 56 [2024-10-24 00:19:55,224 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:19:55,225 INFO L225 Difference]: With dead ends: 74 [2024-10-24 00:19:55,225 INFO L226 Difference]: Without dead ends: 62 [2024-10-24 00:19:55,225 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:19:55,226 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 3 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 127 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:19:55,226 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 127 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:19:55,227 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2024-10-24 00:19:55,245 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2024-10-24 00:19:55,246 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 36 states have (on average 1.1666666666666667) internal successors, (42), 39 states have internal predecessors, (42), 18 states have call successors, (18), 7 states have call predecessors, (18), 7 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2024-10-24 00:19:55,247 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 77 transitions. [2024-10-24 00:19:55,247 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 77 transitions. Word has length 56 [2024-10-24 00:19:55,248 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:19:55,252 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 77 transitions. [2024-10-24 00:19:55,252 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-10-24 00:19:55,252 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 77 transitions. [2024-10-24 00:19:55,254 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-10-24 00:19:55,254 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:19:55,254 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:19:55,254 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-10-24 00:19:55,254 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:19:55,254 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:19:55,255 INFO L85 PathProgramCache]: Analyzing trace with hash 1282123871, now seen corresponding path program 1 times [2024-10-24 00:19:55,255 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:19:55,255 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1433365136] [2024-10-24 00:19:55,255 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:19:55,255 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:19:55,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:19:55,306 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1098250567] [2024-10-24 00:19:55,306 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:19:55,307 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:19:55,307 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:19:55,309 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-24 00:19:55,311 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-24 00:19:55,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:19:55,375 INFO L255 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 38 conjuncts are in the unsatisfiable core [2024-10-24 00:19:55,380 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:19:56,124 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 19 proven. 10 refuted. 0 times theorem prover too weak. 118 trivial. 0 not checked. [2024-10-24 00:19:56,125 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:19:58,020 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2024-10-24 00:19:58,021 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:19:58,021 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1433365136] [2024-10-24 00:19:58,021 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:19:58,021 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1098250567] [2024-10-24 00:19:58,021 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1098250567] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:19:58,021 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:19:58,022 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 9] total 20 [2024-10-24 00:19:58,022 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [867513756] [2024-10-24 00:19:58,023 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:19:58,023 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-10-24 00:19:58,024 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:19:58,024 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-10-24 00:19:58,024 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=307, Unknown=0, NotChecked=0, Total=380 [2024-10-24 00:19:58,025 INFO L87 Difference]: Start difference. First operand 62 states and 77 transitions. Second operand has 20 states, 20 states have (on average 1.75) internal successors, (35), 17 states have internal predecessors, (35), 10 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (22), 9 states have call predecessors, (22), 8 states have call successors, (22) [2024-10-24 00:19:59,754 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:19:59,754 INFO L93 Difference]: Finished difference Result 148 states and 204 transitions. [2024-10-24 00:19:59,755 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-10-24 00:19:59,755 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 1.75) internal successors, (35), 17 states have internal predecessors, (35), 10 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (22), 9 states have call predecessors, (22), 8 states have call successors, (22) Word has length 70 [2024-10-24 00:19:59,755 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:19:59,757 INFO L225 Difference]: With dead ends: 148 [2024-10-24 00:19:59,758 INFO L226 Difference]: Without dead ends: 125 [2024-10-24 00:19:59,758 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 146 GetRequests, 120 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 140 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=164, Invalid=592, Unknown=0, NotChecked=0, Total=756 [2024-10-24 00:19:59,759 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 68 mSDsluCounter, 238 mSDsCounter, 0 mSdLazyCounter, 339 mSolverCounterSat, 87 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 74 SdHoareTripleChecker+Valid, 264 SdHoareTripleChecker+Invalid, 426 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 87 IncrementalHoareTripleChecker+Valid, 339 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-10-24 00:19:59,759 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [74 Valid, 264 Invalid, 426 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [87 Valid, 339 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-10-24 00:19:59,760 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2024-10-24 00:19:59,807 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 101. [2024-10-24 00:19:59,809 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 101 states, 60 states have (on average 1.1833333333333333) internal successors, (71), 64 states have internal predecessors, (71), 29 states have call successors, (29), 11 states have call predecessors, (29), 11 states have return successors, (28), 25 states have call predecessors, (28), 28 states have call successors, (28) [2024-10-24 00:19:59,810 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 128 transitions. [2024-10-24 00:19:59,813 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 128 transitions. Word has length 70 [2024-10-24 00:19:59,813 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:19:59,814 INFO L471 AbstractCegarLoop]: Abstraction has 101 states and 128 transitions. [2024-10-24 00:19:59,814 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 1.75) internal successors, (35), 17 states have internal predecessors, (35), 10 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (22), 9 states have call predecessors, (22), 8 states have call successors, (22) [2024-10-24 00:19:59,814 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 128 transitions. [2024-10-24 00:19:59,815 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2024-10-24 00:19:59,815 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:19:59,816 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:19:59,842 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-24 00:20:00,016 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:20:00,017 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:20:00,017 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:20:00,017 INFO L85 PathProgramCache]: Analyzing trace with hash 1411586487, now seen corresponding path program 1 times [2024-10-24 00:20:00,017 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:20:00,017 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [796712166] [2024-10-24 00:20:00,017 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:00,017 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:20:00,053 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:20:00,057 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1054692387] [2024-10-24 00:20:00,057 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:00,057 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:20:00,057 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:20:00,059 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-24 00:20:00,061 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-24 00:20:00,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:00,121 INFO L255 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-10-24 00:20:00,124 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:20:00,600 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 26 proven. 9 refuted. 0 times theorem prover too weak. 186 trivial. 0 not checked. [2024-10-24 00:20:00,601 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:20:01,431 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 20 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2024-10-24 00:20:01,431 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:20:01,431 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [796712166] [2024-10-24 00:20:01,432 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:20:01,432 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1054692387] [2024-10-24 00:20:01,432 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1054692387] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:20:01,432 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:20:01,432 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 9] total 20 [2024-10-24 00:20:01,432 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1931862396] [2024-10-24 00:20:01,433 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:20:01,433 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-10-24 00:20:01,433 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:20:01,434 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-10-24 00:20:01,434 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=311, Unknown=0, NotChecked=0, Total=380 [2024-10-24 00:20:01,435 INFO L87 Difference]: Start difference. First operand 101 states and 128 transitions. Second operand has 20 states, 19 states have (on average 1.894736842105263) internal successors, (36), 17 states have internal predecessors, (36), 11 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 10 states have call predecessors, (24), 9 states have call successors, (24) [2024-10-24 00:20:01,953 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:20:01,954 INFO L93 Difference]: Finished difference Result 141 states and 176 transitions. [2024-10-24 00:20:01,954 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-24 00:20:01,955 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 1.894736842105263) internal successors, (36), 17 states have internal predecessors, (36), 11 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 10 states have call predecessors, (24), 9 states have call successors, (24) Word has length 81 [2024-10-24 00:20:01,955 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:20:01,956 INFO L225 Difference]: With dead ends: 141 [2024-10-24 00:20:01,957 INFO L226 Difference]: Without dead ends: 107 [2024-10-24 00:20:01,958 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 168 GetRequests, 142 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 89 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=138, Invalid=618, Unknown=0, NotChecked=0, Total=756 [2024-10-24 00:20:01,959 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 26 mSDsluCounter, 357 mSDsCounter, 0 mSdLazyCounter, 316 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 391 SdHoareTripleChecker+Invalid, 345 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 316 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-24 00:20:01,960 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 391 Invalid, 345 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 316 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-24 00:20:01,961 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2024-10-24 00:20:01,989 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 93. [2024-10-24 00:20:01,989 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 56 states have (on average 1.1607142857142858) internal successors, (65), 58 states have internal predecessors, (65), 25 states have call successors, (25), 11 states have call predecessors, (25), 11 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2024-10-24 00:20:01,990 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 114 transitions. [2024-10-24 00:20:01,993 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 114 transitions. Word has length 81 [2024-10-24 00:20:01,993 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:20:01,993 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 114 transitions. [2024-10-24 00:20:01,994 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 1.894736842105263) internal successors, (36), 17 states have internal predecessors, (36), 11 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 10 states have call predecessors, (24), 9 states have call successors, (24) [2024-10-24 00:20:01,994 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 114 transitions. [2024-10-24 00:20:01,995 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2024-10-24 00:20:01,998 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:20:01,998 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:20:02,015 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-10-24 00:20:02,202 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:20:02,203 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:20:02,203 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:20:02,203 INFO L85 PathProgramCache]: Analyzing trace with hash -302279341, now seen corresponding path program 2 times [2024-10-24 00:20:02,203 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:20:02,203 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [636164190] [2024-10-24 00:20:02,204 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:02,204 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:20:02,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,382 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:20:02,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,385 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:20:02,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,387 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:20:02,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,389 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-24 00:20:02,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,391 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-24 00:20:02,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,395 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-24 00:20:02,398 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,401 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-10-24 00:20:02,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,405 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-10-24 00:20:02,406 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,412 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-24 00:20:02,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,419 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 53 [2024-10-24 00:20:02,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,429 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 58 [2024-10-24 00:20:02,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,439 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 66 [2024-10-24 00:20:02,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,453 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 71 [2024-10-24 00:20:02,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:02,461 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2024-10-24 00:20:02,461 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:20:02,461 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [636164190] [2024-10-24 00:20:02,461 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [636164190] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:20:02,461 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1700456310] [2024-10-24 00:20:02,462 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-24 00:20:02,462 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:20:02,462 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:20:02,464 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-24 00:20:02,465 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-24 00:20:02,524 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-24 00:20:02,524 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 00:20:02,526 INFO L255 TraceCheckSpWp]: Trace formula consists of 187 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 00:20:02,528 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:20:02,567 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2024-10-24 00:20:02,567 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:20:02,676 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2024-10-24 00:20:02,676 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1700456310] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:20:02,677 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 00:20:02,677 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 5 [2024-10-24 00:20:02,677 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [853333915] [2024-10-24 00:20:02,677 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 00:20:02,678 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:20:02,678 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:20:02,678 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:20:02,679 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:20:02,679 INFO L87 Difference]: Start difference. First operand 93 states and 114 transitions. Second operand has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 5 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-10-24 00:20:02,737 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:20:02,737 INFO L93 Difference]: Finished difference Result 120 states and 151 transitions. [2024-10-24 00:20:02,738 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-24 00:20:02,738 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 5 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) Word has length 83 [2024-10-24 00:20:02,738 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:20:02,739 INFO L225 Difference]: With dead ends: 120 [2024-10-24 00:20:02,740 INFO L226 Difference]: Without dead ends: 98 [2024-10-24 00:20:02,741 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 195 GetRequests, 192 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:20:02,741 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 0 mSDsluCounter, 65 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:20:02,742 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 110 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:20:02,743 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2024-10-24 00:20:02,765 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 98. [2024-10-24 00:20:02,766 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 59 states have (on average 1.152542372881356) internal successors, (68), 61 states have internal predecessors, (68), 27 states have call successors, (27), 11 states have call predecessors, (27), 11 states have return successors, (26), 25 states have call predecessors, (26), 26 states have call successors, (26) [2024-10-24 00:20:02,767 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 121 transitions. [2024-10-24 00:20:02,767 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 121 transitions. Word has length 83 [2024-10-24 00:20:02,767 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:20:02,768 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 121 transitions. [2024-10-24 00:20:02,768 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 5 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-10-24 00:20:02,768 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 121 transitions. [2024-10-24 00:20:02,769 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2024-10-24 00:20:02,769 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:20:02,769 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:20:02,787 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-24 00:20:02,970 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:20:02,970 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:20:02,971 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:20:02,971 INFO L85 PathProgramCache]: Analyzing trace with hash -1047816948, now seen corresponding path program 1 times [2024-10-24 00:20:02,971 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:20:02,971 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [405613377] [2024-10-24 00:20:02,971 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:02,971 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:20:02,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,225 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:20:03,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,229 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:20:03,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,230 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:20:03,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,232 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-24 00:20:03,233 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,235 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-24 00:20:03,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,239 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-24 00:20:03,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,242 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-10-24 00:20:03,244 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,246 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-10-24 00:20:03,248 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,251 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-24 00:20:03,253 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,257 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 53 [2024-10-24 00:20:03,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,262 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 58 [2024-10-24 00:20:03,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,270 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 66 [2024-10-24 00:20:03,272 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,275 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 71 [2024-10-24 00:20:03,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,280 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 77 [2024-10-24 00:20:03,282 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,285 INFO L134 CoverageAnalysis]: Checked inductivity of 263 backedges. 22 proven. 9 refuted. 0 times theorem prover too weak. 232 trivial. 0 not checked. [2024-10-24 00:20:03,285 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:20:03,286 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [405613377] [2024-10-24 00:20:03,286 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [405613377] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:20:03,286 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1825202206] [2024-10-24 00:20:03,286 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:03,286 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:20:03,286 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:20:03,288 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-24 00:20:03,290 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-24 00:20:03,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:03,347 INFO L255 TraceCheckSpWp]: Trace formula consists of 187 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-10-24 00:20:03,350 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:20:03,697 INFO L134 CoverageAnalysis]: Checked inductivity of 263 backedges. 28 proven. 9 refuted. 0 times theorem prover too weak. 226 trivial. 0 not checked. [2024-10-24 00:20:03,697 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:20:04,088 INFO L134 CoverageAnalysis]: Checked inductivity of 263 backedges. 22 proven. 9 refuted. 0 times theorem prover too weak. 232 trivial. 0 not checked. [2024-10-24 00:20:04,088 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1825202206] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:20:04,088 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 00:20:04,089 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 11, 8] total 18 [2024-10-24 00:20:04,089 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1743137760] [2024-10-24 00:20:04,089 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 00:20:04,089 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-10-24 00:20:04,090 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:20:04,090 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-10-24 00:20:04,091 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=252, Unknown=0, NotChecked=0, Total=306 [2024-10-24 00:20:04,091 INFO L87 Difference]: Start difference. First operand 98 states and 121 transitions. Second operand has 18 states, 18 states have (on average 2.3333333333333335) internal successors, (42), 15 states have internal predecessors, (42), 10 states have call successors, (33), 3 states have call predecessors, (33), 2 states have return successors, (32), 11 states have call predecessors, (32), 10 states have call successors, (32) [2024-10-24 00:20:04,384 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:20:04,384 INFO L93 Difference]: Finished difference Result 113 states and 141 transitions. [2024-10-24 00:20:04,385 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-10-24 00:20:04,385 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 2.3333333333333335) internal successors, (42), 15 states have internal predecessors, (42), 10 states have call successors, (33), 3 states have call predecessors, (33), 2 states have return successors, (32), 11 states have call predecessors, (32), 10 states have call successors, (32) Word has length 86 [2024-10-24 00:20:04,386 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:20:04,387 INFO L225 Difference]: With dead ends: 113 [2024-10-24 00:20:04,387 INFO L226 Difference]: Without dead ends: 96 [2024-10-24 00:20:04,387 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 210 GetRequests, 189 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=85, Invalid=377, Unknown=0, NotChecked=0, Total=462 [2024-10-24 00:20:04,388 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 27 mSDsluCounter, 332 mSDsCounter, 0 mSdLazyCounter, 204 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 373 SdHoareTripleChecker+Invalid, 222 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 204 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-24 00:20:04,388 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 373 Invalid, 222 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 204 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-24 00:20:04,389 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2024-10-24 00:20:04,407 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 89. [2024-10-24 00:20:04,408 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 54 states have (on average 1.1481481481481481) internal successors, (62), 56 states have internal predecessors, (62), 23 states have call successors, (23), 11 states have call predecessors, (23), 11 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2024-10-24 00:20:04,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 107 transitions. [2024-10-24 00:20:04,409 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 107 transitions. Word has length 86 [2024-10-24 00:20:04,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:20:04,409 INFO L471 AbstractCegarLoop]: Abstraction has 89 states and 107 transitions. [2024-10-24 00:20:04,410 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 2.3333333333333335) internal successors, (42), 15 states have internal predecessors, (42), 10 states have call successors, (33), 3 states have call predecessors, (33), 2 states have return successors, (32), 11 states have call predecessors, (32), 10 states have call successors, (32) [2024-10-24 00:20:04,410 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 107 transitions. [2024-10-24 00:20:04,411 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-10-24 00:20:04,412 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:20:04,412 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:20:04,430 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-10-24 00:20:04,612 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:20:04,612 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:20:04,613 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:20:04,613 INFO L85 PathProgramCache]: Analyzing trace with hash -1271237959, now seen corresponding path program 1 times [2024-10-24 00:20:04,613 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:20:04,613 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [861896594] [2024-10-24 00:20:04,613 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:04,613 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:20:04,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,695 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:20:04,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,697 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:20:04,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,699 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:20:04,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,700 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-24 00:20:04,701 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,702 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-24 00:20:04,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,705 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-24 00:20:04,705 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,707 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-10-24 00:20:04,708 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,709 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-10-24 00:20:04,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,712 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-24 00:20:04,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,714 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 53 [2024-10-24 00:20:04,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,716 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 58 [2024-10-24 00:20:04,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,719 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2024-10-24 00:20:04,720 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,722 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-10-24 00:20:04,723 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,725 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 75 [2024-10-24 00:20:04,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,728 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 81 [2024-10-24 00:20:04,729 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,730 INFO L134 CoverageAnalysis]: Checked inductivity of 315 backedges. 29 proven. 10 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-10-24 00:20:04,730 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:20:04,731 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [861896594] [2024-10-24 00:20:04,731 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [861896594] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:20:04,731 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [573936808] [2024-10-24 00:20:04,731 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:04,731 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:20:04,731 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:20:04,733 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-24 00:20:04,734 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-24 00:20:04,788 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:04,790 INFO L255 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-24 00:20:04,792 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:20:04,827 INFO L134 CoverageAnalysis]: Checked inductivity of 315 backedges. 81 proven. 0 refuted. 0 times theorem prover too weak. 234 trivial. 0 not checked. [2024-10-24 00:20:04,827 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 00:20:04,827 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [573936808] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:20:04,827 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-24 00:20:04,827 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 6 [2024-10-24 00:20:04,828 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2046781226] [2024-10-24 00:20:04,828 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:20:04,828 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:20:04,828 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:20:04,829 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:20:04,829 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:20:04,829 INFO L87 Difference]: Start difference. First operand 89 states and 107 transitions. Second operand has 5 states, 5 states have (on average 4.4) internal successors, (22), 5 states have internal predecessors, (22), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2024-10-24 00:20:04,893 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:20:04,893 INFO L93 Difference]: Finished difference Result 96 states and 113 transitions. [2024-10-24 00:20:04,894 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:20:04,894 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 5 states have internal predecessors, (22), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) Word has length 90 [2024-10-24 00:20:04,895 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:20:04,896 INFO L225 Difference]: With dead ends: 96 [2024-10-24 00:20:04,896 INFO L226 Difference]: Without dead ends: 84 [2024-10-24 00:20:04,897 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 120 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:20:04,897 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 7 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:20:04,897 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 83 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:20:04,898 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2024-10-24 00:20:04,918 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 84. [2024-10-24 00:20:04,919 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 51 states have (on average 1.1176470588235294) internal successors, (57), 52 states have internal predecessors, (57), 22 states have call successors, (22), 10 states have call predecessors, (22), 10 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2024-10-24 00:20:04,919 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 100 transitions. [2024-10-24 00:20:04,919 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 100 transitions. Word has length 90 [2024-10-24 00:20:04,920 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:20:04,920 INFO L471 AbstractCegarLoop]: Abstraction has 84 states and 100 transitions. [2024-10-24 00:20:04,920 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 5 states have internal predecessors, (22), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2024-10-24 00:20:04,920 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 100 transitions. [2024-10-24 00:20:04,921 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2024-10-24 00:20:04,921 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:20:04,921 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:20:04,939 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-10-24 00:20:05,122 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,SelfDestructingSolverStorable11 [2024-10-24 00:20:05,122 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:20:05,123 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:20:05,123 INFO L85 PathProgramCache]: Analyzing trace with hash 1209712204, now seen corresponding path program 3 times [2024-10-24 00:20:05,123 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:20:05,123 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [172346321] [2024-10-24 00:20:05,123 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:05,123 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:20:05,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,603 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:20:05,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,631 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:20:05,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,635 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:20:05,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,638 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-24 00:20:05,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,641 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-24 00:20:05,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,644 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-24 00:20:05,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,647 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-10-24 00:20:05,648 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,650 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-10-24 00:20:05,651 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,654 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-24 00:20:05,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,658 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 53 [2024-10-24 00:20:05,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,662 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 58 [2024-10-24 00:20:05,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,666 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2024-10-24 00:20:05,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,670 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-10-24 00:20:05,672 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,678 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 75 [2024-10-24 00:20:05,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,683 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-10-24 00:20:05,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,687 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 88 [2024-10-24 00:20:05,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:05,692 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 45 proven. 11 refuted. 0 times theorem prover too weak. 318 trivial. 0 not checked. [2024-10-24 00:20:05,692 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:20:05,692 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [172346321] [2024-10-24 00:20:05,692 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [172346321] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:20:05,692 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1274626981] [2024-10-24 00:20:05,692 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-24 00:20:05,692 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:20:05,693 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:20:05,695 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-24 00:20:05,696 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-24 00:20:05,757 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-10-24 00:20:05,757 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 00:20:05,759 INFO L255 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-10-24 00:20:05,761 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:20:06,282 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 33 proven. 23 refuted. 0 times theorem prover too weak. 318 trivial. 0 not checked. [2024-10-24 00:20:06,282 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:20:07,098 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 33 proven. 23 refuted. 0 times theorem prover too weak. 318 trivial. 0 not checked. [2024-10-24 00:20:07,098 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1274626981] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:20:07,098 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 00:20:07,099 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 11] total 24 [2024-10-24 00:20:07,099 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1032312233] [2024-10-24 00:20:07,099 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 00:20:07,100 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-10-24 00:20:07,100 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:20:07,101 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-10-24 00:20:07,101 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=465, Unknown=0, NotChecked=0, Total=552 [2024-10-24 00:20:07,101 INFO L87 Difference]: Start difference. First operand 84 states and 100 transitions. Second operand has 24 states, 24 states have (on average 2.2916666666666665) internal successors, (55), 22 states have internal predecessors, (55), 16 states have call successors, (43), 2 states have call predecessors, (43), 2 states have return successors, (44), 16 states have call predecessors, (44), 15 states have call successors, (44) [2024-10-24 00:20:07,764 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:20:07,764 INFO L93 Difference]: Finished difference Result 209 states and 289 transitions. [2024-10-24 00:20:07,764 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-10-24 00:20:07,765 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 2.2916666666666665) internal successors, (55), 22 states have internal predecessors, (55), 16 states have call successors, (43), 2 states have call predecessors, (43), 2 states have return successors, (44), 16 states have call predecessors, (44), 15 states have call successors, (44) Word has length 100 [2024-10-24 00:20:07,765 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:20:07,766 INFO L225 Difference]: With dead ends: 209 [2024-10-24 00:20:07,766 INFO L226 Difference]: Without dead ends: 157 [2024-10-24 00:20:07,767 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 252 GetRequests, 217 SyntacticMatches, 2 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 218 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=238, Invalid=952, Unknown=0, NotChecked=0, Total=1190 [2024-10-24 00:20:07,768 INFO L432 NwaCegarLoop]: 59 mSDtfsCounter, 99 mSDsluCounter, 537 mSDsCounter, 0 mSdLazyCounter, 295 mSolverCounterSat, 110 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 102 SdHoareTripleChecker+Valid, 596 SdHoareTripleChecker+Invalid, 405 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 110 IncrementalHoareTripleChecker+Valid, 295 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-24 00:20:07,768 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [102 Valid, 596 Invalid, 405 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [110 Valid, 295 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-24 00:20:07,769 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 157 states. [2024-10-24 00:20:07,803 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 157 to 110. [2024-10-24 00:20:07,804 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 110 states, 67 states have (on average 1.208955223880597) internal successors, (81), 68 states have internal predecessors, (81), 32 states have call successors, (32), 10 states have call predecessors, (32), 10 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2024-10-24 00:20:07,805 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 144 transitions. [2024-10-24 00:20:07,805 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 144 transitions. Word has length 100 [2024-10-24 00:20:07,805 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:20:07,806 INFO L471 AbstractCegarLoop]: Abstraction has 110 states and 144 transitions. [2024-10-24 00:20:07,806 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 2.2916666666666665) internal successors, (55), 22 states have internal predecessors, (55), 16 states have call successors, (43), 2 states have call predecessors, (43), 2 states have return successors, (44), 16 states have call predecessors, (44), 15 states have call successors, (44) [2024-10-24 00:20:07,806 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 144 transitions. [2024-10-24 00:20:07,807 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2024-10-24 00:20:07,807 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:20:07,807 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:20:07,823 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-10-24 00:20:08,007 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-10-24 00:20:08,008 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:20:08,008 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:20:08,008 INFO L85 PathProgramCache]: Analyzing trace with hash -1299465319, now seen corresponding path program 1 times [2024-10-24 00:20:08,008 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:20:08,008 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [239629562] [2024-10-24 00:20:08,008 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:08,008 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:20:08,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:20:08,033 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [419563574] [2024-10-24 00:20:08,033 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:08,033 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:20:08,033 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:20:08,035 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-24 00:20:08,037 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-24 00:20:08,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:08,107 INFO L255 TraceCheckSpWp]: Trace formula consists of 225 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-10-24 00:20:08,110 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:20:08,684 INFO L134 CoverageAnalysis]: Checked inductivity of 430 backedges. 27 proven. 72 refuted. 0 times theorem prover too weak. 331 trivial. 0 not checked. [2024-10-24 00:20:08,684 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:20:10,870 INFO L134 CoverageAnalysis]: Checked inductivity of 430 backedges. 27 proven. 72 refuted. 0 times theorem prover too weak. 331 trivial. 0 not checked. [2024-10-24 00:20:10,870 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:20:10,870 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [239629562] [2024-10-24 00:20:10,870 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:20:10,870 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [419563574] [2024-10-24 00:20:10,870 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [419563574] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:20:10,870 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:20:10,870 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 15] total 29 [2024-10-24 00:20:10,871 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1514174040] [2024-10-24 00:20:10,871 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:20:10,871 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2024-10-24 00:20:10,871 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:20:10,872 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2024-10-24 00:20:10,872 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=704, Unknown=0, NotChecked=0, Total=812 [2024-10-24 00:20:10,872 INFO L87 Difference]: Start difference. First operand 110 states and 144 transitions. Second operand has 29 states, 29 states have (on average 1.793103448275862) internal successors, (52), 26 states have internal predecessors, (52), 16 states have call successors, (35), 3 states have call predecessors, (35), 3 states have return successors, (34), 13 states have call predecessors, (34), 16 states have call successors, (34) [2024-10-24 00:20:11,702 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:20:11,702 INFO L93 Difference]: Finished difference Result 134 states and 165 transitions. [2024-10-24 00:20:11,702 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-10-24 00:20:11,702 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 29 states have (on average 1.793103448275862) internal successors, (52), 26 states have internal predecessors, (52), 16 states have call successors, (35), 3 states have call predecessors, (35), 3 states have return successors, (34), 13 states have call predecessors, (34), 16 states have call successors, (34) Word has length 105 [2024-10-24 00:20:11,703 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:20:11,703 INFO L225 Difference]: With dead ends: 134 [2024-10-24 00:20:11,704 INFO L226 Difference]: Without dead ends: 91 [2024-10-24 00:20:11,704 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 217 GetRequests, 180 SyntacticMatches, 1 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 166 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=219, Invalid=1187, Unknown=0, NotChecked=0, Total=1406 [2024-10-24 00:20:11,705 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 45 mSDsluCounter, 388 mSDsCounter, 0 mSdLazyCounter, 448 mSolverCounterSat, 80 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 419 SdHoareTripleChecker+Invalid, 528 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 80 IncrementalHoareTripleChecker+Valid, 448 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-10-24 00:20:11,705 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [45 Valid, 419 Invalid, 528 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [80 Valid, 448 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-10-24 00:20:11,705 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2024-10-24 00:20:11,723 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 91. [2024-10-24 00:20:11,724 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 57 states have (on average 1.0175438596491229) internal successors, (58), 58 states have internal predecessors, (58), 20 states have call successors, (20), 13 states have call predecessors, (20), 13 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2024-10-24 00:20:11,725 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 97 transitions. [2024-10-24 00:20:11,725 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 97 transitions. Word has length 105 [2024-10-24 00:20:11,725 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:20:11,725 INFO L471 AbstractCegarLoop]: Abstraction has 91 states and 97 transitions. [2024-10-24 00:20:11,726 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 1.793103448275862) internal successors, (52), 26 states have internal predecessors, (52), 16 states have call successors, (35), 3 states have call predecessors, (35), 3 states have return successors, (34), 13 states have call predecessors, (34), 16 states have call successors, (34) [2024-10-24 00:20:11,726 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 97 transitions. [2024-10-24 00:20:11,727 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2024-10-24 00:20:11,727 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:20:11,727 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:20:11,745 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-10-24 00:20:11,927 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,SelfDestructingSolverStorable13 [2024-10-24 00:20:11,928 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:20:11,928 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:20:11,928 INFO L85 PathProgramCache]: Analyzing trace with hash -663832148, now seen corresponding path program 1 times [2024-10-24 00:20:11,929 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:20:11,929 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2019792810] [2024-10-24 00:20:11,929 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:11,929 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:20:11,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:20:11,962 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1726777593] [2024-10-24 00:20:11,962 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:11,963 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:20:11,963 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:20:11,965 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-24 00:20:11,967 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-24 00:20:12,036 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:12,039 INFO L255 TraceCheckSpWp]: Trace formula consists of 236 conjuncts, 49 conjuncts are in the unsatisfiable core [2024-10-24 00:20:12,042 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:20:13,005 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 64 proven. 72 refuted. 0 times theorem prover too weak. 354 trivial. 0 not checked. [2024-10-24 00:20:13,005 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:20:14,252 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:20:14,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2019792810] [2024-10-24 00:20:14,252 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:20:14,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1726777593] [2024-10-24 00:20:14,252 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1726777593] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:20:14,252 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 00:20:14,252 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-10-24 00:20:14,253 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1072440413] [2024-10-24 00:20:14,253 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 00:20:14,253 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-24 00:20:14,253 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:20:14,254 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-24 00:20:14,254 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=125, Invalid=475, Unknown=0, NotChecked=0, Total=600 [2024-10-24 00:20:14,254 INFO L87 Difference]: Start difference. First operand 91 states and 97 transitions. Second operand has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 14 states have internal predecessors, (29), 9 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 8 states have call successors, (18) [2024-10-24 00:20:14,762 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:20:14,762 INFO L93 Difference]: Finished difference Result 97 states and 102 transitions. [2024-10-24 00:20:14,763 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-10-24 00:20:14,763 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 14 states have internal predecessors, (29), 9 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 8 states have call successors, (18) Word has length 111 [2024-10-24 00:20:14,763 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:20:14,764 INFO L225 Difference]: With dead ends: 97 [2024-10-24 00:20:14,764 INFO L226 Difference]: Without dead ends: 93 [2024-10-24 00:20:14,764 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 144 GetRequests, 119 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 114 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=146, Invalid=556, Unknown=0, NotChecked=0, Total=702 [2024-10-24 00:20:14,765 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 3 mSDsluCounter, 361 mSDsCounter, 0 mSdLazyCounter, 375 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 397 SdHoareTripleChecker+Invalid, 389 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 375 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-10-24 00:20:14,765 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 397 Invalid, 389 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 375 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-10-24 00:20:14,765 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2024-10-24 00:20:14,784 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2024-10-24 00:20:14,784 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 59 states have (on average 1.0) internal successors, (59), 59 states have internal predecessors, (59), 20 states have call successors, (20), 14 states have call predecessors, (20), 13 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2024-10-24 00:20:14,785 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 98 transitions. [2024-10-24 00:20:14,785 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 98 transitions. Word has length 111 [2024-10-24 00:20:14,785 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:20:14,786 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 98 transitions. [2024-10-24 00:20:14,786 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 14 states have internal predecessors, (29), 9 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 8 states have call successors, (18) [2024-10-24 00:20:14,786 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 98 transitions. [2024-10-24 00:20:14,787 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2024-10-24 00:20:14,787 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:20:14,787 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:20:14,801 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-10-24 00:20:14,988 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-10-24 00:20:14,988 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:20:14,989 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:20:14,989 INFO L85 PathProgramCache]: Analyzing trace with hash 683583031, now seen corresponding path program 1 times [2024-10-24 00:20:14,989 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:20:14,989 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [159485404] [2024-10-24 00:20:14,989 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:14,989 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:20:15,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,383 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:20:15,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,386 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:20:15,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,387 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:20:15,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,389 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-24 00:20:15,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,391 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-24 00:20:15,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,394 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-24 00:20:15,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,397 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-10-24 00:20:15,398 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,400 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-10-24 00:20:15,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,403 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-24 00:20:15,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,407 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 53 [2024-10-24 00:20:15,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,412 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 58 [2024-10-24 00:20:15,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,416 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2024-10-24 00:20:15,417 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,420 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-10-24 00:20:15,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,425 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 75 [2024-10-24 00:20:15,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,428 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-10-24 00:20:15,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,432 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 88 [2024-10-24 00:20:15,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,436 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 96 [2024-10-24 00:20:15,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,439 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 101 [2024-10-24 00:20:15,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,441 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 107 [2024-10-24 00:20:15,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,445 INFO L134 CoverageAnalysis]: Checked inductivity of 552 backedges. 32 proven. 28 refuted. 0 times theorem prover too weak. 492 trivial. 0 not checked. [2024-10-24 00:20:15,445 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:20:15,445 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [159485404] [2024-10-24 00:20:15,445 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [159485404] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:20:15,445 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2129164941] [2024-10-24 00:20:15,446 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:20:15,446 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:20:15,446 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:20:15,448 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-24 00:20:15,449 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-10-24 00:20:15,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:20:15,514 INFO L255 TraceCheckSpWp]: Trace formula consists of 245 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-10-24 00:20:15,517 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:20:15,923 INFO L134 CoverageAnalysis]: Checked inductivity of 552 backedges. 31 proven. 74 refuted. 0 times theorem prover too weak. 447 trivial. 0 not checked. [2024-10-24 00:20:15,924 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:20:16,958 INFO L134 CoverageAnalysis]: Checked inductivity of 552 backedges. 31 proven. 74 refuted. 0 times theorem prover too weak. 447 trivial. 0 not checked. [2024-10-24 00:20:16,958 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2129164941] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:20:16,958 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 00:20:16,958 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 13, 12] total 26 [2024-10-24 00:20:16,958 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1551427440] [2024-10-24 00:20:16,958 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 00:20:16,959 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-10-24 00:20:16,959 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:20:16,959 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-10-24 00:20:16,960 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=559, Unknown=0, NotChecked=0, Total=650 [2024-10-24 00:20:16,960 INFO L87 Difference]: Start difference. First operand 93 states and 98 transitions. Second operand has 26 states, 26 states have (on average 2.3076923076923075) internal successors, (60), 23 states have internal predecessors, (60), 19 states have call successors, (50), 3 states have call predecessors, (50), 2 states have return successors, (48), 17 states have call predecessors, (48), 19 states have call successors, (48) [2024-10-24 00:20:17,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:20:17,310 INFO L93 Difference]: Finished difference Result 93 states and 98 transitions. [2024-10-24 00:20:17,310 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-24 00:20:17,311 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 2.3076923076923075) internal successors, (60), 23 states have internal predecessors, (60), 19 states have call successors, (50), 3 states have call predecessors, (50), 2 states have return successors, (48), 17 states have call predecessors, (48), 19 states have call successors, (48) Word has length 116 [2024-10-24 00:20:17,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:20:17,311 INFO L225 Difference]: With dead ends: 93 [2024-10-24 00:20:17,311 INFO L226 Difference]: Without dead ends: 0 [2024-10-24 00:20:17,312 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 284 GetRequests, 254 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 218 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=146, Invalid=846, Unknown=0, NotChecked=0, Total=992 [2024-10-24 00:20:17,313 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 14 mSDsluCounter, 242 mSDsCounter, 0 mSdLazyCounter, 318 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 278 SdHoareTripleChecker+Invalid, 345 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 318 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-24 00:20:17,313 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 278 Invalid, 345 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 318 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-24 00:20:17,313 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-10-24 00:20:17,313 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-10-24 00:20:17,313 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-24 00:20:17,313 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-10-24 00:20:17,314 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 116 [2024-10-24 00:20:17,314 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:20:17,314 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-24 00:20:17,314 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 2.3076923076923075) internal successors, (60), 23 states have internal predecessors, (60), 19 states have call successors, (50), 3 states have call predecessors, (50), 2 states have return successors, (48), 17 states have call predecessors, (48), 19 states have call successors, (48) [2024-10-24 00:20:17,314 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-10-24 00:20:17,314 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-10-24 00:20:17,316 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-10-24 00:20:17,333 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-10-24 00:20:17,521 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-10-24 00:20:17,524 INFO L407 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:20:17,526 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-10-24 00:20:19,206 INFO L165 ceAbstractionStarter]: Computing trace abstraction results [2024-10-24 00:20:19,236 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.10 12:20:19 BoogieIcfgContainer [2024-10-24 00:20:19,236 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-10-24 00:20:19,237 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-24 00:20:19,237 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-24 00:20:19,237 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-24 00:20:19,238 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 12:19:51" (3/4) ... [2024-10-24 00:20:19,240 INFO L139 WitnessPrinter]: Generating witness for correct program [2024-10-24 00:20:19,244 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure assume_abort_if_not [2024-10-24 00:20:19,244 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-10-24 00:20:19,247 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 15 nodes and edges [2024-10-24 00:20:19,247 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 5 nodes and edges [2024-10-24 00:20:19,247 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-10-24 00:20:19,247 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-10-24 00:20:19,322 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-10-24 00:20:19,322 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.yml [2024-10-24 00:20:19,322 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-24 00:20:19,323 INFO L158 Benchmark]: Toolchain (without parser) took 28386.75ms. Allocated memory was 165.7MB in the beginning and 415.2MB in the end (delta: 249.6MB). Free memory was 110.1MB in the beginning and 271.6MB in the end (delta: -161.6MB). Peak memory consumption was 88.2MB. Max. memory is 16.1GB. [2024-10-24 00:20:19,323 INFO L158 Benchmark]: CDTParser took 0.16ms. Allocated memory is still 96.5MB. Free memory is still 51.4MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-24 00:20:19,323 INFO L158 Benchmark]: CACSL2BoogieTranslator took 384.76ms. Allocated memory is still 165.7MB. Free memory was 110.1MB in the beginning and 137.0MB in the end (delta: -26.9MB). Peak memory consumption was 14.7MB. Max. memory is 16.1GB. [2024-10-24 00:20:19,323 INFO L158 Benchmark]: Boogie Procedure Inliner took 33.35ms. Allocated memory is still 165.7MB. Free memory was 137.0MB in the beginning and 135.2MB in the end (delta: 1.9MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-24 00:20:19,323 INFO L158 Benchmark]: Boogie Preprocessor took 50.12ms. Allocated memory is still 165.7MB. Free memory was 135.2MB in the beginning and 133.8MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-24 00:20:19,324 INFO L158 Benchmark]: RCFGBuilder took 332.87ms. Allocated memory is still 165.7MB. Free memory was 133.8MB in the beginning and 120.5MB in the end (delta: 13.3MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-10-24 00:20:19,324 INFO L158 Benchmark]: TraceAbstraction took 27491.21ms. Allocated memory was 165.7MB in the beginning and 415.2MB in the end (delta: 249.6MB). Free memory was 119.9MB in the beginning and 276.9MB in the end (delta: -157.0MB). Peak memory consumption was 235.3MB. Max. memory is 16.1GB. [2024-10-24 00:20:19,324 INFO L158 Benchmark]: Witness Printer took 85.04ms. Allocated memory is still 415.2MB. Free memory was 275.8MB in the beginning and 271.6MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-10-24 00:20:19,331 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.16ms. Allocated memory is still 96.5MB. Free memory is still 51.4MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 384.76ms. Allocated memory is still 165.7MB. Free memory was 110.1MB in the beginning and 137.0MB in the end (delta: -26.9MB). Peak memory consumption was 14.7MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 33.35ms. Allocated memory is still 165.7MB. Free memory was 137.0MB in the beginning and 135.2MB in the end (delta: 1.9MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 50.12ms. Allocated memory is still 165.7MB. Free memory was 135.2MB in the beginning and 133.8MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 332.87ms. Allocated memory is still 165.7MB. Free memory was 133.8MB in the beginning and 120.5MB in the end (delta: 13.3MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * TraceAbstraction took 27491.21ms. Allocated memory was 165.7MB in the beginning and 415.2MB in the end (delta: 249.6MB). Free memory was 119.9MB in the beginning and 276.9MB in the end (delta: -157.0MB). Peak memory consumption was 235.3MB. Max. memory is 16.1GB. * Witness Printer took 85.04ms. Allocated memory is still 415.2MB. Free memory was 275.8MB in the beginning and 271.6MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 17]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 30 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 25.7s, OverallIterations: 16, TraceHistogramMax: 17, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 5.8s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 386 SdHoareTripleChecker+Valid, 3.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 335 mSDsluCounter, 3699 SdHoareTripleChecker+Invalid, 2.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 3115 mSDsCounter, 382 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2660 IncrementalHoareTripleChecker+Invalid, 3042 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 382 mSolverCounterUnsat, 584 mSDtfsCounter, 2660 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 2012 GetRequests, 1771 SyntacticMatches, 7 SemanticMatches, 234 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1022 ImplicationChecksByTransitivity, 5.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=110occurred in iteration=13, InterpolantAutomatonStates: 154, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.4s AutomataMinimizationTime, 16 MinimizatonAttempts, 110 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 15.6s InterpolantComputationTime, 2060 NumberOfCodeBlocks, 2033 NumberOfCodeBlocksAsserted, 32 NumberOfCheckSat, 2271 ConstructedInterpolants, 0 QuantifiedInterpolants, 14813 SizeOfPredicates, 30 NumberOfNonLiveVariables, 2079 ConjunctsInSsa, 278 ConjunctsInUnsatCore, 30 InterpolantComputations, 7 PerfectInterpolantSequences, 6729/7295 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 46]: Loop Invariant Derived loop invariant: (((((((((((((p == 4) && (r <= 2)) && (q == 0)) && (r == A)) && (((__int128) r + 1) <= d)) && (((d >= 0) ? (d % 2) : ((d % 2) + 2)) == 0)) && (((d >= 0) ? (d / 2) : ((d / 2) - 1)) <= r)) && ((((d >= 0) ? (d / 2) : ((d / 2) - 1)) + A) == ((__int128) ((long long) 2 * B) + r))) || ((((((d == 1) && (p == 1)) && (B == 1)) && (r == 0)) && (2 == q)) && (2 == A))) || (((((((A <= 2) && (2 == p)) && (((long long) 2 * B) == d)) && (q == 0)) && (r == A)) && (((__int128) r + 1) <= d)) && (((d >= 0) ? (d / 2) : ((d / 2) - 1)) <= r))) || ((((((2 == p) && (B == 1)) && (r == 0)) && (2 == q)) && (2 == A)) && (2 == d))) || (((((((((__int128) r + B) == A) && (p == 1)) && (A <= 2)) && (0 <= r)) && (q == 1)) && (((__int128) d + A) == ((__int128) ((long long) 2 * B) + r))) && (((__int128) r + 1) <= d))) || ((((p == 1) && (d == B)) && (q == 0)) && (r == A))) - InvariantResult [Line: 36]: Loop Invariant Derived loop invariant: ((((((((p == 1) && (d == B)) && (r <= 2)) && (q == 0)) && (1 <= d)) && (r == A)) || (((((((2 == p) && (((long long) 2 * B) == d)) && (r <= 2)) && (q == 0)) && (1 <= d)) && (r == A)) && (((d >= 0) ? (d / 2) : ((d / 2) - 1)) <= r))) || ((((((((p == 4) && (r <= 2)) && (q == 0)) && (1 <= d)) && (r == A)) && (((d >= 0) ? (d % 2) : ((d % 2) + 2)) == 0)) && (((d >= 0) ? (d / 2) : ((d / 2) - 1)) <= r)) && ((((d >= 0) ? (d / 2) : ((d / 2) - 1)) + A) == ((__int128) ((long long) 2 * B) + r)))) - ProcedureContractResult [Line: 11]: Procedure Contract for assume_abort_if_not Derived contract for procedure assume_abort_if_not. Ensures: (cond != 0) - ProcedureContractResult [Line: 14]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert. Requires: (cond != 0) Ensures: (cond != 0) RESULT: Ultimate proved your program to be correct! [2024-10-24 00:20:19,394 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE