/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 false -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -i ../../../trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.4-tmp.fs.bitabs-eval-d9c3e40-m [2023-12-21 05:42:17,167 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-21 05:42:17,234 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-21 05:42:17,238 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-21 05:42:17,238 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-21 05:42:17,259 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-21 05:42:17,260 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-21 05:42:17,260 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-21 05:42:17,260 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-12-21 05:42:17,263 INFO L153 SettingsManager]: * Use memory slicer=true [2023-12-21 05:42:17,263 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-21 05:42:17,264 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-21 05:42:17,264 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-12-21 05:42:17,265 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-12-21 05:42:17,266 INFO L153 SettingsManager]: * Use SBE=true [2023-12-21 05:42:17,266 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-21 05:42:17,266 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-21 05:42:17,266 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-21 05:42:17,266 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-21 05:42:17,267 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-21 05:42:17,267 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-21 05:42:17,268 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-21 05:42:17,268 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-21 05:42:17,268 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-21 05:42:17,268 INFO L153 SettingsManager]: * Allow undefined functions=false [2023-12-21 05:42:17,268 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-21 05:42:17,269 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-21 05:42:17,269 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-21 05:42:17,269 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-21 05:42:17,269 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-12-21 05:42:17,270 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-21 05:42:17,270 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-21 05:42:17,270 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-21 05:42:17,270 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-21 05:42:17,271 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-21 05:42:17,271 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-21 05:42:17,271 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-12-21 05:42:17,271 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-21 05:42:17,271 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-21 05:42:17,271 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-12-21 05:42:17,271 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-21 05:42:17,272 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-12-21 05:42:17,272 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-21 05:42:17,272 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 -> false [2023-12-21 05:42:17,448 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-21 05:42:17,464 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-21 05:42:17,466 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-21 05:42:17,467 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-21 05:42:17,467 INFO L274 PluginConnector]: CDTParser initialized [2023-12-21 05:42:17,468 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound100.c [2023-12-21 05:42:18,486 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-21 05:42:18,625 INFO L384 CDTParser]: Found 1 translation units. [2023-12-21 05:42:18,629 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound100.c [2023-12-21 05:42:18,638 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/723ad65c5/f602a4f08e174c4cb5c7019948b30fd5/FLAG3e1d4d8ba [2023-12-21 05:42:18,650 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/723ad65c5/f602a4f08e174c4cb5c7019948b30fd5 [2023-12-21 05:42:18,652 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-21 05:42:18,653 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2023-12-21 05:42:18,655 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-21 05:42:18,655 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-21 05:42:18,658 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-21 05:42:18,659 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,659 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@21b9a6e8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18, skipping insertion in model container [2023-12-21 05:42:18,660 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,676 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-21 05:42:18,780 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound100.c[588,601] [2023-12-21 05:42:18,811 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-21 05:42:18,818 INFO L202 MainTranslator]: Completed pre-run [2023-12-21 05:42:18,827 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound100.c[588,601] [2023-12-21 05:42:18,834 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-21 05:42:18,843 INFO L206 MainTranslator]: Completed translation [2023-12-21 05:42:18,843 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18 WrapperNode [2023-12-21 05:42:18,843 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-21 05:42:18,844 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-21 05:42:18,844 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-21 05:42:18,844 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-21 05:42:18,849 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,861 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,879 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 49 [2023-12-21 05:42:18,880 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-21 05:42:18,880 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-21 05:42:18,880 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-21 05:42:18,880 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-21 05:42:18,893 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,893 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,894 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,908 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2023-12-21 05:42:18,909 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,909 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,910 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,918 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,918 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,919 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,920 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-21 05:42:18,920 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-21 05:42:18,920 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-21 05:42:18,920 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-21 05:42:18,921 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18" (1/1) ... [2023-12-21 05:42:18,924 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-21 05:42:18,933 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:18,944 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-21 05:42:18,965 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-21 05:42:18,978 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-21 05:42:18,979 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-12-21 05:42:18,979 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-21 05:42:18,979 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-21 05:42:18,979 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-12-21 05:42:18,979 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-12-21 05:42:19,017 INFO L241 CfgBuilder]: Building ICFG [2023-12-21 05:42:19,018 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-21 05:42:19,150 INFO L282 CfgBuilder]: Performing block encoding [2023-12-21 05:42:19,211 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-21 05:42:19,211 INFO L309 CfgBuilder]: Removed 1 assume(true) statements. [2023-12-21 05:42:19,211 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 05:42:19 BoogieIcfgContainer [2023-12-21 05:42:19,211 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-21 05:42:19,213 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-21 05:42:19,213 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-21 05:42:19,215 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-21 05:42:19,215 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.12 05:42:18" (1/3) ... [2023-12-21 05:42:19,216 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5faafdfa and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 05:42:19, skipping insertion in model container [2023-12-21 05:42:19,216 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 05:42:18" (2/3) ... [2023-12-21 05:42:19,216 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5faafdfa and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 05:42:19, skipping insertion in model container [2023-12-21 05:42:19,216 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 05:42:19" (3/3) ... [2023-12-21 05:42:19,217 INFO L112 eAbstractionObserver]: Analyzing ICFG cohencu-ll_unwindbound100.c [2023-12-21 05:42:19,230 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-21 05:42:19,231 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-21 05:42:19,271 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-21 05:42:19,276 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;@63bc6f26, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-21 05:42:19,276 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-21 05:42:19,279 INFO L276 IsEmpty]: Start isEmpty. Operand has 23 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-12-21 05:42:19,288 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-12-21 05:42:19,288 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:19,289 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-12-21 05:42:19,289 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:19,294 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:19,294 INFO L85 PathProgramCache]: Analyzing trace with hash -1379524608, now seen corresponding path program 1 times [2023-12-21 05:42:19,299 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:19,300 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [714471302] [2023-12-21 05:42:19,300 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:19,300 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:19,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 05:42:19,402 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-21 05:42:19,403 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:19,403 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [714471302] [2023-12-21 05:42:19,403 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [714471302] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 05:42:19,403 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 05:42:19,403 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-21 05:42:19,405 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [551448809] [2023-12-21 05:42:19,405 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 05:42:19,407 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-12-21 05:42:19,408 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:19,439 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-12-21 05:42:19,439 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-21 05:42:19,441 INFO L87 Difference]: Start difference. First operand has 23 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 05:42:19,463 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:19,463 INFO L93 Difference]: Finished difference Result 45 states and 82 transitions. [2023-12-21 05:42:19,464 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-12-21 05:42:19,465 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2023-12-21 05:42:19,465 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:19,469 INFO L225 Difference]: With dead ends: 45 [2023-12-21 05:42:19,469 INFO L226 Difference]: Without dead ends: 21 [2023-12-21 05:42:19,472 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-21 05:42:19,475 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:19,475 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 32 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 05:42:19,487 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2023-12-21 05:42:19,499 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2023-12-21 05:42:19,500 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 8 states have (on average 1.375) internal successors, (11), 9 states have internal predecessors, (11), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-12-21 05:42:19,501 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 32 transitions. [2023-12-21 05:42:19,502 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 32 transitions. Word has length 6 [2023-12-21 05:42:19,502 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:19,503 INFO L495 AbstractCegarLoop]: Abstraction has 21 states and 32 transitions. [2023-12-21 05:42:19,503 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 05:42:19,503 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 32 transitions. [2023-12-21 05:42:19,503 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-12-21 05:42:19,503 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:19,504 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:42:19,504 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-12-21 05:42:19,504 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:19,505 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:19,505 INFO L85 PathProgramCache]: Analyzing trace with hash -345068235, now seen corresponding path program 1 times [2023-12-21 05:42:19,505 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:19,505 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [18729637] [2023-12-21 05:42:19,505 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:19,505 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:19,515 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 05:42:19,612 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-21 05:42:19,612 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:19,612 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [18729637] [2023-12-21 05:42:19,612 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [18729637] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 05:42:19,612 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 05:42:19,612 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-21 05:42:19,613 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1118705277] [2023-12-21 05:42:19,613 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 05:42:19,613 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-12-21 05:42:19,614 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:19,614 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-12-21 05:42:19,614 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-21 05:42:19,614 INFO L87 Difference]: Start difference. First operand 21 states and 32 transitions. Second operand has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 05:42:19,644 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:19,644 INFO L93 Difference]: Finished difference Result 35 states and 51 transitions. [2023-12-21 05:42:19,644 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-12-21 05:42:19,645 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-12-21 05:42:19,645 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:19,645 INFO L225 Difference]: With dead ends: 35 [2023-12-21 05:42:19,645 INFO L226 Difference]: Without dead ends: 23 [2023-12-21 05:42:19,646 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-21 05:42:19,646 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 0 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:19,647 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 86 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 05:42:19,647 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2023-12-21 05:42:19,651 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2023-12-21 05:42:19,651 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-12-21 05:42:19,652 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 34 transitions. [2023-12-21 05:42:19,652 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 34 transitions. Word has length 7 [2023-12-21 05:42:19,652 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:19,652 INFO L495 AbstractCegarLoop]: Abstraction has 23 states and 34 transitions. [2023-12-21 05:42:19,652 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 05:42:19,653 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 34 transitions. [2023-12-21 05:42:19,653 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-12-21 05:42:19,653 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:19,653 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:42:19,653 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-12-21 05:42:19,653 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:19,654 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:19,654 INFO L85 PathProgramCache]: Analyzing trace with hash -343519103, now seen corresponding path program 1 times [2023-12-21 05:42:19,654 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:19,654 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [542224045] [2023-12-21 05:42:19,654 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:19,654 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:19,666 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 05:42:19,766 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-21 05:42:19,766 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:19,767 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [542224045] [2023-12-21 05:42:19,767 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [542224045] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 05:42:19,767 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 05:42:19,767 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-12-21 05:42:19,767 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [379063881] [2023-12-21 05:42:19,767 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 05:42:19,768 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-21 05:42:19,768 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:19,768 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-21 05:42:19,768 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-21 05:42:19,768 INFO L87 Difference]: Start difference. First operand 23 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 05:42:19,867 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:19,867 INFO L93 Difference]: Finished difference Result 29 states and 39 transitions. [2023-12-21 05:42:19,868 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-21 05:42:19,868 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-12-21 05:42:19,868 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:19,869 INFO L225 Difference]: With dead ends: 29 [2023-12-21 05:42:19,869 INFO L226 Difference]: Without dead ends: 27 [2023-12-21 05:42:19,869 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-12-21 05:42:19,870 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 8 mSDsluCounter, 52 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:19,870 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 77 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-21 05:42:19,871 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2023-12-21 05:42:19,877 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2023-12-21 05:42:19,877 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 14 states have internal predecessors, (16), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-12-21 05:42:19,878 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 37 transitions. [2023-12-21 05:42:19,878 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 37 transitions. Word has length 7 [2023-12-21 05:42:19,878 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:19,879 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 37 transitions. [2023-12-21 05:42:19,879 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 05:42:19,879 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 37 transitions. [2023-12-21 05:42:19,879 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2023-12-21 05:42:19,879 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:19,879 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:42:19,879 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-12-21 05:42:19,880 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:19,885 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:19,885 INFO L85 PathProgramCache]: Analyzing trace with hash -875596316, now seen corresponding path program 1 times [2023-12-21 05:42:19,885 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:19,885 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1128098006] [2023-12-21 05:42:19,885 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:19,886 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:19,902 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:42:19,903 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1069548855] [2023-12-21 05:42:19,903 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:19,903 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:19,903 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:19,913 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-21 05:42:19,920 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-21 05:42:19,959 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 05:42:19,961 INFO L262 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 17 conjunts are in the unsatisfiable core [2023-12-21 05:42:19,966 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:42:20,089 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-21 05:42:20,089 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:42:20,234 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-21 05:42:20,234 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:20,235 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1128098006] [2023-12-21 05:42:20,235 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:42:20,235 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1069548855] [2023-12-21 05:42:20,238 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1069548855] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:42:20,238 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:42:20,238 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 12 [2023-12-21 05:42:20,238 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1252626490] [2023-12-21 05:42:20,239 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:42:20,239 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-12-21 05:42:20,239 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:20,240 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-12-21 05:42:20,242 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2023-12-21 05:42:20,242 INFO L87 Difference]: Start difference. First operand 27 states and 37 transitions. Second operand has 12 states, 10 states have (on average 1.6) internal successors, (16), 8 states have internal predecessors, (16), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-21 05:42:20,521 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:20,521 INFO L93 Difference]: Finished difference Result 53 states and 75 transitions. [2023-12-21 05:42:20,521 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-12-21 05:42:20,521 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 1.6) internal successors, (16), 8 states have internal predecessors, (16), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 12 [2023-12-21 05:42:20,522 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:20,523 INFO L225 Difference]: With dead ends: 53 [2023-12-21 05:42:20,523 INFO L226 Difference]: Without dead ends: 51 [2023-12-21 05:42:20,524 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2023-12-21 05:42:20,524 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 26 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 110 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 74 SdHoareTripleChecker+Invalid, 144 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 110 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:20,525 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 74 Invalid, 144 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 110 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-21 05:42:20,525 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2023-12-21 05:42:20,535 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 46. [2023-12-21 05:42:20,535 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 20 states have (on average 1.2) internal successors, (24), 22 states have internal predecessors, (24), 21 states have call successors, (21), 4 states have call predecessors, (21), 4 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2023-12-21 05:42:20,537 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 65 transitions. [2023-12-21 05:42:20,537 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 65 transitions. Word has length 12 [2023-12-21 05:42:20,537 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:20,537 INFO L495 AbstractCegarLoop]: Abstraction has 46 states and 65 transitions. [2023-12-21 05:42:20,537 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 1.6) internal successors, (16), 8 states have internal predecessors, (16), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-21 05:42:20,537 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 65 transitions. [2023-12-21 05:42:20,537 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2023-12-21 05:42:20,538 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:20,538 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:42:20,559 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-21 05:42:20,743 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:20,743 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:20,743 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:20,743 INFO L85 PathProgramCache]: Analyzing trace with hash 2105691681, now seen corresponding path program 1 times [2023-12-21 05:42:20,744 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:20,744 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [273553549] [2023-12-21 05:42:20,744 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:20,744 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:20,757 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:42:20,757 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [302369345] [2023-12-21 05:42:20,757 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:20,758 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:20,758 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:20,760 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-21 05:42:20,762 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-21 05:42:20,808 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 05:42:20,809 INFO L262 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 17 conjunts are in the unsatisfiable core [2023-12-21 05:42:20,810 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:42:20,898 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-21 05:42:20,898 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:42:21,005 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-21 05:42:21,005 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:21,008 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [273553549] [2023-12-21 05:42:21,008 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:42:21,008 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [302369345] [2023-12-21 05:42:21,008 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [302369345] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:42:21,008 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:42:21,008 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 12 [2023-12-21 05:42:21,009 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1654605880] [2023-12-21 05:42:21,009 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:42:21,009 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-12-21 05:42:21,009 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:21,010 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-12-21 05:42:21,010 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2023-12-21 05:42:21,010 INFO L87 Difference]: Start difference. First operand 46 states and 65 transitions. Second operand has 12 states, 10 states have (on average 1.9) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2023-12-21 05:42:21,307 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:21,308 INFO L93 Difference]: Finished difference Result 59 states and 82 transitions. [2023-12-21 05:42:21,308 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-12-21 05:42:21,309 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 1.9) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) Word has length 17 [2023-12-21 05:42:21,309 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:21,309 INFO L225 Difference]: With dead ends: 59 [2023-12-21 05:42:21,310 INFO L226 Difference]: Without dead ends: 57 [2023-12-21 05:42:21,310 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2023-12-21 05:42:21,310 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 19 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 205 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 234 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 205 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:21,311 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 95 Invalid, 234 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 205 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-21 05:42:21,311 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2023-12-21 05:42:21,340 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 50. [2023-12-21 05:42:21,341 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 23 states have (on average 1.173913043478261) internal successors, (27), 25 states have internal predecessors, (27), 21 states have call successors, (21), 5 states have call predecessors, (21), 5 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2023-12-21 05:42:21,345 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 68 transitions. [2023-12-21 05:42:21,345 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 68 transitions. Word has length 17 [2023-12-21 05:42:21,345 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:21,345 INFO L495 AbstractCegarLoop]: Abstraction has 50 states and 68 transitions. [2023-12-21 05:42:21,345 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 1.9) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2023-12-21 05:42:21,345 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 68 transitions. [2023-12-21 05:42:21,346 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-12-21 05:42:21,346 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:21,346 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:42:21,351 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-12-21 05:42:21,550 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:21,551 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:21,551 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:21,551 INFO L85 PathProgramCache]: Analyzing trace with hash 168504260, now seen corresponding path program 1 times [2023-12-21 05:42:21,551 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:21,552 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [681231363] [2023-12-21 05:42:21,552 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:21,552 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:21,559 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:42:21,559 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1181193709] [2023-12-21 05:42:21,559 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:21,559 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:21,560 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:21,567 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-21 05:42:21,569 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-21 05:42:21,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 05:42:21,597 INFO L262 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 19 conjunts are in the unsatisfiable core [2023-12-21 05:42:21,598 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:42:21,676 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-12-21 05:42:21,676 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:42:22,119 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-12-21 05:42:22,119 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:22,119 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [681231363] [2023-12-21 05:42:22,119 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:42:22,119 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1181193709] [2023-12-21 05:42:22,119 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1181193709] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:42:22,119 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:42:22,119 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 12 [2023-12-21 05:42:22,120 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1005479334] [2023-12-21 05:42:22,120 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:42:22,120 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-12-21 05:42:22,120 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:22,120 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-12-21 05:42:22,121 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2023-12-21 05:42:22,121 INFO L87 Difference]: Start difference. First operand 50 states and 68 transitions. Second operand has 12 states, 10 states have (on average 1.9) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (8), 3 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) [2023-12-21 05:42:22,635 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:22,635 INFO L93 Difference]: Finished difference Result 73 states and 99 transitions. [2023-12-21 05:42:22,635 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-12-21 05:42:22,635 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 1.9) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (8), 3 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) Word has length 22 [2023-12-21 05:42:22,635 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:22,636 INFO L225 Difference]: With dead ends: 73 [2023-12-21 05:42:22,636 INFO L226 Difference]: Without dead ends: 64 [2023-12-21 05:42:22,637 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2023-12-21 05:42:22,637 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 21 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 175 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 198 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 175 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:22,637 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 117 Invalid, 198 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 175 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-21 05:42:22,638 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2023-12-21 05:42:22,651 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 64. [2023-12-21 05:42:22,651 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 34 states have internal predecessors, (35), 25 states have call successors, (25), 7 states have call predecessors, (25), 7 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2023-12-21 05:42:22,652 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 83 transitions. [2023-12-21 05:42:22,652 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 83 transitions. Word has length 22 [2023-12-21 05:42:22,652 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:22,652 INFO L495 AbstractCegarLoop]: Abstraction has 64 states and 83 transitions. [2023-12-21 05:42:22,653 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 1.9) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (8), 3 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) [2023-12-21 05:42:22,653 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 83 transitions. [2023-12-21 05:42:22,653 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-12-21 05:42:22,653 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:22,654 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:42:22,673 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-12-21 05:42:22,858 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:22,859 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:22,859 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:22,859 INFO L85 PathProgramCache]: Analyzing trace with hash 1666200982, now seen corresponding path program 1 times [2023-12-21 05:42:22,859 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:22,859 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2038713404] [2023-12-21 05:42:22,859 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:22,860 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:22,867 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:42:22,867 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [985471088] [2023-12-21 05:42:22,867 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:22,867 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:22,867 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:22,889 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-21 05:42:22,947 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-21 05:42:23,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 05:42:23,011 INFO L262 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 5 conjunts are in the unsatisfiable core [2023-12-21 05:42:23,017 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:42:23,058 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 30 proven. 2 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2023-12-21 05:42:23,058 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:42:23,099 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 12 proven. 2 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-12-21 05:42:23,099 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:23,099 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2038713404] [2023-12-21 05:42:23,099 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:42:23,099 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [985471088] [2023-12-21 05:42:23,099 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [985471088] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:42:23,099 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:42:23,099 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2023-12-21 05:42:23,100 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1605047284] [2023-12-21 05:42:23,100 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:42:23,101 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-21 05:42:23,101 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:23,102 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-21 05:42:23,102 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2023-12-21 05:42:23,102 INFO L87 Difference]: Start difference. First operand 64 states and 83 transitions. Second operand has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2023-12-21 05:42:23,214 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:23,214 INFO L93 Difference]: Finished difference Result 139 states and 176 transitions. [2023-12-21 05:42:23,215 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-21 05:42:23,216 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 40 [2023-12-21 05:42:23,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:23,221 INFO L225 Difference]: With dead ends: 139 [2023-12-21 05:42:23,221 INFO L226 Difference]: Without dead ends: 118 [2023-12-21 05:42:23,223 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 72 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2023-12-21 05:42:23,224 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 47 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 73 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 73 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:23,224 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 110 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 73 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-21 05:42:23,225 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2023-12-21 05:42:23,245 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 114. [2023-12-21 05:42:23,245 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 114 states, 58 states have (on average 1.1206896551724137) internal successors, (65), 62 states have internal predecessors, (65), 41 states have call successors, (41), 14 states have call predecessors, (41), 14 states have return successors, (37), 37 states have call predecessors, (37), 37 states have call successors, (37) [2023-12-21 05:42:23,246 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 143 transitions. [2023-12-21 05:42:23,246 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 143 transitions. Word has length 40 [2023-12-21 05:42:23,246 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:23,246 INFO L495 AbstractCegarLoop]: Abstraction has 114 states and 143 transitions. [2023-12-21 05:42:23,246 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2023-12-21 05:42:23,246 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 143 transitions. [2023-12-21 05:42:23,247 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-12-21 05:42:23,247 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:23,247 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:42:23,255 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-21 05:42:23,452 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:23,452 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:23,453 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:23,453 INFO L85 PathProgramCache]: Analyzing trace with hash 1054982331, now seen corresponding path program 1 times [2023-12-21 05:42:23,453 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:23,453 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [951352212] [2023-12-21 05:42:23,453 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:23,453 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:23,460 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:42:23,460 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [577058822] [2023-12-21 05:42:23,460 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:23,460 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:23,461 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:23,461 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-21 05:42:23,480 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-21 05:42:23,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 05:42:23,501 INFO L262 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 23 conjunts are in the unsatisfiable core [2023-12-21 05:42:23,503 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:42:23,596 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 13 proven. 24 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2023-12-21 05:42:23,596 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:42:23,719 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 13 proven. 24 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2023-12-21 05:42:23,720 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:23,720 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [951352212] [2023-12-21 05:42:23,720 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:42:23,720 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [577058822] [2023-12-21 05:42:23,736 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [577058822] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:42:23,736 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:42:23,736 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 14 [2023-12-21 05:42:23,737 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [616783979] [2023-12-21 05:42:23,737 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:42:23,739 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-12-21 05:42:23,739 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:23,739 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-12-21 05:42:23,739 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=143, Unknown=0, NotChecked=0, Total=182 [2023-12-21 05:42:23,740 INFO L87 Difference]: Start difference. First operand 114 states and 143 transitions. Second operand has 14 states, 14 states have (on average 1.7857142857142858) internal successors, (25), 11 states have internal predecessors, (25), 6 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 6 states have call successors, (14) [2023-12-21 05:42:27,903 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:42:28,034 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:28,034 INFO L93 Difference]: Finished difference Result 128 states and 156 transitions. [2023-12-21 05:42:28,035 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-21 05:42:28,035 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 1.7857142857142858) internal successors, (25), 11 states have internal predecessors, (25), 6 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 6 states have call successors, (14) Word has length 45 [2023-12-21 05:42:28,035 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:28,036 INFO L225 Difference]: With dead ends: 128 [2023-12-21 05:42:28,036 INFO L226 Difference]: Without dead ends: 126 [2023-12-21 05:42:28,036 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 76 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=76, Invalid=266, Unknown=0, NotChecked=0, Total=342 [2023-12-21 05:42:28,037 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 20 mSDsluCounter, 134 mSDsCounter, 0 mSdLazyCounter, 239 mSolverCounterSat, 43 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 283 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 239 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.2s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:28,037 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 157 Invalid, 283 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 239 Invalid, 1 Unknown, 0 Unchecked, 4.2s Time] [2023-12-21 05:42:28,037 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2023-12-21 05:42:28,080 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 126. [2023-12-21 05:42:28,081 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 67 states have (on average 1.1044776119402986) internal successors, (74), 71 states have internal predecessors, (74), 41 states have call successors, (41), 17 states have call predecessors, (41), 17 states have return successors, (37), 37 states have call predecessors, (37), 37 states have call successors, (37) [2023-12-21 05:42:28,096 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 152 transitions. [2023-12-21 05:42:28,096 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 152 transitions. Word has length 45 [2023-12-21 05:42:28,097 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:28,098 INFO L495 AbstractCegarLoop]: Abstraction has 126 states and 152 transitions. [2023-12-21 05:42:28,098 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 1.7857142857142858) internal successors, (25), 11 states have internal predecessors, (25), 6 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 6 states have call successors, (14) [2023-12-21 05:42:28,098 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 152 transitions. [2023-12-21 05:42:28,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2023-12-21 05:42:28,099 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:28,099 INFO L195 NwaCegarLoop]: trace histogram [10, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2023-12-21 05:42:28,104 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-21 05:42:28,300 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:28,300 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:28,300 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:28,300 INFO L85 PathProgramCache]: Analyzing trace with hash -2020348453, now seen corresponding path program 2 times [2023-12-21 05:42:28,300 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:28,300 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [507195915] [2023-12-21 05:42:28,301 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:28,301 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:28,308 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:42:28,308 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1076213831] [2023-12-21 05:42:28,308 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-21 05:42:28,308 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:28,308 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:28,317 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-21 05:42:28,365 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-21 05:42:28,390 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-21 05:42:28,390 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 05:42:28,391 INFO L262 TraceCheckSpWp]: Trace formula consists of 142 conjuncts, 23 conjunts are in the unsatisfiable core [2023-12-21 05:42:28,399 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:42:28,477 INFO L134 CoverageAnalysis]: Checked inductivity of 169 backedges. 17 proven. 32 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2023-12-21 05:42:28,477 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:42:28,610 INFO L134 CoverageAnalysis]: Checked inductivity of 169 backedges. 20 proven. 25 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2023-12-21 05:42:28,611 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:28,611 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [507195915] [2023-12-21 05:42:28,611 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:42:28,611 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1076213831] [2023-12-21 05:42:28,611 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1076213831] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:42:28,611 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:42:28,611 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 12 [2023-12-21 05:42:28,611 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [147265554] [2023-12-21 05:42:28,611 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:42:28,612 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-12-21 05:42:28,612 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:28,612 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-12-21 05:42:28,612 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2023-12-21 05:42:28,612 INFO L87 Difference]: Start difference. First operand 126 states and 152 transitions. Second operand has 12 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (15), 3 states have call predecessors, (15), 4 states have call successors, (15) [2023-12-21 05:42:28,737 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:28,737 INFO L93 Difference]: Finished difference Result 140 states and 165 transitions. [2023-12-21 05:42:28,737 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-12-21 05:42:28,738 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (15), 3 states have call predecessors, (15), 4 states have call successors, (15) Word has length 55 [2023-12-21 05:42:28,738 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:28,740 INFO L225 Difference]: With dead ends: 140 [2023-12-21 05:42:28,740 INFO L226 Difference]: Without dead ends: 134 [2023-12-21 05:42:28,740 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 98 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=136, Unknown=0, NotChecked=0, Total=182 [2023-12-21 05:42:28,742 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 21 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 110 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 129 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 110 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:28,742 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 99 Invalid, 129 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 110 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-21 05:42:28,743 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 134 states. [2023-12-21 05:42:28,775 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 134 to 134. [2023-12-21 05:42:28,775 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 76 states have (on average 1.0921052631578947) internal successors, (83), 80 states have internal predecessors, (83), 37 states have call successors, (37), 20 states have call predecessors, (37), 20 states have return successors, (33), 33 states have call predecessors, (33), 33 states have call successors, (33) [2023-12-21 05:42:28,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 153 transitions. [2023-12-21 05:42:28,776 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 153 transitions. Word has length 55 [2023-12-21 05:42:28,776 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:28,776 INFO L495 AbstractCegarLoop]: Abstraction has 134 states and 153 transitions. [2023-12-21 05:42:28,776 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (15), 3 states have call predecessors, (15), 4 states have call successors, (15) [2023-12-21 05:42:28,777 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 153 transitions. [2023-12-21 05:42:28,780 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2023-12-21 05:42:28,780 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:28,780 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:42:28,800 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-21 05:42:28,985 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:28,985 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:28,985 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:28,986 INFO L85 PathProgramCache]: Analyzing trace with hash -1733391679, now seen corresponding path program 1 times [2023-12-21 05:42:28,986 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:28,986 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [152091593] [2023-12-21 05:42:28,986 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:28,986 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:28,992 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:42:28,992 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1563127318] [2023-12-21 05:42:28,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:28,992 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:28,992 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:28,997 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-21 05:42:29,024 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-21 05:42:29,036 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 05:42:29,037 INFO L262 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 28 conjunts are in the unsatisfiable core [2023-12-21 05:42:29,039 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:42:29,306 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 21 proven. 39 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2023-12-21 05:42:29,307 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:42:29,470 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 24 proven. 36 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2023-12-21 05:42:29,470 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:29,470 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [152091593] [2023-12-21 05:42:29,470 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:42:29,470 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1563127318] [2023-12-21 05:42:29,471 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1563127318] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:42:29,471 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:42:29,471 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 14 [2023-12-21 05:42:29,471 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1319353181] [2023-12-21 05:42:29,471 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:42:29,471 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-12-21 05:42:29,471 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:29,472 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-12-21 05:42:29,472 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2023-12-21 05:42:29,472 INFO L87 Difference]: Start difference. First operand 134 states and 153 transitions. Second operand has 14 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) [2023-12-21 05:42:29,895 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:29,896 INFO L93 Difference]: Finished difference Result 148 states and 166 transitions. [2023-12-21 05:42:29,896 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-21 05:42:29,896 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) Word has length 66 [2023-12-21 05:42:29,896 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:29,897 INFO L225 Difference]: With dead ends: 148 [2023-12-21 05:42:29,897 INFO L226 Difference]: Without dead ends: 144 [2023-12-21 05:42:29,897 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 119 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=80, Invalid=300, Unknown=0, NotChecked=0, Total=380 [2023-12-21 05:42:29,898 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 19 mSDsluCounter, 127 mSDsCounter, 0 mSdLazyCounter, 212 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 150 SdHoareTripleChecker+Invalid, 245 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 212 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:29,898 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 150 Invalid, 245 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 212 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-21 05:42:29,898 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 144 states. [2023-12-21 05:42:29,929 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 144 to 144. [2023-12-21 05:42:29,929 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 84 states have (on average 1.0714285714285714) internal successors, (90), 87 states have internal predecessors, (90), 37 states have call successors, (37), 23 states have call predecessors, (37), 22 states have return successors, (33), 33 states have call predecessors, (33), 33 states have call successors, (33) [2023-12-21 05:42:29,930 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 160 transitions. [2023-12-21 05:42:29,930 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 160 transitions. Word has length 66 [2023-12-21 05:42:29,930 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:29,931 INFO L495 AbstractCegarLoop]: Abstraction has 144 states and 160 transitions. [2023-12-21 05:42:29,931 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) [2023-12-21 05:42:29,931 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 160 transitions. [2023-12-21 05:42:29,932 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2023-12-21 05:42:29,932 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:29,932 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:42:29,939 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-21 05:42:30,137 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:30,138 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:30,138 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:30,138 INFO L85 PathProgramCache]: Analyzing trace with hash 2124427812, now seen corresponding path program 1 times [2023-12-21 05:42:30,138 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:30,138 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [154733481] [2023-12-21 05:42:30,139 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:30,139 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:30,148 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:42:30,148 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [958002619] [2023-12-21 05:42:30,148 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:30,149 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:30,149 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:30,170 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-21 05:42:30,197 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-21 05:42:30,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 05:42:30,213 INFO L262 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 27 conjunts are in the unsatisfiable core [2023-12-21 05:42:30,215 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:42:30,472 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 23 proven. 42 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-12-21 05:42:30,473 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:42:30,648 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 23 proven. 42 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-12-21 05:42:30,648 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:30,648 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [154733481] [2023-12-21 05:42:30,648 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:42:30,648 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [958002619] [2023-12-21 05:42:30,648 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [958002619] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:42:30,648 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:42:30,648 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-12-21 05:42:30,648 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1236482182] [2023-12-21 05:42:30,648 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:42:30,649 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-12-21 05:42:30,649 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:30,649 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-12-21 05:42:30,649 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=166, Unknown=0, NotChecked=0, Total=210 [2023-12-21 05:42:30,649 INFO L87 Difference]: Start difference. First operand 144 states and 160 transitions. Second operand has 15 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2023-12-21 05:42:31,039 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:31,040 INFO L93 Difference]: Finished difference Result 163 states and 187 transitions. [2023-12-21 05:42:31,040 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2023-12-21 05:42:31,040 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) Word has length 71 [2023-12-21 05:42:31,040 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:31,041 INFO L225 Difference]: With dead ends: 163 [2023-12-21 05:42:31,041 INFO L226 Difference]: Without dead ends: 152 [2023-12-21 05:42:31,041 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 147 GetRequests, 127 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=104, Invalid=358, Unknown=0, NotChecked=0, Total=462 [2023-12-21 05:42:31,042 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 19 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 196 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 236 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 196 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:31,042 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 130 Invalid, 236 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 196 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-21 05:42:31,042 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2023-12-21 05:42:31,079 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 152. [2023-12-21 05:42:31,080 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 86 states have (on average 1.069767441860465) internal successors, (92), 90 states have internal predecessors, (92), 42 states have call successors, (42), 23 states have call predecessors, (42), 23 states have return successors, (39), 38 states have call predecessors, (39), 39 states have call successors, (39) [2023-12-21 05:42:31,080 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 173 transitions. [2023-12-21 05:42:31,080 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 173 transitions. Word has length 71 [2023-12-21 05:42:31,080 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:31,080 INFO L495 AbstractCegarLoop]: Abstraction has 152 states and 173 transitions. [2023-12-21 05:42:31,081 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2023-12-21 05:42:31,081 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 173 transitions. [2023-12-21 05:42:31,081 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2023-12-21 05:42:31,081 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:31,081 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1] [2023-12-21 05:42:31,088 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-21 05:42:31,286 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,SelfDestructingSolverStorable10 [2023-12-21 05:42:31,286 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:31,286 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:31,287 INFO L85 PathProgramCache]: Analyzing trace with hash -331345392, now seen corresponding path program 3 times [2023-12-21 05:42:31,287 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:31,287 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1395570311] [2023-12-21 05:42:31,287 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:31,287 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:31,304 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:42:31,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [499373482] [2023-12-21 05:42:31,304 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-21 05:42:31,305 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:31,305 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:31,313 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-21 05:42:31,340 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-21 05:42:31,382 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-12-21 05:42:31,382 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 05:42:31,383 INFO L262 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 35 conjunts are in the unsatisfiable core [2023-12-21 05:42:31,385 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:42:31,537 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2023-12-21 05:42:31,537 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:42:32,964 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2023-12-21 05:42:32,964 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:32,964 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1395570311] [2023-12-21 05:42:32,964 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:42:32,964 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [499373482] [2023-12-21 05:42:32,964 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [499373482] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:42:32,964 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:42:32,964 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2023-12-21 05:42:32,964 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1968567316] [2023-12-21 05:42:32,964 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:42:32,965 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-12-21 05:42:32,965 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:32,965 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-12-21 05:42:32,965 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=188, Unknown=0, NotChecked=0, Total=240 [2023-12-21 05:42:32,966 INFO L87 Difference]: Start difference. First operand 152 states and 173 transitions. Second operand has 16 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 13 states have internal predecessors, (31), 8 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 6 states have call predecessors, (26), 8 states have call successors, (26) [2023-12-21 05:42:34,126 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:34,126 INFO L93 Difference]: Finished difference Result 158 states and 178 transitions. [2023-12-21 05:42:34,126 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-21 05:42:34,126 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 13 states have internal predecessors, (31), 8 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 6 states have call predecessors, (26), 8 states have call successors, (26) Word has length 78 [2023-12-21 05:42:34,128 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:34,128 INFO L225 Difference]: With dead ends: 158 [2023-12-21 05:42:34,128 INFO L226 Difference]: Without dead ends: 142 [2023-12-21 05:42:34,129 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 158 GetRequests, 140 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=87, Invalid=293, Unknown=0, NotChecked=0, Total=380 [2023-12-21 05:42:34,129 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 26 mSDsluCounter, 186 mSDsCounter, 0 mSdLazyCounter, 261 mSolverCounterSat, 65 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 216 SdHoareTripleChecker+Invalid, 326 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 65 IncrementalHoareTripleChecker+Valid, 261 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:34,129 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 216 Invalid, 326 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [65 Valid, 261 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2023-12-21 05:42:34,130 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2023-12-21 05:42:34,173 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 140. [2023-12-21 05:42:34,173 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 83 states have (on average 1.0481927710843373) internal successors, (87), 86 states have internal predecessors, (87), 34 states have call successors, (34), 22 states have call predecessors, (34), 22 states have return successors, (33), 31 states have call predecessors, (33), 33 states have call successors, (33) [2023-12-21 05:42:34,174 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 154 transitions. [2023-12-21 05:42:34,174 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 154 transitions. Word has length 78 [2023-12-21 05:42:34,174 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:34,174 INFO L495 AbstractCegarLoop]: Abstraction has 140 states and 154 transitions. [2023-12-21 05:42:34,175 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 13 states have internal predecessors, (31), 8 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 6 states have call predecessors, (26), 8 states have call successors, (26) [2023-12-21 05:42:34,175 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 154 transitions. [2023-12-21 05:42:34,178 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2023-12-21 05:42:34,178 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:34,178 INFO L195 NwaCegarLoop]: trace histogram [22, 21, 21, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:42:34,196 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-21 05:42:34,382 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:34,383 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:34,383 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:34,383 INFO L85 PathProgramCache]: Analyzing trace with hash -1753860344, now seen corresponding path program 2 times [2023-12-21 05:42:34,383 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:34,383 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1794466305] [2023-12-21 05:42:34,383 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:34,383 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:34,391 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:42:34,391 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1250304252] [2023-12-21 05:42:34,391 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-21 05:42:34,391 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:34,391 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:34,409 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-21 05:42:34,425 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-21 05:42:34,467 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-21 05:42:34,467 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 05:42:34,468 INFO L262 TraceCheckSpWp]: Trace formula consists of 292 conjuncts, 11 conjunts are in the unsatisfiable core [2023-12-21 05:42:34,472 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:42:34,595 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 120 proven. 656 refuted. 0 times theorem prover too weak. 162 trivial. 0 not checked. [2023-12-21 05:42:34,595 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:42:34,699 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 42 proven. 56 refuted. 0 times theorem prover too weak. 840 trivial. 0 not checked. [2023-12-21 05:42:34,699 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:34,700 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1794466305] [2023-12-21 05:42:34,700 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:42:34,700 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1250304252] [2023-12-21 05:42:34,700 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1250304252] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:42:34,700 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:42:34,700 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 14 [2023-12-21 05:42:34,700 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1470815883] [2023-12-21 05:42:34,700 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:42:34,701 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-12-21 05:42:34,701 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:34,701 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-12-21 05:42:34,701 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2023-12-21 05:42:34,702 INFO L87 Difference]: Start difference. First operand 140 states and 154 transitions. Second operand has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 9 states have call predecessors, (42), 9 states have call successors, (42) [2023-12-21 05:42:34,976 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:34,976 INFO L93 Difference]: Finished difference Result 397 states and 421 transitions. [2023-12-21 05:42:34,976 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-12-21 05:42:34,977 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 9 states have call predecessors, (42), 9 states have call successors, (42) Word has length 124 [2023-12-21 05:42:34,977 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:34,978 INFO L225 Difference]: With dead ends: 397 [2023-12-21 05:42:34,978 INFO L226 Difference]: Without dead ends: 381 [2023-12-21 05:42:34,979 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 255 GetRequests, 234 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2023-12-21 05:42:34,979 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 131 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 167 mSolverCounterSat, 51 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 131 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 218 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 167 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:34,979 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [131 Valid, 132 Invalid, 218 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 167 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-21 05:42:34,980 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 381 states. [2023-12-21 05:42:35,061 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 381 to 325. [2023-12-21 05:42:35,061 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 325 states, 201 states have (on average 1.0497512437810945) internal successors, (211), 208 states have internal predecessors, (211), 68 states have call successors, (68), 56 states have call predecessors, (68), 55 states have return successors, (65), 60 states have call predecessors, (65), 65 states have call successors, (65) [2023-12-21 05:42:35,062 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 325 states to 325 states and 344 transitions. [2023-12-21 05:42:35,062 INFO L78 Accepts]: Start accepts. Automaton has 325 states and 344 transitions. Word has length 124 [2023-12-21 05:42:35,062 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:35,063 INFO L495 AbstractCegarLoop]: Abstraction has 325 states and 344 transitions. [2023-12-21 05:42:35,063 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 9 states have call predecessors, (42), 9 states have call successors, (42) [2023-12-21 05:42:35,063 INFO L276 IsEmpty]: Start isEmpty. Operand 325 states and 344 transitions. [2023-12-21 05:42:35,063 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 133 [2023-12-21 05:42:35,063 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:35,064 INFO L195 NwaCegarLoop]: trace histogram [24, 23, 23, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:42:35,069 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-12-21 05:42:35,269 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,SelfDestructingSolverStorable12 [2023-12-21 05:42:35,269 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:35,269 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:35,269 INFO L85 PathProgramCache]: Analyzing trace with hash 109149613, now seen corresponding path program 1 times [2023-12-21 05:42:35,269 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:35,270 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [182771755] [2023-12-21 05:42:35,270 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:35,270 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:35,276 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:42:35,276 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1172948105] [2023-12-21 05:42:35,276 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:35,276 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:35,276 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:35,277 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-21 05:42:35,288 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-21 05:42:35,338 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 05:42:35,339 INFO L262 TraceCheckSpWp]: Trace formula consists of 297 conjuncts, 42 conjunts are in the unsatisfiable core [2023-12-21 05:42:35,341 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:42:35,529 INFO L134 CoverageAnalysis]: Checked inductivity of 1106 backedges. 104 proven. 116 refuted. 0 times theorem prover too weak. 886 trivial. 0 not checked. [2023-12-21 05:42:35,529 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:42:35,683 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:35,683 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [182771755] [2023-12-21 05:42:35,683 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:42:35,683 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1172948105] [2023-12-21 05:42:35,683 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1172948105] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-21 05:42:35,683 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-21 05:42:35,683 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2023-12-21 05:42:35,684 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1953886186] [2023-12-21 05:42:35,684 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-21 05:42:35,684 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-12-21 05:42:35,684 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:35,684 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-12-21 05:42:35,684 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=143, Unknown=0, NotChecked=0, Total=182 [2023-12-21 05:42:35,685 INFO L87 Difference]: Start difference. First operand 325 states and 344 transitions. Second operand has 11 states, 11 states have (on average 2.0) internal successors, (22), 9 states have internal predecessors, (22), 5 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (23), 4 states have call predecessors, (23), 5 states have call successors, (23) [2023-12-21 05:42:35,928 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:35,928 INFO L93 Difference]: Finished difference Result 327 states and 345 transitions. [2023-12-21 05:42:35,928 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-21 05:42:35,928 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.0) internal successors, (22), 9 states have internal predecessors, (22), 5 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (23), 4 states have call predecessors, (23), 5 states have call successors, (23) Word has length 132 [2023-12-21 05:42:35,929 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:35,930 INFO L225 Difference]: With dead ends: 327 [2023-12-21 05:42:35,930 INFO L226 Difference]: Without dead ends: 311 [2023-12-21 05:42:35,931 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 129 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=52, Invalid=188, Unknown=0, NotChecked=0, Total=240 [2023-12-21 05:42:35,932 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 11 mSDsluCounter, 238 mSDsCounter, 0 mSdLazyCounter, 331 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 274 SdHoareTripleChecker+Invalid, 342 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 331 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:35,932 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 274 Invalid, 342 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 331 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-21 05:42:35,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 311 states. [2023-12-21 05:42:36,003 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 311 to 311. [2023-12-21 05:42:36,005 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 311 states, 193 states have (on average 1.0466321243523315) internal successors, (202), 200 states have internal predecessors, (202), 64 states have call successors, (64), 53 states have call predecessors, (64), 53 states have return successors, (62), 57 states have call predecessors, (62), 62 states have call successors, (62) [2023-12-21 05:42:36,006 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 311 states to 311 states and 328 transitions. [2023-12-21 05:42:36,006 INFO L78 Accepts]: Start accepts. Automaton has 311 states and 328 transitions. Word has length 132 [2023-12-21 05:42:36,006 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:36,006 INFO L495 AbstractCegarLoop]: Abstraction has 311 states and 328 transitions. [2023-12-21 05:42:36,006 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.0) internal successors, (22), 9 states have internal predecessors, (22), 5 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (23), 4 states have call predecessors, (23), 5 states have call successors, (23) [2023-12-21 05:42:36,006 INFO L276 IsEmpty]: Start isEmpty. Operand 311 states and 328 transitions. [2023-12-21 05:42:36,008 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 156 [2023-12-21 05:42:36,008 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:36,008 INFO L195 NwaCegarLoop]: trace histogram [28, 27, 27, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:42:36,015 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-21 05:42:36,213 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,SelfDestructingSolverStorable13 [2023-12-21 05:42:36,213 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:36,214 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:36,214 INFO L85 PathProgramCache]: Analyzing trace with hash 460751474, now seen corresponding path program 2 times [2023-12-21 05:42:36,214 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:36,214 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2010974031] [2023-12-21 05:42:36,214 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:36,214 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:36,224 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:42:36,224 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1203101100] [2023-12-21 05:42:36,224 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-21 05:42:36,224 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:36,224 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:36,225 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-21 05:42:36,226 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-21 05:42:36,287 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-21 05:42:36,288 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 05:42:36,289 INFO L262 TraceCheckSpWp]: Trace formula consists of 347 conjuncts, 48 conjunts are in the unsatisfiable core [2023-12-21 05:42:36,291 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:42:36,573 INFO L134 CoverageAnalysis]: Checked inductivity of 1538 backedges. 128 proven. 84 refuted. 0 times theorem prover too weak. 1326 trivial. 0 not checked. [2023-12-21 05:42:36,573 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:42:37,323 INFO L134 CoverageAnalysis]: Checked inductivity of 1538 backedges. 128 proven. 76 refuted. 0 times theorem prover too weak. 1334 trivial. 0 not checked. [2023-12-21 05:42:37,323 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:42:37,323 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2010974031] [2023-12-21 05:42:37,323 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:42:37,323 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1203101100] [2023-12-21 05:42:37,323 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1203101100] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:42:37,323 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:42:37,323 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 21 [2023-12-21 05:42:37,323 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [177951467] [2023-12-21 05:42:37,323 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:42:37,324 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-12-21 05:42:37,324 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:42:37,324 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-12-21 05:42:37,324 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=337, Unknown=0, NotChecked=0, Total=420 [2023-12-21 05:42:37,325 INFO L87 Difference]: Start difference. First operand 311 states and 328 transitions. Second operand has 21 states, 17 states have (on average 2.5294117647058822) internal successors, (43), 18 states have internal predecessors, (43), 13 states have call successors, (51), 3 states have call predecessors, (51), 2 states have return successors, (49), 11 states have call predecessors, (49), 13 states have call successors, (49) [2023-12-21 05:42:37,809 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:42:37,809 INFO L93 Difference]: Finished difference Result 329 states and 347 transitions. [2023-12-21 05:42:37,809 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-12-21 05:42:37,809 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 17 states have (on average 2.5294117647058822) internal successors, (43), 18 states have internal predecessors, (43), 13 states have call successors, (51), 3 states have call predecessors, (51), 2 states have return successors, (49), 11 states have call predecessors, (49), 13 states have call successors, (49) Word has length 155 [2023-12-21 05:42:37,809 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:42:37,810 INFO L225 Difference]: With dead ends: 329 [2023-12-21 05:42:37,810 INFO L226 Difference]: Without dead ends: 325 [2023-12-21 05:42:37,811 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 315 GetRequests, 289 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 83 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=149, Invalid=607, Unknown=0, NotChecked=0, Total=756 [2023-12-21 05:42:37,811 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 18 mSDsluCounter, 310 mSDsCounter, 0 mSdLazyCounter, 422 mSolverCounterSat, 54 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 352 SdHoareTripleChecker+Invalid, 476 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 54 IncrementalHoareTripleChecker+Valid, 422 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-21 05:42:37,811 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 352 Invalid, 476 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [54 Valid, 422 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-21 05:42:37,812 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 325 states. [2023-12-21 05:42:37,878 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 325 to 318. [2023-12-21 05:42:37,879 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 318 states, 198 states have (on average 1.0404040404040404) internal successors, (206), 204 states have internal predecessors, (206), 65 states have call successors, (65), 55 states have call predecessors, (65), 54 states have return successors, (63), 58 states have call predecessors, (63), 63 states have call successors, (63) [2023-12-21 05:42:37,879 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 318 states to 318 states and 334 transitions. [2023-12-21 05:42:37,879 INFO L78 Accepts]: Start accepts. Automaton has 318 states and 334 transitions. Word has length 155 [2023-12-21 05:42:37,880 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:42:37,880 INFO L495 AbstractCegarLoop]: Abstraction has 318 states and 334 transitions. [2023-12-21 05:42:37,880 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 17 states have (on average 2.5294117647058822) internal successors, (43), 18 states have internal predecessors, (43), 13 states have call successors, (51), 3 states have call predecessors, (51), 2 states have return successors, (49), 11 states have call predecessors, (49), 13 states have call successors, (49) [2023-12-21 05:42:37,880 INFO L276 IsEmpty]: Start isEmpty. Operand 318 states and 334 transitions. [2023-12-21 05:42:37,881 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 161 [2023-12-21 05:42:37,881 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:42:37,881 INFO L195 NwaCegarLoop]: trace histogram [29, 28, 28, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:42:37,886 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-21 05:42:38,086 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,SelfDestructingSolverStorable14 [2023-12-21 05:42:38,086 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:42:38,087 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:42:38,088 INFO L85 PathProgramCache]: Analyzing trace with hash 1264679123, now seen corresponding path program 2 times [2023-12-21 05:42:38,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:42:38,088 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1476879291] [2023-12-21 05:42:38,088 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:42:38,088 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:42:38,101 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:42:38,101 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [688601670] [2023-12-21 05:42:38,101 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-21 05:42:38,101 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:42:38,101 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:42:38,102 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-21 05:42:38,131 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-21 05:42:38,171 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-21 05:42:38,172 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 05:42:38,173 INFO L262 TraceCheckSpWp]: Trace formula consists of 356 conjuncts, 63 conjunts are in the unsatisfiable core [2023-12-21 05:42:38,175 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:42:38,790 INFO L134 CoverageAnalysis]: Checked inductivity of 1648 backedges. 204 proven. 88 refuted. 0 times theorem prover too weak. 1356 trivial. 0 not checked. [2023-12-21 05:42:38,790 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:43:00,508 INFO L134 CoverageAnalysis]: Checked inductivity of 1648 backedges. 204 proven. 88 refuted. 0 times theorem prover too weak. 1356 trivial. 0 not checked. [2023-12-21 05:43:00,509 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:43:00,509 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1476879291] [2023-12-21 05:43:00,509 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:43:00,509 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [688601670] [2023-12-21 05:43:00,509 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [688601670] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:43:00,509 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:43:00,509 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 12] total 22 [2023-12-21 05:43:00,509 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1005845283] [2023-12-21 05:43:00,509 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:43:00,509 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-12-21 05:43:00,509 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:43:00,510 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-12-21 05:43:00,510 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=101, Invalid=358, Unknown=3, NotChecked=0, Total=462 [2023-12-21 05:43:00,510 INFO L87 Difference]: Start difference. First operand 318 states and 334 transitions. Second operand has 22 states, 18 states have (on average 2.5) internal successors, (45), 17 states have internal predecessors, (45), 14 states have call successors, (58), 3 states have call predecessors, (58), 2 states have return successors, (56), 14 states have call predecessors, (56), 14 states have call successors, (56) [2023-12-21 05:44:24,272 WARN L293 SmtUtils]: Spent 1.39m on a formula simplification that was a NOOP. DAG size: 134 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 05:44:43,047 WARN L293 SmtUtils]: Spent 18.32s on a formula simplification that was a NOOP. DAG size: 107 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 05:45:09,011 WARN L293 SmtUtils]: Spent 25.47s on a formula simplification that was a NOOP. DAG size: 107 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 05:45:13,449 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.43s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:45:14,942 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.48s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:45:19,024 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:45:31,455 WARN L293 SmtUtils]: Spent 12.29s on a formula simplification that was a NOOP. DAG size: 138 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 05:45:41,217 WARN L293 SmtUtils]: Spent 9.19s on a formula simplification that was a NOOP. DAG size: 80 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 05:45:47,274 WARN L293 SmtUtils]: Spent 5.24s on a formula simplification that was a NOOP. DAG size: 80 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 05:45:51,283 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:45:55,472 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.18s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:45:59,691 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:46:04,302 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.08s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:46:08,616 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.07s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:46:24,340 WARN L293 SmtUtils]: Spent 14.14s 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-21 05:46:28,954 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.46s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:46:28,973 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:46:28,973 INFO L93 Difference]: Finished difference Result 339 states and 366 transitions. [2023-12-21 05:46:28,974 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-12-21 05:46:28,974 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 18 states have (on average 2.5) internal successors, (45), 17 states have internal predecessors, (45), 14 states have call successors, (58), 3 states have call predecessors, (58), 2 states have return successors, (56), 14 states have call predecessors, (56), 14 states have call successors, (56) Word has length 160 [2023-12-21 05:46:28,974 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:46:28,975 INFO L225 Difference]: With dead ends: 339 [2023-12-21 05:46:28,975 INFO L226 Difference]: Without dead ends: 307 [2023-12-21 05:46:28,976 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 329 GetRequests, 298 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 105 ImplicationChecksByTransitivity, 185.6s TimeCoverageRelationStatistics Valid=262, Invalid=791, Unknown=3, NotChecked=0, Total=1056 [2023-12-21 05:46:28,976 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 32 mSDsluCounter, 361 mSDsCounter, 0 mSdLazyCounter, 488 mSolverCounterSat, 122 mSolverCounterUnsat, 8 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 38.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 403 SdHoareTripleChecker+Invalid, 618 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 122 IncrementalHoareTripleChecker+Valid, 488 IncrementalHoareTripleChecker+Invalid, 8 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 38.1s IncrementalHoareTripleChecker+Time [2023-12-21 05:46:28,976 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 403 Invalid, 618 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [122 Valid, 488 Invalid, 8 Unknown, 0 Unchecked, 38.1s Time] [2023-12-21 05:46:28,978 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 307 states. [2023-12-21 05:46:29,055 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 307 to 306. [2023-12-21 05:46:29,055 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 306 states, 191 states have (on average 1.0157068062827226) internal successors, (194), 193 states have internal predecessors, (194), 62 states have call successors, (62), 52 states have call predecessors, (62), 52 states have return successors, (61), 60 states have call predecessors, (61), 61 states have call successors, (61) [2023-12-21 05:46:29,056 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 306 states to 306 states and 317 transitions. [2023-12-21 05:46:29,056 INFO L78 Accepts]: Start accepts. Automaton has 306 states and 317 transitions. Word has length 160 [2023-12-21 05:46:29,057 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:46:29,057 INFO L495 AbstractCegarLoop]: Abstraction has 306 states and 317 transitions. [2023-12-21 05:46:29,057 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 18 states have (on average 2.5) internal successors, (45), 17 states have internal predecessors, (45), 14 states have call successors, (58), 3 states have call predecessors, (58), 2 states have return successors, (56), 14 states have call predecessors, (56), 14 states have call successors, (56) [2023-12-21 05:46:29,057 INFO L276 IsEmpty]: Start isEmpty. Operand 306 states and 317 transitions. [2023-12-21 05:46:29,059 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 293 [2023-12-21 05:46:29,059 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:46:29,059 INFO L195 NwaCegarLoop]: trace histogram [52, 51, 51, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:46:29,079 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-21 05:46:29,264 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,SelfDestructingSolverStorable15 [2023-12-21 05:46:29,264 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:46:29,265 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:46:29,265 INFO L85 PathProgramCache]: Analyzing trace with hash -141720852, now seen corresponding path program 3 times [2023-12-21 05:46:29,265 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:46:29,265 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [621221472] [2023-12-21 05:46:29,265 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:46:29,265 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:46:29,274 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:46:29,274 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1875580178] [2023-12-21 05:46:29,274 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-21 05:46:29,274 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:46:29,274 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:46:29,280 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 05:46:29,282 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-12-21 05:46:29,530 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 31 check-sat command(s) [2023-12-21 05:46:29,530 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 05:46:29,532 INFO L262 TraceCheckSpWp]: Trace formula consists of 565 conjuncts, 23 conjunts are in the unsatisfiable core [2023-12-21 05:46:29,553 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:46:29,857 INFO L134 CoverageAnalysis]: Checked inductivity of 5582 backedges. 300 proven. 4880 refuted. 0 times theorem prover too weak. 402 trivial. 0 not checked. [2023-12-21 05:46:29,857 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:46:30,159 INFO L134 CoverageAnalysis]: Checked inductivity of 5582 backedges. 102 proven. 380 refuted. 0 times theorem prover too weak. 5100 trivial. 0 not checked. [2023-12-21 05:46:30,159 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:46:30,159 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [621221472] [2023-12-21 05:46:30,159 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:46:30,159 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1875580178] [2023-12-21 05:46:30,159 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1875580178] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:46:30,159 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:46:30,159 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14] total 26 [2023-12-21 05:46:30,160 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [348523173] [2023-12-21 05:46:30,160 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:46:30,160 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-12-21 05:46:30,160 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:46:30,161 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-12-21 05:46:30,161 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=281, Invalid=369, Unknown=0, NotChecked=0, Total=650 [2023-12-21 05:46:30,161 INFO L87 Difference]: Start difference. First operand 306 states and 317 transitions. Second operand has 26 states, 26 states have (on average 4.0) internal successors, (104), 26 states have internal predecessors, (104), 21 states have call successors, (103), 12 states have call predecessors, (103), 12 states have return successors, (102), 21 states have call predecessors, (102), 21 states have call successors, (102) [2023-12-21 05:46:30,981 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:46:30,981 INFO L93 Difference]: Finished difference Result 848 states and 878 transitions. [2023-12-21 05:46:30,981 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2023-12-21 05:46:30,982 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 4.0) internal successors, (104), 26 states have internal predecessors, (104), 21 states have call successors, (103), 12 states have call predecessors, (103), 12 states have return successors, (102), 21 states have call predecessors, (102), 21 states have call successors, (102) Word has length 292 [2023-12-21 05:46:30,982 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:46:30,984 INFO L225 Difference]: With dead ends: 848 [2023-12-21 05:46:30,984 INFO L226 Difference]: Without dead ends: 812 [2023-12-21 05:46:30,985 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 603 GetRequests, 558 SyntacticMatches, 0 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 286 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=796, Invalid=1366, Unknown=0, NotChecked=0, Total=2162 [2023-12-21 05:46:30,985 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 307 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 353 mSolverCounterSat, 205 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 307 SdHoareTripleChecker+Valid, 199 SdHoareTripleChecker+Invalid, 558 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 205 IncrementalHoareTripleChecker+Valid, 353 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-12-21 05:46:30,985 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [307 Valid, 199 Invalid, 558 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [205 Valid, 353 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-12-21 05:46:30,986 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 812 states. [2023-12-21 05:46:31,148 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 812 to 660. [2023-12-21 05:46:31,149 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 660 states, 414 states have (on average 1.0338164251207729) internal successors, (428), 426 states have internal predecessors, (428), 131 states have call successors, (131), 115 states have call predecessors, (131), 114 states have return successors, (129), 118 states have call predecessors, (129), 129 states have call successors, (129) [2023-12-21 05:46:31,150 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 660 states to 660 states and 688 transitions. [2023-12-21 05:46:31,151 INFO L78 Accepts]: Start accepts. Automaton has 660 states and 688 transitions. Word has length 292 [2023-12-21 05:46:31,151 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:46:31,151 INFO L495 AbstractCegarLoop]: Abstraction has 660 states and 688 transitions. [2023-12-21 05:46:31,151 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 4.0) internal successors, (104), 26 states have internal predecessors, (104), 21 states have call successors, (103), 12 states have call predecessors, (103), 12 states have return successors, (102), 21 states have call predecessors, (102), 21 states have call successors, (102) [2023-12-21 05:46:31,151 INFO L276 IsEmpty]: Start isEmpty. Operand 660 states and 688 transitions. [2023-12-21 05:46:31,154 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 329 [2023-12-21 05:46:31,154 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:46:31,154 INFO L195 NwaCegarLoop]: trace histogram [59, 58, 58, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:46:31,162 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2023-12-21 05:46:31,362 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:46:31,362 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:46:31,362 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:46:31,362 INFO L85 PathProgramCache]: Analyzing trace with hash 1483186871, now seen corresponding path program 3 times [2023-12-21 05:46:31,362 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:46:31,362 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [691140340] [2023-12-21 05:46:31,362 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:46:31,363 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:46:31,372 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:46:31,372 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [255640190] [2023-12-21 05:46:31,372 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-21 05:46:31,372 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:46:31,372 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:46:31,378 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 05:46:31,379 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2023-12-21 05:46:31,531 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-12-21 05:46:31,531 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 05:46:31,532 INFO L262 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 55 conjunts are in the unsatisfiable core [2023-12-21 05:46:31,536 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:47:16,637 INFO L134 CoverageAnalysis]: Checked inductivity of 7168 backedges. 1137 proven. 75 refuted. 0 times theorem prover too weak. 5956 trivial. 0 not checked. [2023-12-21 05:47:16,638 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:48:12,715 WARN L293 SmtUtils]: Spent 8.40s 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-21 05:48:21,247 INFO L134 CoverageAnalysis]: Checked inductivity of 7168 backedges. 957 proven. 52 refuted. 0 times theorem prover too weak. 6159 trivial. 0 not checked. [2023-12-21 05:48:21,248 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:48:21,248 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [691140340] [2023-12-21 05:48:21,248 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:48:21,248 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [255640190] [2023-12-21 05:48:21,248 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [255640190] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:48:21,248 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:48:21,248 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 21 [2023-12-21 05:48:21,248 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [408589888] [2023-12-21 05:48:21,248 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:48:21,249 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-12-21 05:48:21,249 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:48:21,249 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-12-21 05:48:21,249 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=321, Unknown=12, NotChecked=0, Total=420 [2023-12-21 05:48:21,249 INFO L87 Difference]: Start difference. First operand 660 states and 688 transitions. Second operand has 21 states, 16 states have (on average 2.0) internal successors, (32), 13 states have internal predecessors, (32), 13 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (34), 12 states have call predecessors, (34), 11 states have call successors, (34) [2023-12-21 05:48:50,701 WARN L293 SmtUtils]: Spent 29.07s on a formula simplification. DAG size of input: 96 DAG size of output: 99 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 05:48:55,715 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2023-12-21 05:48:59,725 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2023-12-21 05:49:03,625 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.39s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2023-12-21 05:49:07,943 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.25s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2023-12-21 05:49:12,319 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.38s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2023-12-21 05:49:16,668 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.35s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2023-12-21 05:49:20,669 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2023-12-21 05:49:24,672 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2023-12-21 05:49:28,700 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:49:32,701 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:49:36,705 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2023-12-21 05:49:40,753 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.05s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:49:44,755 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:49:49,088 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.73s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:49:53,092 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:50:16,850 WARN L293 SmtUtils]: Spent 22.41s on a formula simplification. DAG size of input: 85 DAG size of output: 79 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 05:50:22,486 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2023-12-21 05:50:27,916 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:50:31,984 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.05s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:50:38,471 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:50:43,092 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.62s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:50:47,801 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:50:51,804 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 05:51:15,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:51:15,966 INFO L93 Difference]: Finished difference Result 670 states and 696 transitions. [2023-12-21 05:51:15,967 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-21 05:51:15,967 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 16 states have (on average 2.0) internal successors, (32), 13 states have internal predecessors, (32), 13 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (34), 12 states have call predecessors, (34), 11 states have call successors, (34) Word has length 328 [2023-12-21 05:51:15,967 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:51:15,969 INFO L225 Difference]: With dead ends: 670 [2023-12-21 05:51:15,969 INFO L226 Difference]: Without dead ends: 625 [2023-12-21 05:51:15,969 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 663 GetRequests, 636 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 133 ImplicationChecksByTransitivity, 141.2s TimeCoverageRelationStatistics Valid=158, Invalid=527, Unknown=17, NotChecked=0, Total=702 [2023-12-21 05:51:15,970 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 28 mSDsluCounter, 166 mSDsCounter, 0 mSdLazyCounter, 227 mSolverCounterSat, 48 mSolverCounterUnsat, 20 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 94.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 189 SdHoareTripleChecker+Invalid, 295 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 227 IncrementalHoareTripleChecker+Invalid, 20 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 94.6s IncrementalHoareTripleChecker+Time [2023-12-21 05:51:15,970 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 189 Invalid, 295 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 227 Invalid, 20 Unknown, 0 Unchecked, 94.6s Time] [2023-12-21 05:51:15,971 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 625 states. [2023-12-21 05:51:16,147 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 625 to 625. [2023-12-21 05:51:16,148 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 625 states, 402 states have (on average 1.0024875621890548) internal successors, (403), 402 states have internal predecessors, (403), 112 states have call successors, (112), 111 states have call predecessors, (112), 110 states have return successors, (111), 111 states have call predecessors, (111), 111 states have call successors, (111) [2023-12-21 05:51:16,149 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 625 states to 625 states and 626 transitions. [2023-12-21 05:51:16,149 INFO L78 Accepts]: Start accepts. Automaton has 625 states and 626 transitions. Word has length 328 [2023-12-21 05:51:16,149 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:51:16,149 INFO L495 AbstractCegarLoop]: Abstraction has 625 states and 626 transitions. [2023-12-21 05:51:16,150 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 16 states have (on average 2.0) internal successors, (32), 13 states have internal predecessors, (32), 13 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (34), 12 states have call predecessors, (34), 11 states have call successors, (34) [2023-12-21 05:51:16,150 INFO L276 IsEmpty]: Start isEmpty. Operand 625 states and 626 transitions. [2023-12-21 05:51:16,156 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 629 [2023-12-21 05:51:16,156 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:51:16,156 INFO L195 NwaCegarLoop]: trace histogram [112, 111, 111, 23, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:51:16,162 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2023-12-21 05:51:16,362 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2023-12-21 05:51:16,362 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:51:16,363 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:51:16,363 INFO L85 PathProgramCache]: Analyzing trace with hash -1785250124, now seen corresponding path program 4 times [2023-12-21 05:51:16,363 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:51:16,363 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [19119261] [2023-12-21 05:51:16,363 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:51:16,363 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:51:16,384 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:51:16,384 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [305168891] [2023-12-21 05:51:16,384 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-21 05:51:16,384 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:51:16,384 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:51:16,385 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 05:51:16,400 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2023-12-21 05:51:16,627 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-21 05:51:16,627 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 05:51:16,631 INFO L262 TraceCheckSpWp]: Trace formula consists of 1354 conjuncts, 47 conjunts are in the unsatisfiable core [2023-12-21 05:51:16,653 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:51:17,366 INFO L134 CoverageAnalysis]: Checked inductivity of 26534 backedges. 660 proven. 24992 refuted. 0 times theorem prover too weak. 882 trivial. 0 not checked. [2023-12-21 05:51:17,366 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:51:18,216 INFO L134 CoverageAnalysis]: Checked inductivity of 26534 backedges. 222 proven. 1892 refuted. 0 times theorem prover too weak. 24420 trivial. 0 not checked. [2023-12-21 05:51:18,216 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:51:18,216 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [19119261] [2023-12-21 05:51:18,216 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:51:18,216 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [305168891] [2023-12-21 05:51:18,216 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [305168891] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:51:18,217 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:51:18,217 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 26] total 50 [2023-12-21 05:51:18,217 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [883612015] [2023-12-21 05:51:18,217 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:51:18,217 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2023-12-21 05:51:18,218 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:51:18,218 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2023-12-21 05:51:18,219 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1133, Invalid=1317, Unknown=0, NotChecked=0, Total=2450 [2023-12-21 05:51:18,219 INFO L87 Difference]: Start difference. First operand 625 states and 626 transitions. Second operand has 50 states, 50 states have (on average 4.24) internal successors, (212), 50 states have internal predecessors, (212), 45 states have call successors, (223), 24 states have call predecessors, (223), 24 states have return successors, (222), 45 states have call predecessors, (222), 45 states have call successors, (222) [2023-12-21 05:51:20,167 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:51:20,167 INFO L93 Difference]: Finished difference Result 1307 states and 1331 transitions. [2023-12-21 05:51:20,167 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2023-12-21 05:51:20,168 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 50 states have (on average 4.24) internal successors, (212), 50 states have internal predecessors, (212), 45 states have call successors, (223), 24 states have call predecessors, (223), 24 states have return successors, (222), 45 states have call predecessors, (222), 45 states have call successors, (222) Word has length 628 [2023-12-21 05:51:20,168 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:51:20,171 INFO L225 Difference]: With dead ends: 1307 [2023-12-21 05:51:20,171 INFO L226 Difference]: Without dead ends: 1297 [2023-12-21 05:51:20,173 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1299 GetRequests, 1206 SyntacticMatches, 0 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1288 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=3316, Invalid=5614, Unknown=0, NotChecked=0, Total=8930 [2023-12-21 05:51:20,174 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 371 mSDsluCounter, 256 mSDsCounter, 0 mSdLazyCounter, 553 mSolverCounterSat, 301 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 371 SdHoareTripleChecker+Valid, 276 SdHoareTripleChecker+Invalid, 854 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 301 IncrementalHoareTripleChecker+Valid, 553 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-12-21 05:51:20,174 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [371 Valid, 276 Invalid, 854 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [301 Valid, 553 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-12-21 05:51:20,175 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1297 states. [2023-12-21 05:51:20,523 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1297 to 1297. [2023-12-21 05:51:20,525 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1297 states, 834 states have (on average 1.001199040767386) internal successors, (835), 834 states have internal predecessors, (835), 232 states have call successors, (232), 231 states have call predecessors, (232), 230 states have return successors, (231), 231 states have call predecessors, (231), 231 states have call successors, (231) [2023-12-21 05:51:20,527 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1297 states to 1297 states and 1298 transitions. [2023-12-21 05:51:20,528 INFO L78 Accepts]: Start accepts. Automaton has 1297 states and 1298 transitions. Word has length 628 [2023-12-21 05:51:20,528 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:51:20,528 INFO L495 AbstractCegarLoop]: Abstraction has 1297 states and 1298 transitions. [2023-12-21 05:51:20,529 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 50 states, 50 states have (on average 4.24) internal successors, (212), 50 states have internal predecessors, (212), 45 states have call successors, (223), 24 states have call predecessors, (223), 24 states have return successors, (222), 45 states have call predecessors, (222), 45 states have call successors, (222) [2023-12-21 05:51:20,529 INFO L276 IsEmpty]: Start isEmpty. Operand 1297 states and 1298 transitions. [2023-12-21 05:51:20,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1301 [2023-12-21 05:51:20,541 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:51:20,541 INFO L195 NwaCegarLoop]: trace histogram [232, 231, 231, 47, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:51:20,562 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2023-12-21 05:51:20,747 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:51:20,748 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:51:20,748 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:51:20,748 INFO L85 PathProgramCache]: Analyzing trace with hash -997767612, now seen corresponding path program 5 times [2023-12-21 05:51:20,748 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:51:20,748 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1042219652] [2023-12-21 05:51:20,748 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:51:20,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:51:20,775 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:51:20,775 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [407197650] [2023-12-21 05:51:20,776 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2023-12-21 05:51:20,776 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:51:20,776 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:51:20,777 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 05:51:20,780 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2023-12-21 05:53:02,964 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 163 check-sat command(s) [2023-12-21 05:53:02,964 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 05:53:03,005 INFO L262 TraceCheckSpWp]: Trace formula consists of 2770 conjuncts, 95 conjunts are in the unsatisfiable core [2023-12-21 05:53:03,018 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 05:53:04,484 INFO L134 CoverageAnalysis]: Checked inductivity of 115094 backedges. 1380 proven. 111872 refuted. 0 times theorem prover too weak. 1842 trivial. 0 not checked. [2023-12-21 05:53:04,484 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 05:53:06,828 INFO L134 CoverageAnalysis]: Checked inductivity of 115094 backedges. 462 proven. 8372 refuted. 0 times theorem prover too weak. 106260 trivial. 0 not checked. [2023-12-21 05:53:06,828 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 05:53:06,828 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1042219652] [2023-12-21 05:53:06,828 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 05:53:06,828 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [407197650] [2023-12-21 05:53:06,828 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [407197650] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 05:53:06,828 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 05:53:06,829 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 50] total 98 [2023-12-21 05:53:06,829 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1057522940] [2023-12-21 05:53:06,829 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 05:53:06,833 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 98 states [2023-12-21 05:53:06,833 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 05:53:06,838 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 98 interpolants. [2023-12-21 05:53:06,844 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=4565, Invalid=4941, Unknown=0, NotChecked=0, Total=9506 [2023-12-21 05:53:06,846 INFO L87 Difference]: Start difference. First operand 1297 states and 1298 transitions. Second operand has 98 states, 98 states have (on average 4.36734693877551) internal successors, (428), 98 states have internal predecessors, (428), 93 states have call successors, (463), 48 states have call predecessors, (463), 48 states have return successors, (462), 93 states have call predecessors, (462), 93 states have call successors, (462) [2023-12-21 05:53:13,538 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 05:53:13,539 INFO L93 Difference]: Finished difference Result 2651 states and 2699 transitions. [2023-12-21 05:53:13,539 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 190 states. [2023-12-21 05:53:13,540 INFO L78 Accepts]: Start accepts. Automaton has has 98 states, 98 states have (on average 4.36734693877551) internal successors, (428), 98 states have internal predecessors, (428), 93 states have call successors, (463), 48 states have call predecessors, (463), 48 states have return successors, (462), 93 states have call predecessors, (462), 93 states have call successors, (462) Word has length 1300 [2023-12-21 05:53:13,541 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 05:53:13,547 INFO L225 Difference]: With dead ends: 2651 [2023-12-21 05:53:13,547 INFO L226 Difference]: Without dead ends: 2641 [2023-12-21 05:53:13,553 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2691 GetRequests, 2502 SyntacticMatches, 0 SemanticMatches, 189 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5452 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=13540, Invalid=22750, Unknown=0, NotChecked=0, Total=36290 [2023-12-21 05:53:13,554 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 743 mSDsluCounter, 466 mSDsCounter, 0 mSdLazyCounter, 1129 mSolverCounterSat, 601 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 743 SdHoareTripleChecker+Valid, 486 SdHoareTripleChecker+Invalid, 1730 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 601 IncrementalHoareTripleChecker+Valid, 1129 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2023-12-21 05:53:13,554 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [743 Valid, 486 Invalid, 1730 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [601 Valid, 1129 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2023-12-21 05:53:13,555 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2641 states. [2023-12-21 05:53:14,298 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2641 to 2641. [2023-12-21 05:53:14,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2641 states, 1698 states have (on average 1.0005889281507656) internal successors, (1699), 1698 states have internal predecessors, (1699), 472 states have call successors, (472), 471 states have call predecessors, (472), 470 states have return successors, (471), 471 states have call predecessors, (471), 471 states have call successors, (471) [2023-12-21 05:53:14,305 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2641 states to 2641 states and 2642 transitions. [2023-12-21 05:53:14,305 INFO L78 Accepts]: Start accepts. Automaton has 2641 states and 2642 transitions. Word has length 1300 [2023-12-21 05:53:14,306 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 05:53:14,306 INFO L495 AbstractCegarLoop]: Abstraction has 2641 states and 2642 transitions. [2023-12-21 05:53:14,307 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 98 states, 98 states have (on average 4.36734693877551) internal successors, (428), 98 states have internal predecessors, (428), 93 states have call successors, (463), 48 states have call predecessors, (463), 48 states have return successors, (462), 93 states have call predecessors, (462), 93 states have call successors, (462) [2023-12-21 05:53:14,307 INFO L276 IsEmpty]: Start isEmpty. Operand 2641 states and 2642 transitions. [2023-12-21 05:53:14,349 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2645 [2023-12-21 05:53:14,350 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 05:53:14,350 INFO L195 NwaCegarLoop]: trace histogram [472, 471, 471, 95, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:53:14,368 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2023-12-21 05:53:14,565 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:53:14,566 INFO L420 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 05:53:14,566 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 05:53:14,566 INFO L85 PathProgramCache]: Analyzing trace with hash 693736804, now seen corresponding path program 6 times [2023-12-21 05:53:14,566 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 05:53:14,566 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [179098288] [2023-12-21 05:53:14,566 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 05:53:14,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 05:53:14,642 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 05:53:14,642 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1894220312] [2023-12-21 05:53:14,642 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2023-12-21 05:53:14,642 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 05:53:14,642 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 05:53:14,643 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 05:53:14,645 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process Received shutdown request... [2023-12-21 05:56:57,382 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-21 05:56:57,382 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2023-12-21 05:56:58,446 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 [2023-12-21 05:56:58,592 WARN L435 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forcibly destroying the process [2023-12-21 05:56:58,600 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 137 [2023-12-21 05:56:58,601 ERROR L246 FreeRefinementEngine]: Caught known exception: Timeout or Toolchain cancelled by user [2023-12-21 05:56:58,603 INFO L805 garLoopResultBuilder]: Registering result TIMEOUT for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-12-21 05:56:58,603 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20 [2023-12-21 05:56:58,603 WARN L619 AbstractCegarLoop]: Verification canceled: while NwaCegarLoop was analyzing trace of length 2645 with TraceHistMax 472,while AutomatonFreeRefinementEngine was Timeout during CAMEL. [2023-12-21 05:56:58,606 INFO L445 BasicCegarLoop]: Path program histogram: [6, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 05:56:58,607 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2023-12-21 05:56:58,609 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 21.12 05:56:58 BoogieIcfgContainer [2023-12-21 05:56:58,609 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-12-21 05:56:58,609 INFO L158 Benchmark]: Toolchain (without parser) took 879956.11ms. Allocated memory was 204.5MB in the beginning and 522.2MB in the end (delta: 317.7MB). Free memory was 140.8MB in the beginning and 346.0MB in the end (delta: -205.2MB). Peak memory consumption was 113.6MB. Max. memory is 8.0GB. [2023-12-21 05:56:58,610 INFO L158 Benchmark]: CDTParser took 0.41ms. Allocated memory is still 204.5MB. Free memory was 154.0MB in the beginning and 153.9MB in the end (delta: 89.6kB). There was no memory consumed. Max. memory is 8.0GB. [2023-12-21 05:56:58,611 INFO L158 Benchmark]: CACSL2BoogieTranslator took 188.53ms. Allocated memory is still 204.5MB. Free memory was 140.5MB in the beginning and 129.0MB in the end (delta: 11.5MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2023-12-21 05:56:58,612 INFO L158 Benchmark]: Boogie Procedure Inliner took 35.68ms. Allocated memory is still 204.5MB. Free memory was 129.0MB in the beginning and 127.5MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2023-12-21 05:56:58,612 INFO L158 Benchmark]: Boogie Preprocessor took 39.71ms. Allocated memory is still 204.5MB. Free memory was 127.5MB in the beginning and 125.8MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2023-12-21 05:56:58,612 INFO L158 Benchmark]: RCFGBuilder took 291.26ms. Allocated memory was 204.5MB in the beginning and 252.7MB in the end (delta: 48.2MB). Free memory was 125.8MB in the beginning and 218.5MB in the end (delta: -92.6MB). Peak memory consumption was 17.2MB. Max. memory is 8.0GB. [2023-12-21 05:56:58,612 INFO L158 Benchmark]: TraceAbstraction took 879395.90ms. Allocated memory was 252.7MB in the beginning and 522.2MB in the end (delta: 269.5MB). Free memory was 217.5MB in the beginning and 346.0MB in the end (delta: -128.5MB). Peak memory consumption was 140.4MB. Max. memory is 8.0GB. [2023-12-21 05:56:58,619 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.41ms. Allocated memory is still 204.5MB. Free memory was 154.0MB in the beginning and 153.9MB in the end (delta: 89.6kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 188.53ms. Allocated memory is still 204.5MB. Free memory was 140.5MB in the beginning and 129.0MB in the end (delta: 11.5MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Procedure Inliner took 35.68ms. Allocated memory is still 204.5MB. Free memory was 129.0MB in the beginning and 127.5MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * Boogie Preprocessor took 39.71ms. Allocated memory is still 204.5MB. Free memory was 127.5MB in the beginning and 125.8MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 291.26ms. Allocated memory was 204.5MB in the beginning and 252.7MB in the end (delta: 48.2MB). Free memory was 125.8MB in the beginning and 218.5MB in the end (delta: -92.6MB). Peak memory consumption was 17.2MB. Max. memory is 8.0GB. * TraceAbstraction took 879395.90ms. Allocated memory was 252.7MB in the beginning and 522.2MB in the end (delta: 269.5MB). Free memory was 217.5MB in the beginning and 346.0MB in the end (delta: -128.5MB). Peak memory consumption was 140.4MB. 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: 17]: Timeout (TraceAbstraction) Unable to prove that a call to reach_error is unreachable (line 17). Cancelled while NwaCegarLoop was analyzing trace of length 2645 with TraceHistMax 472,while AutomatonFreeRefinementEngine was Timeout during CAMEL. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 23 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 879.3s, OverallIterations: 21, TraceHistogramMax: 472, PathProgramHistogramMax: 6, EmptinessCheckTime: 0.1s, AutomataDifference: 401.6s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 29 mSolverCounterUnknown, 1985 SdHoareTripleChecker+Valid, 142.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 1867 mSDsluCounter, 3654 SdHoareTripleChecker+Invalid, 141.3s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 3120 mSDsCounter, 1683 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 5293 IncrementalHoareTripleChecker+Invalid, 7005 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 1683 mSolverCounterUnsat, 534 mSDtfsCounter, 5293 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 7136 GetRequests, 6554 SyntacticMatches, 2 SemanticMatches, 580 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7628 ImplicationChecksByTransitivity, 336.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=2641occurred in iteration=20, InterpolantAutomatonStates: 517, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 2.1s AutomataMinimizationTime, 20 MinimizatonAttempts, 234 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.3s SsaConstructionTime, 103.0s SatisfiabilityAnalysisTime, 144.0s InterpolantComputationTime, 3545 NumberOfCodeBlocks, 3193 NumberOfCodeBlocksAsserted, 222 NumberOfCheckSat, 6902 ConstructedInterpolants, 1 QuantifiedInterpolants, 25942 SizeOfPredicates, 133 NumberOfNonLiveVariables, 7178 ConjunctsInSsa, 578 ConjunctsInUnsatCore, 36 InterpolantComputations, 3 PerfectInterpolantSequences, 166641/320666 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