/usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.use.bitabs.translation false -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard-u_unwindbound10.c -------------------------------------------------------------------------------- This is Ultimate 0.2.4-tmp.fs.bitabs-eval-d9c3e40-m [2023-12-21 07:19:02,876 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-21 07:19:02,966 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf [2023-12-21 07:19:02,971 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-21 07:19:02,972 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-21 07:19:02,998 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-21 07:19:02,998 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-21 07:19:02,998 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-21 07:19:02,999 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-12-21 07:19:03,003 INFO L153 SettingsManager]: * Use memory slicer=true [2023-12-21 07:19:03,003 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-21 07:19:03,004 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-21 07:19:03,004 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-12-21 07:19:03,005 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-12-21 07:19:03,005 INFO L153 SettingsManager]: * Use SBE=true [2023-12-21 07:19:03,006 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-21 07:19:03,006 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-21 07:19:03,006 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-21 07:19:03,006 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-21 07:19:03,008 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-21 07:19:03,008 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-21 07:19:03,008 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-21 07:19:03,008 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-21 07:19:03,009 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-21 07:19:03,009 INFO L153 SettingsManager]: * Allow undefined functions=false [2023-12-21 07:19:03,009 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-21 07:19:03,009 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-21 07:19:03,009 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-21 07:19:03,010 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-21 07:19:03,010 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-12-21 07:19:03,011 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-21 07:19:03,011 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-21 07:19:03,012 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-21 07:19:03,012 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-21 07:19:03,012 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-21 07:19:03,012 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-21 07:19:03,012 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-12-21 07:19:03,013 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-21 07:19:03,013 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-21 07:19:03,013 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-12-21 07:19:03,013 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-21 07:19:03,013 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-12-21 07:19:03,013 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-21 07:19:03,014 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Use bitabs translation -> false [2023-12-21 07:19:03,247 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-21 07:19:03,267 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-21 07:19:03,269 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-21 07:19:03,270 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-21 07:19:03,271 INFO L274 PluginConnector]: CDTParser initialized [2023-12-21 07:19:03,272 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-u_unwindbound10.c [2023-12-21 07:19:04,417 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-21 07:19:04,576 INFO L384 CDTParser]: Found 1 translation units. [2023-12-21 07:19:04,576 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-u_unwindbound10.c [2023-12-21 07:19:04,582 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e2673bca7/ceeaf68fc57b4aa5a3ad1b236d21364d/FLAGcf5fda340 [2023-12-21 07:19:04,595 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e2673bca7/ceeaf68fc57b4aa5a3ad1b236d21364d [2023-12-21 07:19:04,597 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-21 07:19:04,598 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2023-12-21 07:19:04,599 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-21 07:19:04,599 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-21 07:19:04,607 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-21 07:19:04,607 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,608 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2bfe394f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04, skipping insertion in model container [2023-12-21 07:19:04,609 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,630 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-21 07:19:04,749 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-u_unwindbound10.c[537,550] [2023-12-21 07:19:04,777 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-21 07:19:04,786 INFO L202 MainTranslator]: Completed pre-run [2023-12-21 07:19:04,798 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-u_unwindbound10.c[537,550] [2023-12-21 07:19:04,805 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-21 07:19:04,822 INFO L206 MainTranslator]: Completed translation [2023-12-21 07:19:04,823 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04 WrapperNode [2023-12-21 07:19:04,823 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-21 07:19:04,824 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-21 07:19:04,824 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-21 07:19:04,824 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-21 07:19:04,830 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,836 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,850 INFO L138 Inliner]: procedures = 14, calls = 15, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 66 [2023-12-21 07:19:04,851 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-21 07:19:04,851 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-21 07:19:04,852 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-21 07:19:04,852 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-21 07:19:04,858 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,859 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,860 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,873 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2023-12-21 07:19:04,874 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,874 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,876 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,879 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,879 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,880 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,882 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-21 07:19:04,882 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-21 07:19:04,882 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-21 07:19:04,883 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-21 07:19:04,883 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04" (1/1) ... [2023-12-21 07:19:04,888 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-21 07:19:04,902 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:04,956 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2023-12-21 07:19:04,957 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2023-12-21 07:19:04,975 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-21 07:19:04,975 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-12-21 07:19:04,976 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-21 07:19:04,976 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-21 07:19:04,976 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-12-21 07:19:04,976 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-12-21 07:19:05,025 INFO L241 CfgBuilder]: Building ICFG [2023-12-21 07:19:05,026 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-21 07:19:05,153 INFO L282 CfgBuilder]: Performing block encoding [2023-12-21 07:19:05,175 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-21 07:19:05,175 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-12-21 07:19:05,175 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 07:19:05 BoogieIcfgContainer [2023-12-21 07:19:05,176 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-21 07:19:05,177 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-21 07:19:05,177 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-21 07:19:05,179 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-21 07:19:05,179 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.12 07:19:04" (1/3) ... [2023-12-21 07:19:05,180 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4b4c46f6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 07:19:05, skipping insertion in model container [2023-12-21 07:19:05,180 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:04" (2/3) ... [2023-12-21 07:19:05,180 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4b4c46f6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 07:19:05, skipping insertion in model container [2023-12-21 07:19:05,181 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 07:19:05" (3/3) ... [2023-12-21 07:19:05,181 INFO L112 eAbstractionObserver]: Analyzing ICFG hard-u_unwindbound10.c [2023-12-21 07:19:05,197 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-21 07:19:05,197 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-21 07:19:05,228 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-21 07:19:05,233 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;@4364779b, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-21 07:19:05,234 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-21 07:19:05,237 INFO L276 IsEmpty]: Start isEmpty. Operand has 25 states, 15 states have (on average 1.6666666666666667) internal successors, (25), 16 states have internal predecessors, (25), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-12-21 07:19:05,242 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-12-21 07:19:05,242 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:05,243 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:05,243 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:05,247 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:05,248 INFO L85 PathProgramCache]: Analyzing trace with hash 65649153, now seen corresponding path program 1 times [2023-12-21 07:19:05,255 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:05,256 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1795032184] [2023-12-21 07:19:05,256 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:05,256 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:05,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:05,383 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:05,384 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1795032184] [2023-12-21 07:19:05,384 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-21 07:19:05,385 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1566896234] [2023-12-21 07:19:05,385 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:05,385 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:05,385 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:05,388 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:19:05,408 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-12-21 07:19:05,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:05,467 INFO L262 TraceCheckSpWp]: Trace formula consists of 47 conjuncts, 1 conjunts are in the unsatisfiable core [2023-12-21 07:19:05,470 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:19:05,483 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-21 07:19:05,484 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-21 07:19:05,484 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1566896234] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:19:05,484 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:19:05,484 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-21 07:19:05,486 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1816927168] [2023-12-21 07:19:05,487 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:19:05,490 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-12-21 07:19:05,490 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:05,518 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-12-21 07:19:05,519 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-21 07:19:05,520 INFO L87 Difference]: Start difference. First operand has 25 states, 15 states have (on average 1.6666666666666667) internal successors, (25), 16 states have internal predecessors, (25), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 07:19:05,550 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:05,550 INFO L93 Difference]: Finished difference Result 48 states and 82 transitions. [2023-12-21 07:19:05,551 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-12-21 07:19:05,552 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2023-12-21 07:19:05,552 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:05,568 INFO L225 Difference]: With dead ends: 48 [2023-12-21 07:19:05,568 INFO L226 Difference]: Without dead ends: 23 [2023-12-21 07:19:05,571 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-21 07:19:05,573 INFO L413 NwaCegarLoop]: 33 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, 33 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:05,574 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 33 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:19:05,587 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2023-12-21 07:19:05,600 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2023-12-21 07:19:05,601 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-21 07:19:05,602 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 33 transitions. [2023-12-21 07:19:05,603 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 33 transitions. Word has length 9 [2023-12-21 07:19:05,603 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:05,603 INFO L495 AbstractCegarLoop]: Abstraction has 23 states and 33 transitions. [2023-12-21 07:19:05,603 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 07:19:05,604 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 33 transitions. [2023-12-21 07:19:05,604 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-12-21 07:19:05,604 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:05,604 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:05,615 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-12-21 07:19:05,810 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-21 07:19:05,811 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:05,811 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:05,811 INFO L85 PathProgramCache]: Analyzing trace with hash -1205755883, now seen corresponding path program 1 times [2023-12-21 07:19:05,812 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:05,812 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [556248937] [2023-12-21 07:19:05,812 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:05,812 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:05,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:06,033 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-21 07:19:06,033 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:06,033 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [556248937] [2023-12-21 07:19:06,034 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [556248937] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:19:06,034 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:19:06,034 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-21 07:19:06,034 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1185742784] [2023-12-21 07:19:06,034 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:19:06,035 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-21 07:19:06,035 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:06,035 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-21 07:19:06,036 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-21 07:19:06,036 INFO L87 Difference]: Start difference. First operand 23 states and 33 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 07:19:06,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:06,115 INFO L93 Difference]: Finished difference Result 37 states and 52 transitions. [2023-12-21 07:19:06,116 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-21 07:19:06,116 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2023-12-21 07:19:06,116 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:06,117 INFO L225 Difference]: With dead ends: 37 [2023-12-21 07:19:06,117 INFO L226 Difference]: Without dead ends: 35 [2023-12-21 07:19:06,117 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-12-21 07:19:06,118 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 15 mSDsluCounter, 68 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:06,119 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 96 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:19:06,119 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2023-12-21 07:19:06,126 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 27. [2023-12-21 07:19:06,126 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-21 07:19:06,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 36 transitions. [2023-12-21 07:19:06,127 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 36 transitions. Word has length 9 [2023-12-21 07:19:06,127 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:06,128 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 36 transitions. [2023-12-21 07:19:06,131 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 07:19:06,131 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 36 transitions. [2023-12-21 07:19:06,132 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-12-21 07:19:06,132 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:06,132 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:06,132 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-12-21 07:19:06,133 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:06,134 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:06,135 INFO L85 PathProgramCache]: Analyzing trace with hash -2004332404, now seen corresponding path program 1 times [2023-12-21 07:19:06,135 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:06,135 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [700303999] [2023-12-21 07:19:06,136 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:06,136 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:06,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:06,169 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:06,169 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [700303999] [2023-12-21 07:19:06,169 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-21 07:19:06,169 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2005555922] [2023-12-21 07:19:06,169 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:06,169 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:06,170 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:06,174 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:19:06,183 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-12-21 07:19:06,233 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:06,234 INFO L262 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 3 conjunts are in the unsatisfiable core [2023-12-21 07:19:06,235 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:19:06,278 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-21 07:19:06,279 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-21 07:19:06,282 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2005555922] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:19:06,285 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:19:06,285 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-21 07:19:06,285 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [441698226] [2023-12-21 07:19:06,285 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:19:06,286 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-12-21 07:19:06,286 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:06,286 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-12-21 07:19:06,286 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-21 07:19:06,287 INFO L87 Difference]: Start difference. First operand 27 states and 36 transitions. Second operand has 4 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 07:19:06,312 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:06,312 INFO L93 Difference]: Finished difference Result 43 states and 58 transitions. [2023-12-21 07:19:06,314 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-12-21 07:19:06,314 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2023-12-21 07:19:06,314 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:06,315 INFO L225 Difference]: With dead ends: 43 [2023-12-21 07:19:06,315 INFO L226 Difference]: Without dead ends: 29 [2023-12-21 07:19:06,316 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-21 07:19:06,318 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 0 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:06,319 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 86 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:19:06,319 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2023-12-21 07:19:06,324 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2023-12-21 07:19:06,324 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-21 07:19:06,325 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 38 transitions. [2023-12-21 07:19:06,325 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 38 transitions. Word has length 11 [2023-12-21 07:19:06,325 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:06,325 INFO L495 AbstractCegarLoop]: Abstraction has 29 states and 38 transitions. [2023-12-21 07:19:06,326 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 07:19:06,326 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 38 transitions. [2023-12-21 07:19:06,326 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2023-12-21 07:19:06,326 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:06,326 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:06,336 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-12-21 07:19:06,535 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2023-12-21 07:19:06,535 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:06,535 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:06,536 INFO L85 PathProgramCache]: Analyzing trace with hash 1962237034, now seen corresponding path program 1 times [2023-12-21 07:19:06,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:06,536 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [726342738] [2023-12-21 07:19:06,537 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:06,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:06,569 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:06,750 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2023-12-21 07:19:06,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:06,759 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-21 07:19:06,759 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:06,759 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [726342738] [2023-12-21 07:19:06,759 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [726342738] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:19:06,760 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:19:06,760 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-21 07:19:06,760 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1556072824] [2023-12-21 07:19:06,760 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:19:06,760 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-21 07:19:06,760 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:06,761 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-21 07:19:06,761 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-21 07:19:06,762 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), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-21 07:19:06,824 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:06,825 INFO L93 Difference]: Finished difference Result 43 states and 57 transitions. [2023-12-21 07:19:06,825 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-21 07:19:06,825 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), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2023-12-21 07:19:06,825 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:06,828 INFO L225 Difference]: With dead ends: 43 [2023-12-21 07:19:06,828 INFO L226 Difference]: Without dead ends: 41 [2023-12-21 07:19:06,831 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-12-21 07:19:06,833 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 13 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:06,834 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 92 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:19:06,834 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2023-12-21 07:19:06,841 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 33. [2023-12-21 07:19:06,841 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-21 07:19:06,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 41 transitions. [2023-12-21 07:19:06,842 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 41 transitions. Word has length 14 [2023-12-21 07:19:06,842 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:06,843 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 41 transitions. [2023-12-21 07:19:06,843 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), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-21 07:19:06,843 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 41 transitions. [2023-12-21 07:19:06,843 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2023-12-21 07:19:06,843 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:06,843 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:06,844 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-12-21 07:19:06,844 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:06,844 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:06,844 INFO L85 PathProgramCache]: Analyzing trace with hash 608183541, now seen corresponding path program 1 times [2023-12-21 07:19:06,844 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:06,844 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1306872708] [2023-12-21 07:19:06,844 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:06,845 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:06,853 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:19:06,853 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1694305070] [2023-12-21 07:19:06,853 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:06,853 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:06,853 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:06,854 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:19:06,860 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-12-21 07:19:06,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:06,909 INFO L262 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 17 conjunts are in the unsatisfiable core [2023-12-21 07:19:06,913 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:19:07,038 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-21 07:19:07,039 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:19:07,256 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-21 07:19:07,256 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:07,256 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1306872708] [2023-12-21 07:19:07,257 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:19:07,257 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1694305070] [2023-12-21 07:19:07,257 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1694305070] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:19:07,258 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:19:07,258 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 12 [2023-12-21 07:19:07,258 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2090798444] [2023-12-21 07:19:07,258 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:19:07,259 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-12-21 07:19:07,259 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:07,260 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-12-21 07:19:07,260 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2023-12-21 07:19:07,261 INFO L87 Difference]: Start difference. First operand 33 states and 41 transitions. Second operand has 12 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-21 07:19:11,500 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:19:15,585 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.08s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:19:15,634 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:15,634 INFO L93 Difference]: Finished difference Result 77 states and 106 transitions. [2023-12-21 07:19:15,634 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-12-21 07:19:15,635 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) Word has length 19 [2023-12-21 07:19:15,635 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:15,637 INFO L225 Difference]: With dead ends: 77 [2023-12-21 07:19:15,637 INFO L226 Difference]: Without dead ends: 62 [2023-12-21 07:19:15,637 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2023-12-21 07:19:15,638 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 39 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 25 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 176 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.3s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:15,638 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 131 Invalid, 176 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 149 Invalid, 2 Unknown, 0 Unchecked, 8.3s Time] [2023-12-21 07:19:15,639 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2023-12-21 07:19:15,650 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 60. [2023-12-21 07:19:15,650 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 36 states have (on average 1.2777777777777777) internal successors, (46), 40 states have internal predecessors, (46), 18 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2023-12-21 07:19:15,652 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 80 transitions. [2023-12-21 07:19:15,652 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 80 transitions. Word has length 19 [2023-12-21 07:19:15,652 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:15,652 INFO L495 AbstractCegarLoop]: Abstraction has 60 states and 80 transitions. [2023-12-21 07:19:15,653 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-21 07:19:15,653 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 80 transitions. [2023-12-21 07:19:15,653 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-12-21 07:19:15,654 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:15,654 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:15,660 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-21 07:19:15,860 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:15,861 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:15,861 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:15,861 INFO L85 PathProgramCache]: Analyzing trace with hash 560729168, now seen corresponding path program 1 times [2023-12-21 07:19:15,861 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:15,861 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2147009797] [2023-12-21 07:19:15,861 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:15,861 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:15,870 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:19:15,870 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [546052185] [2023-12-21 07:19:15,870 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:15,871 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:15,871 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:15,872 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:19:15,894 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-12-21 07:19:15,916 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:15,916 INFO L262 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 5 conjunts are in the unsatisfiable core [2023-12-21 07:19:15,918 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:19:15,972 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-21 07:19:15,972 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-21 07:19:15,972 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:15,973 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2147009797] [2023-12-21 07:19:15,973 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:19:15,973 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [546052185] [2023-12-21 07:19:15,973 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [546052185] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:19:15,973 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:19:15,973 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-12-21 07:19:15,973 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2139525724] [2023-12-21 07:19:15,973 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:19:15,974 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-21 07:19:15,974 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:15,974 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-21 07:19:15,975 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-21 07:19:15,975 INFO L87 Difference]: Start difference. First operand 60 states and 80 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-21 07:19:16,013 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:16,013 INFO L93 Difference]: Finished difference Result 75 states and 92 transitions. [2023-12-21 07:19:16,013 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-12-21 07:19:16,014 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 27 [2023-12-21 07:19:16,014 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:16,016 INFO L225 Difference]: With dead ends: 75 [2023-12-21 07:19:16,016 INFO L226 Difference]: Without dead ends: 68 [2023-12-21 07:19:16,016 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-21 07:19:16,018 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 1 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:16,018 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 105 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:19:16,020 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2023-12-21 07:19:16,042 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 68. [2023-12-21 07:19:16,042 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 42 states have (on average 1.2142857142857142) internal successors, (51), 46 states have internal predecessors, (51), 18 states have call successors, (18), 7 states have call predecessors, (18), 7 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2023-12-21 07:19:16,043 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 85 transitions. [2023-12-21 07:19:16,044 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 85 transitions. Word has length 27 [2023-12-21 07:19:16,044 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:16,044 INFO L495 AbstractCegarLoop]: Abstraction has 68 states and 85 transitions. [2023-12-21 07:19:16,044 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-21 07:19:16,044 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 85 transitions. [2023-12-21 07:19:16,045 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-12-21 07:19:16,045 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:16,045 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:16,050 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-21 07:19:16,250 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:16,251 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:16,252 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:16,252 INFO L85 PathProgramCache]: Analyzing trace with hash 562457046, now seen corresponding path program 1 times [2023-12-21 07:19:16,252 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:16,252 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1240694614] [2023-12-21 07:19:16,252 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:16,252 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:16,259 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:19:16,259 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2059025893] [2023-12-21 07:19:16,259 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:16,260 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:16,260 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:16,261 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:19:16,263 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-12-21 07:19:16,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:16,313 INFO L262 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 18 conjunts are in the unsatisfiable core [2023-12-21 07:19:16,315 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:19:16,492 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-21 07:19:16,492 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-21 07:19:16,492 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:16,492 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1240694614] [2023-12-21 07:19:16,493 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:19:16,493 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2059025893] [2023-12-21 07:19:16,493 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2059025893] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:19:16,493 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:19:16,493 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2023-12-21 07:19:16,493 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1203850163] [2023-12-21 07:19:16,493 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:19:16,494 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-21 07:19:16,494 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:16,495 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-21 07:19:16,495 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2023-12-21 07:19:16,495 INFO L87 Difference]: Start difference. First operand 68 states and 85 transitions. Second operand has 8 states, 8 states have (on average 1.75) internal successors, (14), 7 states have internal predecessors, (14), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-21 07:19:16,693 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:16,693 INFO L93 Difference]: Finished difference Result 74 states and 90 transitions. [2023-12-21 07:19:16,694 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-12-21 07:19:16,694 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 1.75) internal successors, (14), 7 states have internal predecessors, (14), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 27 [2023-12-21 07:19:16,694 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:16,695 INFO L225 Difference]: With dead ends: 74 [2023-12-21 07:19:16,695 INFO L226 Difference]: Without dead ends: 62 [2023-12-21 07:19:16,695 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2023-12-21 07:19:16,696 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 25 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 75 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 84 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 75 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:16,696 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 111 Invalid, 84 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 75 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-21 07:19:16,697 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2023-12-21 07:19:16,705 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2023-12-21 07:19:16,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 39 states have (on average 1.205128205128205) internal successors, (47), 42 states have internal predecessors, (47), 15 states have call successors, (15), 7 states have call predecessors, (15), 7 states have return successors, (14), 12 states have call predecessors, (14), 14 states have call successors, (14) [2023-12-21 07:19:16,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 76 transitions. [2023-12-21 07:19:16,707 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 76 transitions. Word has length 27 [2023-12-21 07:19:16,707 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:16,707 INFO L495 AbstractCegarLoop]: Abstraction has 62 states and 76 transitions. [2023-12-21 07:19:16,707 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 1.75) internal successors, (14), 7 states have internal predecessors, (14), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-21 07:19:16,708 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 76 transitions. [2023-12-21 07:19:16,708 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2023-12-21 07:19:16,708 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:16,709 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:16,714 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-12-21 07:19:16,912 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:16,913 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:16,913 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:16,913 INFO L85 PathProgramCache]: Analyzing trace with hash 177821141, now seen corresponding path program 1 times [2023-12-21 07:19:16,913 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:16,913 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [273047727] [2023-12-21 07:19:16,914 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:16,914 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:16,921 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:19:16,921 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [312896918] [2023-12-21 07:19:16,921 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:16,921 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:16,921 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:16,922 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:19:16,934 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-12-21 07:19:16,967 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:16,968 INFO L262 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 5 conjunts are in the unsatisfiable core [2023-12-21 07:19:16,969 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:19:17,004 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-21 07:19:17,004 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:19:17,038 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-21 07:19:17,039 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:17,039 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [273047727] [2023-12-21 07:19:17,039 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:19:17,039 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [312896918] [2023-12-21 07:19:17,039 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [312896918] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:19:17,039 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:19:17,039 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2023-12-21 07:19:17,039 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [851994562] [2023-12-21 07:19:17,039 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:19:17,040 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-21 07:19:17,040 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:17,040 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-21 07:19:17,040 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2023-12-21 07:19:17,041 INFO L87 Difference]: Start difference. First operand 62 states and 76 transitions. Second operand has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-21 07:19:17,139 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:17,139 INFO L93 Difference]: Finished difference Result 133 states and 160 transitions. [2023-12-21 07:19:17,140 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-21 07:19:17,140 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 29 [2023-12-21 07:19:17,140 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:17,141 INFO L225 Difference]: With dead ends: 133 [2023-12-21 07:19:17,141 INFO L226 Difference]: Without dead ends: 111 [2023-12-21 07:19:17,141 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 50 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2023-12-21 07:19:17,142 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 34 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:17,142 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 144 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-21 07:19:17,143 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2023-12-21 07:19:17,154 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 106. [2023-12-21 07:19:17,155 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 69 states have (on average 1.173913043478261) internal successors, (81), 72 states have internal predecessors, (81), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2023-12-21 07:19:17,156 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 123 transitions. [2023-12-21 07:19:17,156 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 123 transitions. Word has length 29 [2023-12-21 07:19:17,156 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:17,156 INFO L495 AbstractCegarLoop]: Abstraction has 106 states and 123 transitions. [2023-12-21 07:19:17,156 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-21 07:19:17,156 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 123 transitions. [2023-12-21 07:19:17,157 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-12-21 07:19:17,157 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:17,157 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:17,166 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-12-21 07:19:17,363 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:17,363 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:17,364 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:17,364 INFO L85 PathProgramCache]: Analyzing trace with hash -1287430247, now seen corresponding path program 1 times [2023-12-21 07:19:17,364 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:17,364 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [350797574] [2023-12-21 07:19:17,364 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:17,364 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:17,371 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:19:17,371 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [474473294] [2023-12-21 07:19:17,371 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:17,372 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:17,372 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:17,373 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:19:17,376 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-12-21 07:19:17,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:17,419 INFO L262 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 7 conjunts are in the unsatisfiable core [2023-12-21 07:19:17,423 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:19:17,481 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 42 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-12-21 07:19:17,481 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:19:17,539 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-12-21 07:19:17,539 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:17,539 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [350797574] [2023-12-21 07:19:17,539 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:19:17,540 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [474473294] [2023-12-21 07:19:17,540 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [474473294] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:19:17,540 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:19:17,540 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 10 [2023-12-21 07:19:17,540 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [771959725] [2023-12-21 07:19:17,540 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:19:17,540 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-12-21 07:19:17,541 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:17,541 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-12-21 07:19:17,541 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2023-12-21 07:19:17,541 INFO L87 Difference]: Start difference. First operand 106 states and 123 transitions. Second operand has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-21 07:19:17,685 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:17,685 INFO L93 Difference]: Finished difference Result 198 states and 237 transitions. [2023-12-21 07:19:17,686 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-21 07:19:17,686 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 45 [2023-12-21 07:19:17,686 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:17,687 INFO L225 Difference]: With dead ends: 198 [2023-12-21 07:19:17,687 INFO L226 Difference]: Without dead ends: 184 [2023-12-21 07:19:17,688 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=52, Invalid=104, Unknown=0, NotChecked=0, Total=156 [2023-12-21 07:19:17,688 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 82 mSDsluCounter, 145 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 82 SdHoareTripleChecker+Valid, 174 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:17,688 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [82 Valid, 174 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-21 07:19:17,689 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2023-12-21 07:19:17,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 177. [2023-12-21 07:19:17,708 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 177 states, 114 states have (on average 1.1842105263157894) internal successors, (135), 121 states have internal predecessors, (135), 40 states have call successors, (40), 22 states have call predecessors, (40), 22 states have return successors, (36), 33 states have call predecessors, (36), 36 states have call successors, (36) [2023-12-21 07:19:17,710 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 177 states to 177 states and 211 transitions. [2023-12-21 07:19:17,710 INFO L78 Accepts]: Start accepts. Automaton has 177 states and 211 transitions. Word has length 45 [2023-12-21 07:19:17,710 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:17,710 INFO L495 AbstractCegarLoop]: Abstraction has 177 states and 211 transitions. [2023-12-21 07:19:17,710 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-21 07:19:17,710 INFO L276 IsEmpty]: Start isEmpty. Operand 177 states and 211 transitions. [2023-12-21 07:19:17,711 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-12-21 07:19:17,711 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:17,711 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:17,722 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-12-21 07:19:17,917 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:17,918 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:17,918 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:17,918 INFO L85 PathProgramCache]: Analyzing trace with hash -1285702369, now seen corresponding path program 1 times [2023-12-21 07:19:17,918 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:17,918 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1061661000] [2023-12-21 07:19:17,918 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:17,918 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:17,925 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:19:17,925 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [501680801] [2023-12-21 07:19:17,925 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:17,925 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:17,925 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:17,926 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:19:17,930 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-12-21 07:19:17,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:17,986 INFO L262 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 15 conjunts are in the unsatisfiable core [2023-12-21 07:19:17,988 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:19:18,068 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 14 proven. 13 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2023-12-21 07:19:18,068 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:19:18,143 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:18,143 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1061661000] [2023-12-21 07:19:18,143 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:19:18,144 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [501680801] [2023-12-21 07:19:18,144 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [501680801] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-21 07:19:18,144 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-21 07:19:18,144 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2023-12-21 07:19:18,144 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [410972491] [2023-12-21 07:19:18,144 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-21 07:19:18,144 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-12-21 07:19:18,145 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:18,145 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-12-21 07:19:18,145 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2023-12-21 07:19:18,145 INFO L87 Difference]: Start difference. First operand 177 states and 211 transitions. Second operand has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 1 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-21 07:19:18,241 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:18,241 INFO L93 Difference]: Finished difference Result 221 states and 270 transitions. [2023-12-21 07:19:18,242 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-12-21 07:19:18,242 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 1 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 45 [2023-12-21 07:19:18,242 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:18,244 INFO L225 Difference]: With dead ends: 221 [2023-12-21 07:19:18,244 INFO L226 Difference]: Without dead ends: 219 [2023-12-21 07:19:18,244 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 45 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2023-12-21 07:19:18,245 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 16 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 92 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 95 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 92 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:18,245 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 91 Invalid, 95 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 92 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-21 07:19:18,245 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 219 states. [2023-12-21 07:19:18,263 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 219 to 216. [2023-12-21 07:19:18,264 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 140 states have (on average 1.2) internal successors, (168), 150 states have internal predecessors, (168), 49 states have call successors, (49), 26 states have call predecessors, (49), 26 states have return successors, (45), 39 states have call predecessors, (45), 45 states have call successors, (45) [2023-12-21 07:19:18,265 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 262 transitions. [2023-12-21 07:19:18,265 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 262 transitions. Word has length 45 [2023-12-21 07:19:18,266 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:18,266 INFO L495 AbstractCegarLoop]: Abstraction has 216 states and 262 transitions. [2023-12-21 07:19:18,266 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 1 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-21 07:19:18,266 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 262 transitions. [2023-12-21 07:19:18,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2023-12-21 07:19:18,267 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:18,267 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1] [2023-12-21 07:19:18,275 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-12-21 07:19:18,472 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,SelfDestructingSolverStorable9 [2023-12-21 07:19:18,473 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:18,473 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:18,473 INFO L85 PathProgramCache]: Analyzing trace with hash -1354605241, now seen corresponding path program 1 times [2023-12-21 07:19:18,473 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:18,473 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1280656967] [2023-12-21 07:19:18,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:18,474 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:18,480 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:19:18,480 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1280267802] [2023-12-21 07:19:18,480 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:18,480 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:18,480 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:18,481 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:19:18,499 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-12-21 07:19:18,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:18,647 INFO L262 TraceCheckSpWp]: Trace formula consists of 142 conjuncts, 30 conjunts are in the unsatisfiable core [2023-12-21 07:19:18,650 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:19:18,776 INFO L134 CoverageAnalysis]: Checked inductivity of 144 backedges. 29 proven. 39 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2023-12-21 07:19:18,776 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:19:19,701 INFO L134 CoverageAnalysis]: Checked inductivity of 144 backedges. 41 proven. 7 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2023-12-21 07:19:19,702 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:19,702 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1280656967] [2023-12-21 07:19:19,702 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:19:19,702 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1280267802] [2023-12-21 07:19:19,702 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1280267802] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:19:19,702 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:19:19,702 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 7] total 14 [2023-12-21 07:19:19,703 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1325505660] [2023-12-21 07:19:19,703 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:19:19,703 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-12-21 07:19:19,703 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:19,704 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-12-21 07:19:19,704 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2023-12-21 07:19:19,704 INFO L87 Difference]: Start difference. First operand 216 states and 262 transitions. Second operand has 14 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 11 states have internal predecessors, (31), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 7 states have call predecessors, (14), 6 states have call successors, (14) [2023-12-21 07:19:27,193 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:19:29,025 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:29,025 INFO L93 Difference]: Finished difference Result 267 states and 322 transitions. [2023-12-21 07:19:29,025 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-21 07:19:29,026 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 11 states have internal predecessors, (31), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 7 states have call predecessors, (14), 6 states have call successors, (14) Word has length 55 [2023-12-21 07:19:29,026 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:29,027 INFO L225 Difference]: With dead ends: 267 [2023-12-21 07:19:29,027 INFO L226 Difference]: Without dead ends: 245 [2023-12-21 07:19:29,028 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 96 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=55, Invalid=185, Unknown=0, NotChecked=0, Total=240 [2023-12-21 07:19:29,028 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 32 mSDsluCounter, 193 mSDsCounter, 0 mSdLazyCounter, 283 mSolverCounterSat, 16 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 227 SdHoareTripleChecker+Invalid, 300 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 283 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.3s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:29,028 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 227 Invalid, 300 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 283 Invalid, 1 Unknown, 0 Unchecked, 9.3s Time] [2023-12-21 07:19:29,029 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 245 states. [2023-12-21 07:19:29,053 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 245 to 233. [2023-12-21 07:19:29,053 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 233 states, 154 states have (on average 1.1753246753246753) internal successors, (181), 163 states have internal predecessors, (181), 49 states have call successors, (49), 29 states have call predecessors, (49), 29 states have return successors, (46), 40 states have call predecessors, (46), 46 states have call successors, (46) [2023-12-21 07:19:29,055 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 233 states to 233 states and 276 transitions. [2023-12-21 07:19:29,055 INFO L78 Accepts]: Start accepts. Automaton has 233 states and 276 transitions. Word has length 55 [2023-12-21 07:19:29,055 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:29,055 INFO L495 AbstractCegarLoop]: Abstraction has 233 states and 276 transitions. [2023-12-21 07:19:29,055 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 11 states have internal predecessors, (31), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 7 states have call predecessors, (14), 6 states have call successors, (14) [2023-12-21 07:19:29,055 INFO L276 IsEmpty]: Start isEmpty. Operand 233 states and 276 transitions. [2023-12-21 07:19:29,056 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2023-12-21 07:19:29,056 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:29,056 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:29,064 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-12-21 07:19:29,262 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:29,263 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:29,263 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:29,263 INFO L85 PathProgramCache]: Analyzing trace with hash -293585845, now seen corresponding path program 1 times [2023-12-21 07:19:29,263 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:29,263 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2001493784] [2023-12-21 07:19:29,263 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:29,263 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:29,269 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:19:29,270 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1349172571] [2023-12-21 07:19:29,270 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:29,270 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:29,270 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:29,271 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:19:29,274 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-12-21 07:19:32,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:32,837 INFO L262 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 40 conjunts are in the unsatisfiable core [2023-12-21 07:19:32,839 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:19:33,636 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 18 proven. 28 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-12-21 07:19:33,636 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:20:05,677 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 18 proven. 28 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-12-21 07:20:05,677 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:20:05,677 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2001493784] [2023-12-21 07:20:05,677 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:20:05,677 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1349172571] [2023-12-21 07:20:05,677 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1349172571] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:20:05,677 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:20:05,677 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 21 [2023-12-21 07:20:05,678 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1718121156] [2023-12-21 07:20:05,678 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:20:05,678 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-12-21 07:20:05,678 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:20:05,679 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-12-21 07:20:05,679 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=341, Unknown=2, NotChecked=0, Total=420 [2023-12-21 07:20:05,679 INFO L87 Difference]: Start difference. First operand 233 states and 276 transitions. Second operand has 21 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 19 states have internal predecessors, (43), 9 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-21 07:20:09,468 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.67s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2023-12-21 07:20:15,649 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:20:19,667 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:20:23,676 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:20:26,422 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.41s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:20:39,069 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.15s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:20:44,052 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:08,361 WARN L293 SmtUtils]: Spent 23.89s on a formula simplification. DAG size of input: 55 DAG size of output: 54 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:21:12,374 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:16,637 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:35,741 WARN L293 SmtUtils]: Spent 15.09s on a formula simplification that was a NOOP. DAG size: 51 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:21:39,745 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:43,749 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:47,757 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:51,762 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:56,710 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:58,241 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.53s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:22:00,038 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.11s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:22:04,894 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:22:09,191 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:22:15,739 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.25s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:22:19,862 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:22:23,875 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:22:27,907 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:22:32,188 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:22:55,903 WARN L293 SmtUtils]: Spent 16.52s on a formula simplification. DAG size of input: 43 DAG size of output: 42 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:23:00,083 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:04,086 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:14,980 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.97s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:17,740 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.76s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:21,744 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:40,105 WARN L293 SmtUtils]: Spent 12.57s on a formula simplification that was a NOOP. DAG size: 39 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:23:41,850 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.24s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:46,027 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:50,896 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:54,988 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:59,006 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:24:01,454 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.44s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:24:05,854 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.70s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:24:09,863 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:24:13,896 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:24:45,472 WARN L293 SmtUtils]: Spent 5.01s on a formula simplification that was a NOOP. DAG size: 39 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:24:49,986 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:15,805 WARN L293 SmtUtils]: Spent 5.87s on a formula simplification that was a NOOP. DAG size: 35 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:25:20,432 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:24,501 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:27,154 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.65s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:30,057 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.90s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:32,214 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:39,617 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:07,209 WARN L293 SmtUtils]: Spent 19.63s on a formula simplification that was a NOOP. DAG size: 41 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:26:11,215 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:27:05,099 WARN L293 SmtUtils]: Spent 29.49s on a formula simplification that was a NOOP. DAG size: 53 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:27:11,659 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:27:15,667 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:27:16,332 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:27:16,332 INFO L93 Difference]: Finished difference Result 365 states and 454 transitions. [2023-12-21 07:27:16,336 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2023-12-21 07:27:16,336 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 19 states have internal predecessors, (43), 9 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-21 07:27:16,336 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:27:16,338 INFO L225 Difference]: With dead ends: 365 [2023-12-21 07:27:16,338 INFO L226 Difference]: Without dead ends: 297 [2023-12-21 07:27:16,339 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 98 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 244 ImplicationChecksByTransitivity, 274.6s TimeCoverageRelationStatistics Valid=277, Invalid=1037, Unknown=18, NotChecked=0, Total=1332 [2023-12-21 07:27:16,339 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 103 mSDsluCounter, 318 mSDsCounter, 0 mSdLazyCounter, 423 mSolverCounterSat, 91 mSolverCounterUnsat, 33 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 182.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 105 SdHoareTripleChecker+Valid, 345 SdHoareTripleChecker+Invalid, 547 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 423 IncrementalHoareTripleChecker+Invalid, 33 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 183.3s IncrementalHoareTripleChecker+Time [2023-12-21 07:27:16,340 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [105 Valid, 345 Invalid, 547 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 423 Invalid, 33 Unknown, 0 Unchecked, 183.3s Time] [2023-12-21 07:27:16,340 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 297 states. [2023-12-21 07:27:16,392 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 297 to 252. [2023-12-21 07:27:16,393 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 252 states, 170 states have (on average 1.1529411764705881) internal successors, (196), 179 states have internal predecessors, (196), 47 states have call successors, (47), 34 states have call predecessors, (47), 34 states have return successors, (44), 38 states have call predecessors, (44), 44 states have call successors, (44) [2023-12-21 07:27:16,394 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 252 states to 252 states and 287 transitions. [2023-12-21 07:27:16,395 INFO L78 Accepts]: Start accepts. Automaton has 252 states and 287 transitions. Word has length 59 [2023-12-21 07:27:16,395 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:27:16,395 INFO L495 AbstractCegarLoop]: Abstraction has 252 states and 287 transitions. [2023-12-21 07:27:16,395 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 19 states have internal predecessors, (43), 9 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-21 07:27:16,395 INFO L276 IsEmpty]: Start isEmpty. Operand 252 states and 287 transitions. [2023-12-21 07:27:16,399 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2023-12-21 07:27:16,399 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:27:16,399 INFO L195 NwaCegarLoop]: trace histogram [10, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:27:16,407 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-12-21 07:27:16,606 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,SelfDestructingSolverStorable11 [2023-12-21 07:27:16,607 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:27:16,607 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:27:16,607 INFO L85 PathProgramCache]: Analyzing trace with hash 433404212, now seen corresponding path program 2 times [2023-12-21 07:27:16,607 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:27:16,607 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1971212290] [2023-12-21 07:27:16,607 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:27:16,607 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:27:16,614 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:27:16,615 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1251952301] [2023-12-21 07:27:16,615 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-21 07:27:16,615 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:27:16,615 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:27:16,619 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:27:16,621 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-12-21 07:27:16,945 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-21 07:27:16,945 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 07:27:16,946 INFO L262 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 34 conjunts are in the unsatisfiable core [2023-12-21 07:27:16,948 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:27:17,452 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 20 proven. 32 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2023-12-21 07:27:17,452 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:27:44,463 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 20 proven. 32 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2023-12-21 07:27:44,463 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:27:44,463 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1971212290] [2023-12-21 07:27:44,463 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:27:44,464 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1251952301] [2023-12-21 07:27:44,464 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1251952301] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:27:44,464 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:27:44,464 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 22 [2023-12-21 07:27:44,464 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1360923891] [2023-12-21 07:27:44,464 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:27:44,464 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-12-21 07:27:44,464 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:27:44,465 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-12-21 07:27:44,465 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=365, Unknown=4, NotChecked=0, Total=462 [2023-12-21 07:27:44,466 INFO L87 Difference]: Start difference. First operand 252 states and 287 transitions. Second operand has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 10 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 10 states have call predecessors, (18), 10 states have call successors, (18) [2023-12-21 07:27:51,047 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:27:55,548 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:28:16,686 WARN L293 SmtUtils]: Spent 19.92s on a formula simplification that was a NOOP. DAG size: 27 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:28:19,280 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.29s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:28:21,886 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.99s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:28:26,554 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:29:10,957 WARN L293 SmtUtils]: Spent 43.85s on a formula simplification that was a NOOP. DAG size: 36 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:29:15,450 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:29:19,456 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:29:23,460 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:29:28,485 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:29:30,153 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.67s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:29:34,156 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:29:38,755 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:29:48,246 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:06,365 WARN L293 SmtUtils]: Spent 16.39s on a formula simplification that was a NOOP. DAG size: 27 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:30:10,544 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:22,536 WARN L293 SmtUtils]: Spent 7.44s on a formula simplification that was a NOOP. DAG size: 26 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:30:26,538 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:31,013 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:36,245 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:40,533 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:44,624 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:26,088 WARN L293 SmtUtils]: Spent 20.68s on a formula simplification that was a NOOP. DAG size: 25 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:31:27,355 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.04s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:29,174 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.82s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:33,183 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:37,186 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:41,195 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:45,200 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:46,798 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.35s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:50,907 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:54,915 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:58,926 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:32:04,911 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:32:05,052 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:32:05,053 INFO L93 Difference]: Finished difference Result 316 states and 371 transitions. [2023-12-21 07:32:05,054 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-12-21 07:32:05,054 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 10 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 10 states have call predecessors, (18), 10 states have call successors, (18) Word has length 64 [2023-12-21 07:32:05,054 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:32:05,055 INFO L225 Difference]: With dead ends: 316 [2023-12-21 07:32:05,055 INFO L226 Difference]: Without dead ends: 271 [2023-12-21 07:32:05,056 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 106 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 180 ImplicationChecksByTransitivity, 167.5s TimeCoverageRelationStatistics Valid=212, Invalid=770, Unknown=10, NotChecked=0, Total=992 [2023-12-21 07:32:05,057 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 62 mSDsluCounter, 297 mSDsCounter, 0 mSdLazyCounter, 339 mSolverCounterSat, 65 mSolverCounterUnsat, 24 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 118.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 72 SdHoareTripleChecker+Valid, 325 SdHoareTripleChecker+Invalid, 428 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 65 IncrementalHoareTripleChecker+Valid, 339 IncrementalHoareTripleChecker+Invalid, 24 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 118.7s IncrementalHoareTripleChecker+Time [2023-12-21 07:32:05,057 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [72 Valid, 325 Invalid, 428 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [65 Valid, 339 Invalid, 24 Unknown, 0 Unchecked, 118.7s Time] [2023-12-21 07:32:05,057 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 271 states. [2023-12-21 07:32:05,112 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 271 to 256. [2023-12-21 07:32:05,113 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 256 states, 174 states have (on average 1.132183908045977) internal successors, (197), 182 states have internal predecessors, (197), 46 states have call successors, (46), 36 states have call predecessors, (46), 35 states have return successors, (43), 37 states have call predecessors, (43), 43 states have call successors, (43) [2023-12-21 07:32:05,114 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 256 states to 256 states and 286 transitions. [2023-12-21 07:32:05,114 INFO L78 Accepts]: Start accepts. Automaton has 256 states and 286 transitions. Word has length 64 [2023-12-21 07:32:05,114 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:32:05,114 INFO L495 AbstractCegarLoop]: Abstraction has 256 states and 286 transitions. [2023-12-21 07:32:05,114 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 10 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 10 states have call predecessors, (18), 10 states have call successors, (18) [2023-12-21 07:32:05,114 INFO L276 IsEmpty]: Start isEmpty. Operand 256 states and 286 transitions. [2023-12-21 07:32:05,115 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2023-12-21 07:32:05,115 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:32:05,115 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:32:05,123 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-12-21 07:32:05,323 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,SelfDestructingSolverStorable12 [2023-12-21 07:32:05,324 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:32:05,324 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:32:05,324 INFO L85 PathProgramCache]: Analyzing trace with hash 1181721499, now seen corresponding path program 1 times [2023-12-21 07:32:05,324 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:32:05,324 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [542553480] [2023-12-21 07:32:05,324 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:32:05,325 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:32:05,333 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:32:05,334 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [313570671] [2023-12-21 07:32:05,334 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:32:05,334 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:32:05,334 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:32:05,335 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:32:05,337 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-12-21 07:32:05,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:32:05,527 INFO L262 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 36 conjunts are in the unsatisfiable core [2023-12-21 07:32:05,528 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:32:05,878 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 22 proven. 36 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-12-21 07:32:05,878 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:32:10,298 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:32:10,298 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [542553480] [2023-12-21 07:32:10,298 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:32:10,298 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [313570671] [2023-12-21 07:32:10,298 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [313570671] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-21 07:32:10,298 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-21 07:32:10,298 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2023-12-21 07:32:10,298 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [633409279] [2023-12-21 07:32:10,298 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-21 07:32:10,298 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-12-21 07:32:10,298 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:32:10,299 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-12-21 07:32:10,299 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=251, Unknown=1, NotChecked=0, Total=306 [2023-12-21 07:32:10,299 INFO L87 Difference]: Start difference. First operand 256 states and 286 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, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2023-12-21 07:32:11,219 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:32:11,219 INFO L93 Difference]: Finished difference Result 258 states and 287 transitions. [2023-12-21 07:32:11,219 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-12-21 07:32:11,220 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, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 70 [2023-12-21 07:32:11,220 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:32:11,221 INFO L225 Difference]: With dead ends: 258 [2023-12-21 07:32:11,221 INFO L226 Difference]: Without dead ends: 226 [2023-12-21 07:32:11,221 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 73 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=103, Invalid=496, Unknown=1, NotChecked=0, Total=600 [2023-12-21 07:32:11,222 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 41 mSDsluCounter, 177 mSDsCounter, 0 mSdLazyCounter, 218 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 202 SdHoareTripleChecker+Invalid, 238 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 218 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-12-21 07:32:11,222 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 202 Invalid, 238 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 218 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-12-21 07:32:11,222 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 226 states. [2023-12-21 07:32:11,259 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 226 to 226. [2023-12-21 07:32:11,260 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 226 states, 153 states have (on average 1.1437908496732025) internal successors, (175), 161 states have internal predecessors, (175), 41 states have call successors, (41), 31 states have call predecessors, (41), 31 states have return successors, (39), 33 states have call predecessors, (39), 39 states have call successors, (39) [2023-12-21 07:32:11,261 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 226 states to 226 states and 255 transitions. [2023-12-21 07:32:11,261 INFO L78 Accepts]: Start accepts. Automaton has 226 states and 255 transitions. Word has length 70 [2023-12-21 07:32:11,261 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:32:11,261 INFO L495 AbstractCegarLoop]: Abstraction has 226 states and 255 transitions. [2023-12-21 07:32:11,261 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, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2023-12-21 07:32:11,261 INFO L276 IsEmpty]: Start isEmpty. Operand 226 states and 255 transitions. [2023-12-21 07:32:11,262 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2023-12-21 07:32:11,262 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:32:11,262 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:32:11,267 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-12-21 07:32:11,465 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,SelfDestructingSolverStorable13 [2023-12-21 07:32:11,465 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:32:11,466 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:32:11,466 INFO L85 PathProgramCache]: Analyzing trace with hash 1259846217, now seen corresponding path program 1 times [2023-12-21 07:32:11,466 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:32:11,466 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [11104966] [2023-12-21 07:32:11,466 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:32:11,466 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:32:11,473 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:32:11,473 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [9873441] [2023-12-21 07:32:11,473 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:32:11,473 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:32:11,473 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:32:11,474 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:32:11,493 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-12-21 07:32:11,681 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:32:11,683 INFO L262 TraceCheckSpWp]: Trace formula consists of 195 conjuncts, 13 conjunts are in the unsatisfiable core [2023-12-21 07:32:11,684 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:32:11,990 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 88 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2023-12-21 07:32:11,990 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-21 07:32:11,990 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:32:11,990 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [11104966] [2023-12-21 07:32:11,990 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:32:11,990 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [9873441] [2023-12-21 07:32:11,990 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [9873441] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:32:11,990 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:32:11,990 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-12-21 07:32:11,991 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [379706421] [2023-12-21 07:32:11,991 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:32:11,991 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-12-21 07:32:11,991 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:32:11,991 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-12-21 07:32:11,991 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2023-12-21 07:32:11,991 INFO L87 Difference]: Start difference. First operand 226 states and 255 transitions. Second operand has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2023-12-21 07:32:12,971 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:32:12,971 INFO L93 Difference]: Finished difference Result 304 states and 360 transitions. [2023-12-21 07:32:12,973 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-21 07:32:12,973 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) Word has length 82 [2023-12-21 07:32:12,974 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:32:12,975 INFO L225 Difference]: With dead ends: 304 [2023-12-21 07:32:12,975 INFO L226 Difference]: Without dead ends: 244 [2023-12-21 07:32:12,977 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 77 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2023-12-21 07:32:12,977 INFO L413 NwaCegarLoop]: 51 mSDtfsCounter, 15 mSDsluCounter, 116 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 167 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2023-12-21 07:32:12,977 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 167 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2023-12-21 07:32:12,978 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 244 states. [2023-12-21 07:32:13,028 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 244 to 222. [2023-12-21 07:32:13,028 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 222 states, 151 states have (on average 1.1390728476821192) internal successors, (172), 157 states have internal predecessors, (172), 39 states have call successors, (39), 31 states have call predecessors, (39), 31 states have return successors, (37), 33 states have call predecessors, (37), 37 states have call successors, (37) [2023-12-21 07:32:13,029 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 222 states to 222 states and 248 transitions. [2023-12-21 07:32:13,029 INFO L78 Accepts]: Start accepts. Automaton has 222 states and 248 transitions. Word has length 82 [2023-12-21 07:32:13,029 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:32:13,029 INFO L495 AbstractCegarLoop]: Abstraction has 222 states and 248 transitions. [2023-12-21 07:32:13,030 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2023-12-21 07:32:13,030 INFO L276 IsEmpty]: Start isEmpty. Operand 222 states and 248 transitions. [2023-12-21 07:32:13,034 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2023-12-21 07:32:13,034 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:32:13,034 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:32:13,043 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-12-21 07:32:13,240 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,SelfDestructingSolverStorable14 [2023-12-21 07:32:13,240 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:32:13,241 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:32:13,241 INFO L85 PathProgramCache]: Analyzing trace with hash -808682318, now seen corresponding path program 2 times [2023-12-21 07:32:13,241 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:32:13,241 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [814878675] [2023-12-21 07:32:13,241 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:32:13,241 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:32:13,251 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:32:13,252 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [522492763] [2023-12-21 07:32:13,252 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-21 07:32:13,252 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:32:13,252 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:32:13,253 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:32:13,272 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-12-21 07:32:13,330 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-21 07:32:13,331 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 07:32:13,332 INFO L262 TraceCheckSpWp]: Trace formula consists of 210 conjuncts, 10 conjunts are in the unsatisfiable core [2023-12-21 07:32:13,334 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:32:13,377 INFO L134 CoverageAnalysis]: Checked inductivity of 361 backedges. 26 proven. 23 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2023-12-21 07:32:13,377 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:32:13,459 INFO L134 CoverageAnalysis]: Checked inductivity of 361 backedges. 38 proven. 11 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2023-12-21 07:32:13,459 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:32:13,459 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [814878675] [2023-12-21 07:32:13,459 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:32:13,459 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [522492763] [2023-12-21 07:32:13,459 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [522492763] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:32:13,459 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:32:13,459 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2023-12-21 07:32:13,459 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1094192446] [2023-12-21 07:32:13,459 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:32:13,460 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-21 07:32:13,460 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:32:13,460 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-21 07:32:13,460 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2023-12-21 07:32:13,460 INFO L87 Difference]: Start difference. First operand 222 states and 248 transitions. Second operand has 8 states, 8 states have (on average 5.25) internal successors, (42), 8 states have internal predecessors, (42), 8 states have call successors, (27), 2 states have call predecessors, (27), 1 states have return successors, (26), 7 states have call predecessors, (26), 7 states have call successors, (26) [2023-12-21 07:32:15,653 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.02s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2023-12-21 07:32:19,739 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2023-12-21 07:32:19,814 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:32:19,814 INFO L93 Difference]: Finished difference Result 276 states and 328 transitions. [2023-12-21 07:32:19,814 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-12-21 07:32:19,815 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 5.25) internal successors, (42), 8 states have internal predecessors, (42), 8 states have call successors, (27), 2 states have call predecessors, (27), 1 states have return successors, (26), 7 states have call predecessors, (26), 7 states have call successors, (26) Word has length 88 [2023-12-21 07:32:19,815 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:32:19,816 INFO L225 Difference]: With dead ends: 276 [2023-12-21 07:32:19,816 INFO L226 Difference]: Without dead ends: 239 [2023-12-21 07:32:19,816 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 169 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2023-12-21 07:32:19,817 INFO L413 NwaCegarLoop]: 64 mSDtfsCounter, 20 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 86 mSolverCounterSat, 8 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 224 SdHoareTripleChecker+Invalid, 95 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 86 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.3s IncrementalHoareTripleChecker+Time [2023-12-21 07:32:19,817 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 224 Invalid, 95 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 86 Invalid, 1 Unknown, 0 Unchecked, 6.3s Time] [2023-12-21 07:32:19,818 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 239 states. [2023-12-21 07:32:19,895 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 239 to 229. [2023-12-21 07:32:19,896 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 229 states, 156 states have (on average 1.1282051282051282) internal successors, (176), 160 states have internal predecessors, (176), 43 states have call successors, (43), 29 states have call predecessors, (43), 29 states have return successors, (42), 39 states have call predecessors, (42), 42 states have call successors, (42) [2023-12-21 07:32:19,896 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 229 states to 229 states and 261 transitions. [2023-12-21 07:32:19,897 INFO L78 Accepts]: Start accepts. Automaton has 229 states and 261 transitions. Word has length 88 [2023-12-21 07:32:19,897 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:32:19,897 INFO L495 AbstractCegarLoop]: Abstraction has 229 states and 261 transitions. [2023-12-21 07:32:19,897 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 5.25) internal successors, (42), 8 states have internal predecessors, (42), 8 states have call successors, (27), 2 states have call predecessors, (27), 1 states have return successors, (26), 7 states have call predecessors, (26), 7 states have call successors, (26) [2023-12-21 07:32:19,897 INFO L276 IsEmpty]: Start isEmpty. Operand 229 states and 261 transitions. [2023-12-21 07:32:19,898 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2023-12-21 07:32:19,898 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:32:19,898 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-12-21 07:32:19,904 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-21 07:32:20,104 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:32:20,104 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:32:20,104 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:32:20,104 INFO L85 PathProgramCache]: Analyzing trace with hash 1566685696, now seen corresponding path program 3 times [2023-12-21 07:32:20,104 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:32:20,104 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [868919834] [2023-12-21 07:32:20,104 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:32:20,105 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:32:20,113 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:32:20,113 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [896738501] [2023-12-21 07:32:20,113 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-21 07:32:20,113 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:32:20,113 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:32:20,114 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:32:20,120 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2023-12-21 07:32:37,799 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2023-12-21 07:32:37,799 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2023-12-21 07:32:37,799 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-12-21 07:33:05,513 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-12-21 07:33:05,566 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-12-21 07:33:05,567 INFO L360 BasicCegarLoop]: Counterexample is feasible [2023-12-21 07:33:05,568 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-12-21 07:33:05,587 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2023-12-21 07:33:05,769 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,SelfDestructingSolverStorable16 [2023-12-21 07:33:05,772 INFO L445 BasicCegarLoop]: Path program histogram: [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:33:05,775 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2023-12-21 07:33:05,805 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 21.12 07:33:05 BoogieIcfgContainer [2023-12-21 07:33:05,805 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-12-21 07:33:05,806 INFO L158 Benchmark]: Toolchain (without parser) took 841207.73ms. Allocated memory is still 304.1MB. Free memory was 255.3MB in the beginning and 239.1MB in the end (delta: 16.2MB). Peak memory consumption was 16.8MB. Max. memory is 8.0GB. [2023-12-21 07:33:05,806 INFO L158 Benchmark]: CDTParser took 0.54ms. Allocated memory is still 197.1MB. Free memory was 148.8MB in the beginning and 148.7MB in the end (delta: 89.1kB). There was no memory consumed. Max. memory is 8.0GB. [2023-12-21 07:33:05,806 INFO L158 Benchmark]: CACSL2BoogieTranslator took 224.14ms. Allocated memory is still 304.1MB. Free memory was 255.3MB in the beginning and 244.1MB in the end (delta: 11.2MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2023-12-21 07:33:05,806 INFO L158 Benchmark]: Boogie Procedure Inliner took 26.94ms. Allocated memory is still 304.1MB. Free memory was 244.1MB in the beginning and 242.4MB in the end (delta: 1.7MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2023-12-21 07:33:05,807 INFO L158 Benchmark]: Boogie Preprocessor took 30.34ms. Allocated memory is still 304.1MB. Free memory was 242.4MB in the beginning and 240.6MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2023-12-21 07:33:05,807 INFO L158 Benchmark]: RCFGBuilder took 293.27ms. Allocated memory is still 304.1MB. Free memory was 240.6MB in the beginning and 229.1MB in the end (delta: 11.5MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2023-12-21 07:33:05,807 INFO L158 Benchmark]: TraceAbstraction took 840628.33ms. Allocated memory is still 304.1MB. Free memory was 228.3MB in the beginning and 239.1MB in the end (delta: -10.8MB). There was no memory consumed. Max. memory is 8.0GB. [2023-12-21 07:33:05,808 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.54ms. Allocated memory is still 197.1MB. Free memory was 148.8MB in the beginning and 148.7MB in the end (delta: 89.1kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 224.14ms. Allocated memory is still 304.1MB. Free memory was 255.3MB in the beginning and 244.1MB in the end (delta: 11.2MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Procedure Inliner took 26.94ms. Allocated memory is still 304.1MB. Free memory was 244.1MB in the beginning and 242.4MB in the end (delta: 1.7MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * Boogie Preprocessor took 30.34ms. Allocated memory is still 304.1MB. Free memory was 242.4MB in the beginning and 240.6MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 293.27ms. Allocated memory is still 304.1MB. Free memory was 240.6MB in the beginning and 229.1MB in the end (delta: 11.5MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * TraceAbstraction took 840628.33ms. Allocated memory is still 304.1MB. Free memory was 228.3MB in the beginning and 239.1MB in the end (delta: -10.8MB). There was no memory consumed. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 17]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L22] int counter = 0; [L24] unsigned int A, B; [L25] unsigned int r, d, p, q; [L26] A = __VERIFIER_nondet_uint() [L27] B = __VERIFIER_nondet_uint() [L28] CALL assume_abort_if_not(B >= 1) [L12] COND FALSE !(!cond) VAL [\old(cond)=1, cond=1, counter=0] [L28] RET assume_abort_if_not(B >= 1) [L30] r = A [L31] d = B [L32] p = 1 [L33] q = 0 VAL [A=107374182391, B=11811160062, counter=0, d=11811160062, p=1, q=0, r=107374182391] [L35] EXPR counter++ VAL [A=107374182391, B=11811160062, counter=1, d=11811160062, p=1, q=0, r=107374182391] [L35] COND TRUE counter++<10 [L36] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=1] [L36] RET __VERIFIER_assert(q == 0) VAL [A=107374182391, B=11811160062, counter=1, d=11811160062, p=1, q=0, r=107374182391] [L37] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=1] [L37] RET __VERIFIER_assert(r == A) VAL [A=107374182391, B=11811160062, counter=1, d=11811160062, p=1, q=0, r=107374182391] [L38] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=1] [L38] RET __VERIFIER_assert(d == B * p) VAL [A=107374182391, B=11811160062, counter=1, d=11811160062, p=1, q=0, r=107374182391] [L39] COND FALSE !(!(r >= d)) [L41] d = 2 * d [L42] p = 2 * p VAL [A=107374182391, B=11811160062, counter=1, d=23622320124, p=2, q=0, r=107374182391] [L35] EXPR counter++ VAL [A=107374182391, B=11811160062, counter=2, d=23622320124, p=2, q=0, r=107374182391] [L35] COND TRUE counter++<10 [L36] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L36] RET __VERIFIER_assert(q == 0) VAL [A=107374182391, B=11811160062, counter=2, d=23622320124, p=2, q=0, r=107374182391] [L37] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L37] RET __VERIFIER_assert(r == A) VAL [A=107374182391, B=11811160062, counter=2, d=23622320124, p=2, q=0, r=107374182391] [L38] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L38] RET __VERIFIER_assert(d == B * p) VAL [A=107374182391, B=11811160062, counter=2, d=23622320124, p=2, q=0, r=107374182391] [L39] COND FALSE !(!(r >= d)) [L41] d = 2 * d [L42] p = 2 * p VAL [A=107374182391, B=11811160062, counter=2, d=47244640248, p=4, q=0, r=107374182391] [L35] EXPR counter++ VAL [A=107374182391, B=11811160062, counter=3, d=47244640248, p=4, q=0, r=107374182391] [L35] COND TRUE counter++<10 [L36] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=3] [L36] RET __VERIFIER_assert(q == 0) VAL [A=107374182391, B=11811160062, counter=3, d=47244640248, p=4, q=0, r=107374182391] [L37] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=3] [L37] RET __VERIFIER_assert(r == A) VAL [A=107374182391, B=11811160062, counter=3, d=47244640248, p=4, q=0, r=107374182391] [L38] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=3] [L38] RET __VERIFIER_assert(d == B * p) VAL [A=107374182391, B=11811160062, counter=3, d=47244640248, p=4, q=0, r=107374182391] [L39] COND TRUE !(r >= d) VAL [A=107374182391, B=11811160062, counter=3, d=47244640248, p=4, q=0, r=107374182391] [L45] EXPR counter++ VAL [A=107374182391, B=11811160062, counter=4, d=47244640248, p=4, q=0, r=107374182391] [L45] COND TRUE counter++<10 [L46] CALL __VERIFIER_assert(A == q*B + r) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L46] RET __VERIFIER_assert(A == q*B + r) VAL [A=107374182391, B=11811160062, counter=4, d=47244640248, p=4, q=0, r=107374182391] [L47] CALL __VERIFIER_assert(d == B*p) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L47] RET __VERIFIER_assert(d == B*p) VAL [A=107374182391, B=11811160062, counter=4, d=47244640248, p=4, q=0, r=107374182391] [L49] COND FALSE !(!(p != 1)) [L51] d = d / 2 [L52] p = p / 2 VAL [A=107374182391, B=11811160062, counter=4, d=2147483644, p=2, q=0, r=107374182391] [L53] COND TRUE r >= d [L54] r = r - d [L55] q = q + p VAL [A=107374182391, B=11811160062, counter=4, d=2147483644, p=2, q=2, r=105226698747] [L45] EXPR counter++ VAL [A=107374182391, B=11811160062, counter=5, d=2147483644, p=2, q=2, r=105226698747] [L45] COND TRUE counter++<10 [L46] CALL __VERIFIER_assert(A == q*B + r) VAL [\old(cond)=1, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L46] RET __VERIFIER_assert(A == q*B + r) VAL [A=107374182391, B=11811160062, counter=5, d=2147483644, p=2, q=2, r=105226698747] [L47] CALL __VERIFIER_assert(d == B*p) VAL [\old(cond)=1, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L47] RET __VERIFIER_assert(d == B*p) VAL [A=107374182391, B=11811160062, counter=5, d=2147483644, p=2, q=2, r=105226698747] [L49] COND FALSE !(!(p != 1)) [L51] d = d / 2 [L52] p = p / 2 VAL [A=107374182391, B=11811160062, counter=5, d=1073741822, p=1, q=2, r=105226698747] [L53] COND TRUE r >= d [L54] r = r - d [L55] q = q + p VAL [A=107374182391, B=11811160062, counter=5, d=1073741822, p=1, q=3, r=104152956925] [L45] EXPR counter++ VAL [A=107374182391, B=11811160062, counter=6, d=1073741822, p=1, q=3, r=104152956925] [L45] COND TRUE counter++<10 [L46] CALL __VERIFIER_assert(A == q*B + r) VAL [\old(cond)=0, counter=6] [L15] COND TRUE !(cond) VAL [\old(cond)=0, cond=0, counter=6] [L17] reach_error() VAL [\old(cond)=0, cond=0, counter=6] - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 25 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 840.6s, OverallIterations: 17, TraceHistogramMax: 14, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 718.1s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 61 mSolverCounterUnknown, 572 SdHoareTripleChecker+Valid, 327.9s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 498 mSDsluCounter, 2553 SdHoareTripleChecker+Invalid, 327.0s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2053 mSDsCounter, 257 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1974 IncrementalHoareTripleChecker+Invalid, 2292 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 257 mSolverCounterUnsat, 500 mSDtfsCounter, 1974 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 61 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1061 GetRequests, 885 SyntacticMatches, 0 SemanticMatches, 176 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 536 ImplicationChecksByTransitivity, 448.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=256occurred in iteration=13, InterpolantAutomatonStates: 155, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.4s AutomataMinimizationTime, 16 MinimizatonAttempts, 137 StatesRemovedByMinimization, 11 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 22.2s SatisfiabilityAnalysisTime, 68.1s InterpolantComputationTime, 764 NumberOfCodeBlocks, 764 NumberOfCodeBlocksAsserted, 28 NumberOfCheckSat, 989 ConstructedInterpolants, 0 QuantifiedInterpolants, 5357 SizeOfPredicates, 42 NumberOfNonLiveVariables, 1703 ConjunctsInSsa, 234 ConjunctsInUnsatCore, 23 InterpolantComputations, 7 PerfectInterpolantSequences, 2174/2477 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 proved your program to be incorrect! [2023-12-21 07:33:06,016 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-21 07:33:06,040 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 Received shutdown request...