/usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.use.bitabs.translation true -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -i ../../../trunk/examples/svcomp/nla-digbench/egcd2-ll.c -------------------------------------------------------------------------------- This is Ultimate 0.2.4-tmp.fs.bitabs-eval-d9c3e40-m [2023-12-19 18:52:37,167 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-19 18:52:37,232 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-19 18:52:37,235 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-19 18:52:37,235 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-19 18:52:37,254 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-19 18:52:37,254 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-19 18:52:37,254 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-19 18:52:37,255 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-12-19 18:52:37,255 INFO L153 SettingsManager]: * Use memory slicer=true [2023-12-19 18:52:37,255 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-19 18:52:37,255 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-19 18:52:37,260 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-12-19 18:52:37,260 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-12-19 18:52:37,260 INFO L153 SettingsManager]: * Use SBE=true [2023-12-19 18:52:37,260 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-19 18:52:37,261 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-19 18:52:37,261 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-19 18:52:37,261 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-19 18:52:37,261 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-19 18:52:37,261 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-19 18:52:37,262 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-19 18:52:37,262 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-19 18:52:37,262 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-19 18:52:37,262 INFO L153 SettingsManager]: * Allow undefined functions=false [2023-12-19 18:52:37,263 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-19 18:52:37,263 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-19 18:52:37,263 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-19 18:52:37,263 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-19 18:52:37,263 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-12-19 18:52:37,264 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-19 18:52:37,264 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-19 18:52:37,264 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-19 18:52:37,264 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-19 18:52:37,264 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-19 18:52:37,264 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-19 18:52:37,265 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-12-19 18:52:37,265 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-19 18:52:37,265 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-19 18:52:37,265 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-12-19 18:52:37,265 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-19 18:52:37,266 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-12-19 18:52:37,266 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-19 18:52:37,266 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Use bitabs translation -> true [2023-12-19 18:52:37,444 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-19 18:52:37,461 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-19 18:52:37,463 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-19 18:52:37,464 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-19 18:52:37,464 INFO L274 PluginConnector]: CDTParser initialized [2023-12-19 18:52:37,465 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench/egcd2-ll.c [2023-12-19 18:52:38,463 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-19 18:52:38,573 INFO L384 CDTParser]: Found 1 translation units. [2023-12-19 18:52:38,576 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench/egcd2-ll.c [2023-12-19 18:52:38,588 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c3ff6b0b5/df13e0c4ecc94ba6aeef72c2bc0febe6/FLAG7521cf3ef [2023-12-19 18:52:38,604 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c3ff6b0b5/df13e0c4ecc94ba6aeef72c2bc0febe6 [2023-12-19 18:52:38,606 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-19 18:52:38,608 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2023-12-19 18:52:38,609 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-19 18:52:38,609 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-19 18:52:38,613 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-19 18:52:38,614 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,614 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1ebe440c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38, skipping insertion in model container [2023-12-19 18:52:38,614 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,635 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-19 18:52:38,769 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/egcd2-ll.c[490,503] [2023-12-19 18:52:38,783 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-19 18:52:38,791 INFO L202 MainTranslator]: Completed pre-run [2023-12-19 18:52:38,802 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/egcd2-ll.c[490,503] [2023-12-19 18:52:38,809 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-19 18:52:38,819 INFO L206 MainTranslator]: Completed translation [2023-12-19 18:52:38,820 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38 WrapperNode [2023-12-19 18:52:38,820 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-19 18:52:38,821 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-19 18:52:38,821 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-19 18:52:38,821 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-19 18:52:38,826 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,831 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,846 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 77 [2023-12-19 18:52:38,846 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-19 18:52:38,847 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-19 18:52:38,847 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-19 18:52:38,847 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-19 18:52:38,861 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,861 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,862 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,871 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-19 18:52:38,871 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,871 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,874 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,876 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,877 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,878 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,879 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-19 18:52:38,880 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-19 18:52:38,880 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-19 18:52:38,880 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-19 18:52:38,881 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38" (1/1) ... [2023-12-19 18:52:38,885 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-19 18:52:38,893 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:52:38,903 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-19 18:52:38,905 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-19 18:52:38,924 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-19 18:52:38,925 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-12-19 18:52:38,925 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-12-19 18:52:38,925 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-12-19 18:52:38,925 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-19 18:52:38,925 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-19 18:52:38,925 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-12-19 18:52:38,925 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-12-19 18:52:38,984 INFO L241 CfgBuilder]: Building ICFG [2023-12-19 18:52:38,993 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-19 18:52:39,122 INFO L282 CfgBuilder]: Performing block encoding [2023-12-19 18:52:39,138 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-19 18:52:39,138 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-12-19 18:52:39,139 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.12 06:52:39 BoogieIcfgContainer [2023-12-19 18:52:39,139 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-19 18:52:39,140 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-19 18:52:39,140 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-19 18:52:39,142 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-19 18:52:39,142 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.12 06:52:38" (1/3) ... [2023-12-19 18:52:39,143 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@21551afc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.12 06:52:39, skipping insertion in model container [2023-12-19 18:52:39,143 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 06:52:38" (2/3) ... [2023-12-19 18:52:39,143 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@21551afc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.12 06:52:39, skipping insertion in model container [2023-12-19 18:52:39,143 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.12 06:52:39" (3/3) ... [2023-12-19 18:52:39,144 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll.c [2023-12-19 18:52:39,155 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-19 18:52:39,155 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-19 18:52:39,181 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-19 18:52:39,185 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;@653816aa, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-19 18:52:39,186 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-19 18:52:39,188 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 15 states have (on average 1.6) internal successors, (24), 17 states have internal predecessors, (24), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-12-19 18:52:39,193 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-12-19 18:52:39,193 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:52:39,193 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:52:39,193 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:52:39,196 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:52:39,197 INFO L85 PathProgramCache]: Analyzing trace with hash 883046315, now seen corresponding path program 1 times [2023-12-19 18:52:39,202 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:52:39,202 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [953107076] [2023-12-19 18:52:39,202 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:39,203 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:52:39,259 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 18:52:39,275 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:52:39,275 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [953107076] [2023-12-19 18:52:39,275 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-19 18:52:39,276 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1953723326] [2023-12-19 18:52:39,276 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:39,276 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:39,276 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:52:39,278 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-19 18:52:39,296 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-19 18:52:39,330 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 18:52:39,332 INFO L262 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 1 conjunts are in the unsatisfiable core [2023-12-19 18:52:39,335 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:52:39,356 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-12-19 18:52:39,356 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-19 18:52:39,356 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1953723326] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-19 18:52:39,357 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-19 18:52:39,357 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-19 18:52:39,358 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [352629161] [2023-12-19 18:52:39,358 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-19 18:52:39,379 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-12-19 18:52:39,379 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:52:39,418 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-12-19 18:52:39,419 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-19 18:52:39,420 INFO L87 Difference]: Start difference. First operand has 29 states, 15 states have (on average 1.6) internal successors, (24), 17 states have internal predecessors, (24), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-19 18:52:39,442 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:52:39,442 INFO L93 Difference]: Finished difference Result 56 states and 95 transitions. [2023-12-19 18:52:39,443 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-12-19 18:52:39,443 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 27 [2023-12-19 18:52:39,444 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:52:39,448 INFO L225 Difference]: With dead ends: 56 [2023-12-19 18:52:39,448 INFO L226 Difference]: Without dead ends: 27 [2023-12-19 18:52:39,450 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 26 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-19 18:52:39,452 INFO L413 NwaCegarLoop]: 36 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, 36 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-19 18:52:39,453 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 36 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 18:52:39,463 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2023-12-19 18:52:39,475 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2023-12-19 18:52:39,476 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 16 states have internal predecessors, (17), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-19 18:52:39,477 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 36 transitions. [2023-12-19 18:52:39,478 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 36 transitions. Word has length 27 [2023-12-19 18:52:39,479 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:52:39,479 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 36 transitions. [2023-12-19 18:52:39,479 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-19 18:52:39,479 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 36 transitions. [2023-12-19 18:52:39,480 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-12-19 18:52:39,480 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:52:39,480 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:52:39,490 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-12-19 18:52:39,686 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-12-19 18:52:39,686 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:52:39,687 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:52:39,687 INFO L85 PathProgramCache]: Analyzing trace with hash -296693581, now seen corresponding path program 1 times [2023-12-19 18:52:39,687 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:52:39,687 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2069069946] [2023-12-19 18:52:39,688 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:39,688 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:52:39,700 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:52:39,700 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [132160524] [2023-12-19 18:52:39,700 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:39,701 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:39,701 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:52:39,709 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-19 18:52:39,714 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-19 18:52:39,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 18:52:39,796 INFO L262 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 7 conjunts are in the unsatisfiable core [2023-12-19 18:52:39,797 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:52:39,869 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-12-19 18:52:39,870 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:52:39,930 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-12-19 18:52:39,930 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:52:39,931 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2069069946] [2023-12-19 18:52:39,931 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:52:39,931 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [132160524] [2023-12-19 18:52:39,931 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [132160524] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 18:52:39,931 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 18:52:39,931 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2023-12-19 18:52:39,931 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1169952242] [2023-12-19 18:52:39,932 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 18:52:39,932 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-12-19 18:52:39,933 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:52:39,933 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-12-19 18:52:39,933 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2023-12-19 18:52:39,934 INFO L87 Difference]: Start difference. First operand 27 states and 36 transitions. Second operand has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-19 18:52:40,002 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:52:40,003 INFO L93 Difference]: Finished difference Result 44 states and 59 transitions. [2023-12-19 18:52:40,003 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-19 18:52:40,003 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2023-12-19 18:52:40,003 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:52:40,004 INFO L225 Difference]: With dead ends: 44 [2023-12-19 18:52:40,004 INFO L226 Difference]: Without dead ends: 36 [2023-12-19 18:52:40,005 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 47 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2023-12-19 18:52:40,005 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 20 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 66 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 76 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 66 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 18:52:40,006 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 123 Invalid, 76 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 66 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 18:52:40,008 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2023-12-19 18:52:40,019 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 29. [2023-12-19 18:52:40,020 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 16 states have (on average 1.1875) internal successors, (19), 17 states have internal predecessors, (19), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-19 18:52:40,022 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 38 transitions. [2023-12-19 18:52:40,022 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 38 transitions. Word has length 28 [2023-12-19 18:52:40,022 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:52:40,023 INFO L495 AbstractCegarLoop]: Abstraction has 29 states and 38 transitions. [2023-12-19 18:52:40,023 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-19 18:52:40,023 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 38 transitions. [2023-12-19 18:52:40,023 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2023-12-19 18:52:40,023 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:52:40,024 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:52:40,044 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-19 18:52:40,228 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2023-12-19 18:52:40,229 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:52:40,231 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:52:40,231 INFO L85 PathProgramCache]: Analyzing trace with hash -603309185, now seen corresponding path program 1 times [2023-12-19 18:52:40,231 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:52:40,232 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [237174145] [2023-12-19 18:52:40,232 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:40,233 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:52:40,255 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:52:40,256 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1153049651] [2023-12-19 18:52:40,256 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:40,256 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:40,256 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:52:40,260 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-19 18:52:40,294 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-19 18:52:40,303 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 18:52:40,305 INFO L262 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 17 conjunts are in the unsatisfiable core [2023-12-19 18:52:40,310 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:52:40,401 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-12-19 18:52:40,401 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:52:40,451 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-12-19 18:52:40,452 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:52:40,452 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [237174145] [2023-12-19 18:52:40,452 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:52:40,452 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1153049651] [2023-12-19 18:52:40,452 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1153049651] provided 1 perfect and 1 imperfect interpolant sequences [2023-12-19 18:52:40,452 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-12-19 18:52:40,452 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 12 [2023-12-19 18:52:40,453 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1215764417] [2023-12-19 18:52:40,453 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-19 18:52:40,453 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-19 18:52:40,453 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:52:40,453 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-19 18:52:40,454 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=107, Unknown=0, NotChecked=0, Total=132 [2023-12-19 18:52:40,454 INFO L87 Difference]: Start difference. First operand 29 states and 38 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-19 18:52:40,495 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:52:40,495 INFO L93 Difference]: Finished difference Result 35 states and 43 transitions. [2023-12-19 18:52:40,495 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-19 18:52:40,496 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2023-12-19 18:52:40,496 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:52:40,497 INFO L225 Difference]: With dead ends: 35 [2023-12-19 18:52:40,497 INFO L226 Difference]: Without dead ends: 33 [2023-12-19 18:52:40,498 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 46 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2023-12-19 18:52:40,500 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 7 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 102 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 18:52:40,503 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 102 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 18:52:40,504 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2023-12-19 18:52:40,509 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2023-12-19 18:52:40,509 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 19 states have (on average 1.1578947368421053) internal successors, (22), 20 states have internal predecessors, (22), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-19 18:52:40,510 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 41 transitions. [2023-12-19 18:52:40,510 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 41 transitions. Word has length 29 [2023-12-19 18:52:40,510 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:52:40,510 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 41 transitions. [2023-12-19 18:52:40,510 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-19 18:52:40,510 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 41 transitions. [2023-12-19 18:52:40,511 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2023-12-19 18:52:40,511 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:52:40,511 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:52:40,527 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-12-19 18:52:40,716 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:40,717 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:52:40,717 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:52:40,717 INFO L85 PathProgramCache]: Analyzing trace with hash -1233313153, now seen corresponding path program 1 times [2023-12-19 18:52:40,717 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:52:40,717 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1234982620] [2023-12-19 18:52:40,717 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:40,718 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:52:40,725 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:52:40,725 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [980039749] [2023-12-19 18:52:40,725 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:40,725 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:40,726 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:52:40,727 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-19 18:52:40,732 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-19 18:52:40,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 18:52:40,766 INFO L262 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 23 conjunts are in the unsatisfiable core [2023-12-19 18:52:40,768 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:52:40,908 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 4 proven. 7 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-12-19 18:52:40,910 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:52:40,988 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-12-19 18:52:40,988 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:52:40,989 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1234982620] [2023-12-19 18:52:40,989 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:52:40,989 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [980039749] [2023-12-19 18:52:40,989 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [980039749] provided 1 perfect and 1 imperfect interpolant sequences [2023-12-19 18:52:40,989 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-12-19 18:52:40,989 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [11] total 13 [2023-12-19 18:52:40,989 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [708768160] [2023-12-19 18:52:40,989 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-19 18:52:40,989 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-19 18:52:40,989 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:52:40,990 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-19 18:52:40,991 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2023-12-19 18:52:40,991 INFO L87 Difference]: Start difference. First operand 33 states and 41 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-12-19 18:52:41,033 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:52:41,033 INFO L93 Difference]: Finished difference Result 46 states and 58 transitions. [2023-12-19 18:52:41,034 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-19 18:52:41,034 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2023-12-19 18:52:41,035 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:52:41,036 INFO L225 Difference]: With dead ends: 46 [2023-12-19 18:52:41,036 INFO L226 Difference]: Without dead ends: 44 [2023-12-19 18:52:41,036 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 55 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=33, Invalid=149, Unknown=0, NotChecked=0, Total=182 [2023-12-19 18:52:41,039 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 6 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 18:52:41,040 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 117 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 18:52:41,041 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2023-12-19 18:52:41,053 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 43. [2023-12-19 18:52:41,053 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 24 states have (on average 1.1666666666666667) internal successors, (28), 25 states have internal predecessors, (28), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-12-19 18:52:41,054 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 55 transitions. [2023-12-19 18:52:41,054 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 55 transitions. Word has length 34 [2023-12-19 18:52:41,054 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:52:41,055 INFO L495 AbstractCegarLoop]: Abstraction has 43 states and 55 transitions. [2023-12-19 18:52:41,055 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-12-19 18:52:41,055 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 55 transitions. [2023-12-19 18:52:41,057 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2023-12-19 18:52:41,057 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:52:41,057 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:52:41,062 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-12-19 18:52:41,261 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:41,261 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:52:41,262 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:52:41,262 INFO L85 PathProgramCache]: Analyzing trace with hash -1025526977, now seen corresponding path program 1 times [2023-12-19 18:52:41,262 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:52:41,262 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1056608341] [2023-12-19 18:52:41,262 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:41,262 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:52:41,271 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:52:41,272 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [563076696] [2023-12-19 18:52:41,303 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:41,303 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:41,303 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:52:41,304 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-19 18:52:41,332 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-19 18:52:41,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 18:52:41,341 INFO L262 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 23 conjunts are in the unsatisfiable core [2023-12-19 18:52:41,344 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:52:41,494 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-12-19 18:52:41,497 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:52:41,575 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-12-19 18:52:41,576 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:52:41,579 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1056608341] [2023-12-19 18:52:41,579 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:52:41,579 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [563076696] [2023-12-19 18:52:41,579 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [563076696] provided 1 perfect and 1 imperfect interpolant sequences [2023-12-19 18:52:41,579 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-12-19 18:52:41,579 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [11] total 13 [2023-12-19 18:52:41,579 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1916012918] [2023-12-19 18:52:41,579 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-19 18:52:41,579 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-19 18:52:41,579 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:52:41,580 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-19 18:52:41,580 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2023-12-19 18:52:41,580 INFO L87 Difference]: Start difference. First operand 43 states and 55 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-19 18:52:41,622 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:52:41,622 INFO L93 Difference]: Finished difference Result 50 states and 61 transitions. [2023-12-19 18:52:41,622 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-19 18:52:41,622 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 39 [2023-12-19 18:52:41,623 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:52:41,623 INFO L225 Difference]: With dead ends: 50 [2023-12-19 18:52:41,623 INFO L226 Difference]: Without dead ends: 48 [2023-12-19 18:52:41,624 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=33, Invalid=149, Unknown=0, NotChecked=0, Total=182 [2023-12-19 18:52:41,624 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 77 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 18:52:41,626 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 108 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 18:52:41,626 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2023-12-19 18:52:41,633 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 47. [2023-12-19 18:52:41,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 28 states have internal predecessors, (31), 14 states have call successors, (14), 5 states have call predecessors, (14), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-12-19 18:52:41,637 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 58 transitions. [2023-12-19 18:52:41,637 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 58 transitions. Word has length 39 [2023-12-19 18:52:41,638 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:52:41,638 INFO L495 AbstractCegarLoop]: Abstraction has 47 states and 58 transitions. [2023-12-19 18:52:41,638 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-19 18:52:41,639 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 58 transitions. [2023-12-19 18:52:41,639 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2023-12-19 18:52:41,639 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:52:41,639 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:52:41,645 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-19 18:52:41,843 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:41,843 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:52:41,843 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:52:41,843 INFO L85 PathProgramCache]: Analyzing trace with hash 626438719, now seen corresponding path program 1 times [2023-12-19 18:52:41,843 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:52:41,844 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1213119893] [2023-12-19 18:52:41,844 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:41,844 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:52:41,851 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:52:41,851 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [35979201] [2023-12-19 18:52:41,851 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:41,851 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:41,851 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:52:41,852 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-19 18:52:41,873 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-19 18:52:41,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 18:52:41,897 INFO L262 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 19 conjunts are in the unsatisfiable core [2023-12-19 18:52:41,902 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:52:42,003 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-12-19 18:52:42,003 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:52:42,093 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:52:42,093 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1213119893] [2023-12-19 18:52:42,093 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:52:42,093 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [35979201] [2023-12-19 18:52:42,093 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [35979201] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-19 18:52:42,093 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-19 18:52:42,093 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2023-12-19 18:52:42,093 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2012782617] [2023-12-19 18:52:42,093 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-19 18:52:42,094 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-12-19 18:52:42,094 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:52:42,094 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-12-19 18:52:42,094 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2023-12-19 18:52:42,094 INFO L87 Difference]: Start difference. First operand 47 states and 58 transitions. Second operand has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-12-19 18:52:42,181 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:52:42,181 INFO L93 Difference]: Finished difference Result 54 states and 64 transitions. [2023-12-19 18:52:42,181 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-12-19 18:52:42,181 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 44 [2023-12-19 18:52:42,182 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:52:42,183 INFO L225 Difference]: With dead ends: 54 [2023-12-19 18:52:42,183 INFO L226 Difference]: Without dead ends: 52 [2023-12-19 18:52:42,184 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2023-12-19 18:52:42,184 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 11 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 95 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 96 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 95 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-19 18:52:42,184 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 117 Invalid, 96 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 95 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-19 18:52:42,185 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2023-12-19 18:52:42,194 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 51. [2023-12-19 18:52:42,194 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 31 states have internal predecessors, (34), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-12-19 18:52:42,194 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 61 transitions. [2023-12-19 18:52:42,194 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 61 transitions. Word has length 44 [2023-12-19 18:52:42,195 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:52:42,195 INFO L495 AbstractCegarLoop]: Abstraction has 51 states and 61 transitions. [2023-12-19 18:52:42,195 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-12-19 18:52:42,195 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 61 transitions. [2023-12-19 18:52:42,195 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2023-12-19 18:52:42,195 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:52:42,196 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:52:42,214 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-12-19 18:52:42,400 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:42,401 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:52:42,401 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:52:42,401 INFO L85 PathProgramCache]: Analyzing trace with hash -1106872408, now seen corresponding path program 1 times [2023-12-19 18:52:42,401 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:52:42,401 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [99796835] [2023-12-19 18:52:42,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:42,402 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:52:42,408 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:52:42,408 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1716369989] [2023-12-19 18:52:42,409 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:42,409 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:42,409 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:52:42,410 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-19 18:52:42,415 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-19 18:52:42,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 18:52:42,461 INFO L262 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 9 conjunts are in the unsatisfiable core [2023-12-19 18:52:42,462 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:52:42,499 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2023-12-19 18:52:42,499 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:52:42,562 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2023-12-19 18:52:42,563 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:52:42,563 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [99796835] [2023-12-19 18:52:42,563 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:52:42,563 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1716369989] [2023-12-19 18:52:42,563 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1716369989] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 18:52:42,563 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 18:52:42,563 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2023-12-19 18:52:42,563 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2146195803] [2023-12-19 18:52:42,563 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 18:52:42,564 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-12-19 18:52:42,564 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:52:42,564 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-12-19 18:52:42,564 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2023-12-19 18:52:42,564 INFO L87 Difference]: Start difference. First operand 51 states and 61 transitions. Second operand has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 8 states have internal predecessors, (23), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2023-12-19 18:52:42,675 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:52:42,675 INFO L93 Difference]: Finished difference Result 98 states and 136 transitions. [2023-12-19 18:52:42,676 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-12-19 18:52:42,676 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 8 states have internal predecessors, (23), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 53 [2023-12-19 18:52:42,676 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:52:42,677 INFO L225 Difference]: With dead ends: 98 [2023-12-19 18:52:42,677 INFO L226 Difference]: Without dead ends: 90 [2023-12-19 18:52:42,677 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 93 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2023-12-19 18:52:42,677 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 36 mSDsluCounter, 224 mSDsCounter, 0 mSdLazyCounter, 102 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 263 SdHoareTripleChecker+Invalid, 132 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 102 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-19 18:52:42,678 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 263 Invalid, 132 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 102 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-19 18:52:42,678 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2023-12-19 18:52:42,691 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 81. [2023-12-19 18:52:42,691 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 44 states have (on average 1.2045454545454546) internal successors, (53), 45 states have internal predecessors, (53), 30 states have call successors, (30), 6 states have call predecessors, (30), 6 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2023-12-19 18:52:42,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 112 transitions. [2023-12-19 18:52:42,692 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 112 transitions. Word has length 53 [2023-12-19 18:52:42,692 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:52:42,692 INFO L495 AbstractCegarLoop]: Abstraction has 81 states and 112 transitions. [2023-12-19 18:52:42,693 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 8 states have internal predecessors, (23), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2023-12-19 18:52:42,693 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 112 transitions. [2023-12-19 18:52:42,693 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2023-12-19 18:52:42,693 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:52:42,693 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:52:42,698 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-19 18:52:42,898 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:42,899 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:52:42,900 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:52:42,900 INFO L85 PathProgramCache]: Analyzing trace with hash 355794356, now seen corresponding path program 1 times [2023-12-19 18:52:42,900 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:52:42,900 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [442816021] [2023-12-19 18:52:42,900 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:42,900 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:52:42,907 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:52:42,907 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1546574548] [2023-12-19 18:52:42,907 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:42,907 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:42,907 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:52:42,920 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-19 18:52:42,937 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-19 18:52:42,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 18:52:42,980 INFO L262 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 30 conjunts are in the unsatisfiable core [2023-12-19 18:52:43,005 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:52:43,123 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 23 proven. 10 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2023-12-19 18:52:43,123 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:52:43,224 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2023-12-19 18:52:43,224 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:52:43,224 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [442816021] [2023-12-19 18:52:43,224 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:52:43,224 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1546574548] [2023-12-19 18:52:43,224 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1546574548] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 18:52:43,224 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 18:52:43,225 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 7] total 15 [2023-12-19 18:52:43,225 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [261684847] [2023-12-19 18:52:43,225 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 18:52:43,225 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-12-19 18:52:43,225 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:52:43,226 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-12-19 18:52:43,226 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=173, Unknown=0, NotChecked=0, Total=210 [2023-12-19 18:52:43,226 INFO L87 Difference]: Start difference. First operand 81 states and 112 transitions. Second operand has 15 states, 14 states have (on average 2.5) internal successors, (35), 13 states have internal predecessors, (35), 8 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2023-12-19 18:52:43,533 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:52:43,533 INFO L93 Difference]: Finished difference Result 124 states and 177 transitions. [2023-12-19 18:52:43,534 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-12-19 18:52:43,534 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.5) internal successors, (35), 13 states have internal predecessors, (35), 8 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) Word has length 59 [2023-12-19 18:52:43,535 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:52:43,538 INFO L225 Difference]: With dead ends: 124 [2023-12-19 18:52:43,538 INFO L226 Difference]: Without dead ends: 120 [2023-12-19 18:52:43,538 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 108 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=85, Invalid=377, Unknown=0, NotChecked=0, Total=462 [2023-12-19 18:52:43,539 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 46 mSDsluCounter, 246 mSDsCounter, 0 mSdLazyCounter, 265 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 281 SdHoareTripleChecker+Invalid, 314 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 265 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-19 18:52:43,539 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 281 Invalid, 314 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 265 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-19 18:52:43,540 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2023-12-19 18:52:43,564 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 88. [2023-12-19 18:52:43,565 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 48 states have (on average 1.1875) internal successors, (57), 50 states have internal predecessors, (57), 32 states have call successors, (32), 7 states have call predecessors, (32), 7 states have return successors, (31), 30 states have call predecessors, (31), 31 states have call successors, (31) [2023-12-19 18:52:43,566 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 120 transitions. [2023-12-19 18:52:43,566 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 120 transitions. Word has length 59 [2023-12-19 18:52:43,566 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:52:43,566 INFO L495 AbstractCegarLoop]: Abstraction has 88 states and 120 transitions. [2023-12-19 18:52:43,567 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.5) internal successors, (35), 13 states have internal predecessors, (35), 8 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2023-12-19 18:52:43,567 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 120 transitions. [2023-12-19 18:52:43,571 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2023-12-19 18:52:43,571 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:52:43,572 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:52:43,593 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-19 18:52:43,777 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,SelfDestructingSolverStorable7 [2023-12-19 18:52:43,777 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:52:43,778 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:52:43,778 INFO L85 PathProgramCache]: Analyzing trace with hash 239702314, now seen corresponding path program 2 times [2023-12-19 18:52:43,778 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:52:43,778 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1073611613] [2023-12-19 18:52:43,778 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:43,778 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:52:43,785 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:52:43,785 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2137669740] [2023-12-19 18:52:43,786 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-19 18:52:43,786 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:43,786 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:52:43,787 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-19 18:52:43,813 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-19 18:52:43,829 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-19 18:52:43,829 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-19 18:52:43,830 INFO L262 TraceCheckSpWp]: Trace formula consists of 171 conjuncts, 37 conjunts are in the unsatisfiable core [2023-12-19 18:52:43,832 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:52:44,141 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 26 proven. 16 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-12-19 18:52:44,141 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:52:44,236 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:52:44,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1073611613] [2023-12-19 18:52:44,236 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:52:44,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2137669740] [2023-12-19 18:52:44,236 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2137669740] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-19 18:52:44,236 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-19 18:52:44,236 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2023-12-19 18:52:44,236 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [168859441] [2023-12-19 18:52:44,237 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-19 18:52:44,237 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-12-19 18:52:44,237 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:52:44,237 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-12-19 18:52:44,237 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=256, Unknown=0, NotChecked=0, Total=306 [2023-12-19 18:52:44,238 INFO L87 Difference]: Start difference. First operand 88 states and 120 transitions. Second operand has 14 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 12 states have internal predecessors, (25), 5 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) [2023-12-19 18:52:44,488 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:52:44,488 INFO L93 Difference]: Finished difference Result 120 states and 159 transitions. [2023-12-19 18:52:44,489 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-12-19 18:52:44,489 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 12 states have internal predecessors, (25), 5 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) Word has length 64 [2023-12-19 18:52:44,489 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:52:44,490 INFO L225 Difference]: With dead ends: 120 [2023-12-19 18:52:44,490 INFO L226 Difference]: Without dead ends: 118 [2023-12-19 18:52:44,490 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 77 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=85, Invalid=421, Unknown=0, NotChecked=0, Total=506 [2023-12-19 18:52:44,490 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 49 mSDsluCounter, 120 mSDsCounter, 0 mSdLazyCounter, 285 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 304 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 285 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-19 18:52:44,491 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 142 Invalid, 304 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 285 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-19 18:52:44,491 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2023-12-19 18:52:44,506 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 115. [2023-12-19 18:52:44,506 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 64 states have (on average 1.171875) internal successors, (75), 66 states have internal predecessors, (75), 40 states have call successors, (40), 10 states have call predecessors, (40), 10 states have return successors, (39), 38 states have call predecessors, (39), 39 states have call successors, (39) [2023-12-19 18:52:44,507 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 154 transitions. [2023-12-19 18:52:44,507 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 154 transitions. Word has length 64 [2023-12-19 18:52:44,507 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:52:44,507 INFO L495 AbstractCegarLoop]: Abstraction has 115 states and 154 transitions. [2023-12-19 18:52:44,507 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 12 states have internal predecessors, (25), 5 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) [2023-12-19 18:52:44,508 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 154 transitions. [2023-12-19 18:52:44,508 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2023-12-19 18:52:44,508 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:52:44,508 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:52:44,530 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2023-12-19 18:52:44,713 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:44,713 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:52:44,713 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:52:44,714 INFO L85 PathProgramCache]: Analyzing trace with hash 1133629236, now seen corresponding path program 3 times [2023-12-19 18:52:44,714 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:52:44,714 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [394334591] [2023-12-19 18:52:44,714 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:44,714 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:52:44,720 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:52:44,720 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [484955697] [2023-12-19 18:52:44,720 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-19 18:52:44,720 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:44,720 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:52:44,721 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-19 18:52:44,751 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-19 18:52:44,766 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-12-19 18:52:44,767 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-19 18:52:44,768 INFO L262 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 40 conjunts are in the unsatisfiable core [2023-12-19 18:52:44,769 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:52:45,074 INFO L134 CoverageAnalysis]: Checked inductivity of 129 backedges. 40 proven. 8 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2023-12-19 18:52:45,074 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:52:51,796 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:52:51,796 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [394334591] [2023-12-19 18:52:51,796 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:52:51,796 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [484955697] [2023-12-19 18:52:51,796 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [484955697] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-19 18:52:51,796 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-19 18:52:51,796 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2023-12-19 18:52:51,797 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1817072817] [2023-12-19 18:52:51,797 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-19 18:52:51,797 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-12-19 18:52:51,797 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:52:51,797 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-12-19 18:52:51,798 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=260, Unknown=0, NotChecked=0, Total=306 [2023-12-19 18:52:51,798 INFO L87 Difference]: Start difference. First operand 115 states and 154 transitions. Second operand has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 12 states have internal predecessors, (25), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2023-12-19 18:52:52,189 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:52:52,189 INFO L93 Difference]: Finished difference Result 124 states and 162 transitions. [2023-12-19 18:52:52,189 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-19 18:52:52,189 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 12 states have internal predecessors, (25), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 69 [2023-12-19 18:52:52,190 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:52:52,190 INFO L225 Difference]: With dead ends: 124 [2023-12-19 18:52:52,190 INFO L226 Difference]: Without dead ends: 122 [2023-12-19 18:52:52,191 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 77 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 6.7s TimeCoverageRelationStatistics Valid=71, Invalid=391, Unknown=0, NotChecked=0, Total=462 [2023-12-19 18:52:52,191 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 25 mSDsluCounter, 180 mSDsCounter, 0 mSdLazyCounter, 271 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 203 SdHoareTripleChecker+Invalid, 283 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 271 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-19 18:52:52,191 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 203 Invalid, 283 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 271 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-19 18:52:52,192 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2023-12-19 18:52:52,207 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 119. [2023-12-19 18:52:52,207 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 119 states, 67 states have (on average 1.164179104477612) internal successors, (78), 69 states have internal predecessors, (78), 40 states have call successors, (40), 11 states have call predecessors, (40), 11 states have return successors, (39), 38 states have call predecessors, (39), 39 states have call successors, (39) [2023-12-19 18:52:52,208 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 157 transitions. [2023-12-19 18:52:52,208 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 157 transitions. Word has length 69 [2023-12-19 18:52:52,208 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:52:52,208 INFO L495 AbstractCegarLoop]: Abstraction has 119 states and 157 transitions. [2023-12-19 18:52:52,208 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 12 states have internal predecessors, (25), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2023-12-19 18:52:52,208 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 157 transitions. [2023-12-19 18:52:52,209 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2023-12-19 18:52:52,209 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:52:52,209 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:52:52,217 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-19 18:52:52,414 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,SelfDestructingSolverStorable9 [2023-12-19 18:52:52,415 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:52:52,415 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:52:52,415 INFO L85 PathProgramCache]: Analyzing trace with hash -1982553465, now seen corresponding path program 1 times [2023-12-19 18:52:52,415 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:52:52,415 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [245826350] [2023-12-19 18:52:52,415 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:52,416 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:52:52,430 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:52:52,431 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2932758] [2023-12-19 18:52:52,431 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:52:52,431 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:52:52,431 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:52:52,437 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-19 18:52:52,439 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-19 18:52:52,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 18:52:52,484 INFO L262 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 41 conjunts are in the unsatisfiable core [2023-12-19 18:52:52,486 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:52:52,908 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 16 proven. 17 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2023-12-19 18:52:52,908 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:52:53,539 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2023-12-19 18:52:53,539 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:52:53,539 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [245826350] [2023-12-19 18:52:53,539 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:52:53,540 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2932758] [2023-12-19 18:52:53,540 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2932758] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 18:52:53,540 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 18:52:53,540 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2023-12-19 18:52:53,540 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1572387118] [2023-12-19 18:52:53,540 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 18:52:53,540 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-12-19 18:52:53,540 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:52:53,541 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-12-19 18:52:53,542 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2023-12-19 18:52:53,542 INFO L87 Difference]: Start difference. First operand 119 states and 157 transitions. Second operand has 21 states, 19 states have (on average 1.8421052631578947) internal successors, (35), 18 states have internal predecessors, (35), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2023-12-19 18:53:01,716 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:53:01,717 INFO L93 Difference]: Finished difference Result 204 states and 289 transitions. [2023-12-19 18:53:01,717 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2023-12-19 18:53:01,718 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 1.8421052631578947) internal successors, (35), 18 states have internal predecessors, (35), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 75 [2023-12-19 18:53:01,718 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:53:01,721 INFO L225 Difference]: With dead ends: 204 [2023-12-19 18:53:01,721 INFO L226 Difference]: Without dead ends: 200 [2023-12-19 18:53:01,723 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 129 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 301 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=309, Invalid=1413, Unknown=0, NotChecked=0, Total=1722 [2023-12-19 18:53:01,724 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 97 mSDsluCounter, 426 mSDsCounter, 0 mSdLazyCounter, 524 mSolverCounterSat, 120 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 467 SdHoareTripleChecker+Invalid, 644 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 120 IncrementalHoareTripleChecker+Valid, 524 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.8s IncrementalHoareTripleChecker+Time [2023-12-19 18:53:01,724 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [101 Valid, 467 Invalid, 644 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [120 Valid, 524 Invalid, 0 Unknown, 0 Unchecked, 3.8s Time] [2023-12-19 18:53:01,724 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 200 states. [2023-12-19 18:53:01,774 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 200 to 196. [2023-12-19 18:53:01,775 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 196 states, 104 states have (on average 1.2019230769230769) internal successors, (125), 105 states have internal predecessors, (125), 77 states have call successors, (77), 14 states have call predecessors, (77), 14 states have return successors, (76), 76 states have call predecessors, (76), 76 states have call successors, (76) [2023-12-19 18:53:01,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 196 states to 196 states and 278 transitions. [2023-12-19 18:53:01,776 INFO L78 Accepts]: Start accepts. Automaton has 196 states and 278 transitions. Word has length 75 [2023-12-19 18:53:01,776 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:53:01,776 INFO L495 AbstractCegarLoop]: Abstraction has 196 states and 278 transitions. [2023-12-19 18:53:01,776 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 1.8421052631578947) internal successors, (35), 18 states have internal predecessors, (35), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2023-12-19 18:53:01,776 INFO L276 IsEmpty]: Start isEmpty. Operand 196 states and 278 transitions. [2023-12-19 18:53:01,777 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2023-12-19 18:53:01,777 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:53:01,777 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:53:01,791 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-19 18:53:01,991 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,SelfDestructingSolverStorable10 [2023-12-19 18:53:01,992 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:53:01,993 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:53:01,993 INFO L85 PathProgramCache]: Analyzing trace with hash -1975410273, now seen corresponding path program 4 times [2023-12-19 18:53:01,993 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:53:01,994 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1791585174] [2023-12-19 18:53:01,994 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:53:01,994 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:53:02,000 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:53:02,000 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1534249638] [2023-12-19 18:53:02,000 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-19 18:53:02,000 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:53:02,000 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:53:02,016 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-19 18:53:02,018 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-19 18:53:02,059 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-19 18:53:02,060 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-19 18:53:02,061 INFO L262 TraceCheckSpWp]: Trace formula consists of 196 conjuncts, 5 conjunts are in the unsatisfiable core [2023-12-19 18:53:02,063 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:53:02,081 INFO L134 CoverageAnalysis]: Checked inductivity of 245 backedges. 101 proven. 0 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2023-12-19 18:53:02,081 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-19 18:53:02,081 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:53:02,081 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1791585174] [2023-12-19 18:53:02,081 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:53:02,082 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1534249638] [2023-12-19 18:53:02,082 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1534249638] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-19 18:53:02,082 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-19 18:53:02,082 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-19 18:53:02,082 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2055831406] [2023-12-19 18:53:02,082 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-19 18:53:02,082 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-19 18:53:02,082 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:53:02,083 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-19 18:53:02,083 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-19 18:53:02,083 INFO L87 Difference]: Start difference. First operand 196 states and 278 transitions. Second operand has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 3 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) [2023-12-19 18:53:02,216 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:53:02,217 INFO L93 Difference]: Finished difference Result 249 states and 350 transitions. [2023-12-19 18:53:02,217 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-19 18:53:02,217 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 3 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) Word has length 89 [2023-12-19 18:53:02,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:53:02,219 INFO L225 Difference]: With dead ends: 249 [2023-12-19 18:53:02,219 INFO L226 Difference]: Without dead ends: 177 [2023-12-19 18:53:02,223 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2023-12-19 18:53:02,223 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 7 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 18:53:02,224 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 138 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 18:53:02,224 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2023-12-19 18:53:02,281 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 163. [2023-12-19 18:53:02,281 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 163 states, 87 states have (on average 1.1494252873563218) internal successors, (100), 88 states have internal predecessors, (100), 61 states have call successors, (61), 14 states have call predecessors, (61), 14 states have return successors, (60), 60 states have call predecessors, (60), 60 states have call successors, (60) [2023-12-19 18:53:02,283 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 221 transitions. [2023-12-19 18:53:02,283 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 221 transitions. Word has length 89 [2023-12-19 18:53:02,283 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:53:02,284 INFO L495 AbstractCegarLoop]: Abstraction has 163 states and 221 transitions. [2023-12-19 18:53:02,284 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 3 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) [2023-12-19 18:53:02,284 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 221 transitions. [2023-12-19 18:53:02,284 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2023-12-19 18:53:02,284 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:53:02,284 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:53:02,289 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-19 18:53:02,489 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,SelfDestructingSolverStorable11 [2023-12-19 18:53:02,490 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:53:02,490 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:53:02,490 INFO L85 PathProgramCache]: Analyzing trace with hash -708551661, now seen corresponding path program 1 times [2023-12-19 18:53:02,490 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:53:02,490 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1818375019] [2023-12-19 18:53:02,490 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:53:02,490 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:53:02,496 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:53:02,496 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [24844599] [2023-12-19 18:53:02,496 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:53:02,496 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:53:02,496 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:53:02,505 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-19 18:53:02,507 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-19 18:53:02,570 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 18:53:02,572 INFO L262 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 48 conjunts are in the unsatisfiable core [2023-12-19 18:53:02,573 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:53:03,172 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 51 proven. 28 refuted. 0 times theorem prover too weak. 205 trivial. 0 not checked. [2023-12-19 18:53:03,172 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:53:04,237 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 51 proven. 19 refuted. 0 times theorem prover too weak. 214 trivial. 0 not checked. [2023-12-19 18:53:04,238 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:53:04,238 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1818375019] [2023-12-19 18:53:04,238 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:53:04,238 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [24844599] [2023-12-19 18:53:04,238 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [24844599] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 18:53:04,238 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 18:53:04,238 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 22 [2023-12-19 18:53:04,238 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1886902259] [2023-12-19 18:53:04,238 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 18:53:04,239 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-12-19 18:53:04,239 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:53:04,239 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-12-19 18:53:04,240 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=380, Unknown=0, NotChecked=0, Total=462 [2023-12-19 18:53:04,240 INFO L87 Difference]: Start difference. First operand 163 states and 221 transitions. Second operand has 22 states, 21 states have (on average 2.0) internal successors, (42), 19 states have internal predecessors, (42), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2023-12-19 18:53:13,964 WARN L293 SmtUtils]: Spent 5.14s on a formula simplification that was a NOOP. DAG size: 59 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-19 18:53:32,246 WARN L293 SmtUtils]: Spent 16.59s on a formula simplification that was a NOOP. DAG size: 59 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-19 18:53:34,894 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.68s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-19 18:53:40,592 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-19 18:53:48,179 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:53:48,179 INFO L93 Difference]: Finished difference Result 205 states and 281 transitions. [2023-12-19 18:53:48,180 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2023-12-19 18:53:48,180 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 2.0) internal successors, (42), 19 states have internal predecessors, (42), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) Word has length 91 [2023-12-19 18:53:48,180 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:53:48,182 INFO L225 Difference]: With dead ends: 205 [2023-12-19 18:53:48,182 INFO L226 Difference]: Without dead ends: 203 [2023-12-19 18:53:48,187 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 198 GetRequests, 160 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 295 ImplicationChecksByTransitivity, 32.7s TimeCoverageRelationStatistics Valid=334, Invalid=1226, Unknown=0, NotChecked=0, Total=1560 [2023-12-19 18:53:48,188 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 86 mSDsluCounter, 338 mSDsCounter, 0 mSdLazyCounter, 508 mSolverCounterSat, 90 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 95 SdHoareTripleChecker+Valid, 365 SdHoareTripleChecker+Invalid, 599 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 90 IncrementalHoareTripleChecker+Valid, 508 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 11.7s IncrementalHoareTripleChecker+Time [2023-12-19 18:53:48,188 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [95 Valid, 365 Invalid, 599 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [90 Valid, 508 Invalid, 1 Unknown, 0 Unchecked, 11.7s Time] [2023-12-19 18:53:48,189 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2023-12-19 18:53:48,295 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 193. [2023-12-19 18:53:48,296 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 193 states, 104 states have (on average 1.1442307692307692) internal successors, (119), 106 states have internal predecessors, (119), 73 states have call successors, (73), 15 states have call predecessors, (73), 15 states have return successors, (72), 71 states have call predecessors, (72), 72 states have call successors, (72) [2023-12-19 18:53:48,300 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 193 states to 193 states and 264 transitions. [2023-12-19 18:53:48,324 INFO L78 Accepts]: Start accepts. Automaton has 193 states and 264 transitions. Word has length 91 [2023-12-19 18:53:48,324 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:53:48,324 INFO L495 AbstractCegarLoop]: Abstraction has 193 states and 264 transitions. [2023-12-19 18:53:48,325 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 2.0) internal successors, (42), 19 states have internal predecessors, (42), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2023-12-19 18:53:48,325 INFO L276 IsEmpty]: Start isEmpty. Operand 193 states and 264 transitions. [2023-12-19 18:53:48,326 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2023-12-19 18:53:48,326 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:53:48,327 INFO L195 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:53:48,334 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-19 18:53:48,529 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,SelfDestructingSolverStorable12 [2023-12-19 18:53:48,530 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:53:48,530 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:53:48,530 INFO L85 PathProgramCache]: Analyzing trace with hash 694624748, now seen corresponding path program 2 times [2023-12-19 18:53:48,530 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:53:48,530 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1167498758] [2023-12-19 18:53:48,530 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:53:48,530 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:53:48,538 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:53:48,538 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1701435233] [2023-12-19 18:53:48,538 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-19 18:53:48,538 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:53:48,538 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:53:48,542 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-19 18:53:48,543 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-19 18:53:48,622 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-19 18:53:48,623 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-19 18:53:48,624 INFO L262 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 44 conjunts are in the unsatisfiable core [2023-12-19 18:53:48,626 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:53:49,270 INFO L134 CoverageAnalysis]: Checked inductivity of 448 backedges. 31 proven. 38 refuted. 0 times theorem prover too weak. 379 trivial. 0 not checked. [2023-12-19 18:53:49,270 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:53:49,938 INFO L134 CoverageAnalysis]: Checked inductivity of 448 backedges. 28 proven. 32 refuted. 0 times theorem prover too weak. 388 trivial. 0 not checked. [2023-12-19 18:53:49,939 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:53:49,939 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1167498758] [2023-12-19 18:53:49,939 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:53:49,939 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1701435233] [2023-12-19 18:53:49,939 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1701435233] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 18:53:49,939 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 18:53:49,939 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 10] total 22 [2023-12-19 18:53:49,940 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1756882821] [2023-12-19 18:53:49,940 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 18:53:49,941 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-12-19 18:53:49,941 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:53:49,942 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-12-19 18:53:49,942 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=385, Unknown=0, NotChecked=0, Total=462 [2023-12-19 18:53:49,942 INFO L87 Difference]: Start difference. First operand 193 states and 264 transitions. Second operand has 22 states, 21 states have (on average 2.0) internal successors, (42), 19 states have internal predecessors, (42), 12 states have call successors, (38), 3 states have call predecessors, (38), 2 states have return successors, (36), 13 states have call predecessors, (36), 12 states have call successors, (36) [2023-12-19 18:54:01,483 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:54:01,484 INFO L93 Difference]: Finished difference Result 299 states and 426 transitions. [2023-12-19 18:54:01,484 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2023-12-19 18:54:01,484 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 2.0) internal successors, (42), 19 states have internal predecessors, (42), 12 states have call successors, (38), 3 states have call predecessors, (38), 2 states have return successors, (36), 13 states have call predecessors, (36), 12 states have call successors, (36) Word has length 108 [2023-12-19 18:54:01,484 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:54:01,486 INFO L225 Difference]: With dead ends: 299 [2023-12-19 18:54:01,486 INFO L226 Difference]: Without dead ends: 297 [2023-12-19 18:54:01,486 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 240 GetRequests, 194 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 432 ImplicationChecksByTransitivity, 8.4s TimeCoverageRelationStatistics Valid=450, Invalid=1806, Unknown=0, NotChecked=0, Total=2256 [2023-12-19 18:54:01,487 INFO L413 NwaCegarLoop]: 55 mSDtfsCounter, 97 mSDsluCounter, 502 mSDsCounter, 0 mSdLazyCounter, 524 mSolverCounterSat, 119 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 557 SdHoareTripleChecker+Invalid, 643 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 119 IncrementalHoareTripleChecker+Valid, 524 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.6s IncrementalHoareTripleChecker+Time [2023-12-19 18:54:01,487 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [101 Valid, 557 Invalid, 643 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [119 Valid, 524 Invalid, 0 Unknown, 0 Unchecked, 3.6s Time] [2023-12-19 18:54:01,487 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 297 states. [2023-12-19 18:54:01,631 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 297 to 262. [2023-12-19 18:54:01,632 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 262 states, 138 states have (on average 1.1666666666666667) internal successors, (161), 140 states have internal predecessors, (161), 105 states have call successors, (105), 18 states have call predecessors, (105), 18 states have return successors, (104), 103 states have call predecessors, (104), 104 states have call successors, (104) [2023-12-19 18:54:01,633 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 262 states to 262 states and 370 transitions. [2023-12-19 18:54:01,633 INFO L78 Accepts]: Start accepts. Automaton has 262 states and 370 transitions. Word has length 108 [2023-12-19 18:54:01,633 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:54:01,633 INFO L495 AbstractCegarLoop]: Abstraction has 262 states and 370 transitions. [2023-12-19 18:54:01,633 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 2.0) internal successors, (42), 19 states have internal predecessors, (42), 12 states have call successors, (38), 3 states have call predecessors, (38), 2 states have return successors, (36), 13 states have call predecessors, (36), 12 states have call successors, (36) [2023-12-19 18:54:01,633 INFO L276 IsEmpty]: Start isEmpty. Operand 262 states and 370 transitions. [2023-12-19 18:54:01,634 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2023-12-19 18:54:01,634 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:54:01,634 INFO L195 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:54:01,643 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2023-12-19 18:54:01,839 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:54:01,839 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:54:01,839 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:54:01,839 INFO L85 PathProgramCache]: Analyzing trace with hash 47402912, now seen corresponding path program 3 times [2023-12-19 18:54:01,839 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:54:01,839 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1550942542] [2023-12-19 18:54:01,840 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:54:01,840 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:54:01,850 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:54:01,850 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1908985998] [2023-12-19 18:54:01,850 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-19 18:54:01,851 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:54:01,853 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:54:01,853 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-19 18:54:01,855 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-19 18:54:01,920 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-12-19 18:54:01,920 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-19 18:54:01,921 INFO L262 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 60 conjunts are in the unsatisfiable core [2023-12-19 18:54:01,923 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:54:02,587 INFO L134 CoverageAnalysis]: Checked inductivity of 453 backedges. 69 proven. 44 refuted. 0 times theorem prover too weak. 340 trivial. 0 not checked. [2023-12-19 18:54:02,587 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:54:03,120 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:54:03,120 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1550942542] [2023-12-19 18:54:03,120 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:54:03,120 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1908985998] [2023-12-19 18:54:03,120 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1908985998] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-19 18:54:03,120 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-19 18:54:03,120 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2023-12-19 18:54:03,120 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1840813745] [2023-12-19 18:54:03,120 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-19 18:54:03,121 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-12-19 18:54:03,121 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:54:03,121 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-12-19 18:54:03,121 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=428, Unknown=0, NotChecked=0, Total=506 [2023-12-19 18:54:03,121 INFO L87 Difference]: Start difference. First operand 262 states and 370 transitions. Second operand has 18 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 16 states have internal predecessors, (32), 6 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 8 states have call predecessors, (18), 6 states have call successors, (18) [2023-12-19 18:54:03,780 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:54:03,780 INFO L93 Difference]: Finished difference Result 302 states and 421 transitions. [2023-12-19 18:54:03,780 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2023-12-19 18:54:03,780 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 16 states have internal predecessors, (32), 6 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 8 states have call predecessors, (18), 6 states have call successors, (18) Word has length 111 [2023-12-19 18:54:03,781 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:54:03,782 INFO L225 Difference]: With dead ends: 302 [2023-12-19 18:54:03,782 INFO L226 Difference]: Without dead ends: 300 [2023-12-19 18:54:03,783 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 109 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 99 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=143, Invalid=787, Unknown=0, NotChecked=0, Total=930 [2023-12-19 18:54:03,783 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 40 mSDsluCounter, 386 mSDsCounter, 0 mSdLazyCounter, 589 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 420 SdHoareTripleChecker+Invalid, 623 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 589 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-12-19 18:54:03,783 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 420 Invalid, 623 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 589 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-12-19 18:54:03,783 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 300 states. [2023-12-19 18:54:03,930 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 300 to 295. [2023-12-19 18:54:03,930 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 295 states, 156 states have (on average 1.1602564102564104) internal successors, (181), 158 states have internal predecessors, (181), 117 states have call successors, (117), 21 states have call predecessors, (117), 21 states have return successors, (116), 115 states have call predecessors, (116), 116 states have call successors, (116) [2023-12-19 18:54:03,932 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 295 states to 295 states and 414 transitions. [2023-12-19 18:54:03,932 INFO L78 Accepts]: Start accepts. Automaton has 295 states and 414 transitions. Word has length 111 [2023-12-19 18:54:03,932 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:54:03,932 INFO L495 AbstractCegarLoop]: Abstraction has 295 states and 414 transitions. [2023-12-19 18:54:03,932 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 16 states have internal predecessors, (32), 6 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 8 states have call predecessors, (18), 6 states have call successors, (18) [2023-12-19 18:54:03,932 INFO L276 IsEmpty]: Start isEmpty. Operand 295 states and 414 transitions. [2023-12-19 18:54:03,933 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2023-12-19 18:54:03,933 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:54:03,933 INFO L195 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:54:03,938 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-19 18:54:04,138 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,SelfDestructingSolverStorable14 [2023-12-19 18:54:04,138 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:54:04,138 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:54:04,138 INFO L85 PathProgramCache]: Analyzing trace with hash -95789487, now seen corresponding path program 2 times [2023-12-19 18:54:04,138 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:54:04,138 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1180046181] [2023-12-19 18:54:04,139 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:54:04,139 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:54:04,147 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:54:04,147 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [570532712] [2023-12-19 18:54:04,147 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-19 18:54:04,148 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:54:04,148 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:54:04,148 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-19 18:54:04,157 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-19 18:54:04,220 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-19 18:54:04,220 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-19 18:54:04,221 INFO L262 TraceCheckSpWp]: Trace formula consists of 289 conjuncts, 61 conjunts are in the unsatisfiable core [2023-12-19 18:54:04,224 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:54:04,914 INFO L134 CoverageAnalysis]: Checked inductivity of 579 backedges. 35 proven. 49 refuted. 0 times theorem prover too weak. 495 trivial. 0 not checked. [2023-12-19 18:54:04,914 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:54:06,573 INFO L134 CoverageAnalysis]: Checked inductivity of 579 backedges. 32 proven. 43 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2023-12-19 18:54:06,574 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:54:06,574 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1180046181] [2023-12-19 18:54:06,574 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:54:06,574 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [570532712] [2023-12-19 18:54:06,574 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [570532712] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 18:54:06,574 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 18:54:06,574 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 13] total 28 [2023-12-19 18:54:06,574 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [437477517] [2023-12-19 18:54:06,574 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 18:54:06,574 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-12-19 18:54:06,574 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:54:06,575 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-12-19 18:54:06,575 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=647, Unknown=0, NotChecked=0, Total=756 [2023-12-19 18:54:06,575 INFO L87 Difference]: Start difference. First operand 295 states and 414 transitions. Second operand has 28 states, 26 states have (on average 1.8846153846153846) internal successors, (49), 25 states have internal predecessors, (49), 13 states have call successors, (40), 3 states have call predecessors, (40), 2 states have return successors, (39), 12 states have call predecessors, (39), 11 states have call successors, (39) [2023-12-19 18:54:27,873 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:54:27,873 INFO L93 Difference]: Finished difference Result 412 states and 589 transitions. [2023-12-19 18:54:27,873 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2023-12-19 18:54:27,873 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 26 states have (on average 1.8846153846153846) internal successors, (49), 25 states have internal predecessors, (49), 13 states have call successors, (40), 3 states have call predecessors, (40), 2 states have return successors, (39), 12 states have call predecessors, (39), 11 states have call successors, (39) Word has length 122 [2023-12-19 18:54:27,874 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:54:27,875 INFO L225 Difference]: With dead ends: 412 [2023-12-19 18:54:27,875 INFO L226 Difference]: Without dead ends: 404 [2023-12-19 18:54:27,876 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 285 GetRequests, 216 SyntacticMatches, 0 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1197 ImplicationChecksByTransitivity, 17.0s TimeCoverageRelationStatistics Valid=853, Invalid=4117, Unknown=0, NotChecked=0, Total=4970 [2023-12-19 18:54:27,877 INFO L413 NwaCegarLoop]: 62 mSDtfsCounter, 195 mSDsluCounter, 617 mSDsCounter, 0 mSdLazyCounter, 814 mSolverCounterSat, 293 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 203 SdHoareTripleChecker+Valid, 679 SdHoareTripleChecker+Invalid, 1107 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 293 IncrementalHoareTripleChecker+Valid, 814 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.5s IncrementalHoareTripleChecker+Time [2023-12-19 18:54:27,877 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [203 Valid, 679 Invalid, 1107 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [293 Valid, 814 Invalid, 0 Unknown, 0 Unchecked, 5.5s Time] [2023-12-19 18:54:27,877 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 404 states. [2023-12-19 18:54:28,118 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 404 to 380. [2023-12-19 18:54:28,119 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 380 states, 197 states have (on average 1.16751269035533) internal successors, (230), 199 states have internal predecessors, (230), 157 states have call successors, (157), 25 states have call predecessors, (157), 25 states have return successors, (156), 155 states have call predecessors, (156), 156 states have call successors, (156) [2023-12-19 18:54:28,120 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 380 states to 380 states and 543 transitions. [2023-12-19 18:54:28,121 INFO L78 Accepts]: Start accepts. Automaton has 380 states and 543 transitions. Word has length 122 [2023-12-19 18:54:28,121 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:54:28,121 INFO L495 AbstractCegarLoop]: Abstraction has 380 states and 543 transitions. [2023-12-19 18:54:28,121 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 26 states have (on average 1.8846153846153846) internal successors, (49), 25 states have internal predecessors, (49), 13 states have call successors, (40), 3 states have call predecessors, (40), 2 states have return successors, (39), 12 states have call predecessors, (39), 11 states have call successors, (39) [2023-12-19 18:54:28,121 INFO L276 IsEmpty]: Start isEmpty. Operand 380 states and 543 transitions. [2023-12-19 18:54:28,122 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 134 [2023-12-19 18:54:28,122 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:54:28,122 INFO L195 NwaCegarLoop]: trace histogram [19, 18, 18, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:54:28,127 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-19 18:54:28,327 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2023-12-19 18:54:28,328 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:54:28,328 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:54:28,328 INFO L85 PathProgramCache]: Analyzing trace with hash 857101759, now seen corresponding path program 4 times [2023-12-19 18:54:28,328 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:54:28,328 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [797209164] [2023-12-19 18:54:28,328 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:54:28,328 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:54:28,334 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:54:28,334 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [951830606] [2023-12-19 18:54:28,334 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-19 18:54:28,334 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:54:28,334 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:54:28,335 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-19 18:54:28,337 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-19 18:54:28,415 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-19 18:54:28,415 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-19 18:54:28,416 INFO L262 TraceCheckSpWp]: Trace formula consists of 280 conjuncts, 61 conjunts are in the unsatisfiable core [2023-12-19 18:54:28,418 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:54:29,125 INFO L134 CoverageAnalysis]: Checked inductivity of 731 backedges. 36 proven. 68 refuted. 0 times theorem prover too weak. 627 trivial. 0 not checked. [2023-12-19 18:54:29,125 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:54:30,795 INFO L134 CoverageAnalysis]: Checked inductivity of 731 backedges. 42 proven. 53 refuted. 0 times theorem prover too weak. 636 trivial. 0 not checked. [2023-12-19 18:54:30,795 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:54:30,795 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [797209164] [2023-12-19 18:54:30,795 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:54:30,795 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [951830606] [2023-12-19 18:54:30,795 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [951830606] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 18:54:30,795 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 18:54:30,795 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 27 [2023-12-19 18:54:30,795 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [297188869] [2023-12-19 18:54:30,795 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 18:54:30,796 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-12-19 18:54:30,796 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:54:30,796 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-12-19 18:54:30,797 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=592, Unknown=0, NotChecked=0, Total=702 [2023-12-19 18:54:30,797 INFO L87 Difference]: Start difference. First operand 380 states and 543 transitions. Second operand has 27 states, 27 states have (on average 1.8888888888888888) internal successors, (51), 24 states have internal predecessors, (51), 14 states have call successors, (45), 3 states have call predecessors, (45), 2 states have return successors, (44), 14 states have call predecessors, (44), 14 states have call successors, (44) [2023-12-19 18:54:45,173 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:54:45,174 INFO L93 Difference]: Finished difference Result 460 states and 656 transitions. [2023-12-19 18:54:45,174 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2023-12-19 18:54:45,174 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 27 states have (on average 1.8888888888888888) internal successors, (51), 24 states have internal predecessors, (51), 14 states have call successors, (45), 3 states have call predecessors, (45), 2 states have return successors, (44), 14 states have call predecessors, (44), 14 states have call successors, (44) Word has length 133 [2023-12-19 18:54:45,174 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:54:45,176 INFO L225 Difference]: With dead ends: 460 [2023-12-19 18:54:45,176 INFO L226 Difference]: Without dead ends: 458 [2023-12-19 18:54:45,177 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 292 GetRequests, 239 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 624 ImplicationChecksByTransitivity, 12.7s TimeCoverageRelationStatistics Valid=583, Invalid=2387, Unknown=0, NotChecked=0, Total=2970 [2023-12-19 18:54:45,177 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 101 mSDsluCounter, 565 mSDsCounter, 0 mSdLazyCounter, 732 mSolverCounterSat, 151 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 105 SdHoareTripleChecker+Valid, 611 SdHoareTripleChecker+Invalid, 883 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 151 IncrementalHoareTripleChecker+Valid, 732 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.8s IncrementalHoareTripleChecker+Time [2023-12-19 18:54:45,177 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [105 Valid, 611 Invalid, 883 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [151 Valid, 732 Invalid, 0 Unknown, 0 Unchecked, 2.8s Time] [2023-12-19 18:54:45,178 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 458 states. [2023-12-19 18:54:45,478 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 458 to 433. [2023-12-19 18:54:45,479 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 433 states, 225 states have (on average 1.1644444444444444) internal successors, (262), 227 states have internal predecessors, (262), 177 states have call successors, (177), 30 states have call predecessors, (177), 30 states have return successors, (176), 175 states have call predecessors, (176), 176 states have call successors, (176) [2023-12-19 18:54:45,481 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 433 states to 433 states and 615 transitions. [2023-12-19 18:54:45,481 INFO L78 Accepts]: Start accepts. Automaton has 433 states and 615 transitions. Word has length 133 [2023-12-19 18:54:45,481 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:54:45,481 INFO L495 AbstractCegarLoop]: Abstraction has 433 states and 615 transitions. [2023-12-19 18:54:45,481 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 27 states have (on average 1.8888888888888888) internal successors, (51), 24 states have internal predecessors, (51), 14 states have call successors, (45), 3 states have call predecessors, (45), 2 states have return successors, (44), 14 states have call predecessors, (44), 14 states have call successors, (44) [2023-12-19 18:54:45,481 INFO L276 IsEmpty]: Start isEmpty. Operand 433 states and 615 transitions. [2023-12-19 18:54:45,482 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2023-12-19 18:54:45,482 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:54:45,483 INFO L195 NwaCegarLoop]: trace histogram [20, 19, 19, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:54:45,488 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-19 18:54:45,687 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-12-19 18:54:45,688 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:54:45,688 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:54:45,688 INFO L85 PathProgramCache]: Analyzing trace with hash 2003649501, now seen corresponding path program 5 times [2023-12-19 18:54:45,688 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:54:45,688 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1521021889] [2023-12-19 18:54:45,688 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:54:45,688 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:54:45,697 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:54:45,697 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [143505849] [2023-12-19 18:54:45,698 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2023-12-19 18:54:45,698 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:54:45,698 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:54:45,700 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-19 18:54:45,701 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2023-12-19 18:54:46,436 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2023-12-19 18:54:46,436 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-19 18:54:46,440 INFO L262 TraceCheckSpWp]: Trace formula consists of 320 conjuncts, 72 conjunts are in the unsatisfiable core [2023-12-19 18:54:46,443 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:54:52,153 INFO L134 CoverageAnalysis]: Checked inductivity of 809 backedges. 101 proven. 156 refuted. 0 times theorem prover too weak. 552 trivial. 0 not checked. [2023-12-19 18:54:52,153 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:54:52,737 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:54:52,738 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1521021889] [2023-12-19 18:54:52,738 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:54:52,738 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [143505849] [2023-12-19 18:54:52,738 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [143505849] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-19 18:54:52,738 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-19 18:54:52,738 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2023-12-19 18:54:52,738 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1537174305] [2023-12-19 18:54:52,738 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-19 18:54:52,739 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-12-19 18:54:52,739 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:54:52,739 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-12-19 18:54:52,739 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=479, Unknown=0, NotChecked=0, Total=552 [2023-12-19 18:54:52,739 INFO L87 Difference]: Start difference. First operand 433 states and 615 transitions. Second operand has 21 states, 19 states have (on average 1.7894736842105263) internal successors, (34), 18 states have internal predecessors, (34), 9 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (23), 10 states have call predecessors, (23), 8 states have call successors, (23) [2023-12-19 18:54:56,226 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:54:56,226 INFO L93 Difference]: Finished difference Result 448 states and 628 transitions. [2023-12-19 18:54:56,226 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-12-19 18:54:56,227 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 1.7894736842105263) internal successors, (34), 18 states have internal predecessors, (34), 9 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (23), 10 states have call predecessors, (23), 8 states have call successors, (23) Word has length 138 [2023-12-19 18:54:56,227 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:54:56,236 INFO L225 Difference]: With dead ends: 448 [2023-12-19 18:54:56,236 INFO L226 Difference]: Without dead ends: 446 [2023-12-19 18:54:56,236 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 120 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 177 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=132, Invalid=924, Unknown=0, NotChecked=0, Total=1056 [2023-12-19 18:54:56,246 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 52 mSDsluCounter, 298 mSDsCounter, 0 mSdLazyCounter, 765 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 67 SdHoareTripleChecker+Valid, 340 SdHoareTripleChecker+Invalid, 794 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 765 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2023-12-19 18:54:56,246 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [67 Valid, 340 Invalid, 794 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 765 Invalid, 0 Unknown, 0 Unchecked, 2.1s Time] [2023-12-19 18:54:56,247 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 446 states. [2023-12-19 18:54:56,565 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 446 to 441. [2023-12-19 18:54:56,566 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 441 states, 231 states have (on average 1.1601731601731602) internal successors, (268), 233 states have internal predecessors, (268), 177 states have call successors, (177), 32 states have call predecessors, (177), 32 states have return successors, (176), 175 states have call predecessors, (176), 176 states have call successors, (176) [2023-12-19 18:54:56,580 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 441 states to 441 states and 621 transitions. [2023-12-19 18:54:56,581 INFO L78 Accepts]: Start accepts. Automaton has 441 states and 621 transitions. Word has length 138 [2023-12-19 18:54:56,581 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:54:56,581 INFO L495 AbstractCegarLoop]: Abstraction has 441 states and 621 transitions. [2023-12-19 18:54:56,581 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 1.7894736842105263) internal successors, (34), 18 states have internal predecessors, (34), 9 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (23), 10 states have call predecessors, (23), 8 states have call successors, (23) [2023-12-19 18:54:56,581 INFO L276 IsEmpty]: Start isEmpty. Operand 441 states and 621 transitions. [2023-12-19 18:54:56,582 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 142 [2023-12-19 18:54:56,582 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:54:56,582 INFO L195 NwaCegarLoop]: trace histogram [21, 20, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:54:56,603 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2023-12-19 18:54:56,798 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2023-12-19 18:54:56,798 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:54:56,799 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:54:56,799 INFO L85 PathProgramCache]: Analyzing trace with hash -664609884, now seen corresponding path program 3 times [2023-12-19 18:54:56,799 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:54:56,799 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [995493159] [2023-12-19 18:54:56,799 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:54:56,799 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:54:56,805 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:54:56,805 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [664199946] [2023-12-19 18:54:56,805 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-19 18:54:56,806 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:54:56,806 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:54:56,806 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-19 18:54:56,811 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2023-12-19 18:54:56,874 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-12-19 18:54:56,875 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-19 18:54:56,876 INFO L262 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 42 conjunts are in the unsatisfiable core [2023-12-19 18:54:56,877 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:54:57,280 INFO L134 CoverageAnalysis]: Checked inductivity of 886 backedges. 93 proven. 31 refuted. 0 times theorem prover too weak. 762 trivial. 0 not checked. [2023-12-19 18:54:57,281 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:55:01,546 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:55:01,546 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [995493159] [2023-12-19 18:55:01,546 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:55:01,546 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [664199946] [2023-12-19 18:55:01,546 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [664199946] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-19 18:55:01,547 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-19 18:55:01,547 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2023-12-19 18:55:01,547 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1779319723] [2023-12-19 18:55:01,547 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-19 18:55:01,547 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-12-19 18:55:01,547 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:55:01,548 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-12-19 18:55:01,548 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=291, Unknown=1, NotChecked=0, Total=342 [2023-12-19 18:55:01,548 INFO L87 Difference]: Start difference. First operand 441 states and 621 transitions. Second operand has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2023-12-19 18:55:02,079 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:55:02,079 INFO L93 Difference]: Finished difference Result 487 states and 683 transitions. [2023-12-19 18:55:02,080 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-19 18:55:02,080 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 141 [2023-12-19 18:55:02,080 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:55:02,082 INFO L225 Difference]: With dead ends: 487 [2023-12-19 18:55:02,082 INFO L226 Difference]: Without dead ends: 480 [2023-12-19 18:55:02,082 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 154 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=83, Invalid=468, Unknown=1, NotChecked=0, Total=552 [2023-12-19 18:55:02,082 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 21 mSDsluCounter, 158 mSDsCounter, 0 mSdLazyCounter, 257 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 267 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 257 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-19 18:55:02,083 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 180 Invalid, 267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 257 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-19 18:55:02,083 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 480 states. [2023-12-19 18:55:02,379 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 480 to 426. [2023-12-19 18:55:02,380 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 426 states, 224 states have (on average 1.1517857142857142) internal successors, (258), 226 states have internal predecessors, (258), 169 states have call successors, (169), 32 states have call predecessors, (169), 32 states have return successors, (168), 167 states have call predecessors, (168), 168 states have call successors, (168) [2023-12-19 18:55:02,381 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 426 states to 426 states and 595 transitions. [2023-12-19 18:55:02,382 INFO L78 Accepts]: Start accepts. Automaton has 426 states and 595 transitions. Word has length 141 [2023-12-19 18:55:02,382 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:55:02,382 INFO L495 AbstractCegarLoop]: Abstraction has 426 states and 595 transitions. [2023-12-19 18:55:02,382 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2023-12-19 18:55:02,382 INFO L276 IsEmpty]: Start isEmpty. Operand 426 states and 595 transitions. [2023-12-19 18:55:02,383 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 156 [2023-12-19 18:55:02,383 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:55:02,383 INFO L195 NwaCegarLoop]: trace histogram [23, 22, 22, 6, 6, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:55:02,390 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2023-12-19 18:55:02,588 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:55:02,588 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:55:02,588 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:55:02,589 INFO L85 PathProgramCache]: Analyzing trace with hash -890927262, now seen corresponding path program 6 times [2023-12-19 18:55:02,589 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:55:02,589 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1484669646] [2023-12-19 18:55:02,589 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:55:02,589 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:55:02,596 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:55:02,596 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1628530023] [2023-12-19 18:55:02,596 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2023-12-19 18:55:02,596 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:55:02,596 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:55:02,597 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-19 18:55:02,628 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2023-12-19 18:55:02,707 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2023-12-19 18:55:02,707 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-19 18:55:02,709 INFO L262 TraceCheckSpWp]: Trace formula consists of 272 conjuncts, 63 conjunts are in the unsatisfiable core [2023-12-19 18:55:02,711 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:55:03,377 INFO L134 CoverageAnalysis]: Checked inductivity of 1079 backedges. 50 proven. 90 refuted. 0 times theorem prover too weak. 939 trivial. 0 not checked. [2023-12-19 18:55:03,377 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:55:04,714 INFO L134 CoverageAnalysis]: Checked inductivity of 1079 backedges. 44 proven. 87 refuted. 0 times theorem prover too weak. 948 trivial. 0 not checked. [2023-12-19 18:55:04,714 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 18:55:04,715 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1484669646] [2023-12-19 18:55:04,715 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 18:55:04,715 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1628530023] [2023-12-19 18:55:04,724 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1628530023] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 18:55:04,724 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 18:55:04,724 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 26 [2023-12-19 18:55:04,724 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [653719095] [2023-12-19 18:55:04,724 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 18:55:04,725 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-12-19 18:55:04,725 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 18:55:04,725 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-12-19 18:55:04,726 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=554, Unknown=0, NotChecked=0, Total=650 [2023-12-19 18:55:04,726 INFO L87 Difference]: Start difference. First operand 426 states and 595 transitions. Second operand has 26 states, 26 states have (on average 2.1153846153846154) internal successors, (55), 24 states have internal predecessors, (55), 15 states have call successors, (52), 3 states have call predecessors, (52), 2 states have return successors, (50), 15 states have call predecessors, (50), 15 states have call successors, (50) [2023-12-19 18:55:24,543 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 18:55:24,543 INFO L93 Difference]: Finished difference Result 604 states and 870 transitions. [2023-12-19 18:55:24,544 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2023-12-19 18:55:24,544 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 2.1153846153846154) internal successors, (55), 24 states have internal predecessors, (55), 15 states have call successors, (52), 3 states have call predecessors, (52), 2 states have return successors, (50), 15 states have call predecessors, (50), 15 states have call successors, (50) Word has length 155 [2023-12-19 18:55:24,544 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 18:55:24,546 INFO L225 Difference]: With dead ends: 604 [2023-12-19 18:55:24,546 INFO L226 Difference]: Without dead ends: 602 [2023-12-19 18:55:24,547 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 341 GetRequests, 284 SyntacticMatches, 0 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 595 ImplicationChecksByTransitivity, 12.8s TimeCoverageRelationStatistics Valid=623, Invalid=2799, Unknown=0, NotChecked=0, Total=3422 [2023-12-19 18:55:24,552 INFO L413 NwaCegarLoop]: 76 mSDtfsCounter, 140 mSDsluCounter, 934 mSDsCounter, 0 mSdLazyCounter, 1073 mSolverCounterSat, 199 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 144 SdHoareTripleChecker+Valid, 1010 SdHoareTripleChecker+Invalid, 1272 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 199 IncrementalHoareTripleChecker+Valid, 1073 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.4s IncrementalHoareTripleChecker+Time [2023-12-19 18:55:24,553 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [144 Valid, 1010 Invalid, 1272 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [199 Valid, 1073 Invalid, 0 Unknown, 0 Unchecked, 7.4s Time] [2023-12-19 18:55:24,557 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 602 states. [2023-12-19 18:55:25,083 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 602 to 580. [2023-12-19 18:55:25,085 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 580 states, 295 states have (on average 1.176271186440678) internal successors, (347), 297 states have internal predecessors, (347), 245 states have call successors, (245), 39 states have call predecessors, (245), 39 states have return successors, (244), 243 states have call predecessors, (244), 244 states have call successors, (244) [2023-12-19 18:55:25,086 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 580 states to 580 states and 836 transitions. [2023-12-19 18:55:25,087 INFO L78 Accepts]: Start accepts. Automaton has 580 states and 836 transitions. Word has length 155 [2023-12-19 18:55:25,087 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 18:55:25,087 INFO L495 AbstractCegarLoop]: Abstraction has 580 states and 836 transitions. [2023-12-19 18:55:25,087 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 2.1153846153846154) internal successors, (55), 24 states have internal predecessors, (55), 15 states have call successors, (52), 3 states have call predecessors, (52), 2 states have return successors, (50), 15 states have call predecessors, (50), 15 states have call successors, (50) [2023-12-19 18:55:25,087 INFO L276 IsEmpty]: Start isEmpty. Operand 580 states and 836 transitions. [2023-12-19 18:55:25,088 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 161 [2023-12-19 18:55:25,088 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 18:55:25,088 INFO L195 NwaCegarLoop]: trace histogram [24, 23, 23, 6, 6, 6, 6, 6, 6, 6, 6, 5, 4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 18:55:25,103 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2023-12-19 18:55:25,293 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:55:25,293 INFO L420 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 18:55:25,293 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 18:55:25,294 INFO L85 PathProgramCache]: Analyzing trace with hash 1468988412, now seen corresponding path program 7 times [2023-12-19 18:55:25,294 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 18:55:25,294 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1431726355] [2023-12-19 18:55:25,294 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 18:55:25,294 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 18:55:25,300 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 18:55:25,300 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2108840462] [2023-12-19 18:55:25,300 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-12-19 18:55:25,300 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 18:55:25,300 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 18:55:25,301 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-19 18:55:25,305 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2023-12-19 18:55:25,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 18:55:25,422 INFO L262 TraceCheckSpWp]: Trace formula consists of 362 conjuncts, 82 conjunts are in the unsatisfiable core [2023-12-19 18:55:25,424 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 18:55:27,475 INFO L134 CoverageAnalysis]: Checked inductivity of 1174 backedges. 175 proven. 152 refuted. 0 times theorem prover too weak. 847 trivial. 0 not checked. [2023-12-19 18:55:27,475 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 18:56:10,562 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 28 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 18:56:24,305 WARN L876 $PredicateComparison]: unable to prove that (let ((.cse1 (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1|))) (let ((.cse8 (* .cse0 2)) (.cse9 (* .cse1 2)) (.cse2 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~b~0#1|)) (.cse10 (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse11 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|)) (.cse3 (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse6 (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~p~0#1|)) (.cse7 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~r~0#1|)) (.cse5 (* 2 |c_ULTIMATE.start_main_~b~0#1|)) (.cse4 (* |c_ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~s~0#1|))) (or (not (= (+ .cse0 .cse1 .cse2) (+ .cse3 .cse4 |c_ULTIMATE.start_main_~b~0#1|))) (< |c_ULTIMATE.start_main_~c~0#1| .cse5) (not (= (+ .cse6 .cse7 .cse5) (+ |c_ULTIMATE.start_main_~c~0#1| .cse8 .cse9 .cse10 .cse11))) (< (* 3 |c_ULTIMATE.start_main_~b~0#1|) (+ |c_ULTIMATE.start_main_~c~0#1| 1)) (= |c_ULTIMATE.start_main_~c~0#1| .cse5) (= (+ |c_ULTIMATE.start_main_~c~0#1| .cse8 .cse9 (* |c_ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~r~0#1|) (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~p~0#1|) (* 2 .cse2) .cse10 .cse11) (+ (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|) (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|) (* .cse3 2) .cse6 (* |c_ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|) .cse7 .cse5 (* 2 .cse4)))))) is different from true [2023-12-19 18:56:38,037 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 35 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 18:57:16,594 WARN L293 SmtUtils]: Spent 21.05s on a formula simplification that was a NOOP. DAG size: 58 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-19 18:58:02,435 WARN L293 SmtUtils]: Spent 45.68s on a formula simplification that was a NOOP. DAG size: 23 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 18:58:31,900 WARN L293 SmtUtils]: Spent 10.18s on a formula simplification that was a NOOP. DAG size: 61 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-19 18:58:51,176 WARN L293 SmtUtils]: Spent 6.81s on a formula simplification that was a NOOP. DAG size: 29 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:00:15,935 WARN L293 SmtUtils]: Spent 18.42s on a formula simplification that was a NOOP. DAG size: 67 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-19 19:00:32,857 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:00:32,857 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1431726355] [2023-12-19 19:00:32,857 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:00:32,857 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2108840462] [2023-12-19 19:00:32,857 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2108840462] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-19 19:00:32,857 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-19 19:00:32,857 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2023-12-19 19:00:32,858 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1318763392] [2023-12-19 19:00:32,858 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-19 19:00:32,858 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-12-19 19:00:32,858 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:00:32,858 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-12-19 19:00:32,859 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=225, Invalid=891, Unknown=10, NotChecked=64, Total=1190 [2023-12-19 19:00:32,859 INFO L87 Difference]: Start difference. First operand 580 states and 836 transitions. Second operand has 21 states, 20 states have (on average 1.8) internal successors, (36), 18 states have internal predecessors, (36), 10 states have call successors, (28), 2 states have call predecessors, (28), 3 states have return successors, (27), 9 states have call predecessors, (27), 10 states have call successors, (27) [2023-12-19 19:00:35,716 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:00:35,716 INFO L93 Difference]: Finished difference Result 626 states and 885 transitions. [2023-12-19 19:00:35,716 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-12-19 19:00:35,716 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 1.8) internal successors, (36), 18 states have internal predecessors, (36), 10 states have call successors, (28), 2 states have call predecessors, (28), 3 states have return successors, (27), 9 states have call predecessors, (27), 10 states have call successors, (27) Word has length 160 [2023-12-19 19:00:35,717 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:00:35,719 INFO L225 Difference]: With dead ends: 626 [2023-12-19 19:00:35,719 INFO L226 Difference]: Without dead ends: 624 [2023-12-19 19:00:35,719 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 285 GetRequests, 241 SyntacticMatches, 1 SemanticMatches, 43 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 383 ImplicationChecksByTransitivity, 130.3s TimeCoverageRelationStatistics Valid=366, Invalid=1520, Unknown=10, NotChecked=84, Total=1980 [2023-12-19 19:00:35,720 INFO L413 NwaCegarLoop]: 43 mSDtfsCounter, 56 mSDsluCounter, 552 mSDsCounter, 0 mSdLazyCounter, 782 mSolverCounterSat, 69 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 595 SdHoareTripleChecker+Invalid, 851 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 69 IncrementalHoareTripleChecker+Valid, 782 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2023-12-19 19:00:35,721 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 595 Invalid, 851 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [69 Valid, 782 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2023-12-19 19:00:35,721 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 624 states. [2023-12-19 19:00:36,248 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 624 to 620. [2023-12-19 19:00:36,249 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 620 states, 320 states have (on average 1.16875) internal successors, (374), 322 states have internal predecessors, (374), 253 states have call successors, (253), 46 states have call predecessors, (253), 46 states have return successors, (252), 251 states have call predecessors, (252), 252 states have call successors, (252) [2023-12-19 19:00:36,251 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 620 states to 620 states and 879 transitions. [2023-12-19 19:00:36,252 INFO L78 Accepts]: Start accepts. Automaton has 620 states and 879 transitions. Word has length 160 [2023-12-19 19:00:36,252 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:00:36,252 INFO L495 AbstractCegarLoop]: Abstraction has 620 states and 879 transitions. [2023-12-19 19:00:36,252 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 1.8) internal successors, (36), 18 states have internal predecessors, (36), 10 states have call successors, (28), 2 states have call predecessors, (28), 3 states have return successors, (27), 9 states have call predecessors, (27), 10 states have call successors, (27) [2023-12-19 19:00:36,252 INFO L276 IsEmpty]: Start isEmpty. Operand 620 states and 879 transitions. [2023-12-19 19:00:36,253 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 164 [2023-12-19 19:00:36,253 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:00:36,253 INFO L195 NwaCegarLoop]: trace histogram [24, 23, 23, 6, 6, 6, 6, 6, 6, 6, 6, 5, 4, 4, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:00:36,261 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2023-12-19 19:00:36,458 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:00:36,459 INFO L420 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:00:36,459 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:00:36,459 INFO L85 PathProgramCache]: Analyzing trace with hash 1503607284, now seen corresponding path program 8 times [2023-12-19 19:00:36,459 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:00:36,459 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1754558790] [2023-12-19 19:00:36,459 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:00:36,459 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:00:36,467 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:00:36,467 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1409932678] [2023-12-19 19:00:36,467 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-19 19:00:36,467 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:00:36,467 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:00:36,477 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-19 19:00:36,477 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2023-12-19 19:00:37,054 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-19 19:00:37,054 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-19 19:00:37,058 INFO L262 TraceCheckSpWp]: Trace formula consists of 376 conjuncts, 105 conjunts are in the unsatisfiable core [2023-12-19 19:00:37,061 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:00:41,651 INFO L134 CoverageAnalysis]: Checked inductivity of 1182 backedges. 267 proven. 116 refuted. 0 times theorem prover too weak. 799 trivial. 0 not checked. [2023-12-19 19:00:41,652 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:01:24,939 WARN L293 SmtUtils]: Spent 5.12s on a formula simplification that was a NOOP. DAG size: 10 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:01:28,944 WARN L876 $PredicateComparison]: unable to prove that (let ((.cse8 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~r~0#1|)) (.cse9 (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse10 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~p~0#1|)) (.cse11 (* |c_ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|)) (.cse4 (* |c_ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~r~0#1|)) (.cse5 (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~p~0#1|)) (.cse6 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|)) (.cse7 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse0 (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~p~0#1|)) (.cse1 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~r~0#1|)) (.cse12 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1|)) (.cse13 (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse2 (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse3 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|))) (or (not (= (+ .cse0 .cse1) (+ |c_ULTIMATE.start_main_~c~0#1| .cse2 .cse3))) (not (= (+ .cse4 .cse5 .cse6 .cse7) (+ .cse8 .cse9 .cse10 .cse11))) (= (+ .cse8 .cse9 (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~q~0#1|) .cse10 .cse11 (* |c_ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~s~0#1|)) (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1|) .cse4 .cse5 .cse6 .cse7 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~q~0#1|))) (not (= (+ .cse12 .cse13) |c_ULTIMATE.start_main_~b~0#1|)) (< |c_ULTIMATE.start_main_~b~0#1| (+ |c_ULTIMATE.start_main_~c~0#1| 1)) (< (+ (* 2 .cse0) (* 2 .cse1)) (+ .cse12 .cse13 (* 2 .cse2) 1 (* 2 .cse3))))) is different from true [2023-12-19 19:01:47,581 WARN L293 SmtUtils]: Spent 8.10s on a formula simplification that was a NOOP. DAG size: 21 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:02:05,350 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 21 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:02:18,600 WARN L293 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 21 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:02:31,845 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 19 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:03:17,771 WARN L293 SmtUtils]: Spent 24.50s on a formula simplification that was a NOOP. DAG size: 63 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-19 19:03:38,729 WARN L293 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 19 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:04:03,566 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 25 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:04:23,235 WARN L293 SmtUtils]: Spent 6.19s on a formula simplification that was a NOOP. DAG size: 19 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:04:52,081 WARN L293 SmtUtils]: Spent 6.15s on a formula simplification that was a NOOP. DAG size: 54 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-19 19:05:00,191 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 15 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:05:11,462 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 16 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:05:24,270 WARN L876 $PredicateComparison]: unable to prove that (let ((.cse5 (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse6 (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse8 (* |c_ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|)) (.cse9 (* |c_ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~s~0#1|)) (.cse4 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~r~0#1|)) (.cse7 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~p~0#1|)) (.cse14 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse13 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|)) (.cse12 (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~p~0#1|)) (.cse10 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1|)) (.cse15 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse11 (* |c_ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~r~0#1|)) (.cse2 (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse16 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1|)) (.cse3 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|)) (.cse17 (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse1 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~r~0#1|)) (.cse0 (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~p~0#1|))) (or (not (= (+ .cse0 .cse1) (+ |c_ULTIMATE.start_main_~c~0#1| .cse2 .cse3))) (not (= (+ .cse4 .cse5 .cse6 .cse7 .cse8 .cse9) (+ .cse10 .cse11 .cse12 .cse13 .cse14 .cse15))) (not (= (+ .cse16 .cse17) |c_ULTIMATE.start_main_~b~0#1|)) (= (+ (* .cse5 2) .cse6 (* 2 .cse8) .cse9 (* .cse4 2) (* .cse7 2)) (+ (* 2 .cse14) (* 2 .cse13) (* 2 .cse12) .cse10 .cse15 (* 2 .cse11))) (< (+ (* 2 .cse0) (* 2 .cse1)) (+ .cse16 .cse17 (* 2 .cse2) 1 (* 2 .cse3))) (< (+ (* 3 .cse2) (* .cse16 2) (* 3 .cse3) (* .cse17 2)) (+ (* 3 .cse1) (* 3 .cse0) 1)))) is different from true [2023-12-19 19:05:32,294 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 16 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:05:44,502 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 25 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:06:00,653 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 22 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:06:18,180 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 22 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:06:34,555 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 33 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:06:46,664 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 10 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:06:58,996 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 33 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:07:08,967 WARN L293 SmtUtils]: Spent 7.14s on a formula simplification that was a NOOP. DAG size: 25 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-12-19 19:07:21,030 WARN L293 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 33 (called from [L 731] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) Received shutdown request... [2023-12-19 19:07:22,733 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-19 19:07:22,736 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2023-12-19 19:07:23,758 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Forceful destruction successful, exit code 0 [2023-12-19 19:07:23,934 WARN L435 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forcibly destroying the process [2023-12-19 19:07:23,951 INFO L805 garLoopResultBuilder]: Registering result TIMEOUT for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-12-19 19:07:23,951 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21 [2023-12-19 19:07:23,951 WARN L619 AbstractCegarLoop]: Verification canceled: while NwaCegarLoop was analyzing trace of length 164 with TraceHistMax 24,while TraceCheckSpWp was constructing backward predicates,while executing Executor. [2023-12-19 19:07:23,955 INFO L445 BasicCegarLoop]: Path program histogram: [8, 4, 3, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:07:23,958 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2023-12-19 19:07:23,960 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 19.12 07:07:23 BoogieIcfgContainer [2023-12-19 19:07:23,960 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-12-19 19:07:23,960 INFO L158 Benchmark]: Toolchain (without parser) took 885352.81ms. Allocated memory was 213.9MB in the beginning and 329.3MB in the end (delta: 115.3MB). Free memory was 149.8MB in the beginning and 160.1MB in the end (delta: -10.2MB). Peak memory consumption was 105.5MB. Max. memory is 8.0GB. [2023-12-19 19:07:23,960 INFO L158 Benchmark]: CDTParser took 0.09ms. Allocated memory is still 213.9MB. Free memory was 164.2MB in the beginning and 164.1MB in the end (delta: 156.8kB). There was no memory consumed. Max. memory is 8.0GB. [2023-12-19 19:07:23,961 INFO L158 Benchmark]: CACSL2BoogieTranslator took 211.09ms. Allocated memory is still 213.9MB. Free memory was 149.8MB in the beginning and 138.2MB in the end (delta: 11.6MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2023-12-19 19:07:23,962 INFO L158 Benchmark]: Boogie Procedure Inliner took 25.69ms. Allocated memory is still 213.9MB. Free memory was 138.2MB in the beginning and 136.6MB in the end (delta: 1.6MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2023-12-19 19:07:23,963 INFO L158 Benchmark]: Boogie Preprocessor took 32.41ms. Allocated memory is still 213.9MB. Free memory was 136.6MB in the beginning and 134.8MB in the end (delta: 1.9MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2023-12-19 19:07:23,963 INFO L158 Benchmark]: RCFGBuilder took 259.24ms. Allocated memory is still 213.9MB. Free memory was 134.8MB in the beginning and 121.9MB in the end (delta: 12.8MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2023-12-19 19:07:23,963 INFO L158 Benchmark]: TraceAbstraction took 884819.86ms. Allocated memory was 213.9MB in the beginning and 329.3MB in the end (delta: 115.3MB). Free memory was 121.1MB in the beginning and 160.1MB in the end (delta: -38.9MB). Peak memory consumption was 77.2MB. Max. memory is 8.0GB. [2023-12-19 19:07:23,965 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### [2023-12-19 19:07:23,966 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 137 --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.09ms. Allocated memory is still 213.9MB. Free memory was 164.2MB in the beginning and 164.1MB in the end (delta: 156.8kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 211.09ms. Allocated memory is still 213.9MB. Free memory was 149.8MB in the beginning and 138.2MB in the end (delta: 11.6MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Procedure Inliner took 25.69ms. Allocated memory is still 213.9MB. Free memory was 138.2MB in the beginning and 136.6MB in the end (delta: 1.6MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * Boogie Preprocessor took 32.41ms. Allocated memory is still 213.9MB. Free memory was 136.6MB in the beginning and 134.8MB in the end (delta: 1.9MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 259.24ms. Allocated memory is still 213.9MB. Free memory was 134.8MB in the beginning and 121.9MB in the end (delta: 12.8MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * TraceAbstraction took 884819.86ms. Allocated memory was 213.9MB in the beginning and 329.3MB in the end (delta: 115.3MB). Free memory was 121.1MB in the beginning and 160.1MB in the end (delta: -38.9MB). Peak memory consumption was 77.2MB. 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: 13]: Timeout (TraceAbstraction) Unable to prove that a call to reach_error is unreachable (line 13). Cancelled while NwaCegarLoop was analyzing trace of length 164 with TraceHistMax 24,while TraceCheckSpWp was constructing backward predicates,while executing Executor. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 29 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 884.8s, OverallIterations: 22, TraceHistogramMax: 24, PathProgramHistogramMax: 8, EmptinessCheckTime: 0.0s, AutomataDifference: 128.4s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 1 mSolverCounterUnknown, 1225 SdHoareTripleChecker+Valid, 39.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 1098 mSDsluCounter, 6854 SdHoareTripleChecker+Invalid, 38.3s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 6067 mSDsCounter, 1243 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 7789 IncrementalHoareTripleChecker+Invalid, 9033 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 1243 mSolverCounterUnsat, 787 mSDtfsCounter, 7789 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 3120 GetRequests, 2555 SyntacticMatches, 7 SemanticMatches, 558 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 4381 ImplicationChecksByTransitivity, 235.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=620occurred in iteration=21, InterpolantAutomatonStates: 370, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 2.9s AutomataMinimizationTime, 21 MinimizatonAttempts, 259 StatesRemovedByMinimization, 19 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.2s SsaConstructionTime, 1.3s SatisfiabilityAnalysisTime, 339.2s InterpolantComputationTime, 1796 NumberOfCodeBlocks, 1606 NumberOfCodeBlocksAsserted, 44 NumberOfCheckSat, 2662 ConstructedInterpolants, 0 QuantifiedInterpolants, 21188 SizeOfPredicates, 158 NumberOfNonLiveVariables, 4006 ConjunctsInSsa, 785 ConjunctsInUnsatCore, 33 InterpolantComputations, 5 PerfectInterpolantSequences, 9898/10912 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