/usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.use.bitabs.translation true -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -i ../../../trunk/examples/svcomp/array-patterns/array2_pattern.c -------------------------------------------------------------------------------- This is Ultimate 0.2.4-tmp.fs.bitabs-eval-d9c3e40-m [2023-12-18 20:21:03,010 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-18 20:21:03,077 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf [2023-12-18 20:21:03,080 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-18 20:21:03,081 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-18 20:21:03,102 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-18 20:21:03,102 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-18 20:21:03,102 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-18 20:21:03,103 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-12-18 20:21:03,105 INFO L153 SettingsManager]: * Use memory slicer=true [2023-12-18 20:21:03,106 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-18 20:21:03,106 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-18 20:21:03,106 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-12-18 20:21:03,107 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-12-18 20:21:03,107 INFO L153 SettingsManager]: * Use SBE=true [2023-12-18 20:21:03,107 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-18 20:21:03,108 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-18 20:21:03,108 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-18 20:21:03,108 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-18 20:21:03,108 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-18 20:21:03,108 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-18 20:21:03,109 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-18 20:21:03,109 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-18 20:21:03,109 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-18 20:21:03,109 INFO L153 SettingsManager]: * Allow undefined functions=false [2023-12-18 20:21:03,109 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-18 20:21:03,109 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-18 20:21:03,109 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-18 20:21:03,110 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-18 20:21:03,110 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-12-18 20:21:03,111 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-18 20:21:03,111 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-18 20:21:03,111 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-18 20:21:03,111 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-18 20:21:03,111 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-18 20:21:03,111 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-18 20:21:03,111 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-12-18 20:21:03,111 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-18 20:21:03,112 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-18 20:21:03,112 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-12-18 20:21:03,112 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-18 20:21:03,112 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-12-18 20:21:03,112 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-18 20:21:03,112 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: Use bitabs translation -> true [2023-12-18 20:21:03,291 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-18 20:21:03,306 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-18 20:21:03,308 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-18 20:21:03,309 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-18 20:21:03,309 INFO L274 PluginConnector]: CDTParser initialized [2023-12-18 20:21:03,310 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-patterns/array2_pattern.c [2023-12-18 20:21:04,396 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-18 20:21:04,538 INFO L384 CDTParser]: Found 1 translation units. [2023-12-18 20:21:04,538 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/array-patterns/array2_pattern.c [2023-12-18 20:21:04,544 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a38719023/c34824de564b4b2d999a50b243c58b59/FLAG9f209abc2 [2023-12-18 20:21:04,554 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a38719023/c34824de564b4b2d999a50b243c58b59 [2023-12-18 20:21:04,556 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-18 20:21:04,557 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2023-12-18 20:21:04,568 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-18 20:21:04,568 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-18 20:21:04,572 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-18 20:21:04,573 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,573 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@143deadf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04, skipping insertion in model container [2023-12-18 20:21:04,574 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,593 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-18 20:21:04,706 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/array-patterns/array2_pattern.c[1322,1335] [2023-12-18 20:21:04,717 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-18 20:21:04,723 INFO L202 MainTranslator]: Completed pre-run [2023-12-18 20:21:04,733 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/array-patterns/array2_pattern.c[1322,1335] [2023-12-18 20:21:04,738 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-18 20:21:04,747 INFO L206 MainTranslator]: Completed translation [2023-12-18 20:21:04,748 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04 WrapperNode [2023-12-18 20:21:04,748 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-18 20:21:04,749 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-18 20:21:04,749 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-18 20:21:04,749 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-18 20:21:04,753 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,763 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,781 INFO L138 Inliner]: procedures = 16, calls = 24, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 82 [2023-12-18 20:21:04,781 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-18 20:21:04,782 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-18 20:21:04,782 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-18 20:21:04,782 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-18 20:21:04,790 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,790 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,793 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,803 INFO L175 MemorySlicer]: Split 10 memory accesses to 3 slices as follows [2, 4, 4]. 40 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0]. The 4 writes are split as follows [0, 2, 2]. [2023-12-18 20:21:04,804 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,804 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,808 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,811 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,812 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,813 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,814 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-18 20:21:04,815 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-18 20:21:04,815 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-18 20:21:04,815 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-18 20:21:04,816 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04" (1/1) ... [2023-12-18 20:21:04,820 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-18 20:21:04,828 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:21:04,838 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) [2023-12-18 20:21:04,858 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 [2023-12-18 20:21:04,862 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-18 20:21:04,862 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-12-18 20:21:04,863 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-12-18 20:21:04,863 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-12-18 20:21:04,863 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2023-12-18 20:21:04,863 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2023-12-18 20:21:04,864 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-12-18 20:21:04,865 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2023-12-18 20:21:04,865 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2023-12-18 20:21:04,865 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2023-12-18 20:21:04,865 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-18 20:21:04,865 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-18 20:21:04,865 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2023-12-18 20:21:04,865 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2023-12-18 20:21:04,866 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2023-12-18 20:21:04,866 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-12-18 20:21:04,920 INFO L241 CfgBuilder]: Building ICFG [2023-12-18 20:21:04,923 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-18 20:21:05,048 INFO L282 CfgBuilder]: Performing block encoding [2023-12-18 20:21:05,066 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-18 20:21:05,066 INFO L309 CfgBuilder]: Removed 3 assume(true) statements. [2023-12-18 20:21:05,066 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.12 08:21:05 BoogieIcfgContainer [2023-12-18 20:21:05,066 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-18 20:21:05,076 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-18 20:21:05,076 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-18 20:21:05,078 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-18 20:21:05,078 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.12 08:21:04" (1/3) ... [2023-12-18 20:21:05,079 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@67d6c140 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.12 08:21:05, skipping insertion in model container [2023-12-18 20:21:05,079 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 08:21:04" (2/3) ... [2023-12-18 20:21:05,079 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@67d6c140 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.12 08:21:05, skipping insertion in model container [2023-12-18 20:21:05,079 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.12 08:21:05" (3/3) ... [2023-12-18 20:21:05,080 INFO L112 eAbstractionObserver]: Analyzing ICFG array2_pattern.c [2023-12-18 20:21:05,091 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-18 20:21:05,091 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-18 20:21:05,120 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-18 20:21:05,125 INFO L357 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, mHoare=true, 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;@60dc642d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-18 20:21:05,125 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-18 20:21:05,136 INFO L276 IsEmpty]: Start isEmpty. Operand has 20 states, 15 states have (on average 1.6666666666666667) internal successors, (25), 16 states have internal predecessors, (25), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:21:05,141 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2023-12-18 20:21:05,141 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:21:05,141 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:21:05,142 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:21:05,145 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:21:05,146 INFO L85 PathProgramCache]: Analyzing trace with hash -714475118, now seen corresponding path program 1 times [2023-12-18 20:21:05,151 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:21:05,152 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1959085048] [2023-12-18 20:21:05,152 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:21:05,152 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:21:05,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-18 20:21:05,309 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-12-18 20:21:05,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-18 20:21:05,317 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-18 20:21:05,317 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:21:05,317 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1959085048] [2023-12-18 20:21:05,318 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1959085048] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-18 20:21:05,318 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-18 20:21:05,318 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-18 20:21:05,319 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [219630616] [2023-12-18 20:21:05,320 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-18 20:21:05,322 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-12-18 20:21:05,322 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:21:05,348 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-12-18 20:21:05,348 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-18 20:21:05,350 INFO L87 Difference]: Start difference. First operand has 20 states, 15 states have (on average 1.6666666666666667) internal successors, (25), 16 states have internal predecessors, (25), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-18 20:21:05,379 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-18 20:21:05,379 INFO L93 Difference]: Finished difference Result 38 states and 57 transitions. [2023-12-18 20:21:05,396 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-12-18 20:21:05,398 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2023-12-18 20:21:05,398 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-18 20:21:05,402 INFO L225 Difference]: With dead ends: 38 [2023-12-18 20:21:05,402 INFO L226 Difference]: Without dead ends: 18 [2023-12-18 20:21:05,404 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-18 20:21:05,406 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 4 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 19 SdHoareTripleChecker+Invalid, 4 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 4 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-18 20:21:05,406 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 19 Invalid, 4 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 4 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-18 20:21:05,417 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2023-12-18 20:21:05,425 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2023-12-18 20:21:05,426 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:21:05,427 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 21 transitions. [2023-12-18 20:21:05,427 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 21 transitions. Word has length 14 [2023-12-18 20:21:05,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-18 20:21:05,428 INFO L495 AbstractCegarLoop]: Abstraction has 18 states and 21 transitions. [2023-12-18 20:21:05,428 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-18 20:21:05,428 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 21 transitions. [2023-12-18 20:21:05,429 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2023-12-18 20:21:05,429 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:21:05,429 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:21:05,429 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-12-18 20:21:05,430 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:21:05,430 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:21:05,430 INFO L85 PathProgramCache]: Analyzing trace with hash -1309234247, now seen corresponding path program 1 times [2023-12-18 20:21:05,430 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:21:05,431 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [704694475] [2023-12-18 20:21:05,431 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:21:05,431 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:21:05,457 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-18 20:21:05,457 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [62406534] [2023-12-18 20:21:05,457 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:21:05,457 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:21:05,458 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:21:05,460 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) [2023-12-18 20:21:05,477 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-12-18 20:21:05,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-18 20:21:05,527 INFO L262 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 8 conjunts are in the unsatisfiable core [2023-12-18 20:21:05,530 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-18 20:21:05,596 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-18 20:21:05,597 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-18 20:21:05,597 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:21:05,597 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [704694475] [2023-12-18 20:21:05,597 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-18 20:21:05,597 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [62406534] [2023-12-18 20:21:05,597 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [62406534] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-18 20:21:05,597 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-18 20:21:05,598 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-12-18 20:21:05,598 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2138429035] [2023-12-18 20:21:05,598 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-18 20:21:05,599 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-12-18 20:21:05,599 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:21:05,599 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-12-18 20:21:05,599 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-18 20:21:05,600 INFO L87 Difference]: Start difference. First operand 18 states and 21 transitions. Second operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:21:05,621 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-18 20:21:05,621 INFO L93 Difference]: Finished difference Result 23 states and 26 transitions. [2023-12-18 20:21:05,621 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-12-18 20:21:05,622 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2023-12-18 20:21:05,622 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-18 20:21:05,622 INFO L225 Difference]: With dead ends: 23 [2023-12-18 20:21:05,622 INFO L226 Difference]: Without dead ends: 19 [2023-12-18 20:21:05,623 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-12-18 20:21:05,624 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 3 mSDsluCounter, 25 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-18 20:21:05,624 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 42 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-18 20:21:05,626 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2023-12-18 20:21:05,628 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2023-12-18 20:21:05,628 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 15 states have (on average 1.2) internal successors, (18), 15 states have internal predecessors, (18), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:21:05,629 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 22 transitions. [2023-12-18 20:21:05,629 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 22 transitions. Word has length 21 [2023-12-18 20:21:05,630 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-18 20:21:05,630 INFO L495 AbstractCegarLoop]: Abstraction has 19 states and 22 transitions. [2023-12-18 20:21:05,630 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:21:05,630 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 22 transitions. [2023-12-18 20:21:05,630 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-12-18 20:21:05,631 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:21:05,631 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:21:05,637 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-12-18 20:21:05,834 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:21:05,834 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:21:05,835 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:21:05,835 INFO L85 PathProgramCache]: Analyzing trace with hash -1904091573, now seen corresponding path program 1 times [2023-12-18 20:21:05,835 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:21:05,835 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [69409119] [2023-12-18 20:21:05,835 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:21:05,836 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:21:05,863 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-18 20:21:05,863 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1018846110] [2023-12-18 20:21:05,863 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:21:05,864 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:21:05,864 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:21:05,869 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) [2023-12-18 20:21:05,871 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-12-18 20:21:05,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-18 20:21:05,950 INFO L262 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 4 conjunts are in the unsatisfiable core [2023-12-18 20:21:05,951 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-18 20:21:05,997 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-18 20:21:05,998 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-18 20:21:05,998 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:21:05,998 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [69409119] [2023-12-18 20:21:05,998 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-18 20:21:05,998 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1018846110] [2023-12-18 20:21:05,998 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1018846110] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-18 20:21:05,998 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-18 20:21:05,998 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-18 20:21:05,999 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1864368198] [2023-12-18 20:21:05,999 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-18 20:21:05,999 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-18 20:21:05,999 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:21:06,000 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-18 20:21:06,000 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-18 20:21:06,000 INFO L87 Difference]: Start difference. First operand 19 states and 22 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 5 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:21:06,049 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-18 20:21:06,049 INFO L93 Difference]: Finished difference Result 35 states and 40 transitions. [2023-12-18 20:21:06,049 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-18 20:21:06,050 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 5 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2023-12-18 20:21:06,050 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-18 20:21:06,050 INFO L225 Difference]: With dead ends: 35 [2023-12-18 20:21:06,050 INFO L226 Difference]: Without dead ends: 20 [2023-12-18 20:21:06,051 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2023-12-18 20:21:06,053 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 6 mSDsluCounter, 34 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 52 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-18 20:21:06,054 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 52 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-18 20:21:06,056 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2023-12-18 20:21:06,060 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2023-12-18 20:21:06,060 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 16 states have (on average 1.1875) internal successors, (19), 16 states have internal predecessors, (19), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:21:06,062 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 23 transitions. [2023-12-18 20:21:06,062 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 23 transitions. Word has length 22 [2023-12-18 20:21:06,062 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-18 20:21:06,062 INFO L495 AbstractCegarLoop]: Abstraction has 20 states and 23 transitions. [2023-12-18 20:21:06,063 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 5 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:21:06,063 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 23 transitions. [2023-12-18 20:21:06,063 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2023-12-18 20:21:06,063 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:21:06,064 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:21:06,068 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-12-18 20:21:06,268 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2023-12-18 20:21:06,268 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:21:06,269 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:21:06,269 INFO L85 PathProgramCache]: Analyzing trace with hash 610200211, now seen corresponding path program 1 times [2023-12-18 20:21:06,269 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:21:06,269 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2136831935] [2023-12-18 20:21:06,269 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:21:06,269 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:21:06,289 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-18 20:21:06,289 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2020893698] [2023-12-18 20:21:06,289 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:21:06,289 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:21:06,289 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:21:06,292 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) [2023-12-18 20:21:06,329 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-12-18 20:21:06,367 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-18 20:21:06,368 INFO L262 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 46 conjunts are in the unsatisfiable core [2023-12-18 20:21:06,371 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-18 20:21:06,445 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-18 20:21:06,455 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-18 20:21:06,753 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2023-12-18 20:21:06,753 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 21 [2023-12-18 20:21:06,785 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2023-12-18 20:21:06,786 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 21 [2023-12-18 20:21:06,884 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-18 20:21:06,884 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-18 20:21:07,654 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:21:07,654 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2136831935] [2023-12-18 20:21:07,654 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-18 20:21:07,654 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2020893698] [2023-12-18 20:21:07,655 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2020893698] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-18 20:21:07,655 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-18 20:21:07,655 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2023-12-18 20:21:07,655 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1764181350] [2023-12-18 20:21:07,655 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-18 20:21:07,655 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-12-18 20:21:07,655 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:21:07,656 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-12-18 20:21:07,656 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=347, Unknown=0, NotChecked=0, Total=420 [2023-12-18 20:21:07,657 INFO L87 Difference]: Start difference. First operand 20 states and 23 transitions. Second operand has 16 states, 16 states have (on average 1.1875) internal successors, (19), 13 states have internal predecessors, (19), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:21:12,188 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-18 20:21:12,188 INFO L93 Difference]: Finished difference Result 47 states and 53 transitions. [2023-12-18 20:21:12,188 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2023-12-18 20:21:12,189 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 1.1875) internal successors, (19), 13 states have internal predecessors, (19), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 23 [2023-12-18 20:21:12,189 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-18 20:21:12,190 INFO L225 Difference]: With dead ends: 47 [2023-12-18 20:21:12,190 INFO L226 Difference]: Without dead ends: 28 [2023-12-18 20:21:12,190 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 181 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=179, Invalid=750, Unknown=1, NotChecked=0, Total=930 [2023-12-18 20:21:12,191 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 51 mSDsluCounter, 68 mSDsCounter, 0 mSdLazyCounter, 123 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 141 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 123 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-18 20:21:12,191 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 81 Invalid, 141 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 123 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-18 20:21:12,192 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2023-12-18 20:21:12,195 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 25. [2023-12-18 20:21:12,195 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 20 states have (on average 1.15) internal successors, (23), 20 states have internal predecessors, (23), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:21:12,196 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 27 transitions. [2023-12-18 20:21:12,196 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 27 transitions. Word has length 23 [2023-12-18 20:21:12,196 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-18 20:21:12,196 INFO L495 AbstractCegarLoop]: Abstraction has 25 states and 27 transitions. [2023-12-18 20:21:12,196 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 1.1875) internal successors, (19), 13 states have internal predecessors, (19), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:21:12,196 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 27 transitions. [2023-12-18 20:21:12,197 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2023-12-18 20:21:12,197 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:21:12,197 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:21:12,214 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-12-18 20:21:12,416 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:21:12,417 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:21:12,417 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:21:12,417 INFO L85 PathProgramCache]: Analyzing trace with hash 1243834187, now seen corresponding path program 2 times [2023-12-18 20:21:12,417 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:21:12,417 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1342921403] [2023-12-18 20:21:12,418 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:21:12,418 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:21:12,432 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-18 20:21:12,432 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2071798387] [2023-12-18 20:21:12,433 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-18 20:21:12,433 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:21:12,433 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:21:12,434 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) [2023-12-18 20:21:12,467 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-12-18 20:21:12,485 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-18 20:21:12,486 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-18 20:21:12,486 INFO L262 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 6 conjunts are in the unsatisfiable core [2023-12-18 20:21:12,487 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-18 20:21:12,522 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-18 20:21:12,522 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-18 20:21:12,566 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-18 20:21:12,567 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:21:12,567 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1342921403] [2023-12-18 20:21:12,567 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-18 20:21:12,567 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2071798387] [2023-12-18 20:21:12,567 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2071798387] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-18 20:21:12,567 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-18 20:21:12,568 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2023-12-18 20:21:12,568 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1994899836] [2023-12-18 20:21:12,568 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-18 20:21:12,569 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-12-18 20:21:12,569 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:21:12,569 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-12-18 20:21:12,570 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=49, Unknown=0, NotChecked=0, Total=72 [2023-12-18 20:21:12,570 INFO L87 Difference]: Start difference. First operand 25 states and 27 transitions. Second operand has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-18 20:21:12,643 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-18 20:21:12,643 INFO L93 Difference]: Finished difference Result 30 states and 32 transitions. [2023-12-18 20:21:12,643 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-12-18 20:21:12,643 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2023-12-18 20:21:12,644 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-18 20:21:12,644 INFO L225 Difference]: With dead ends: 30 [2023-12-18 20:21:12,644 INFO L226 Difference]: Without dead ends: 26 [2023-12-18 20:21:12,644 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 36 SyntacticMatches, 3 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=44, Invalid=88, Unknown=0, NotChecked=0, Total=132 [2023-12-18 20:21:12,645 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 25 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 64 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-18 20:21:12,645 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 68 Invalid, 64 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-18 20:21:12,645 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2023-12-18 20:21:12,648 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2023-12-18 20:21:12,648 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 21 states have internal predecessors, (24), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:21:12,649 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 28 transitions. [2023-12-18 20:21:12,649 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 28 transitions. Word has length 24 [2023-12-18 20:21:12,649 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-18 20:21:12,649 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 28 transitions. [2023-12-18 20:21:12,649 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-18 20:21:12,649 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 28 transitions. [2023-12-18 20:21:12,650 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2023-12-18 20:21:12,650 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:21:12,650 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:21:12,656 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-12-18 20:21:12,854 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:21:12,854 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:21:12,855 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:21:12,855 INFO L85 PathProgramCache]: Analyzing trace with hash -68381447, now seen corresponding path program 3 times [2023-12-18 20:21:12,855 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:21:12,855 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [435914194] [2023-12-18 20:21:12,855 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:21:12,855 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:21:12,881 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-18 20:21:12,882 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [508083566] [2023-12-18 20:21:12,882 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-18 20:21:12,882 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:21:12,882 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:21:12,897 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-18 20:21:12,927 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-12-18 20:21:12,978 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-12-18 20:21:12,978 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-18 20:21:12,979 INFO L262 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 55 conjunts are in the unsatisfiable core [2023-12-18 20:21:12,982 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-18 20:21:13,023 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-18 20:21:13,028 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-18 20:21:13,059 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 19 treesize of output 18 [2023-12-18 20:21:13,067 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 19 treesize of output 18 [2023-12-18 20:21:13,424 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2023-12-18 20:21:13,424 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 136 treesize of output 129 [2023-12-18 20:21:13,577 INFO L349 Elim1Store]: treesize reduction 128, result has 26.0 percent of original size [2023-12-18 20:21:13,578 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 1 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 14 case distinctions, treesize of input 50 treesize of output 68 [2023-12-18 20:21:13,641 INFO L349 Elim1Store]: treesize reduction 100, result has 1.0 percent of original size [2023-12-18 20:21:13,641 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 6 new quantified variables, introduced 4 case distinctions, treesize of input 102 treesize of output 167 [2023-12-18 20:21:13,713 INFO L349 Elim1Store]: treesize reduction 64, result has 51.1 percent of original size [2023-12-18 20:21:13,713 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 132 treesize of output 111 [2023-12-18 20:21:15,631 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:21:15,632 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 1 case distinctions, treesize of input 355 treesize of output 291 [2023-12-18 20:21:15,643 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:21:15,644 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 1 case distinctions, treesize of input 294 treesize of output 266 [2023-12-18 20:21:15,906 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-18 20:21:15,907 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-18 20:22:03,925 WARN L293 SmtUtils]: Spent 10.36s on a formula simplification that was a NOOP. DAG size: 167 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-18 20:23:02,867 WARN L293 SmtUtils]: Spent 22.06s on a formula simplification that was a NOOP. DAG size: 173 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-18 20:23:02,978 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 464 treesize of output 452 [2023-12-18 20:23:02,985 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 452 treesize of output 436 [2023-12-18 20:23:03,842 INFO L349 Elim1Store]: treesize reduction 11, result has 42.1 percent of original size [2023-12-18 20:23:03,842 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 133335 treesize of output 131495 [2023-12-18 20:23:04,851 INFO L349 Elim1Store]: treesize reduction 18, result has 71.4 percent of original size [2023-12-18 20:23:04,853 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 46278 treesize of output 43420 [2023-12-18 20:23:33,391 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 6 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-18 20:24:13,696 WARN L293 SmtUtils]: Spent 8.19s on a formula simplification that was a NOOP. DAG size: 3 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-18 20:26:36,264 WARN L667 sPolynomialRelations]: Constructing 64(two to the power of 6 dual juncts. [2023-12-18 20:26:47,407 WARN L293 SmtUtils]: Spent 8.00s on a formula simplification that was a NOOP. DAG size: 7 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-18 20:27:13,087 WARN L667 sPolynomialRelations]: Constructing 64(two to the power of 6 dual juncts. [2023-12-18 20:27:33,041 WARN L293 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 3 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-18 20:27:45,411 WARN L293 SmtUtils]: Spent 7.36s on a formula simplification that was a NOOP. DAG size: 3 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-18 20:27:53,429 WARN L293 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-18 20:28:06,261 WARN L293 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 3 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-18 20:28:09,071 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 222 treesize of output 214 [2023-12-18 20:28:09,075 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 214 treesize of output 206 [2023-12-18 20:28:09,082 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 1662 treesize of output 1641 [2023-12-18 20:28:20,994 WARN L293 SmtUtils]: Spent 11.90s on a formula simplification. DAG size of input: 8 DAG size of output: 4 (called from [L 346] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.Elim1Store.elim1) [2023-12-18 20:28:20,994 INFO L349 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2023-12-18 20:28:20,995 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 516 treesize of output 487 [2023-12-18 20:28:33,083 WARN L293 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-18 20:28:41,664 WARN L293 SmtUtils]: Spent 8.57s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-18 20:28:55,078 WARN L293 SmtUtils]: Spent 5.06s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-18 20:29:12,730 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 222 treesize of output 214 [2023-12-18 20:29:12,736 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 214 treesize of output 206 [2023-12-18 20:29:12,745 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 2102 treesize of output 2075 [2023-12-18 20:29:12,765 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 1385 treesize of output 1322 [2023-12-18 20:29:13,264 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 222 treesize of output 214 [2023-12-18 20:29:13,272 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 328 treesize of output 312 [2023-12-18 20:29:13,315 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2023-12-18 20:29:13,316 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 1824 treesize of output 1 [2023-12-18 20:29:13,735 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 3 proven. 5 refuted. 1 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-18 20:29:13,735 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:29:13,735 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [435914194] [2023-12-18 20:29:13,735 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-18 20:29:13,736 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [508083566] [2023-12-18 20:29:13,736 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [508083566] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-18 20:29:13,736 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-18 20:29:13,736 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 29 [2023-12-18 20:29:13,736 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1250177291] [2023-12-18 20:29:13,736 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-18 20:29:13,736 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2023-12-18 20:29:13,736 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:29:13,737 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2023-12-18 20:29:13,737 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=684, Unknown=8, NotChecked=0, Total=812 [2023-12-18 20:29:13,737 INFO L87 Difference]: Start difference. First operand 26 states and 28 transitions. Second operand has 29 states, 27 states have (on average 1.5185185185185186) internal successors, (41), 26 states have internal predecessors, (41), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-12-18 20:29:23,491 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:29:25,855 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.27s for a HTC check with result VALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:29:34,116 WARN L876 $PredicateComparison]: unable to prove that (let ((.cse0 (= |c_ULTIMATE.start_main_~count~0#1| 0)) (.cse15 (not (= c_~ARR_SIZE~0 2))) (.cse17 (* (- 1) |c_ULTIMATE.start_main_~num~0#1| |c_ULTIMATE.start_main_~num~0#1|)) (.cse18 (* 4294967294 |c_ULTIMATE.start_main_~num~0#1|)) (.cse16 (* (- 18446744065119617025) |c_ULTIMATE.start_main_~num~0#1|)) (.cse6 (* (- 1) |c_ULTIMATE.start_main_~sum~0#1|)) (.cse2 (* |c_ULTIMATE.start_main_~sum~0#1| 4294967295)) (.cse8 (+ |c_ULTIMATE.start_main_~#array1~0#1.offset| 4)) (.cse10 (+ |c_ULTIMATE.start_main_~#array2~0#1.offset| 4)) (.cse11 (select |c_#memory_int#2| |c_ULTIMATE.start_main_~#array2~0#1.base|)) (.cse13 (select |c_#memory_int#1| |c_ULTIMATE.start_main_~#array1~0#1.base|))) (and (<= c_~ARR_SIZE~0 32767) .cse0 (or (let ((.cse7 (let ((.cse14 (+ |c_ULTIMATE.start_main_~#array1~0#1.offset| (* |c_ULTIMATE.start_main_~index~0#1| 4)))) (store .cse13 .cse14 (+ (* |c_ULTIMATE.start_main_~index~0#1| |c_ULTIMATE.start_main_~num~0#1| |c_ULTIMATE.start_main_~num~0#1|) (select .cse13 .cse14))))) (.cse9 (let ((.cse12 (+ |c_ULTIMATE.start_main_~#array2~0#1.offset| (* (mod (+ (* 4294967295 |c_ULTIMATE.start_main_~index~0#1|) 1) 4294967296) 4)))) (store .cse11 .cse12 (+ (select .cse11 .cse12) (* |c_ULTIMATE.start_main_~index~0#1| |c_ULTIMATE.start_main_~num~0#1|)))))) (let ((.cse5 (select .cse9 |c_ULTIMATE.start_main_~#array2~0#1.offset|)) (.cse1 (select .cse9 .cse10)) (.cse4 (select .cse7 .cse8)) (.cse3 (select .cse7 |c_ULTIMATE.start_main_~#array1~0#1.offset|))) (and (= (mod (+ (* .cse1 4294967295) .cse2 (* .cse3 4294967295) (* .cse4 4294967295) (* 4294967295 .cse5)) 4294967296) 0) (= (div (+ (* (- 1) .cse5) (* (- 1) .cse1) .cse6 (* (- 1) .cse4) (* (- 1) .cse3)) 4294967296) 0)))) .cse15) (= |c_ULTIMATE.start_main_~#array2~0#1.offset| 0) (= |c_ULTIMATE.start_main_~#array1~0#1.offset| 0) (or (and (= (+ (div (+ .cse6 .cse16 .cse17) 4294967296) .cse18) 0) (= (div .cse6 4294967296) 0) .cse0 (= (mod .cse2 4294967296) 0)) .cse15) (or .cse15 (let ((.cse55 (select .cse11 .cse10)) (.cse54 (select .cse11 |c_ULTIMATE.start_main_~#array2~0#1.offset|))) (let ((.cse24 (* (- 1) .cse54)) (.cse25 (* (- 1) .cse55)) (.cse37 (* 4294967295 .cse55)) (.cse27 (select .cse13 |c_ULTIMATE.start_main_~#array1~0#1.offset|)) (.cse39 (* 4294967295 .cse54)) (.cse40 (* 4294967295 |c_ULTIMATE.start_main_~num~0#1|)) (.cse26 (select .cse13 .cse8))) (and (forall ((v_z_6 Int)) (or (< 4294967295 v_z_6) (< v_z_6 0) (= 4294967295 v_z_6) (forall ((v_y_6 Int)) (let ((.cse19 (+ (* 4294967295 v_z_6) (* v_y_6 4294967296)))) (or (< .cse19 0) (= (mod (let ((.cse20 (let ((.cse23 (+ |c_ULTIMATE.start_main_~#array2~0#1.offset| (* v_z_6 4) 4))) (store .cse11 .cse23 (+ (select .cse11 .cse23) (* .cse19 |c_ULTIMATE.start_main_~num~0#1|))))) (.cse21 (let ((.cse22 (+ |c_ULTIMATE.start_main_~#array1~0#1.offset| (* 17179869184 v_y_6) (* 17179869180 v_z_6)))) (store .cse13 .cse22 (+ (* .cse19 |c_ULTIMATE.start_main_~num~0#1| |c_ULTIMATE.start_main_~num~0#1|) (select .cse13 .cse22)))))) (+ (* (select .cse20 |c_ULTIMATE.start_main_~#array2~0#1.offset|) 4294967295) (* (select .cse20 .cse10) 4294967295) (* 4294967295 (select .cse21 .cse8)) .cse2 (* (select .cse21 |c_ULTIMATE.start_main_~#array1~0#1.offset|) 4294967295))) 4294967296) 0) (< 1 .cse19)))))) (= (+ (div (+ .cse24 .cse6 .cse16 .cse25 .cse17 (* (- 1) .cse26) (* (- 1) .cse27)) 4294967296) .cse18) 0) (forall ((v_z_7 Int)) (or (forall ((v_y_7 Int)) (let ((.cse36 (* v_y_7 4294967296))) (let ((.cse32 (* 17179869184 v_y_7)) (.cse31 (+ .cse36 (* 4294967295 v_z_7)))) (or (= 0 (div (let ((.cse28 (let ((.cse33 (+ |c_ULTIMATE.start_main_~#array2~0#1.offset| 4 (* v_z_7 4)))) (store .cse11 .cse33 (+ (select .cse11 .cse33) (* .cse31 |c_ULTIMATE.start_main_~num~0#1|))))) (.cse29 (let ((.cse30 (+ |c_ULTIMATE.start_main_~#array1~0#1.offset| (* 17179869180 v_z_7) .cse32))) (store .cse13 .cse30 (+ (* .cse31 |c_ULTIMATE.start_main_~num~0#1| |c_ULTIMATE.start_main_~num~0#1|) (select .cse13 .cse30)))))) (+ (* (- 1) (select .cse28 |c_ULTIMATE.start_main_~#array2~0#1.offset|)) (* (- 1) (select .cse29 |c_ULTIMATE.start_main_~#array1~0#1.offset|)) (* (- 1) (select .cse28 .cse10)) .cse6 (* (- 1) (select .cse29 .cse8)))) 4294967296)) (= (* v_y_7 |c_ULTIMATE.start_main_~num~0#1|) (div (let ((.cse34 (let ((.cse35 (+ |c_ULTIMATE.start_main_~#array1~0#1.offset| .cse32 73786976260478468100))) (store .cse13 .cse35 (+ (select .cse13 .cse35) (* (+ .cse36 18446744065119617025) |c_ULTIMATE.start_main_~num~0#1| |c_ULTIMATE.start_main_~num~0#1|)))))) (+ (* (- 1) (select .cse34 |c_ULTIMATE.start_main_~#array1~0#1.offset|)) .cse24 .cse6 .cse16 .cse25 (* (- 1) (select .cse34 .cse8)))) 4294967296)) (< .cse31 0) (< 1 .cse31))))) (< v_z_7 0) (< 4294967295 v_z_7))) (forall ((v_z_6 Int)) (or (< 4294967295 v_z_6) (< v_z_6 0) (forall ((v_y_6 Int)) (let ((.cse42 (* v_y_6 4294967296))) (let ((.cse43 (* 17179869184 v_y_6)) (.cse44 (+ (* 4294967295 v_z_6) .cse42))) (or (= (mod (let ((.cse38 (let ((.cse41 (+ |c_ULTIMATE.start_main_~#array1~0#1.offset| .cse43 73786976260478468100))) (store .cse13 .cse41 (+ (* (+ .cse42 18446744065119617025) |c_ULTIMATE.start_main_~num~0#1| |c_ULTIMATE.start_main_~num~0#1|) (select .cse13 .cse41)))))) (+ .cse37 .cse2 (* (select .cse38 |c_ULTIMATE.start_main_~#array1~0#1.offset|) 4294967295) .cse39 .cse40 (* 4294967295 (select .cse38 .cse8)))) 4294967296) 0) (< .cse44 0) (= (mod (let ((.cse45 (let ((.cse48 (+ |c_ULTIMATE.start_main_~#array2~0#1.offset| (* v_z_6 4) 4))) (store .cse11 .cse48 (+ (select .cse11 .cse48) (* .cse44 |c_ULTIMATE.start_main_~num~0#1|))))) (.cse46 (let ((.cse47 (+ |c_ULTIMATE.start_main_~#array1~0#1.offset| .cse43 (* 17179869180 v_z_6)))) (store .cse13 .cse47 (+ (* .cse44 |c_ULTIMATE.start_main_~num~0#1| |c_ULTIMATE.start_main_~num~0#1|) (select .cse13 .cse47)))))) (+ (* (select .cse45 |c_ULTIMATE.start_main_~#array2~0#1.offset|) 4294967295) (* (select .cse45 .cse10) 4294967295) (* 4294967295 (select .cse46 .cse8)) .cse2 (* (select .cse46 |c_ULTIMATE.start_main_~#array1~0#1.offset|) 4294967295))) 4294967296) 0) (< 1 .cse44))))))) (forall ((v_z_7 Int)) (or (= 4294967295 v_z_7) (< v_z_7 0) (< 4294967295 v_z_7) (forall ((v_y_7 Int)) (let ((.cse52 (+ (* v_y_7 4294967296) (* 4294967295 v_z_7)))) (or (= 0 (div (let ((.cse49 (let ((.cse53 (+ |c_ULTIMATE.start_main_~#array2~0#1.offset| 4 (* v_z_7 4)))) (store .cse11 .cse53 (+ (select .cse11 .cse53) (* .cse52 |c_ULTIMATE.start_main_~num~0#1|))))) (.cse50 (let ((.cse51 (+ |c_ULTIMATE.start_main_~#array1~0#1.offset| (* 17179869180 v_z_7) (* 17179869184 v_y_7)))) (store .cse13 .cse51 (+ (* .cse52 |c_ULTIMATE.start_main_~num~0#1| |c_ULTIMATE.start_main_~num~0#1|) (select .cse13 .cse51)))))) (+ (* (- 1) (select .cse49 |c_ULTIMATE.start_main_~#array2~0#1.offset|)) (* (- 1) (select .cse50 |c_ULTIMATE.start_main_~#array1~0#1.offset|)) (* (- 1) (select .cse49 .cse10)) .cse6 (* (- 1) (select .cse50 .cse8)))) 4294967296)) (< .cse52 0) (< 1 .cse52)))))) (= (mod (+ .cse37 (* .cse27 4294967295) .cse2 .cse39 .cse40 (* 4294967295 .cse26) (* 4294967295 |c_ULTIMATE.start_main_~num~0#1| |c_ULTIMATE.start_main_~num~0#1|)) 4294967296) 0))))) (= |c_ULTIMATE.start_main_~sum~0#1| 0) (let ((.cse72 (select .cse13 4)) (.cse59 (select .cse11 4)) (.cse70 (select .cse11 0))) (let ((.cse69 (= 0 .cse70)) (.cse66 (= 0 .cse59)) (.cse61 (= .cse72 1)) (.cse68 (= .cse72 0))) (or (and (let ((.cse65 (mod (+ c_~ARR_SIZE~0 4294967295) 4294967296))) (let ((.cse60 (* .cse65 4294967295))) (let ((.cse56 (* c_~ARR_SIZE~0 4294967295)) (.cse58 (+ c_~ARR_SIZE~0 .cse60))) (or (let ((.cse57 (* (div (+ (- 18446744073709551614) .cse60) 4294967296) 4294967296))) (and (= (mod (+ 3 .cse56) 4294967296) 0) (<= (+ .cse57 18446744073709551616) .cse58) (= (+ .cse57 18446744073709551615 .cse59) .cse60) .cse61)) (and (exists ((v_z_2 Int) (v_y_2 Int)) (let ((.cse62 (* v_y_2 4294967296)) (.cse63 (* 4294967295 v_z_2)) (.cse64 (+ .cse65 v_z_2))) (and (= (+ .cse62 .cse63) 1) (<= 0 v_z_2) (not (= .cse64 4294967297)) (<= v_z_2 4294967295) (<= (+ .cse62 .cse63 1) c_~ARR_SIZE~0) (not (= .cse64 4294967296))))) .cse66 .cse61) (let ((.cse67 (* (div (+ (* (- 1) .cse59) .cse60 (- 18446744073709551615)) 4294967296) 4294967296))) (and (<= .cse60 (+ 18446744073709551615 .cse67)) (= (mod (+ 2 (* 4294967295 .cse59) .cse56) 4294967296) 0) .cse68 (<= (+ 18446744073709551616 .cse67) .cse58) (not (= (+ 18446744073709551614 .cse67) .cse60)))))))) .cse69) (let ((.cse71 (= (+ .cse70 1) 0))) (and (or .cse69 (= (mod (+ c_~ARR_SIZE~0 4294967295 .cse70) 4294967296) 0)) .cse66 (or (not .cse71) .cse61) (or .cse71 .cse68) (<= .cse70 0) (<= 1 (+ c_~ARR_SIZE~0 .cse70))))))) (= (select .cse13 0) 0))) is different from true [2023-12-18 20:29:38,547 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-18 20:29:53,453 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:30:01,789 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:30:05,966 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:30:19,687 WARN L293 SmtUtils]: Spent 5.36s on a formula simplification. DAG size of input: 362 DAG size of output: 140 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-18 20:30:24,185 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.21s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:30:28,195 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:30:40,702 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:30:44,735 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:30:52,024 WARN L293 SmtUtils]: Spent 6.27s on a formula simplification. DAG size of input: 180 DAG size of output: 139 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-18 20:30:59,119 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:31:03,133 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:31:15,942 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:31:19,124 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.18s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:31:26,768 WARN L293 SmtUtils]: Spent 5.76s on a formula simplification that was a NOOP. DAG size: 127 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-18 20:31:31,548 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.68s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:31:52,293 WARN L293 SmtUtils]: Spent 12.79s on a formula simplification. DAG size of input: 295 DAG size of output: 148 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-18 20:32:06,421 WARN L293 SmtUtils]: Spent 7.92s on a formula simplification. DAG size of input: 307 DAG size of output: 157 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-18 20:32:08,392 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.59s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:32:17,329 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.69s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:32:23,808 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:32:24,962 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.14s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-18 20:32:33,960 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-18 20:32:38,218 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.51s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:32:42,226 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:32:53,508 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:32:57,733 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:33:01,744 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:33:03,014 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.27s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2023-12-18 20:33:13,811 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:33:19,145 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.24s for a HTC check with result VALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:33:23,185 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:33:25,247 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.94s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-18 20:33:33,857 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-12-18 20:33:49,302 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:33:51,049 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.37s for a HTC check with result VALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:34:47,392 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:34:49,643 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.23s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:34:53,652 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2023-12-18 20:34:58,031 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-12-18 20:34:58,186 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-18 20:34:58,187 INFO L93 Difference]: Finished difference Result 116 states and 139 transitions. [2023-12-18 20:34:58,187 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 62 states. [2023-12-18 20:34:58,187 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 27 states have (on average 1.5185185185185186) internal successors, (41), 26 states have internal predecessors, (41), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 25 [2023-12-18 20:34:58,188 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-18 20:34:58,189 INFO L225 Difference]: With dead ends: 116 [2023-12-18 20:34:58,189 INFO L226 Difference]: Without dead ends: 106 [2023-12-18 20:34:58,191 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 21 SyntacticMatches, 2 SemanticMatches, 81 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 1986 ImplicationChecksByTransitivity, 281.3s TimeCoverageRelationStatistics Valid=1187, Invalid=5431, Unknown=28, NotChecked=160, Total=6806 [2023-12-18 20:34:58,191 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 307 mSDsluCounter, 220 mSDsCounter, 0 mSdLazyCounter, 536 mSolverCounterSat, 121 mSolverCounterUnsat, 24 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 146.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 307 SdHoareTripleChecker+Valid, 241 SdHoareTripleChecker+Invalid, 706 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 121 IncrementalHoareTripleChecker+Valid, 536 IncrementalHoareTripleChecker+Invalid, 24 IncrementalHoareTripleChecker+Unknown, 25 IncrementalHoareTripleChecker+Unchecked, 146.7s IncrementalHoareTripleChecker+Time [2023-12-18 20:34:58,191 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [307 Valid, 241 Invalid, 706 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [121 Valid, 536 Invalid, 24 Unknown, 25 Unchecked, 146.7s Time] [2023-12-18 20:34:58,192 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2023-12-18 20:34:58,218 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 48. [2023-12-18 20:34:58,219 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 38 states have (on average 1.2105263157894737) internal successors, (46), 39 states have internal predecessors, (46), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-18 20:34:58,219 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 58 transitions. [2023-12-18 20:34:58,219 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 58 transitions. Word has length 25 [2023-12-18 20:34:58,219 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-18 20:34:58,220 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 58 transitions. [2023-12-18 20:34:58,220 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 27 states have (on average 1.5185185185185186) internal successors, (41), 26 states have internal predecessors, (41), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-12-18 20:34:58,220 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 58 transitions. [2023-12-18 20:34:58,220 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2023-12-18 20:34:58,220 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:34:58,220 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:34:58,228 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-12-18 20:34:58,421 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:34:58,421 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:34:58,422 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:34:58,422 INFO L85 PathProgramCache]: Analyzing trace with hash -2092360437, now seen corresponding path program 4 times [2023-12-18 20:34:58,422 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:34:58,422 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [967166839] [2023-12-18 20:34:58,422 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:34:58,422 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:34:58,443 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-18 20:34:58,443 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [865603794] [2023-12-18 20:34:58,443 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-18 20:34:58,443 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:34:58,443 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:34:58,445 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-18 20:34:58,446 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-12-18 20:34:58,512 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-18 20:34:58,512 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-18 20:34:58,513 INFO L262 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 8 conjunts are in the unsatisfiable core [2023-12-18 20:34:58,514 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-18 20:34:58,576 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-18 20:34:58,576 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-18 20:34:58,626 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-18 20:34:58,626 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:34:58,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [967166839] [2023-12-18 20:34:58,627 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-18 20:34:58,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [865603794] [2023-12-18 20:34:58,627 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [865603794] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-18 20:34:58,627 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-18 20:34:58,627 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 12 [2023-12-18 20:34:58,627 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1039391459] [2023-12-18 20:34:58,627 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-18 20:34:58,627 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-12-18 20:34:58,627 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:34:58,628 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-12-18 20:34:58,628 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=93, Unknown=0, NotChecked=0, Total=132 [2023-12-18 20:34:58,628 INFO L87 Difference]: Start difference. First operand 48 states and 58 transitions. Second operand has 12 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 12 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-18 20:34:58,774 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-18 20:34:58,774 INFO L93 Difference]: Finished difference Result 92 states and 106 transitions. [2023-12-18 20:34:58,775 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-18 20:34:58,775 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 12 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 26 [2023-12-18 20:34:58,775 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-18 20:34:58,776 INFO L225 Difference]: With dead ends: 92 [2023-12-18 20:34:58,776 INFO L226 Difference]: Without dead ends: 83 [2023-12-18 20:34:58,777 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 36 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=74, Invalid=166, Unknown=0, NotChecked=0, Total=240 [2023-12-18 20:34:58,777 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 54 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 92 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-18 20:34:58,777 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 101 Invalid, 92 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-18 20:34:58,778 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2023-12-18 20:34:58,812 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 72. [2023-12-18 20:34:58,812 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 57 states have (on average 1.1578947368421053) internal successors, (66), 58 states have internal predecessors, (66), 9 states have call successors, (9), 5 states have call predecessors, (9), 5 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-18 20:34:58,813 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 84 transitions. [2023-12-18 20:34:58,813 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 84 transitions. Word has length 26 [2023-12-18 20:34:58,813 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-18 20:34:58,813 INFO L495 AbstractCegarLoop]: Abstraction has 72 states and 84 transitions. [2023-12-18 20:34:58,813 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 12 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-18 20:34:58,813 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 84 transitions. [2023-12-18 20:34:58,814 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-12-18 20:34:58,814 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:34:58,814 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:34:58,823 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-12-18 20:34:59,018 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:34:59,019 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:34:59,019 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:34:59,019 INFO L85 PathProgramCache]: Analyzing trace with hash -1883847341, now seen corresponding path program 5 times [2023-12-18 20:34:59,019 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:34:59,019 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1158409187] [2023-12-18 20:34:59,019 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:34:59,020 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:34:59,032 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-18 20:34:59,032 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [442940280] [2023-12-18 20:34:59,032 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2023-12-18 20:34:59,032 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:34:59,032 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:34:59,033 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-18 20:34:59,049 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-12-18 20:34:59,184 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2023-12-18 20:34:59,185 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-18 20:34:59,186 WARN L260 TraceCheckSpWp]: Trace formula consists of 142 conjuncts, 71 conjunts are in the unsatisfiable core [2023-12-18 20:34:59,194 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-18 20:34:59,257 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-18 20:34:59,265 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-18 20:34:59,301 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 19 treesize of output 18 [2023-12-18 20:34:59,308 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 19 treesize of output 18 [2023-12-18 20:34:59,375 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:34:59,375 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2023-12-18 20:34:59,388 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:34:59,389 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2023-12-18 20:34:59,899 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2023-12-18 20:34:59,900 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 144 treesize of output 133 [2023-12-18 20:35:00,161 INFO L349 Elim1Store]: treesize reduction 197, result has 23.9 percent of original size [2023-12-18 20:35:00,161 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 3 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 27 case distinctions, treesize of input 64 treesize of output 91 [2023-12-18 20:35:00,213 INFO L349 Elim1Store]: treesize reduction 141, result has 0.7 percent of original size [2023-12-18 20:35:00,213 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 5 select indices, 5 select index equivalence classes, 7 disjoint index pairs (out of 10 index pairs), introduced 7 new quantified variables, introduced 6 case distinctions, treesize of input 101 treesize of output 165 [2023-12-18 20:35:00,297 INFO L349 Elim1Store]: treesize reduction 139, result has 24.5 percent of original size [2023-12-18 20:35:00,298 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 5 select indices, 5 select index equivalence classes, 7 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 6 case distinctions, treesize of input 129 treesize of output 90 [2023-12-18 20:35:00,915 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:00,916 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 3 case distinctions, treesize of input 118 treesize of output 86 [2023-12-18 20:35:00,932 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:00,932 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 3 case distinctions, treesize of input 86 treesize of output 50 [2023-12-18 20:35:00,974 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-18 20:35:00,974 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-18 20:35:05,058 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:35:05,058 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1158409187] [2023-12-18 20:35:05,058 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-18 20:35:05,058 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [442940280] [2023-12-18 20:35:05,058 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [442940280] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-18 20:35:05,058 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-18 20:35:05,058 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2023-12-18 20:35:05,059 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [54237468] [2023-12-18 20:35:05,059 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-18 20:35:05,059 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-12-18 20:35:05,059 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:35:05,059 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-12-18 20:35:05,060 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=697, Unknown=0, NotChecked=0, Total=812 [2023-12-18 20:35:05,060 INFO L87 Difference]: Start difference. First operand 72 states and 84 transitions. Second operand has 22 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 18 states have internal predecessors, (23), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:35:07,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-18 20:35:07,978 INFO L93 Difference]: Finished difference Result 95 states and 110 transitions. [2023-12-18 20:35:07,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2023-12-18 20:35:07,978 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 18 states have internal predecessors, (23), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 27 [2023-12-18 20:35:07,978 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-18 20:35:07,979 INFO L225 Difference]: With dead ends: 95 [2023-12-18 20:35:07,979 INFO L226 Difference]: Without dead ends: 91 [2023-12-18 20:35:07,979 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 375 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=236, Invalid=1404, Unknown=0, NotChecked=0, Total=1640 [2023-12-18 20:35:07,980 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 55 mSDsluCounter, 169 mSDsCounter, 0 mSdLazyCounter, 369 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 380 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 369 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-12-18 20:35:07,980 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 186 Invalid, 380 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 369 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-12-18 20:35:07,982 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2023-12-18 20:35:08,029 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 80. [2023-12-18 20:35:08,030 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 64 states have (on average 1.15625) internal successors, (74), 64 states have internal predecessors, (74), 9 states have call successors, (9), 6 states have call predecessors, (9), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-18 20:35:08,030 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 92 transitions. [2023-12-18 20:35:08,030 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 92 transitions. Word has length 27 [2023-12-18 20:35:08,031 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-18 20:35:08,031 INFO L495 AbstractCegarLoop]: Abstraction has 80 states and 92 transitions. [2023-12-18 20:35:08,032 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 18 states have internal predecessors, (23), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:35:08,032 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 92 transitions. [2023-12-18 20:35:08,032 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-12-18 20:35:08,032 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:35:08,032 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:35:08,039 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-12-18 20:35:08,239 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:35:08,242 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:35:08,242 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:35:08,242 INFO L85 PathProgramCache]: Analyzing trace with hash 1757738993, now seen corresponding path program 6 times [2023-12-18 20:35:08,242 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:35:08,242 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1819057076] [2023-12-18 20:35:08,242 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:35:08,243 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:35:08,253 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-18 20:35:08,254 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [281013891] [2023-12-18 20:35:08,254 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2023-12-18 20:35:08,254 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:35:08,254 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:35:08,255 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-18 20:35:08,276 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-12-18 20:35:08,345 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2023-12-18 20:35:08,346 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-18 20:35:08,347 INFO L262 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 10 conjunts are in the unsatisfiable core [2023-12-18 20:35:08,348 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-18 20:35:08,416 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-18 20:35:08,416 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-18 20:35:08,479 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-18 20:35:08,480 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:35:08,480 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1819057076] [2023-12-18 20:35:08,480 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-18 20:35:08,480 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [281013891] [2023-12-18 20:35:08,480 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [281013891] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-18 20:35:08,480 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-18 20:35:08,480 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 15 [2023-12-18 20:35:08,480 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [973423031] [2023-12-18 20:35:08,480 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-18 20:35:08,480 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-12-18 20:35:08,480 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:35:08,481 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-12-18 20:35:08,481 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=151, Unknown=0, NotChecked=0, Total=210 [2023-12-18 20:35:08,481 INFO L87 Difference]: Start difference. First operand 80 states and 92 transitions. Second operand has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 15 states have internal predecessors, (29), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-18 20:35:08,708 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-18 20:35:08,708 INFO L93 Difference]: Finished difference Result 117 states and 127 transitions. [2023-12-18 20:35:08,708 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2023-12-18 20:35:08,708 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 15 states have internal predecessors, (29), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 28 [2023-12-18 20:35:08,709 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-18 20:35:08,709 INFO L225 Difference]: With dead ends: 117 [2023-12-18 20:35:08,709 INFO L226 Difference]: Without dead ends: 107 [2023-12-18 20:35:08,709 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 36 SyntacticMatches, 5 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 105 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=158, Invalid=394, Unknown=0, NotChecked=0, Total=552 [2023-12-18 20:35:08,710 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 68 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 114 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-18 20:35:08,710 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 114 Invalid, 114 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-18 20:35:08,710 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2023-12-18 20:35:08,756 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 84. [2023-12-18 20:35:08,756 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 67 states have (on average 1.1343283582089552) internal successors, (76), 67 states have internal predecessors, (76), 9 states have call successors, (9), 7 states have call predecessors, (9), 7 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-18 20:35:08,756 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 94 transitions. [2023-12-18 20:35:08,757 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 94 transitions. Word has length 28 [2023-12-18 20:35:08,757 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-18 20:35:08,757 INFO L495 AbstractCegarLoop]: Abstraction has 84 states and 94 transitions. [2023-12-18 20:35:08,757 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 15 states have internal predecessors, (29), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-18 20:35:08,757 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 94 transitions. [2023-12-18 20:35:08,757 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-12-18 20:35:08,757 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:35:08,758 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:35:08,764 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-12-18 20:35:08,959 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2023-12-18 20:35:08,960 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:35:08,960 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:35:08,960 INFO L85 PathProgramCache]: Analyzing trace with hash 285091339, now seen corresponding path program 7 times [2023-12-18 20:35:08,960 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:35:08,960 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1565394478] [2023-12-18 20:35:08,960 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:35:08,960 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:35:08,971 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-18 20:35:08,972 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [924351633] [2023-12-18 20:35:08,972 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-12-18 20:35:08,972 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:35:08,972 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:35:08,973 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-18 20:35:08,977 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-12-18 20:35:09,029 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-18 20:35:09,030 INFO L262 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 10 conjunts are in the unsatisfiable core [2023-12-18 20:35:09,031 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-18 20:35:09,110 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-18 20:35:09,110 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-18 20:35:09,169 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-18 20:35:09,169 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:35:09,169 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1565394478] [2023-12-18 20:35:09,169 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-18 20:35:09,170 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [924351633] [2023-12-18 20:35:09,170 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [924351633] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-18 20:35:09,170 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-18 20:35:09,170 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 15 [2023-12-18 20:35:09,170 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1471087930] [2023-12-18 20:35:09,170 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-18 20:35:09,170 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-12-18 20:35:09,170 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:35:09,171 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-12-18 20:35:09,171 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=151, Unknown=0, NotChecked=0, Total=210 [2023-12-18 20:35:09,171 INFO L87 Difference]: Start difference. First operand 84 states and 94 transitions. Second operand has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 15 states have internal predecessors, (29), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-18 20:35:09,461 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-18 20:35:09,461 INFO L93 Difference]: Finished difference Result 103 states and 112 transitions. [2023-12-18 20:35:09,461 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-18 20:35:09,462 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 15 states have internal predecessors, (29), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 28 [2023-12-18 20:35:09,462 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-18 20:35:09,462 INFO L225 Difference]: With dead ends: 103 [2023-12-18 20:35:09,462 INFO L226 Difference]: Without dead ends: 99 [2023-12-18 20:35:09,462 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 36 SyntacticMatches, 5 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 83 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=109, Invalid=271, Unknown=0, NotChecked=0, Total=380 [2023-12-18 20:35:09,463 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 59 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 145 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-18 20:35:09,463 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 129 Invalid, 145 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-18 20:35:09,463 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2023-12-18 20:35:09,505 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 72. [2023-12-18 20:35:09,506 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 58 states have (on average 1.1206896551724137) internal successors, (65), 58 states have internal predecessors, (65), 7 states have call successors, (7), 6 states have call predecessors, (7), 6 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-12-18 20:35:09,506 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 79 transitions. [2023-12-18 20:35:09,506 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 79 transitions. Word has length 28 [2023-12-18 20:35:09,506 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-18 20:35:09,506 INFO L495 AbstractCegarLoop]: Abstraction has 72 states and 79 transitions. [2023-12-18 20:35:09,507 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 15 states have internal predecessors, (29), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-18 20:35:09,507 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 79 transitions. [2023-12-18 20:35:09,507 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2023-12-18 20:35:09,507 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:35:09,507 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:35:09,512 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-12-18 20:35:09,709 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-12-18 20:35:09,709 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:35:09,709 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:35:09,709 INFO L85 PathProgramCache]: Analyzing trace with hash 275361337, now seen corresponding path program 8 times [2023-12-18 20:35:09,709 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:35:09,709 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [874789118] [2023-12-18 20:35:09,709 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:35:09,709 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:35:09,720 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-18 20:35:09,720 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [275776929] [2023-12-18 20:35:09,721 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-18 20:35:09,721 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:35:09,721 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:35:09,722 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-18 20:35:09,735 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-12-18 20:35:09,853 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-18 20:35:09,853 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-18 20:35:09,855 WARN L260 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 83 conjunts are in the unsatisfiable core [2023-12-18 20:35:09,858 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-18 20:35:09,901 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-18 20:35:09,907 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-18 20:35:09,933 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 19 treesize of output 18 [2023-12-18 20:35:09,941 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 19 treesize of output 18 [2023-12-18 20:35:09,987 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:09,987 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2023-12-18 20:35:10,001 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:10,001 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2023-12-18 20:35:10,051 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:10,051 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2023-12-18 20:35:10,069 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:10,069 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2023-12-18 20:35:10,662 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2023-12-18 20:35:10,663 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 158 treesize of output 143 [2023-12-18 20:35:11,083 INFO L349 Elim1Store]: treesize reduction 261, result has 24.3 percent of original size [2023-12-18 20:35:11,083 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 9 select indices, 9 select index equivalence classes, 6 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 44 case distinctions, treesize of input 78 treesize of output 119 [2023-12-18 20:35:11,175 INFO L349 Elim1Store]: treesize reduction 188, result has 0.5 percent of original size [2023-12-18 20:35:11,175 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 6 select indices, 6 select index equivalence classes, 11 disjoint index pairs (out of 15 index pairs), introduced 8 new quantified variables, introduced 8 case distinctions, treesize of input 106 treesize of output 173 [2023-12-18 20:35:11,280 INFO L349 Elim1Store]: treesize reduction 183, result has 25.3 percent of original size [2023-12-18 20:35:11,280 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 6 select indices, 6 select index equivalence classes, 11 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 8 case distinctions, treesize of input 134 treesize of output 110 [2023-12-18 20:35:12,423 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:12,424 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 203 treesize of output 151 [2023-12-18 20:35:12,431 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:12,431 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 150 treesize of output 86 [2023-12-18 20:35:12,471 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 4 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-18 20:35:12,471 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-18 20:35:17,179 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:35:17,179 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [874789118] [2023-12-18 20:35:17,179 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-18 20:35:17,179 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [275776929] [2023-12-18 20:35:17,179 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [275776929] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-18 20:35:17,179 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-18 20:35:17,179 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2023-12-18 20:35:17,179 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1333498887] [2023-12-18 20:35:17,179 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-18 20:35:17,180 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2023-12-18 20:35:17,180 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:35:17,180 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2023-12-18 20:35:17,180 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=820, Unknown=0, NotChecked=0, Total=930 [2023-12-18 20:35:17,181 INFO L87 Difference]: Start difference. First operand 72 states and 79 transitions. Second operand has 23 states, 23 states have (on average 1.0869565217391304) internal successors, (25), 20 states have internal predecessors, (25), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:35:21,411 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-18 20:35:21,411 INFO L93 Difference]: Finished difference Result 96 states and 107 transitions. [2023-12-18 20:35:21,411 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2023-12-18 20:35:21,411 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 1.0869565217391304) internal successors, (25), 20 states have internal predecessors, (25), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 29 [2023-12-18 20:35:21,412 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-18 20:35:21,412 INFO L225 Difference]: With dead ends: 96 [2023-12-18 20:35:21,412 INFO L226 Difference]: Without dead ends: 92 [2023-12-18 20:35:21,413 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 403 ImplicationChecksByTransitivity, 7.5s TimeCoverageRelationStatistics Valid=225, Invalid=1667, Unknown=0, NotChecked=0, Total=1892 [2023-12-18 20:35:21,413 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 59 mSDsluCounter, 178 mSDsCounter, 0 mSdLazyCounter, 426 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 197 SdHoareTripleChecker+Invalid, 438 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 426 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2023-12-18 20:35:21,413 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 197 Invalid, 438 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 426 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2023-12-18 20:35:21,414 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2023-12-18 20:35:21,478 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 83. [2023-12-18 20:35:21,479 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 67 states have (on average 1.1343283582089552) internal successors, (76), 67 states have internal predecessors, (76), 8 states have call successors, (8), 7 states have call predecessors, (8), 7 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2023-12-18 20:35:21,479 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 92 transitions. [2023-12-18 20:35:21,479 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 92 transitions. Word has length 29 [2023-12-18 20:35:21,479 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-18 20:35:21,479 INFO L495 AbstractCegarLoop]: Abstraction has 83 states and 92 transitions. [2023-12-18 20:35:21,480 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 1.0869565217391304) internal successors, (25), 20 states have internal predecessors, (25), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-18 20:35:21,480 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 92 transitions. [2023-12-18 20:35:21,480 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2023-12-18 20:35:21,480 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:35:21,480 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:35:21,488 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2023-12-18 20:35:21,684 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-12-18 20:35:21,684 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:35:21,685 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:35:21,685 INFO L85 PathProgramCache]: Analyzing trace with hash -26268725, now seen corresponding path program 9 times [2023-12-18 20:35:21,685 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:35:21,685 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [782120399] [2023-12-18 20:35:21,685 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:35:21,685 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:35:21,698 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-18 20:35:21,699 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1388488982] [2023-12-18 20:35:21,699 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-18 20:35:21,699 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:35:21,699 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:35:21,700 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-18 20:35:21,701 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-12-18 20:35:21,823 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-12-18 20:35:21,823 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-18 20:35:21,824 INFO L262 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 12 conjunts are in the unsatisfiable core [2023-12-18 20:35:21,828 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-18 20:35:21,914 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 19 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-18 20:35:21,914 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-18 20:35:21,994 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-18 20:35:21,994 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:35:21,994 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [782120399] [2023-12-18 20:35:21,994 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-18 20:35:21,995 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1388488982] [2023-12-18 20:35:21,995 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1388488982] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-18 20:35:21,995 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-18 20:35:21,995 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 18 [2023-12-18 20:35:21,995 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1301093999] [2023-12-18 20:35:21,995 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-18 20:35:21,995 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-12-18 20:35:21,995 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:35:21,996 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-12-18 20:35:21,996 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=223, Unknown=0, NotChecked=0, Total=306 [2023-12-18 20:35:21,996 INFO L87 Difference]: Start difference. First operand 83 states and 92 transitions. Second operand has 18 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 18 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-18 20:35:22,329 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-18 20:35:22,329 INFO L93 Difference]: Finished difference Result 126 states and 134 transitions. [2023-12-18 20:35:22,330 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2023-12-18 20:35:22,330 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 18 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 30 [2023-12-18 20:35:22,330 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-18 20:35:22,330 INFO L225 Difference]: With dead ends: 126 [2023-12-18 20:35:22,331 INFO L226 Difference]: Without dead ends: 115 [2023-12-18 20:35:22,331 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 36 SyntacticMatches, 6 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 220 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=281, Invalid=775, Unknown=0, NotChecked=0, Total=1056 [2023-12-18 20:35:22,332 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 97 mSDsluCounter, 129 mSDsCounter, 0 mSdLazyCounter, 146 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 98 SdHoareTripleChecker+Valid, 159 SdHoareTripleChecker+Invalid, 188 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 146 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-18 20:35:22,332 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [98 Valid, 159 Invalid, 188 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 146 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-18 20:35:22,332 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2023-12-18 20:35:22,396 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 91. [2023-12-18 20:35:22,397 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 73 states have (on average 1.1232876712328768) internal successors, (82), 73 states have internal predecessors, (82), 9 states have call successors, (9), 8 states have call predecessors, (9), 8 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-18 20:35:22,397 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 100 transitions. [2023-12-18 20:35:22,397 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 100 transitions. Word has length 30 [2023-12-18 20:35:22,397 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-18 20:35:22,397 INFO L495 AbstractCegarLoop]: Abstraction has 91 states and 100 transitions. [2023-12-18 20:35:22,397 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 18 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-18 20:35:22,397 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 100 transitions. [2023-12-18 20:35:22,398 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2023-12-18 20:35:22,398 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:35:22,398 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:35:22,405 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-12-18 20:35:22,599 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-12-18 20:35:22,601 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:35:22,602 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:35:22,602 INFO L85 PathProgramCache]: Analyzing trace with hash 1566294257, now seen corresponding path program 10 times [2023-12-18 20:35:22,602 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:35:22,602 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1323781208] [2023-12-18 20:35:22,602 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:35:22,602 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:35:22,617 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-18 20:35:22,617 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1883299992] [2023-12-18 20:35:22,617 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-18 20:35:22,617 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:35:22,617 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:35:22,624 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-18 20:35:22,625 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-12-18 20:35:22,702 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-18 20:35:22,702 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-18 20:35:22,703 INFO L262 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 12 conjunts are in the unsatisfiable core [2023-12-18 20:35:22,704 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-18 20:35:22,801 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 14 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-18 20:35:22,802 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-18 20:35:22,878 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 10 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-18 20:35:22,878 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:35:22,878 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1323781208] [2023-12-18 20:35:22,878 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-18 20:35:22,879 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1883299992] [2023-12-18 20:35:22,879 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1883299992] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-18 20:35:22,879 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-18 20:35:22,879 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 18 [2023-12-18 20:35:22,879 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1952845772] [2023-12-18 20:35:22,879 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-18 20:35:22,879 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-12-18 20:35:22,879 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:35:22,880 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-12-18 20:35:22,880 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=223, Unknown=0, NotChecked=0, Total=306 [2023-12-18 20:35:22,880 INFO L87 Difference]: Start difference. First operand 91 states and 100 transitions. Second operand has 18 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 18 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-18 20:35:23,188 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-18 20:35:23,188 INFO L93 Difference]: Finished difference Result 115 states and 121 transitions. [2023-12-18 20:35:23,188 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-12-18 20:35:23,189 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 18 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 30 [2023-12-18 20:35:23,189 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-18 20:35:23,189 INFO L225 Difference]: With dead ends: 115 [2023-12-18 20:35:23,189 INFO L226 Difference]: Without dead ends: 111 [2023-12-18 20:35:23,190 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 36 SyntacticMatches, 6 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 134 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=152, Invalid=400, Unknown=0, NotChecked=0, Total=552 [2023-12-18 20:35:23,190 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 58 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 135 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 154 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 135 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-18 20:35:23,190 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 132 Invalid, 154 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 135 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-18 20:35:23,190 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2023-12-18 20:35:23,255 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 92. [2023-12-18 20:35:23,256 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 74 states have (on average 1.1216216216216217) internal successors, (83), 74 states have internal predecessors, (83), 9 states have call successors, (9), 8 states have call predecessors, (9), 8 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-18 20:35:23,256 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 101 transitions. [2023-12-18 20:35:23,256 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 101 transitions. Word has length 30 [2023-12-18 20:35:23,256 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-18 20:35:23,257 INFO L495 AbstractCegarLoop]: Abstraction has 92 states and 101 transitions. [2023-12-18 20:35:23,257 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 18 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-18 20:35:23,257 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 101 transitions. [2023-12-18 20:35:23,257 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2023-12-18 20:35:23,257 INFO L187 NwaCegarLoop]: Found error trace [2023-12-18 20:35:23,257 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-18 20:35:23,262 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-12-18 20:35:23,458 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-12-18 20:35:23,459 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-18 20:35:23,459 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-18 20:35:23,459 INFO L85 PathProgramCache]: Analyzing trace with hash 1337946131, now seen corresponding path program 11 times [2023-12-18 20:35:23,459 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-18 20:35:23,459 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [397095369] [2023-12-18 20:35:23,459 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-18 20:35:23,459 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-18 20:35:23,470 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-18 20:35:23,470 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2095324767] [2023-12-18 20:35:23,470 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2023-12-18 20:35:23,470 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-18 20:35:23,470 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-18 20:35:23,471 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-18 20:35:23,473 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-12-18 20:35:23,835 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2023-12-18 20:35:23,835 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-18 20:35:23,842 WARN L260 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 95 conjunts are in the unsatisfiable core [2023-12-18 20:35:23,845 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-18 20:35:23,916 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-18 20:35:23,925 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-18 20:35:23,962 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 19 treesize of output 18 [2023-12-18 20:35:23,972 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 19 treesize of output 18 [2023-12-18 20:35:24,024 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:24,024 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2023-12-18 20:35:24,035 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:24,035 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2023-12-18 20:35:24,112 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:24,112 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2023-12-18 20:35:24,126 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:24,126 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2023-12-18 20:35:24,197 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:24,197 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 40 treesize of output 48 [2023-12-18 20:35:24,212 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:24,212 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 40 treesize of output 48 [2023-12-18 20:35:25,363 INFO L349 Elim1Store]: treesize reduction 325, result has 24.6 percent of original size [2023-12-18 20:35:25,364 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 11 select indices, 11 select index equivalence classes, 10 disjoint index pairs (out of 55 index pairs), introduced 11 new quantified variables, introduced 65 case distinctions, treesize of input 92 treesize of output 147 [2023-12-18 20:35:25,495 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2023-12-18 20:35:25,496 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 172 treesize of output 153 [2023-12-18 20:35:25,607 INFO L349 Elim1Store]: treesize reduction 235, result has 0.4 percent of original size [2023-12-18 20:35:25,608 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 7 select indices, 7 select index equivalence classes, 16 disjoint index pairs (out of 21 index pairs), introduced 9 new quantified variables, introduced 10 case distinctions, treesize of input 111 treesize of output 181 [2023-12-18 20:35:25,745 INFO L349 Elim1Store]: treesize reduction 227, result has 25.8 percent of original size [2023-12-18 20:35:25,746 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 7 select indices, 7 select index equivalence classes, 16 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 10 case distinctions, treesize of input 139 treesize of output 130 [2023-12-18 20:35:27,749 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:27,750 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 10 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 309 treesize of output 209 [2023-12-18 20:35:27,759 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-18 20:35:27,759 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 10 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 184 treesize of output 124 [2023-12-18 20:35:27,807 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 4 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-18 20:35:27,808 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-18 20:35:38,717 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-18 20:35:38,717 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [397095369] [2023-12-18 20:35:38,717 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-18 20:35:38,717 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2095324767] [2023-12-18 20:35:38,717 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2095324767] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-18 20:35:38,717 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-18 20:35:38,717 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2023-12-18 20:35:38,718 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [93052005] [2023-12-18 20:35:38,718 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-18 20:35:38,718 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-12-18 20:35:38,718 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-18 20:35:38,718 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-12-18 20:35:38,719 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=135, Invalid=1054, Unknown=1, NotChecked=0, Total=1190 [2023-12-18 20:35:38,719 INFO L87 Difference]: Start difference. First operand 92 states and 101 transitions. Second operand has 26 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 22 states have internal predecessors, (27), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Received shutdown request... [2023-12-18 20:35:42,547 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2023-12-18 20:35:42,554 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2023-12-18 20:35:42,566 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2023-12-18 20:35:42,567 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 517 ImplicationChecksByTransitivity, 13.7s TimeCoverageRelationStatistics Valid=258, Invalid=1997, Unknown=1, NotChecked=0, Total=2256 [2023-12-18 20:35:42,567 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 90 mSDsluCounter, 170 mSDsCounter, 0 mSdLazyCounter, 498 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 93 SdHoareTripleChecker+Valid, 189 SdHoareTripleChecker+Invalid, 524 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 498 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2023-12-18 20:35:42,567 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [93 Valid, 189 Invalid, 524 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 498 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2023-12-18 20:35:42,568 INFO L805 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-12-18 20:35:42,577 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-12-18 20:35:42,769 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2023-12-18 20:35:42,770 WARN L619 AbstractCegarLoop]: Verification canceled: while NwaCegarLoop was constructing difference of abstraction (92states) and FLOYD_HOARE automaton (currently 26 states, 26 states before enhancement),while ReachableStatesComputation was computing reachable states (95 states constructed, input type IntersectNwa). [2023-12-18 20:35:42,773 INFO L445 BasicCegarLoop]: Path program histogram: [11, 1, 1, 1] [2023-12-18 20:35:42,775 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2023-12-18 20:35:42,776 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.12 08:35:42 BoogieIcfgContainer [2023-12-18 20:35:42,776 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-12-18 20:35:42,776 INFO L158 Benchmark]: Toolchain (without parser) took 878219.23ms. Allocated memory was 206.6MB in the beginning and 307.2MB in the end (delta: 100.7MB). Free memory was 157.3MB in the beginning and 232.6MB in the end (delta: -75.3MB). Peak memory consumption was 26.3MB. Max. memory is 8.0GB. [2023-12-18 20:35:42,776 INFO L158 Benchmark]: CDTParser took 0.11ms. Allocated memory is still 206.6MB. Free memory is still 154.2MB. There was no memory consumed. Max. memory is 8.0GB. [2023-12-18 20:35:42,777 INFO L158 Benchmark]: CACSL2BoogieTranslator took 179.91ms. Allocated memory is still 206.6MB. Free memory was 157.3MB in the beginning and 145.9MB in the end (delta: 11.3MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2023-12-18 20:35:42,777 INFO L158 Benchmark]: Boogie Procedure Inliner took 32.73ms. Allocated memory is still 206.6MB. Free memory was 145.9MB in the beginning and 144.3MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2023-12-18 20:35:42,777 INFO L158 Benchmark]: Boogie Preprocessor took 32.79ms. Allocated memory is still 206.6MB. Free memory was 144.3MB in the beginning and 142.2MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2023-12-18 20:35:42,777 INFO L158 Benchmark]: RCFGBuilder took 251.15ms. Allocated memory is still 206.6MB. Free memory was 142.2MB in the beginning and 129.0MB in the end (delta: 13.2MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2023-12-18 20:35:42,777 INFO L158 Benchmark]: TraceAbstraction took 877700.23ms. Allocated memory was 206.6MB in the beginning and 307.2MB in the end (delta: 100.7MB). Free memory was 128.2MB in the beginning and 232.6MB in the end (delta: -104.4MB). There was no memory consumed. Max. memory is 8.0GB. [2023-12-18 20:35:42,778 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.11ms. Allocated memory is still 206.6MB. Free memory is still 154.2MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 179.91ms. Allocated memory is still 206.6MB. Free memory was 157.3MB in the beginning and 145.9MB in the end (delta: 11.3MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Procedure Inliner took 32.73ms. Allocated memory is still 206.6MB. Free memory was 145.9MB in the beginning and 144.3MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * Boogie Preprocessor took 32.79ms. Allocated memory is still 206.6MB. Free memory was 144.3MB in the beginning and 142.2MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 251.15ms. Allocated memory is still 206.6MB. Free memory was 142.2MB in the beginning and 129.0MB in the end (delta: 13.2MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * TraceAbstraction took 877700.23ms. Allocated memory was 206.6MB in the beginning and 307.2MB in the end (delta: 100.7MB). Free memory was 128.2MB in the beginning and 232.6MB in the end (delta: -104.4MB). There was no memory consumed. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - TimeoutResultAtElement [Line: 30]: Timeout (TraceAbstraction) Unable to prove that a call to reach_error is unreachable (line 30). Cancelled while NwaCegarLoop was constructing difference of abstraction (92states) and FLOYD_HOARE automaton (currently 26 states, 26 states before enhancement),while ReachableStatesComputation was computing reachable states (95 states constructed, input type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 20 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 877.7s, OverallIterations: 14, TraceHistogramMax: 5, PathProgramHistogramMax: 11, EmptinessCheckTime: 0.0s, AutomataDifference: 361.6s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 24 mSolverCounterUnknown, 946 SdHoareTripleChecker+Valid, 150.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 932 mSDsluCounter, 1710 SdHoareTripleChecker+Invalid, 149.1s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 25 IncrementalHoareTripleChecker+Unchecked, 1415 mSDsCounter, 328 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2613 IncrementalHoareTripleChecker+Invalid, 2990 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 328 mSolverCounterUnsat, 295 mSDtfsCounter, 2613 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 714 GetRequests, 321 SyntacticMatches, 31 SemanticMatches, 362 ConstructedPredicates, 1 IntricatePredicates, 3 DeprecatedPredicates, 4063 ImplicationChecksByTransitivity, 313.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=92occurred in iteration=13, InterpolantAutomatonStates: 225, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.4s AutomataMinimizationTime, 13 MinimizatonAttempts, 185 StatesRemovedByMinimization, 9 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 1.0s SatisfiabilityAnalysisTime, 511.1s InterpolantComputationTime, 358 NumberOfCodeBlocks, 358 NumberOfCodeBlocksAsserted, 33 NumberOfCheckSat, 528 ConstructedInterpolants, 39 QuantifiedInterpolants, 14433 SizeOfPredicates, 91 NumberOfNonLiveVariables, 1787 ConjunctsInSsa, 420 ConjunctsInUnsatCore, 21 InterpolantComputations, 3 PerfectInterpolantSequences, 177/347 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown