./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/heap-manipulation/dancing.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8be7027f Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/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 ../sv-benchmarks/c/heap-manipulation/dancing.i -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 c2e0266b63b958a771d0226973905d5a39a7a28d05d194ae66381394d9ab520a --- Real Ultimate output --- This is Ultimate 0.2.5-wip.dk.perfect-tracechecks-8be7027-m [2024-11-11 19:30:08,073 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-11 19:30:08,131 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-11 19:30:08,136 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-11 19:30:08,137 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-11 19:30:08,178 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-11 19:30:08,178 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-11 19:30:08,193 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-11 19:30:08,194 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-11 19:30:08,194 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-11 19:30:08,195 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-11 19:30:08,195 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-11 19:30:08,195 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-11 19:30:08,196 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-11 19:30:08,196 INFO L153 SettingsManager]: * Use SBE=true [2024-11-11 19:30:08,196 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-11 19:30:08,196 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-11 19:30:08,197 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-11 19:30:08,197 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-11 19:30:08,197 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-11 19:30:08,197 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-11 19:30:08,198 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-11 19:30:08,198 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-11 19:30:08,198 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-11 19:30:08,198 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-11 19:30:08,198 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-11 19:30:08,199 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-11 19:30:08,199 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-11 19:30:08,199 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-11 19:30:08,199 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-11 19:30:08,199 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-11 19:30:08,200 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-11 19:30:08,200 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-11 19:30:08,200 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-11 19:30:08,200 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-11 19:30:08,201 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-11 19:30:08,201 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-11 19:30:08,201 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-11 19:30:08,201 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-11 19:30:08,201 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-11 19:30:08,202 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-11 19:30:08,202 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-11 19:30:08,202 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 -> c2e0266b63b958a771d0226973905d5a39a7a28d05d194ae66381394d9ab520a [2024-11-11 19:30:08,413 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-11 19:30:08,433 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-11 19:30:08,435 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-11 19:30:08,436 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-11 19:30:08,437 INFO L274 PluginConnector]: CDTParser initialized [2024-11-11 19:30:08,438 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/heap-manipulation/dancing.i [2024-11-11 19:30:09,747 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-11 19:30:09,932 INFO L384 CDTParser]: Found 1 translation units. [2024-11-11 19:30:09,932 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/heap-manipulation/dancing.i [2024-11-11 19:30:09,947 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f35de04e9/b67fec01b075449e80f59d78b28bcc58/FLAG4a6d726d3 [2024-11-11 19:30:09,958 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f35de04e9/b67fec01b075449e80f59d78b28bcc58 [2024-11-11 19:30:09,960 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-11 19:30:09,962 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-11 19:30:09,963 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-11 19:30:09,964 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-11 19:30:09,968 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-11 19:30:09,968 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.11 07:30:09" (1/1) ... [2024-11-11 19:30:09,969 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5b9c5f96 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:09, skipping insertion in model container [2024-11-11 19:30:09,969 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.11 07:30:09" (1/1) ... [2024-11-11 19:30:10,004 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-11 19:30:10,147 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/heap-manipulation/dancing.i[938,951] [2024-11-11 19:30:10,247 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-11 19:30:10,255 INFO L200 MainTranslator]: Completed pre-run [2024-11-11 19:30:10,266 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/heap-manipulation/dancing.i[938,951] [2024-11-11 19:30:10,292 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-11 19:30:10,315 INFO L204 MainTranslator]: Completed translation [2024-11-11 19:30:10,315 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10 WrapperNode [2024-11-11 19:30:10,316 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-11 19:30:10,316 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-11 19:30:10,317 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-11 19:30:10,317 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-11 19:30:10,322 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10" (1/1) ... [2024-11-11 19:30:10,335 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10" (1/1) ... [2024-11-11 19:30:10,361 INFO L138 Inliner]: procedures = 124, calls = 40, calls flagged for inlining = 5, calls inlined = 5, statements flattened = 88 [2024-11-11 19:30:10,361 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-11 19:30:10,362 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-11 19:30:10,362 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-11 19:30:10,362 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-11 19:30:10,373 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10" (1/1) ... [2024-11-11 19:30:10,373 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10" (1/1) ... [2024-11-11 19:30:10,376 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10" (1/1) ... [2024-11-11 19:30:10,390 INFO L175 MemorySlicer]: Split 23 memory accesses to 2 slices as follows [2, 21]. 91 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0]. The 9 writes are split as follows [0, 9]. [2024-11-11 19:30:10,390 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10" (1/1) ... [2024-11-11 19:30:10,391 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10" (1/1) ... [2024-11-11 19:30:10,396 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10" (1/1) ... [2024-11-11 19:30:10,398 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10" (1/1) ... [2024-11-11 19:30:10,399 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10" (1/1) ... [2024-11-11 19:30:10,400 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10" (1/1) ... [2024-11-11 19:30:10,402 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-11 19:30:10,403 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-11 19:30:10,403 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-11 19:30:10,403 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-11 19:30:10,404 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10" (1/1) ... [2024-11-11 19:30:10,408 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-11 19:30:10,419 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 19:30:10,432 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-11-11 19:30:10,434 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-11-11 19:30:10,469 INFO L130 BoogieDeclarations]: Found specification of procedure is_list_containing_x [2024-11-11 19:30:10,469 INFO L138 BoogieDeclarations]: Found implementation of procedure is_list_containing_x [2024-11-11 19:30:10,469 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-11 19:30:10,469 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-11 19:30:10,469 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-11 19:30:10,469 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-11 19:30:10,469 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-11 19:30:10,469 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-11 19:30:10,470 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-11 19:30:10,470 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-11 19:30:10,470 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-11 19:30:10,470 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-11 19:30:10,470 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-11 19:30:10,470 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-11 19:30:10,470 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-11 19:30:10,470 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-11 19:30:10,557 INFO L238 CfgBuilder]: Building ICFG [2024-11-11 19:30:10,559 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-11 19:30:10,778 INFO L? ?]: Removed 39 outVars from TransFormulas that were not future-live. [2024-11-11 19:30:10,778 INFO L287 CfgBuilder]: Performing block encoding [2024-11-11 19:30:10,794 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-11 19:30:10,794 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-11 19:30:10,794 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.11 07:30:10 BoogieIcfgContainer [2024-11-11 19:30:10,795 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-11 19:30:10,796 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-11 19:30:10,796 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-11 19:30:10,799 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-11 19:30:10,799 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.11 07:30:09" (1/3) ... [2024-11-11 19:30:10,800 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b17194a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.11 07:30:10, skipping insertion in model container [2024-11-11 19:30:10,802 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:30:10" (2/3) ... [2024-11-11 19:30:10,802 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b17194a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.11 07:30:10, skipping insertion in model container [2024-11-11 19:30:10,802 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.11 07:30:10" (3/3) ... [2024-11-11 19:30:10,803 INFO L112 eAbstractionObserver]: Analyzing ICFG dancing.i [2024-11-11 19:30:10,817 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-11 19:30:10,818 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-11 19:30:10,871 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-11 19:30:10,876 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;@575d926a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-11 19:30:10,876 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-11 19:30:10,879 INFO L276 IsEmpty]: Start isEmpty. Operand has 43 states, 33 states have (on average 1.4242424242424243) internal successors, (47), 34 states have internal predecessors, (47), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-11 19:30:10,884 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2024-11-11 19:30:10,885 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:30:10,885 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:30:10,886 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:30:10,891 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:30:10,891 INFO L85 PathProgramCache]: Analyzing trace with hash 329443655, now seen corresponding path program 1 times [2024-11-11 19:30:10,898 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:30:10,898 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [873656250] [2024-11-11 19:30:10,898 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:10,899 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:30:11,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:11,080 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-11 19:30:11,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:11,090 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:30:11,091 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:30:11,091 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [873656250] [2024-11-11 19:30:11,092 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [873656250] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 19:30:11,092 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 19:30:11,092 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-11 19:30:11,093 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1560673913] [2024-11-11 19:30:11,094 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 19:30:11,096 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-11 19:30:11,097 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:30:11,125 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-11 19:30:11,126 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-11 19:30:11,127 INFO L87 Difference]: Start difference. First operand has 43 states, 33 states have (on average 1.4242424242424243) internal successors, (47), 34 states have internal predecessors, (47), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 2 states, 2 states have (on average 8.5) internal successors, (17), 2 states have internal predecessors, (17), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-11 19:30:11,154 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:30:11,158 INFO L93 Difference]: Finished difference Result 79 states and 109 transitions. [2024-11-11 19:30:11,159 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-11 19:30:11,160 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 8.5) internal successors, (17), 2 states have internal predecessors, (17), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 20 [2024-11-11 19:30:11,164 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:30:11,173 INFO L225 Difference]: With dead ends: 79 [2024-11-11 19:30:11,173 INFO L226 Difference]: Without dead ends: 39 [2024-11-11 19:30:11,176 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 4 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-11-11 19:30:11,183 INFO L435 NwaCegarLoop]: 56 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-11 19:30:11,187 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 19:30:11,204 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2024-11-11 19:30:11,218 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2024-11-11 19:30:11,219 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 30 states have (on average 1.3666666666666667) internal successors, (41), 31 states have internal predecessors, (41), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-11 19:30:11,220 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 52 transitions. [2024-11-11 19:30:11,222 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 52 transitions. Word has length 20 [2024-11-11 19:30:11,222 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:30:11,223 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 52 transitions. [2024-11-11 19:30:11,223 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 8.5) internal successors, (17), 2 states have internal predecessors, (17), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-11 19:30:11,223 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 52 transitions. [2024-11-11 19:30:11,224 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-11 19:30:11,225 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:30:11,225 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:30:11,226 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-11 19:30:11,226 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:30:11,227 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:30:11,228 INFO L85 PathProgramCache]: Analyzing trace with hash -654440058, now seen corresponding path program 1 times [2024-11-11 19:30:11,228 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:30:11,228 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1390625898] [2024-11-11 19:30:11,228 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:11,228 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:30:11,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:11,395 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-11 19:30:11,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:11,404 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:30:11,408 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:30:11,408 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1390625898] [2024-11-11 19:30:11,408 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1390625898] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 19:30:11,409 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 19:30:11,409 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-11 19:30:11,409 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [600501637] [2024-11-11 19:30:11,409 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 19:30:11,410 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-11 19:30:11,410 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:30:11,410 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-11 19:30:11,411 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-11 19:30:11,411 INFO L87 Difference]: Start difference. First operand 39 states and 52 transitions. Second operand has 5 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-11 19:30:11,451 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:30:11,452 INFO L93 Difference]: Finished difference Result 47 states and 60 transitions. [2024-11-11 19:30:11,452 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-11 19:30:11,452 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 21 [2024-11-11 19:30:11,452 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:30:11,453 INFO L225 Difference]: With dead ends: 47 [2024-11-11 19:30:11,453 INFO L226 Difference]: Without dead ends: 45 [2024-11-11 19:30:11,454 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 5 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-11-11 19:30:11,454 INFO L435 NwaCegarLoop]: 49 mSDtfsCounter, 3 mSDsluCounter, 140 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 189 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-11 19:30:11,455 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 189 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 18 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 19:30:11,455 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-11-11 19:30:11,459 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 44. [2024-11-11 19:30:11,463 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 33 states have (on average 1.3333333333333333) internal successors, (44), 35 states have internal predecessors, (44), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-11 19:30:11,464 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 57 transitions. [2024-11-11 19:30:11,464 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 57 transitions. Word has length 21 [2024-11-11 19:30:11,465 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:30:11,465 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 57 transitions. [2024-11-11 19:30:11,465 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-11 19:30:11,465 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 57 transitions. [2024-11-11 19:30:11,466 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-11 19:30:11,466 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:30:11,466 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:30:11,466 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-11 19:30:11,467 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:30:11,467 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:30:11,467 INFO L85 PathProgramCache]: Analyzing trace with hash -698021828, now seen corresponding path program 1 times [2024-11-11 19:30:11,467 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:30:11,467 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1772826618] [2024-11-11 19:30:11,468 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:11,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:30:11,487 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:11,552 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-11 19:30:11,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:11,563 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-11-11 19:30:11,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:11,580 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-11 19:30:11,580 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:30:11,580 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1772826618] [2024-11-11 19:30:11,580 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1772826618] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 19:30:11,580 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 19:30:11,580 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-11 19:30:11,581 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [116127804] [2024-11-11 19:30:11,581 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 19:30:11,581 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-11 19:30:11,581 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:30:11,582 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-11 19:30:11,582 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-11 19:30:11,582 INFO L87 Difference]: Start difference. First operand 44 states and 57 transitions. Second operand has 4 states, 4 states have (on average 4.75) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-11 19:30:11,620 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:30:11,620 INFO L93 Difference]: Finished difference Result 90 states and 120 transitions. [2024-11-11 19:30:11,620 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-11 19:30:11,621 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 4.75) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 27 [2024-11-11 19:30:11,621 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:30:11,622 INFO L225 Difference]: With dead ends: 90 [2024-11-11 19:30:11,622 INFO L226 Difference]: Without dead ends: 67 [2024-11-11 19:30:11,622 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2024-11-11 19:30:11,623 INFO L435 NwaCegarLoop]: 49 mSDtfsCounter, 17 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-11 19:30:11,623 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 142 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 19:30:11,624 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-11 19:30:11,629 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 58. [2024-11-11 19:30:11,629 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 46 states have (on average 1.3478260869565217) internal successors, (62), 48 states have internal predecessors, (62), 8 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-11 19:30:11,630 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 77 transitions. [2024-11-11 19:30:11,630 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 77 transitions. Word has length 27 [2024-11-11 19:30:11,630 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:30:11,630 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 77 transitions. [2024-11-11 19:30:11,630 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 4.75) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-11 19:30:11,631 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 77 transitions. [2024-11-11 19:30:11,631 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-11 19:30:11,632 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:30:11,632 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:30:11,632 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-11 19:30:11,632 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:30:11,632 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:30:11,633 INFO L85 PathProgramCache]: Analyzing trace with hash -1050140346, now seen corresponding path program 1 times [2024-11-11 19:30:11,633 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:30:11,633 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1760494911] [2024-11-11 19:30:11,633 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:11,633 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:30:11,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:11,817 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-11 19:30:11,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:11,845 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-11-11 19:30:11,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:11,850 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-11 19:30:11,850 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:30:11,851 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1760494911] [2024-11-11 19:30:11,851 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1760494911] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 19:30:11,851 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1279899373] [2024-11-11 19:30:11,851 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:11,851 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:30:11,851 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 19:30:11,853 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-11-11 19:30:11,854 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-11-11 19:30:11,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:11,966 INFO L256 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-11 19:30:11,970 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 19:30:12,124 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:30:12,126 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 19:30:12,263 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-11 19:30:12,263 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1279899373] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 19:30:12,264 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 19:30:12,264 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 16 [2024-11-11 19:30:12,264 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [862292996] [2024-11-11 19:30:12,264 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 19:30:12,265 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-11 19:30:12,265 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:30:12,265 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-11 19:30:12,265 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2024-11-11 19:30:12,266 INFO L87 Difference]: Start difference. First operand 58 states and 77 transitions. Second operand has 16 states, 16 states have (on average 3.1875) internal successors, (51), 16 states have internal predecessors, (51), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (5), 1 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-11 19:30:12,567 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:30:12,568 INFO L93 Difference]: Finished difference Result 107 states and 149 transitions. [2024-11-11 19:30:12,568 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-11 19:30:12,568 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.1875) internal successors, (51), 16 states have internal predecessors, (51), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (5), 1 states have call predecessors, (5), 4 states have call successors, (5) Word has length 32 [2024-11-11 19:30:12,570 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:30:12,572 INFO L225 Difference]: With dead ends: 107 [2024-11-11 19:30:12,572 INFO L226 Difference]: Without dead ends: 71 [2024-11-11 19:30:12,572 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 57 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=79, Invalid=301, Unknown=0, NotChecked=0, Total=380 [2024-11-11 19:30:12,575 INFO L435 NwaCegarLoop]: 66 mSDtfsCounter, 81 mSDsluCounter, 455 mSDsCounter, 0 mSdLazyCounter, 276 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 521 SdHoareTripleChecker+Invalid, 301 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 276 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-11 19:30:12,576 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [81 Valid, 521 Invalid, 301 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 276 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-11 19:30:12,577 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2024-11-11 19:30:12,592 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 67. [2024-11-11 19:30:12,592 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 52 states have (on average 1.3461538461538463) internal successors, (70), 56 states have internal predecessors, (70), 10 states have call successors, (10), 3 states have call predecessors, (10), 4 states have return successors, (12), 7 states have call predecessors, (12), 9 states have call successors, (12) [2024-11-11 19:30:12,593 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 92 transitions. [2024-11-11 19:30:12,593 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 92 transitions. Word has length 32 [2024-11-11 19:30:12,593 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:30:12,593 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 92 transitions. [2024-11-11 19:30:12,594 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.1875) internal successors, (51), 16 states have internal predecessors, (51), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (5), 1 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-11 19:30:12,594 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 92 transitions. [2024-11-11 19:30:12,596 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-11-11 19:30:12,596 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:30:12,597 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:30:12,622 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-11 19:30:12,797 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-11-11 19:30:12,798 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:30:12,798 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:30:12,798 INFO L85 PathProgramCache]: Analyzing trace with hash 94816722, now seen corresponding path program 1 times [2024-11-11 19:30:12,798 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:30:12,798 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1266713667] [2024-11-11 19:30:12,799 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:12,799 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:30:12,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:12,974 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-11 19:30:12,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:12,977 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-11 19:30:12,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:12,988 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-11 19:30:12,989 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:30:12,989 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1266713667] [2024-11-11 19:30:12,989 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1266713667] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 19:30:12,989 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 19:30:12,989 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-11-11 19:30:12,989 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1666311135] [2024-11-11 19:30:12,990 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 19:30:12,990 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-11 19:30:12,990 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:30:12,990 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-11 19:30:12,991 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-11-11 19:30:12,991 INFO L87 Difference]: Start difference. First operand 67 states and 92 transitions. Second operand has 7 states, 6 states have (on average 4.333333333333333) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-11 19:30:13,055 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:30:13,055 INFO L93 Difference]: Finished difference Result 78 states and 108 transitions. [2024-11-11 19:30:13,055 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-11 19:30:13,055 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 4.333333333333333) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 34 [2024-11-11 19:30:13,056 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:30:13,056 INFO L225 Difference]: With dead ends: 78 [2024-11-11 19:30:13,056 INFO L226 Difference]: Without dead ends: 76 [2024-11-11 19:30:13,057 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-11 19:30:13,058 INFO L435 NwaCegarLoop]: 52 mSDtfsCounter, 3 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 300 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-11 19:30:13,058 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 300 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-11 19:30:13,058 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2024-11-11 19:30:13,065 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 75. [2024-11-11 19:30:13,065 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 57 states have (on average 1.3157894736842106) internal successors, (75), 62 states have internal predecessors, (75), 11 states have call successors, (11), 4 states have call predecessors, (11), 6 states have return successors, (19), 8 states have call predecessors, (19), 10 states have call successors, (19) [2024-11-11 19:30:13,066 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 105 transitions. [2024-11-11 19:30:13,066 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 105 transitions. Word has length 34 [2024-11-11 19:30:13,066 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:30:13,067 INFO L471 AbstractCegarLoop]: Abstraction has 75 states and 105 transitions. [2024-11-11 19:30:13,067 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 4.333333333333333) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-11 19:30:13,067 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 105 transitions. [2024-11-11 19:30:13,068 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-11 19:30:13,068 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:30:13,068 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:30:13,068 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-11-11 19:30:13,069 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:30:13,072 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:30:13,072 INFO L85 PathProgramCache]: Analyzing trace with hash -1911567681, now seen corresponding path program 1 times [2024-11-11 19:30:13,072 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:30:13,072 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1484767674] [2024-11-11 19:30:13,073 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:13,073 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:30:13,092 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:13,381 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-11 19:30:13,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:13,387 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-11-11 19:30:13,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:13,389 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-11-11 19:30:13,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:13,392 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-11 19:30:13,392 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:30:13,392 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1484767674] [2024-11-11 19:30:13,392 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1484767674] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 19:30:13,393 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 19:30:13,393 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-11 19:30:13,393 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1764098137] [2024-11-11 19:30:13,393 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 19:30:13,393 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-11 19:30:13,393 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:30:13,394 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-11 19:30:13,394 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-11 19:30:13,394 INFO L87 Difference]: Start difference. First operand 75 states and 105 transitions. Second operand has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-11 19:30:13,511 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:30:13,511 INFO L93 Difference]: Finished difference Result 126 states and 175 transitions. [2024-11-11 19:30:13,512 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-11 19:30:13,512 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 36 [2024-11-11 19:30:13,512 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:30:13,513 INFO L225 Difference]: With dead ends: 126 [2024-11-11 19:30:13,513 INFO L226 Difference]: Without dead ends: 95 [2024-11-11 19:30:13,514 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2024-11-11 19:30:13,514 INFO L435 NwaCegarLoop]: 49 mSDtfsCounter, 19 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 61 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 170 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 61 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-11 19:30:13,514 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 170 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 61 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-11 19:30:13,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2024-11-11 19:30:13,532 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 85. [2024-11-11 19:30:13,533 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 66 states have (on average 1.3181818181818181) internal successors, (87), 71 states have internal predecessors, (87), 12 states have call successors, (12), 4 states have call predecessors, (12), 6 states have return successors, (22), 9 states have call predecessors, (22), 11 states have call successors, (22) [2024-11-11 19:30:13,535 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 121 transitions. [2024-11-11 19:30:13,538 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 121 transitions. Word has length 36 [2024-11-11 19:30:13,538 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:30:13,538 INFO L471 AbstractCegarLoop]: Abstraction has 85 states and 121 transitions. [2024-11-11 19:30:13,538 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-11 19:30:13,539 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 121 transitions. [2024-11-11 19:30:13,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-11 19:30:13,542 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:30:13,542 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:30:13,542 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-11 19:30:13,543 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:30:13,543 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:30:13,543 INFO L85 PathProgramCache]: Analyzing trace with hash -1692712963, now seen corresponding path program 1 times [2024-11-11 19:30:13,543 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:30:13,543 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [698160409] [2024-11-11 19:30:13,543 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:13,544 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:30:13,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:13,649 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-11 19:30:13,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:13,653 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-11-11 19:30:13,657 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:13,658 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-11-11 19:30:13,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:13,677 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-11 19:30:13,677 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:30:13,678 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [698160409] [2024-11-11 19:30:13,678 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [698160409] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 19:30:13,678 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 19:30:13,678 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-11 19:30:13,678 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [493192215] [2024-11-11 19:30:13,678 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 19:30:13,681 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-11 19:30:13,681 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:30:13,682 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-11 19:30:13,682 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-11 19:30:13,682 INFO L87 Difference]: Start difference. First operand 85 states and 121 transitions. Second operand has 6 states, 5 states have (on average 5.6) internal successors, (28), 4 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-11 19:30:13,715 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:30:13,716 INFO L93 Difference]: Finished difference Result 92 states and 127 transitions. [2024-11-11 19:30:13,716 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-11 19:30:13,716 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 5.6) internal successors, (28), 4 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 36 [2024-11-11 19:30:13,717 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:30:13,718 INFO L225 Difference]: With dead ends: 92 [2024-11-11 19:30:13,720 INFO L226 Difference]: Without dead ends: 85 [2024-11-11 19:30:13,721 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-11 19:30:13,721 INFO L435 NwaCegarLoop]: 53 mSDtfsCounter, 3 mSDsluCounter, 201 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 254 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-11 19:30:13,722 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 254 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 19:30:13,722 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2024-11-11 19:30:13,735 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 73. [2024-11-11 19:30:13,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 58 states have (on average 1.3275862068965518) internal successors, (77), 61 states have internal predecessors, (77), 9 states have call successors, (9), 3 states have call predecessors, (9), 5 states have return successors, (17), 8 states have call predecessors, (17), 8 states have call successors, (17) [2024-11-11 19:30:13,736 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 103 transitions. [2024-11-11 19:30:13,738 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 103 transitions. Word has length 36 [2024-11-11 19:30:13,738 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:30:13,738 INFO L471 AbstractCegarLoop]: Abstraction has 73 states and 103 transitions. [2024-11-11 19:30:13,738 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 5.6) internal successors, (28), 4 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-11 19:30:13,739 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 103 transitions. [2024-11-11 19:30:13,739 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-11-11 19:30:13,741 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:30:13,741 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:30:13,741 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-11-11 19:30:13,742 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:30:13,742 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:30:13,742 INFO L85 PathProgramCache]: Analyzing trace with hash 1295305490, now seen corresponding path program 1 times [2024-11-11 19:30:13,742 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:30:13,742 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [976204943] [2024-11-11 19:30:13,742 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:13,743 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:30:13,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:13,846 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-11 19:30:13,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:13,852 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-11-11 19:30:13,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:13,863 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-11-11 19:30:13,869 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:13,910 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-11 19:30:13,910 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:30:13,910 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [976204943] [2024-11-11 19:30:13,910 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [976204943] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 19:30:13,911 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 19:30:13,911 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-11 19:30:13,911 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [822522958] [2024-11-11 19:30:13,912 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 19:30:13,912 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-11 19:30:13,912 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:30:13,916 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-11 19:30:13,916 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-11 19:30:13,916 INFO L87 Difference]: Start difference. First operand 73 states and 103 transitions. Second operand has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-11 19:30:13,985 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:30:13,986 INFO L93 Difference]: Finished difference Result 123 states and 166 transitions. [2024-11-11 19:30:13,986 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-11 19:30:13,986 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 37 [2024-11-11 19:30:13,986 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:30:13,987 INFO L225 Difference]: With dead ends: 123 [2024-11-11 19:30:13,989 INFO L226 Difference]: Without dead ends: 57 [2024-11-11 19:30:13,989 INFO L434 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-11-11 19:30:13,990 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 14 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-11 19:30:13,990 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 163 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 19:30:13,993 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2024-11-11 19:30:14,001 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 54. [2024-11-11 19:30:14,003 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 41 states have (on average 1.2926829268292683) internal successors, (53), 44 states have internal predecessors, (53), 7 states have call successors, (7), 3 states have call predecessors, (7), 5 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) [2024-11-11 19:30:14,003 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 71 transitions. [2024-11-11 19:30:14,004 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 71 transitions. Word has length 37 [2024-11-11 19:30:14,004 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:30:14,004 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 71 transitions. [2024-11-11 19:30:14,004 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-11 19:30:14,004 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 71 transitions. [2024-11-11 19:30:14,007 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-11 19:30:14,007 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:30:14,007 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:30:14,007 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-11-11 19:30:14,007 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:30:14,008 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:30:14,008 INFO L85 PathProgramCache]: Analyzing trace with hash 569979573, now seen corresponding path program 1 times [2024-11-11 19:30:14,008 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:30:14,010 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1871548022] [2024-11-11 19:30:14,010 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:14,010 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:30:14,049 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:14,134 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-11 19:30:14,136 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:14,147 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-11 19:30:14,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:14,152 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-11 19:30:14,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:14,155 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-11 19:30:14,156 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:30:14,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1871548022] [2024-11-11 19:30:14,156 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1871548022] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 19:30:14,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [266558688] [2024-11-11 19:30:14,156 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:14,156 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:30:14,156 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 19:30:14,158 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-11-11 19:30:14,159 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-11-11 19:30:14,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:14,263 INFO L256 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-11-11 19:30:14,265 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 19:30:14,314 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 25 [2024-11-11 19:30:14,318 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-11 19:30:14,319 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 18 [2024-11-11 19:30:14,327 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 25 [2024-11-11 19:30:14,331 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-11 19:30:14,332 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 13 [2024-11-11 19:30:14,595 INFO L349 Elim1Store]: treesize reduction 12, result has 77.4 percent of original size [2024-11-11 19:30:14,596 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 2 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 37 treesize of output 57 [2024-11-11 19:30:14,606 INFO L349 Elim1Store]: treesize reduction 11, result has 8.3 percent of original size [2024-11-11 19:30:14,606 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 7 [2024-11-11 19:30:14,649 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 9 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-11 19:30:14,649 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 19:30:14,684 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 4 [2024-11-11 19:30:14,773 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 19:30:14,773 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 25 treesize of output 31 [2024-11-11 19:30:14,778 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 19:30:14,778 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 44 treesize of output 28 [2024-11-11 19:30:14,785 INFO L349 Elim1Store]: treesize reduction 18, result has 5.3 percent of original size [2024-11-11 19:30:14,785 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 25 treesize of output 1 [2024-11-11 19:30:14,810 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-11 19:30:14,810 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [266558688] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 19:30:14,810 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 19:30:14,810 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 9, 7] total 16 [2024-11-11 19:30:14,811 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1506155339] [2024-11-11 19:30:14,811 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 19:30:14,811 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-11 19:30:14,811 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:30:14,811 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-11 19:30:14,812 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=202, Unknown=0, NotChecked=0, Total=240 [2024-11-11 19:30:14,812 INFO L87 Difference]: Start difference. First operand 54 states and 71 transitions. Second operand has 16 states, 16 states have (on average 3.875) internal successors, (62), 15 states have internal predecessors, (62), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) [2024-11-11 19:30:15,397 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:30:15,401 INFO L93 Difference]: Finished difference Result 162 states and 215 transitions. [2024-11-11 19:30:15,405 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-11 19:30:15,406 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.875) internal successors, (62), 15 states have internal predecessors, (62), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) Word has length 40 [2024-11-11 19:30:15,406 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:30:15,407 INFO L225 Difference]: With dead ends: 162 [2024-11-11 19:30:15,407 INFO L226 Difference]: Without dead ends: 119 [2024-11-11 19:30:15,408 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=156, Invalid=656, Unknown=0, NotChecked=0, Total=812 [2024-11-11 19:30:15,408 INFO L435 NwaCegarLoop]: 67 mSDtfsCounter, 135 mSDsluCounter, 567 mSDsCounter, 0 mSdLazyCounter, 371 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 139 SdHoareTripleChecker+Valid, 634 SdHoareTripleChecker+Invalid, 401 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 371 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-11 19:30:15,408 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [139 Valid, 634 Invalid, 401 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 371 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-11 19:30:15,409 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2024-11-11 19:30:15,419 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 98. [2024-11-11 19:30:15,419 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 73 states have (on average 1.2876712328767124) internal successors, (94), 79 states have internal predecessors, (94), 14 states have call successors, (14), 6 states have call predecessors, (14), 10 states have return successors, (20), 12 states have call predecessors, (20), 12 states have call successors, (20) [2024-11-11 19:30:15,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 128 transitions. [2024-11-11 19:30:15,420 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 128 transitions. Word has length 40 [2024-11-11 19:30:15,421 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:30:15,421 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 128 transitions. [2024-11-11 19:30:15,421 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.875) internal successors, (62), 15 states have internal predecessors, (62), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) [2024-11-11 19:30:15,421 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 128 transitions. [2024-11-11 19:30:15,421 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-11-11 19:30:15,422 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:30:15,422 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:30:15,438 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-11 19:30:15,625 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-11 19:30:15,626 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:30:15,626 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:30:15,627 INFO L85 PathProgramCache]: Analyzing trace with hash -1413843308, now seen corresponding path program 1 times [2024-11-11 19:30:15,627 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:30:15,627 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [673107713] [2024-11-11 19:30:15,627 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:15,627 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:30:15,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:15,876 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-11 19:30:15,878 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:15,882 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-11 19:30:15,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:15,884 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-11 19:30:15,886 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:15,888 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-11 19:30:15,889 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:15,890 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2024-11-11 19:30:15,890 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:30:15,890 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [673107713] [2024-11-11 19:30:15,890 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [673107713] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 19:30:15,891 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [695579691] [2024-11-11 19:30:15,891 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:15,891 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:30:15,891 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 19:30:15,893 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-11-11 19:30:15,897 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-11-11 19:30:15,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:15,995 INFO L256 TraceCheckSpWp]: Trace formula consists of 273 conjuncts, 53 conjuncts are in the unsatisfiable core [2024-11-11 19:30:15,998 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 19:30:16,050 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-11 19:30:16,051 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 25 [2024-11-11 19:30:16,056 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-11 19:30:16,057 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 18 [2024-11-11 19:30:16,414 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 19 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-11 19:30:16,415 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 19:30:16,472 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [695579691] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 19:30:16,472 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-11 19:30:16,472 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 11] total 19 [2024-11-11 19:30:16,472 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [202696244] [2024-11-11 19:30:16,473 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-11 19:30:16,473 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-11 19:30:16,473 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:30:16,473 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-11 19:30:16,474 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=332, Unknown=0, NotChecked=0, Total=380 [2024-11-11 19:30:16,474 INFO L87 Difference]: Start difference. First operand 98 states and 128 transitions. Second operand has 19 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 19 states have internal predecessors, (54), 5 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2024-11-11 19:30:17,323 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:30:17,323 INFO L93 Difference]: Finished difference Result 182 states and 232 transitions. [2024-11-11 19:30:17,323 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-11 19:30:17,323 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 19 states have internal predecessors, (54), 5 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) Word has length 46 [2024-11-11 19:30:17,324 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:30:17,324 INFO L225 Difference]: With dead ends: 182 [2024-11-11 19:30:17,324 INFO L226 Difference]: Without dead ends: 114 [2024-11-11 19:30:17,325 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 52 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 138 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=222, Invalid=900, Unknown=0, NotChecked=0, Total=1122 [2024-11-11 19:30:17,326 INFO L435 NwaCegarLoop]: 53 mSDtfsCounter, 124 mSDsluCounter, 505 mSDsCounter, 0 mSdLazyCounter, 485 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 124 SdHoareTripleChecker+Valid, 558 SdHoareTripleChecker+Invalid, 519 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 485 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-11 19:30:17,326 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [124 Valid, 558 Invalid, 519 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 485 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-11 19:30:17,326 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2024-11-11 19:30:17,336 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 72. [2024-11-11 19:30:17,336 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 55 states have (on average 1.2727272727272727) internal successors, (70), 59 states have internal predecessors, (70), 9 states have call successors, (9), 4 states have call predecessors, (9), 7 states have return successors, (13), 8 states have call predecessors, (13), 8 states have call successors, (13) [2024-11-11 19:30:17,336 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 92 transitions. [2024-11-11 19:30:17,337 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 92 transitions. Word has length 46 [2024-11-11 19:30:17,337 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:30:17,337 INFO L471 AbstractCegarLoop]: Abstraction has 72 states and 92 transitions. [2024-11-11 19:30:17,337 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 19 states have internal predecessors, (54), 5 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2024-11-11 19:30:17,337 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 92 transitions. [2024-11-11 19:30:17,337 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-11-11 19:30:17,337 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:30:17,338 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:30:17,352 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-11 19:30:17,538 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:30:17,539 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:30:17,539 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:30:17,539 INFO L85 PathProgramCache]: Analyzing trace with hash -596194858, now seen corresponding path program 1 times [2024-11-11 19:30:17,539 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:30:17,539 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1004855033] [2024-11-11 19:30:17,539 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:17,539 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:30:17,561 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:18,102 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-11 19:30:18,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:18,115 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-11 19:30:18,115 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:18,116 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-11 19:30:18,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:18,195 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-11 19:30:18,197 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:18,229 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 15 proven. 5 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-11 19:30:18,229 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:30:18,230 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1004855033] [2024-11-11 19:30:18,230 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1004855033] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 19:30:18,230 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1376243477] [2024-11-11 19:30:18,230 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:30:18,230 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:30:18,230 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 19:30:18,232 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-11-11 19:30:18,233 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-11-11 19:30:18,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:30:18,334 INFO L256 TraceCheckSpWp]: Trace formula consists of 290 conjuncts, 101 conjuncts are in the unsatisfiable core [2024-11-11 19:30:18,337 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 19:30:18,402 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2024-11-11 19:30:18,405 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-11 19:30:18,406 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 16 [2024-11-11 19:30:18,416 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2024-11-11 19:30:18,419 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-11 19:30:18,420 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 16 [2024-11-11 19:30:18,911 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-11 19:30:18,911 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 34 treesize of output 31 [2024-11-11 19:30:18,922 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-11-11 19:30:43,632 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 2 proven. 23 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-11 19:30:43,633 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 19:30:43,729 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 18 [2024-11-11 19:30:44,070 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 18 [2024-11-11 19:30:44,602 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 19:30:44,602 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 218 treesize of output 237 [2024-11-11 19:30:44,619 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 19:30:44,620 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 220 treesize of output 154 [2024-11-11 19:30:44,720 INFO L349 Elim1Store]: treesize reduction 68, result has 48.5 percent of original size [2024-11-11 19:30:44,721 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 5 new quantified variables, introduced 9 case distinctions, treesize of input 774 treesize of output 756 [2024-11-11 19:30:44,756 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 470 treesize of output 445 [2024-11-11 19:30:44,774 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 295 treesize of output 285 [2024-11-11 19:30:44,917 INFO L349 Elim1Store]: treesize reduction 44, result has 70.9 percent of original size [2024-11-11 19:30:44,918 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 7 new quantified variables, introduced 15 case distinctions, treesize of input 862 treesize of output 882 [2024-11-11 19:30:45,000 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 19:30:45,001 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 1 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 5 case distinctions, treesize of input 768 treesize of output 702 [2024-11-11 19:30:45,033 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 353 treesize of output 321 [2024-11-11 19:30:45,097 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 19:30:45,097 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 489 treesize of output 477 [2024-11-11 19:30:47,643 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 326 treesize of output 320 [2024-11-11 19:30:47,945 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 80 treesize of output 74 [2024-11-11 19:30:48,828 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 900 treesize of output 882 [2024-11-11 19:30:51,930 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-11 19:30:51,936 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 19:30:51,937 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 326 treesize of output 306 [2024-11-11 19:30:51,957 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 19:30:51,957 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 287 treesize of output 276 [2024-11-11 19:30:52,252 INFO L349 Elim1Store]: treesize reduction 5, result has 73.7 percent of original size [2024-11-11 19:30:52,253 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 130 treesize of output 122 [2024-11-11 19:30:52,274 INFO L349 Elim1Store]: treesize reduction 9, result has 52.6 percent of original size [2024-11-11 19:30:52,274 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 123 treesize of output 116 [2024-11-11 19:30:52,340 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-11 19:30:52,371 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 19:30:52,371 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 4 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 7 case distinctions, treesize of input 361 treesize of output 359 [2024-11-11 19:30:52,819 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2024-11-11 19:30:52,830 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2024-11-11 19:30:52,843 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 59 treesize of output 43 [2024-11-11 19:30:52,858 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 120 treesize of output 100 [2024-11-11 19:30:52,918 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2024-11-11 19:30:52,937 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2024-11-11 19:30:52,955 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 8 [2024-11-11 19:30:52,977 INFO L349 Elim1Store]: treesize reduction 70, result has 1.4 percent of original size [2024-11-11 19:30:52,978 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 2 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 8 case distinctions, treesize of input 145 treesize of output 1 [2024-11-11 19:30:53,219 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 15 proven. 5 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-11 19:30:53,219 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1376243477] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 19:30:53,219 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 19:30:53,219 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 19, 15] total 46 [2024-11-11 19:30:53,220 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1442759221] [2024-11-11 19:30:53,220 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 19:30:53,220 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2024-11-11 19:30:53,220 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:30:53,221 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2024-11-11 19:30:53,221 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=163, Invalid=1901, Unknown=6, NotChecked=0, Total=2070 [2024-11-11 19:30:53,222 INFO L87 Difference]: Start difference. First operand 72 states and 92 transitions. Second operand has 46 states, 42 states have (on average 2.119047619047619) internal successors, (89), 44 states have internal predecessors, (89), 12 states have call successors, (12), 5 states have call predecessors, (12), 8 states have return successors, (11), 9 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-11 19:30:58,656 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 19:31:06,748 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 19:31:10,757 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 19:31:18,837 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 19:31:22,844 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 19:31:26,880 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 19:31:38,939 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 19:31:42,956 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 19:31:46,975 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0]