/usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.use.bitabs.translation true -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -i ../../../trunk/examples/svcomp/recursified_nla-digbench/recursified_divbin2.i -------------------------------------------------------------------------------- This is Ultimate 0.2.4-tmp.fs.bitabs-eval-d9c3e40-m [2023-12-20 00:16:07,081 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-20 00:16:07,150 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-20 00:16:07,154 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-20 00:16:07,154 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-20 00:16:07,175 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-20 00:16:07,175 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-20 00:16:07,175 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-20 00:16:07,176 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-12-20 00:16:07,178 INFO L153 SettingsManager]: * Use memory slicer=true [2023-12-20 00:16:07,179 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-20 00:16:07,179 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-20 00:16:07,179 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-12-20 00:16:07,180 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-12-20 00:16:07,180 INFO L153 SettingsManager]: * Use SBE=true [2023-12-20 00:16:07,180 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-20 00:16:07,181 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-20 00:16:07,181 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-20 00:16:07,181 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-20 00:16:07,181 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-20 00:16:07,181 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-20 00:16:07,181 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-20 00:16:07,182 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-20 00:16:07,182 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-20 00:16:07,182 INFO L153 SettingsManager]: * Allow undefined functions=false [2023-12-20 00:16:07,182 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-20 00:16:07,182 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-20 00:16:07,182 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-20 00:16:07,183 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-20 00:16:07,183 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-12-20 00:16:07,184 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-20 00:16:07,184 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-20 00:16:07,184 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-20 00:16:07,184 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-20 00:16:07,184 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-20 00:16:07,184 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-20 00:16:07,185 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-12-20 00:16:07,185 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-20 00:16:07,185 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-20 00:16:07,185 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-12-20 00:16:07,185 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-20 00:16:07,185 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-12-20 00:16:07,185 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-20 00:16:07,185 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Use bitabs translation -> true [2023-12-20 00:16:07,387 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-20 00:16:07,405 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-20 00:16:07,406 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-20 00:16:07,407 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-20 00:16:07,420 INFO L274 PluginConnector]: CDTParser initialized [2023-12-20 00:16:07,421 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/recursified_nla-digbench/recursified_divbin2.i [2023-12-20 00:16:08,375 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-20 00:16:08,485 INFO L384 CDTParser]: Found 1 translation units. [2023-12-20 00:16:08,486 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/recursified_nla-digbench/recursified_divbin2.i [2023-12-20 00:16:08,490 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d7b6e6564/e07077f1fe7a4f3e8c3490d568ee29d4/FLAG0fe180ad5 [2023-12-20 00:16:08,501 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d7b6e6564/e07077f1fe7a4f3e8c3490d568ee29d4 [2023-12-20 00:16:08,503 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-20 00:16:08,504 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2023-12-20 00:16:08,505 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-20 00:16:08,505 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-20 00:16:08,508 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-20 00:16:08,508 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,509 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@291cee1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08, skipping insertion in model container [2023-12-20 00:16:08,509 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,524 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-20 00:16:08,627 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/recursified_nla-digbench/recursified_divbin2.i[1567,1580] [2023-12-20 00:16:08,637 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-20 00:16:08,642 INFO L202 MainTranslator]: Completed pre-run [2023-12-20 00:16:08,649 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/recursified_nla-digbench/recursified_divbin2.i[1567,1580] [2023-12-20 00:16:08,658 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-20 00:16:08,667 INFO L206 MainTranslator]: Completed translation [2023-12-20 00:16:08,667 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08 WrapperNode [2023-12-20 00:16:08,667 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-20 00:16:08,668 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-20 00:16:08,668 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-20 00:16:08,668 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-20 00:16:08,672 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,677 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,687 INFO L138 Inliner]: procedures = 19, calls = 59, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 57 [2023-12-20 00:16:08,687 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-20 00:16:08,688 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-20 00:16:08,688 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-20 00:16:08,688 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-20 00:16:08,696 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,696 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,698 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,708 INFO L175 MemorySlicer]: Split 34 memory accesses to 6 slices as follows [2, 3, 7, 11, 7, 4]. 32 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0]. The 10 writes are split as follows [0, 1, 2, 3, 3, 1]. [2023-12-20 00:16:08,709 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,709 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,713 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,715 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,716 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,716 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,718 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-20 00:16:08,718 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-20 00:16:08,719 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-20 00:16:08,719 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-20 00:16:08,719 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08" (1/1) ... [2023-12-20 00:16:08,722 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-20 00:16:08,731 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:16:08,740 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-20 00:16:08,745 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-20 00:16:08,760 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-20 00:16:08,764 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_33_to_35_0 [2023-12-20 00:16:08,764 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_33_to_35_0 [2023-12-20 00:16:08,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-12-20 00:16:08,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2023-12-20 00:16:08,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2023-12-20 00:16:08,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2023-12-20 00:16:08,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2023-12-20 00:16:08,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2023-12-20 00:16:08,765 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-12-20 00:16:08,765 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2023-12-20 00:16:08,765 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2023-12-20 00:16:08,765 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2023-12-20 00:16:08,765 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2023-12-20 00:16:08,765 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2023-12-20 00:16:08,765 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2023-12-20 00:16:08,765 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_37_to_44_0 [2023-12-20 00:16:08,765 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_37_to_44_0 [2023-12-20 00:16:08,765 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-20 00:16:08,765 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-20 00:16:08,766 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2023-12-20 00:16:08,766 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2023-12-20 00:16:08,766 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2023-12-20 00:16:08,766 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2023-12-20 00:16:08,767 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2023-12-20 00:16:08,767 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2023-12-20 00:16:08,767 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-12-20 00:16:08,767 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-12-20 00:16:08,767 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-12-20 00:16:08,847 INFO L241 CfgBuilder]: Building ICFG [2023-12-20 00:16:08,848 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-20 00:16:08,978 INFO L282 CfgBuilder]: Performing block encoding [2023-12-20 00:16:08,997 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-20 00:16:08,997 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-12-20 00:16:08,998 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.12 12:16:08 BoogieIcfgContainer [2023-12-20 00:16:08,998 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-20 00:16:08,999 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-20 00:16:08,999 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-20 00:16:09,001 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-20 00:16:09,001 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.12 12:16:08" (1/3) ... [2023-12-20 00:16:09,002 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@27e2507e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.12 12:16:09, skipping insertion in model container [2023-12-20 00:16:09,002 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.12 12:16:08" (2/3) ... [2023-12-20 00:16:09,002 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@27e2507e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.12 12:16:09, skipping insertion in model container [2023-12-20 00:16:09,002 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.12 12:16:08" (3/3) ... [2023-12-20 00:16:09,035 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_divbin2.i [2023-12-20 00:16:09,046 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-20 00:16:09,046 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-20 00:16:09,074 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-20 00:16:09,078 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;@21f11741, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-20 00:16:09,078 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-20 00:16:09,080 INFO L276 IsEmpty]: Start isEmpty. Operand has 28 states, 17 states have (on average 1.411764705882353) internal successors, (24), 20 states have internal predecessors, (24), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-20 00:16:09,085 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2023-12-20 00:16:09,085 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:16:09,085 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:16:09,085 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:16:09,088 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:16:09,089 INFO L85 PathProgramCache]: Analyzing trace with hash 2028572640, now seen corresponding path program 1 times [2023-12-20 00:16:09,094 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:16:09,095 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1424483847] [2023-12-20 00:16:09,095 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:16:09,095 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:16:09,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-20 00:16:09,247 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:16:09,247 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1424483847] [2023-12-20 00:16:09,247 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-20 00:16:09,247 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1950345838] [2023-12-20 00:16:09,247 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:16:09,248 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:16:09,248 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:16:09,253 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-20 00:16:09,264 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-20 00:16:09,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-20 00:16:09,397 INFO L262 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 1 conjunts are in the unsatisfiable core [2023-12-20 00:16:09,402 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:16:09,421 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-20 00:16:09,421 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-20 00:16:09,421 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1950345838] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-20 00:16:09,421 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-20 00:16:09,422 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-20 00:16:09,423 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1515422681] [2023-12-20 00:16:09,426 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-20 00:16:09,428 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-12-20 00:16:09,428 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:16:09,457 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-12-20 00:16:09,457 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-20 00:16:09,459 INFO L87 Difference]: Start difference. First operand has 28 states, 17 states have (on average 1.411764705882353) internal successors, (24), 20 states have internal predecessors, (24), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-20 00:16:09,481 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:16:09,481 INFO L93 Difference]: Finished difference Result 50 states and 68 transitions. [2023-12-20 00:16:09,482 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-12-20 00:16:09,483 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 13 [2023-12-20 00:16:09,484 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:16:09,487 INFO L225 Difference]: With dead ends: 50 [2023-12-20 00:16:09,487 INFO L226 Difference]: Without dead ends: 26 [2023-12-20 00:16:09,489 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 12 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-20 00:16:09,491 INFO L413 NwaCegarLoop]: 31 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, 31 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-20 00:16:09,493 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 31 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-20 00:16:09,503 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2023-12-20 00:16:09,512 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2023-12-20 00:16:09,513 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.25) internal successors, (20), 19 states have internal predecessors, (20), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-12-20 00:16:09,514 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 31 transitions. [2023-12-20 00:16:09,514 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 31 transitions. Word has length 13 [2023-12-20 00:16:09,515 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:16:09,515 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 31 transitions. [2023-12-20 00:16:09,515 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-20 00:16:09,515 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 31 transitions. [2023-12-20 00:16:09,516 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2023-12-20 00:16:09,516 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:16:09,516 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:16:09,521 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-12-20 00:16:09,718 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-20 00:16:09,719 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:16:09,719 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:16:09,720 INFO L85 PathProgramCache]: Analyzing trace with hash 1765858941, now seen corresponding path program 1 times [2023-12-20 00:16:09,720 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:16:09,720 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [517316320] [2023-12-20 00:16:09,720 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:16:09,720 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:16:09,771 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:16:09,771 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [475672780] [2023-12-20 00:16:09,771 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:16:09,771 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:16:09,771 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:16:09,774 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-20 00:16:09,786 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-20 00:16:09,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-20 00:16:09,984 INFO L262 TraceCheckSpWp]: Trace formula consists of 177 conjuncts, 83 conjunts are in the unsatisfiable core [2023-12-20 00:16:09,994 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:16:10,065 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:16:10,079 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:16:10,085 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:16:10,089 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:16:10,542 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:16:10,542 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 26 [2023-12-20 00:16:10,551 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:16:10,552 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 40 treesize of output 28 [2023-12-20 00:16:10,610 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-20 00:16:10,610 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-20 00:16:10,611 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:16:10,611 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [517316320] [2023-12-20 00:16:10,611 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:16:10,611 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [475672780] [2023-12-20 00:16:10,611 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [475672780] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-20 00:16:10,611 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-20 00:16:10,612 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2023-12-20 00:16:10,612 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1310677151] [2023-12-20 00:16:10,612 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-20 00:16:10,612 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-12-20 00:16:10,612 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:16:10,613 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-12-20 00:16:10,614 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=130, Unknown=0, NotChecked=0, Total=156 [2023-12-20 00:16:10,614 INFO L87 Difference]: Start difference. First operand 26 states and 31 transitions. Second operand has 13 states, 10 states have (on average 1.0) internal successors, (10), 8 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-20 00:16:11,240 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:16:11,240 INFO L93 Difference]: Finished difference Result 57 states and 68 transitions. [2023-12-20 00:16:11,241 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-12-20 00:16:11,241 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 1.0) internal successors, (10), 8 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2023-12-20 00:16:11,241 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:16:11,243 INFO L225 Difference]: With dead ends: 57 [2023-12-20 00:16:11,243 INFO L226 Difference]: Without dead ends: 53 [2023-12-20 00:16:11,244 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=74, Invalid=388, Unknown=0, NotChecked=0, Total=462 [2023-12-20 00:16:11,244 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 35 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 273 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 288 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 273 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-20 00:16:11,245 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 123 Invalid, 288 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 273 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-20 00:16:11,245 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2023-12-20 00:16:11,254 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 51. [2023-12-20 00:16:11,255 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 33 states have (on average 1.2121212121212122) internal successors, (40), 36 states have internal predecessors, (40), 10 states have call successors, (10), 7 states have call predecessors, (10), 7 states have return successors, (13), 9 states have call predecessors, (13), 8 states have call successors, (13) [2023-12-20 00:16:11,256 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 63 transitions. [2023-12-20 00:16:11,256 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 63 transitions. Word has length 14 [2023-12-20 00:16:11,256 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:16:11,256 INFO L495 AbstractCegarLoop]: Abstraction has 51 states and 63 transitions. [2023-12-20 00:16:11,256 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 1.0) internal successors, (10), 8 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-20 00:16:11,256 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 63 transitions. [2023-12-20 00:16:11,257 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2023-12-20 00:16:11,257 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:16:11,257 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:16:11,274 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-12-20 00:16:11,458 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2023-12-20 00:16:11,458 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:16:11,458 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:16:11,459 INFO L85 PathProgramCache]: Analyzing trace with hash 1425184068, now seen corresponding path program 1 times [2023-12-20 00:16:11,459 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:16:11,459 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [101072729] [2023-12-20 00:16:11,459 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:16:11,459 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:16:11,500 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:16:11,501 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1864639818] [2023-12-20 00:16:11,501 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:16:11,501 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:16:11,501 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:16:11,502 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-20 00:16:11,532 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-20 00:16:11,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-20 00:16:11,685 INFO L262 TraceCheckSpWp]: Trace formula consists of 206 conjuncts, 62 conjunts are in the unsatisfiable core [2023-12-20 00:16:11,687 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:16:11,695 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:16:11,700 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:16:11,702 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:16:11,846 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:16:11,849 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-12-20 00:16:11,874 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-20 00:16:11,874 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-20 00:16:12,085 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:16:12,085 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [101072729] [2023-12-20 00:16:12,085 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:16:12,085 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1864639818] [2023-12-20 00:16:12,085 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1864639818] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-20 00:16:12,086 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-20 00:16:12,086 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2023-12-20 00:16:12,087 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1755004697] [2023-12-20 00:16:12,087 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-20 00:16:12,087 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-12-20 00:16:12,090 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:16:12,090 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-12-20 00:16:12,090 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=201, Unknown=0, NotChecked=0, Total=240 [2023-12-20 00:16:12,091 INFO L87 Difference]: Start difference. First operand 51 states and 63 transitions. Second operand has 10 states, 8 states have (on average 1.625) internal successors, (13), 7 states have internal predecessors, (13), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-20 00:16:12,312 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:16:12,312 INFO L93 Difference]: Finished difference Result 80 states and 99 transitions. [2023-12-20 00:16:12,312 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-20 00:16:12,312 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 1.625) internal successors, (13), 7 states have internal predecessors, (13), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2023-12-20 00:16:12,313 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:16:12,313 INFO L225 Difference]: With dead ends: 80 [2023-12-20 00:16:12,313 INFO L226 Difference]: Without dead ends: 76 [2023-12-20 00:16:12,314 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 12 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 58 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=69, Invalid=311, Unknown=0, NotChecked=0, Total=380 [2023-12-20 00:16:12,314 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 37 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 138 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 138 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-20 00:16:12,315 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 126 Invalid, 152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 138 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-20 00:16:12,315 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2023-12-20 00:16:12,322 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 48. [2023-12-20 00:16:12,322 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 9 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (10), 8 states have call predecessors, (10), 7 states have call successors, (10) [2023-12-20 00:16:12,322 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 58 transitions. [2023-12-20 00:16:12,323 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 58 transitions. Word has length 20 [2023-12-20 00:16:12,323 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:16:12,323 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 58 transitions. [2023-12-20 00:16:12,323 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 1.625) internal successors, (13), 7 states have internal predecessors, (13), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-20 00:16:12,323 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 58 transitions. [2023-12-20 00:16:12,323 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2023-12-20 00:16:12,323 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:16:12,323 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:16:12,335 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-20 00:16:12,529 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:16:12,529 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:16:12,530 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:16:12,530 INFO L85 PathProgramCache]: Analyzing trace with hash 1894831411, now seen corresponding path program 1 times [2023-12-20 00:16:12,530 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:16:12,530 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [542364263] [2023-12-20 00:16:12,530 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:16:12,530 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:16:12,553 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:16:12,553 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1530566624] [2023-12-20 00:16:12,553 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:16:12,553 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:16:12,553 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:16:12,562 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-20 00:16:12,564 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-20 00:16:12,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-20 00:16:12,738 INFO L262 TraceCheckSpWp]: Trace formula consists of 202 conjuncts, 60 conjunts are in the unsatisfiable core [2023-12-20 00:16:12,741 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:16:12,749 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:16:12,756 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:16:12,764 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:16:12,908 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:16:12,909 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 32 treesize of output 28 [2023-12-20 00:16:13,044 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:16:13,045 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 30 [2023-12-20 00:16:13,051 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:16:13,051 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 40 treesize of output 32 [2023-12-20 00:16:13,092 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-20 00:16:13,093 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-20 00:16:13,240 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:16:13,240 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [542364263] [2023-12-20 00:16:13,240 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:16:13,240 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1530566624] [2023-12-20 00:16:13,240 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1530566624] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-20 00:16:13,240 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-20 00:16:13,241 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2023-12-20 00:16:13,241 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1236425353] [2023-12-20 00:16:13,241 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-20 00:16:13,241 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-12-20 00:16:13,241 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:16:13,242 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-12-20 00:16:13,242 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=294, Unknown=0, NotChecked=0, Total=342 [2023-12-20 00:16:13,242 INFO L87 Difference]: Start difference. First operand 48 states and 58 transitions. Second operand has 15 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 10 states have internal predecessors, (17), 4 states have call successors, (4), 4 states have call predecessors, (4), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2023-12-20 00:16:13,907 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:16:13,908 INFO L93 Difference]: Finished difference Result 104 states and 121 transitions. [2023-12-20 00:16:13,908 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2023-12-20 00:16:13,908 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 10 states have internal predecessors, (17), 4 states have call successors, (4), 4 states have call predecessors, (4), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Word has length 24 [2023-12-20 00:16:13,908 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:16:13,909 INFO L225 Difference]: With dead ends: 104 [2023-12-20 00:16:13,909 INFO L226 Difference]: Without dead ends: 96 [2023-12-20 00:16:13,910 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 11 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 133 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=139, Invalid=731, Unknown=0, NotChecked=0, Total=870 [2023-12-20 00:16:13,910 INFO L413 NwaCegarLoop]: 15 mSDtfsCounter, 37 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 286 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 298 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 286 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-12-20 00:16:13,910 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 153 Invalid, 298 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 286 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-12-20 00:16:13,911 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2023-12-20 00:16:13,923 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 90. [2023-12-20 00:16:13,923 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 60 states have (on average 1.2) internal successors, (72), 64 states have internal predecessors, (72), 16 states have call successors, (16), 13 states have call predecessors, (16), 13 states have return successors, (20), 15 states have call predecessors, (20), 13 states have call successors, (20) [2023-12-20 00:16:13,924 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 108 transitions. [2023-12-20 00:16:13,924 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 108 transitions. Word has length 24 [2023-12-20 00:16:13,924 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:16:13,924 INFO L495 AbstractCegarLoop]: Abstraction has 90 states and 108 transitions. [2023-12-20 00:16:13,925 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 10 states have internal predecessors, (17), 4 states have call successors, (4), 4 states have call predecessors, (4), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2023-12-20 00:16:13,925 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 108 transitions. [2023-12-20 00:16:13,925 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2023-12-20 00:16:13,925 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:16:13,925 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:16:13,932 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-12-20 00:16:14,127 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:16:14,127 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:16:14,128 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:16:14,128 INFO L85 PathProgramCache]: Analyzing trace with hash -892537059, now seen corresponding path program 1 times [2023-12-20 00:16:14,128 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:16:14,128 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1842784300] [2023-12-20 00:16:14,128 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:16:14,128 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:16:14,143 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:16:14,143 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [427346071] [2023-12-20 00:16:14,143 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:16:14,143 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:16:14,143 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:16:14,144 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-20 00:16:14,170 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-20 00:16:14,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-20 00:16:14,236 INFO L262 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 39 conjunts are in the unsatisfiable core [2023-12-20 00:16:14,238 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:16:14,243 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:16:14,245 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:16:14,254 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:16:18,299 WARN L876 $PredicateComparison]: unable to prove that (exists ((v_func_to_recursive_line_37_to_44_0_~B.base_BEFORE_CALL_1 Int) (v_func_to_recursive_line_37_to_44_0_~b.base_BEFORE_CALL_1 Int)) (= (select (select |c_#memory_int#1| v_func_to_recursive_line_37_to_44_0_~B.base_BEFORE_CALL_1) 0) (select (select |c_#memory_int#3| v_func_to_recursive_line_37_to_44_0_~b.base_BEFORE_CALL_1) 0))) is different from true [2023-12-20 00:16:18,333 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:16:18,335 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-12-20 00:16:18,342 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-20 00:16:18,342 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-20 00:16:18,342 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:16:18,342 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1842784300] [2023-12-20 00:16:18,342 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:16:18,342 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [427346071] [2023-12-20 00:16:18,342 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [427346071] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-20 00:16:18,342 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-20 00:16:18,343 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2023-12-20 00:16:18,343 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1223626110] [2023-12-20 00:16:18,343 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-20 00:16:18,343 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-20 00:16:18,343 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:16:18,343 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-20 00:16:18,344 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=32, Unknown=1, NotChecked=10, Total=56 [2023-12-20 00:16:18,344 INFO L87 Difference]: Start difference. First operand 90 states and 108 transitions. Second operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-20 00:16:18,494 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:16:18,494 INFO L93 Difference]: Finished difference Result 102 states and 120 transitions. [2023-12-20 00:16:18,494 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-12-20 00:16:18,495 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 25 [2023-12-20 00:16:18,495 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:16:18,495 INFO L225 Difference]: With dead ends: 102 [2023-12-20 00:16:18,495 INFO L226 Difference]: Without dead ends: 52 [2023-12-20 00:16:18,496 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=37, Invalid=76, Unknown=1, NotChecked=18, Total=132 [2023-12-20 00:16:18,496 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 20 mSDsluCounter, 45 mSDsCounter, 0 mSdLazyCounter, 104 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 62 SdHoareTripleChecker+Invalid, 155 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 104 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 42 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-20 00:16:18,496 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 62 Invalid, 155 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 104 Invalid, 0 Unknown, 42 Unchecked, 0.1s Time] [2023-12-20 00:16:18,497 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2023-12-20 00:16:18,502 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 50. [2023-12-20 00:16:18,503 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 33 states have (on average 1.1818181818181819) internal successors, (39), 35 states have internal predecessors, (39), 9 states have call successors, (9), 7 states have call predecessors, (9), 7 states have return successors, (11), 8 states have call predecessors, (11), 7 states have call successors, (11) [2023-12-20 00:16:18,503 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 59 transitions. [2023-12-20 00:16:18,503 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 59 transitions. Word has length 25 [2023-12-20 00:16:18,503 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:16:18,503 INFO L495 AbstractCegarLoop]: Abstraction has 50 states and 59 transitions. [2023-12-20 00:16:18,503 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-12-20 00:16:18,503 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 59 transitions. [2023-12-20 00:16:18,504 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2023-12-20 00:16:18,504 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:16:18,504 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:16:18,532 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-20 00:16:18,710 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:16:18,710 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:16:18,710 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:16:18,711 INFO L85 PathProgramCache]: Analyzing trace with hash -2009202886, now seen corresponding path program 1 times [2023-12-20 00:16:18,711 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:16:18,711 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1351778914] [2023-12-20 00:16:18,711 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:16:18,711 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:16:18,727 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:16:18,727 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2036604165] [2023-12-20 00:16:18,727 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:16:18,727 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:16:18,727 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:16:18,733 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-20 00:16:18,734 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-20 00:16:18,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-20 00:16:18,834 INFO L262 TraceCheckSpWp]: Trace formula consists of 231 conjuncts, 89 conjunts are in the unsatisfiable core [2023-12-20 00:16:18,839 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:16:18,847 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:16:18,854 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:16:18,860 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:16:18,875 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:16:19,001 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 11 [2023-12-20 00:16:19,161 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:16:19,162 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 55 treesize of output 47 [2023-12-20 00:16:19,173 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 42 treesize of output 19 [2023-12-20 00:16:19,206 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 13 [2023-12-20 00:16:49,137 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2023-12-20 00:16:49,138 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 46 treesize of output 34 [2023-12-20 00:16:49,140 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-12-20 00:16:49,140 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-20 00:17:02,135 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:17:02,135 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1351778914] [2023-12-20 00:17:02,135 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:17:02,135 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2036604165] [2023-12-20 00:17:02,135 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2036604165] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-20 00:17:02,135 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-20 00:17:02,135 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2023-12-20 00:17:02,135 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [519670137] [2023-12-20 00:17:02,135 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-20 00:17:02,135 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-12-20 00:17:02,135 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:17:02,136 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-12-20 00:17:02,136 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=457, Unknown=10, NotChecked=0, Total=552 [2023-12-20 00:17:02,136 INFO L87 Difference]: Start difference. First operand 50 states and 59 transitions. Second operand has 16 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 12 states have internal predecessors, (20), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-12-20 00:17:06,158 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:17:07,630 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.44s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:17:11,952 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:17:15,975 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:17:19,998 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:17:21,789 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.76s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:17:25,932 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:17:34,015 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:17:38,074 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:17:42,131 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:17:46,142 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:17:50,156 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-20 00:17:54,174 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:17:58,189 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:18:02,202 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:18:06,220 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:18:14,293 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:18:22,365 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:18:26,386 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:18:30,401 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:18:34,413 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:18:38,467 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-20 00:18:38,476 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:18:38,476 INFO L93 Difference]: Finished difference Result 58 states and 67 transitions. [2023-12-20 00:18:38,495 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-12-20 00:18:38,495 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 12 states have internal predecessors, (20), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 30 [2023-12-20 00:18:38,496 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:18:38,496 INFO L225 Difference]: With dead ends: 58 [2023-12-20 00:18:38,496 INFO L226 Difference]: Without dead ends: 52 [2023-12-20 00:18:38,497 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 151 ImplicationChecksByTransitivity, 54.6s TimeCoverageRelationStatistics Valid=117, Invalid=626, Unknown=13, NotChecked=0, Total=756 [2023-12-20 00:18:38,497 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 18 mSDsluCounter, 43 mSDsCounter, 0 mSdLazyCounter, 268 mSolverCounterSat, 6 mSolverCounterUnsat, 20 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 83.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 294 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 268 IncrementalHoareTripleChecker+Invalid, 20 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 84.1s IncrementalHoareTripleChecker+Time [2023-12-20 00:18:38,498 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 56 Invalid, 294 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 268 Invalid, 20 Unknown, 0 Unchecked, 84.1s Time] [2023-12-20 00:18:38,498 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2023-12-20 00:18:38,503 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2023-12-20 00:18:38,503 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 34 states have (on average 1.1764705882352942) internal successors, (40), 36 states have internal predecessors, (40), 9 states have call successors, (9), 7 states have call predecessors, (9), 8 states have return successors, (12), 8 states have call predecessors, (12), 7 states have call successors, (12) [2023-12-20 00:18:38,504 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 61 transitions. [2023-12-20 00:18:38,504 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 61 transitions. Word has length 30 [2023-12-20 00:18:38,504 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:18:38,504 INFO L495 AbstractCegarLoop]: Abstraction has 52 states and 61 transitions. [2023-12-20 00:18:38,504 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 12 states have internal predecessors, (20), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-12-20 00:18:38,504 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 61 transitions. [2023-12-20 00:18:38,504 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2023-12-20 00:18:38,504 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:18:38,505 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:18:38,514 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-20 00:18:38,705 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:18:38,705 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:18:38,706 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:18:38,706 INFO L85 PathProgramCache]: Analyzing trace with hash -1658515978, now seen corresponding path program 1 times [2023-12-20 00:18:38,706 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:18:38,706 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1198809396] [2023-12-20 00:18:38,706 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:18:38,706 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:18:38,719 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:18:38,719 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1155341123] [2023-12-20 00:18:38,719 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:18:38,719 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:18:38,719 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:18:38,732 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-20 00:18:38,733 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-20 00:18:38,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-20 00:18:38,858 WARN L260 TraceCheckSpWp]: Trace formula consists of 295 conjuncts, 180 conjunts are in the unsatisfiable core [2023-12-20 00:18:38,862 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:18:38,869 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:18:38,874 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:18:38,879 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:18:38,886 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:18:39,154 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:18:39,719 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:18:39,741 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2023-12-20 00:18:39,742 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 21 [2023-12-20 00:18:39,834 INFO L349 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2023-12-20 00:18:39,835 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 25 [2023-12-20 00:18:39,861 INFO L349 Elim1Store]: treesize reduction 14, result has 58.8 percent of original size [2023-12-20 00:18:39,861 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 49 treesize of output 48 [2023-12-20 00:18:40,171 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:18:40,172 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 81 treesize of output 93 [2023-12-20 00:18:40,189 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:18:40,189 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 44 treesize of output 52 [2023-12-20 00:18:40,369 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-12-20 00:18:40,369 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-20 00:19:01,235 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:19:01,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1198809396] [2023-12-20 00:19:01,236 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:19:01,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1155341123] [2023-12-20 00:19:01,236 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1155341123] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-20 00:19:01,236 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-20 00:19:01,236 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2023-12-20 00:19:01,236 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2134569797] [2023-12-20 00:19:01,236 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-20 00:19:01,236 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-12-20 00:19:01,236 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:19:01,237 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-12-20 00:19:01,237 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=961, Unknown=3, NotChecked=0, Total=1056 [2023-12-20 00:19:01,237 INFO L87 Difference]: Start difference. First operand 52 states and 61 transitions. Second operand has 22 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 15 states have internal predecessors, (21), 6 states have call successors, (6), 5 states have call predecessors, (6), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-12-20 00:19:15,641 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:19:15,641 INFO L93 Difference]: Finished difference Result 95 states and 113 transitions. [2023-12-20 00:19:15,642 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2023-12-20 00:19:15,642 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 15 states have internal predecessors, (21), 6 states have call successors, (6), 5 states have call predecessors, (6), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 31 [2023-12-20 00:19:15,642 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:19:15,643 INFO L225 Difference]: With dead ends: 95 [2023-12-20 00:19:15,643 INFO L226 Difference]: Without dead ends: 91 [2023-12-20 00:19:15,643 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 20 SyntacticMatches, 1 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 306 ImplicationChecksByTransitivity, 33.9s TimeCoverageRelationStatistics Valid=181, Invalid=1794, Unknown=5, NotChecked=0, Total=1980 [2023-12-20 00:19:15,644 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 46 mSDsluCounter, 166 mSDsCounter, 0 mSdLazyCounter, 509 mSolverCounterSat, 12 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 526 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 509 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2023-12-20 00:19:15,644 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 186 Invalid, 526 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 509 Invalid, 5 Unknown, 0 Unchecked, 1.0s Time] [2023-12-20 00:19:15,644 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2023-12-20 00:19:15,659 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 79. [2023-12-20 00:19:15,659 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 52 states have (on average 1.1538461538461537) internal successors, (60), 54 states have internal predecessors, (60), 13 states have call successors, (13), 11 states have call predecessors, (13), 13 states have return successors, (21), 13 states have call predecessors, (21), 11 states have call successors, (21) [2023-12-20 00:19:15,661 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 94 transitions. [2023-12-20 00:19:15,661 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 94 transitions. Word has length 31 [2023-12-20 00:19:15,661 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:19:15,661 INFO L495 AbstractCegarLoop]: Abstraction has 79 states and 94 transitions. [2023-12-20 00:19:15,661 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 15 states have internal predecessors, (21), 6 states have call successors, (6), 5 states have call predecessors, (6), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-12-20 00:19:15,661 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 94 transitions. [2023-12-20 00:19:15,662 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2023-12-20 00:19:15,662 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:19:15,662 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:19:15,670 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-20 00:19:15,862 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:19:15,863 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:19:15,863 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:19:15,863 INFO L85 PathProgramCache]: Analyzing trace with hash -642817649, now seen corresponding path program 2 times [2023-12-20 00:19:15,863 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:19:15,863 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1520160683] [2023-12-20 00:19:15,863 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:19:15,864 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:19:15,877 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:19:15,877 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [360757084] [2023-12-20 00:19:15,878 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-20 00:19:15,878 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:19:15,878 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:19:15,896 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-20 00:19:15,908 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-20 00:19:16,191 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-20 00:19:16,192 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-20 00:19:16,195 WARN L260 TraceCheckSpWp]: Trace formula consists of 324 conjuncts, 203 conjunts are in the unsatisfiable core [2023-12-20 00:19:16,199 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:19:16,205 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:19:16,211 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:19:16,216 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:19:16,221 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:19:16,441 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:19:16,710 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:19:17,787 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 3 [2023-12-20 00:19:17,796 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2023-12-20 00:19:17,797 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 21 [2023-12-20 00:19:17,868 INFO L349 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2023-12-20 00:19:17,868 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 25 [2023-12-20 00:19:17,891 INFO L349 Elim1Store]: treesize reduction 18, result has 52.6 percent of original size [2023-12-20 00:19:17,891 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 64 treesize of output 57 [2023-12-20 00:19:18,249 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:19:18,249 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 118 treesize of output 110 [2023-12-20 00:19:18,273 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:19:18,273 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 118 treesize of output 118 [2023-12-20 00:19:18,294 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 112 treesize of output 76 [2023-12-20 00:19:18,437 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 2 proven. 13 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-12-20 00:19:18,437 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-20 00:19:24,379 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:19:24,379 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1520160683] [2023-12-20 00:19:24,379 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:19:24,379 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [360757084] [2023-12-20 00:19:24,379 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [360757084] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-20 00:19:24,379 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-20 00:19:24,379 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2023-12-20 00:19:24,379 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1048996802] [2023-12-20 00:19:24,379 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-20 00:19:24,380 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2023-12-20 00:19:24,380 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:19:24,380 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2023-12-20 00:19:24,380 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=842, Unknown=0, NotChecked=0, Total=930 [2023-12-20 00:19:24,381 INFO L87 Difference]: Start difference. First operand 79 states and 94 transitions. Second operand has 25 states, 19 states have (on average 1.263157894736842) internal successors, (24), 18 states have internal predecessors, (24), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-12-20 00:19:27,184 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:19:27,184 INFO L93 Difference]: Finished difference Result 122 states and 146 transitions. [2023-12-20 00:19:27,184 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2023-12-20 00:19:27,185 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 19 states have (on average 1.263157894736842) internal successors, (24), 18 states have internal predecessors, (24), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 37 [2023-12-20 00:19:27,185 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:19:27,186 INFO L225 Difference]: With dead ends: 122 [2023-12-20 00:19:27,186 INFO L226 Difference]: Without dead ends: 118 [2023-12-20 00:19:27,186 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 16 SyntacticMatches, 2 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 341 ImplicationChecksByTransitivity, 8.0s TimeCoverageRelationStatistics Valid=172, Invalid=1550, Unknown=0, NotChecked=0, Total=1722 [2023-12-20 00:19:27,187 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 45 mSDsluCounter, 317 mSDsCounter, 0 mSdLazyCounter, 678 mSolverCounterSat, 13 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 353 SdHoareTripleChecker+Invalid, 693 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 678 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2023-12-20 00:19:27,187 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 353 Invalid, 693 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 678 Invalid, 2 Unknown, 0 Unchecked, 1.7s Time] [2023-12-20 00:19:27,187 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2023-12-20 00:19:27,203 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 81. [2023-12-20 00:19:27,204 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 53 states have (on average 1.150943396226415) internal successors, (61), 55 states have internal predecessors, (61), 13 states have call successors, (13), 11 states have call predecessors, (13), 14 states have return successors, (23), 14 states have call predecessors, (23), 11 states have call successors, (23) [2023-12-20 00:19:27,204 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 97 transitions. [2023-12-20 00:19:27,204 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 97 transitions. Word has length 37 [2023-12-20 00:19:27,204 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:19:27,204 INFO L495 AbstractCegarLoop]: Abstraction has 81 states and 97 transitions. [2023-12-20 00:19:27,204 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 19 states have (on average 1.263157894736842) internal successors, (24), 18 states have internal predecessors, (24), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-12-20 00:19:27,205 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 97 transitions. [2023-12-20 00:19:27,205 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-12-20 00:19:27,205 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:19:27,205 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:19:27,213 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-20 00:19:27,406 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-12-20 00:19:27,406 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:19:27,407 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:19:27,407 INFO L85 PathProgramCache]: Analyzing trace with hash 48792040, now seen corresponding path program 3 times [2023-12-20 00:19:27,407 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:19:27,407 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2040637819] [2023-12-20 00:19:27,407 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:19:27,407 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:19:27,422 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:19:27,422 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [700740234] [2023-12-20 00:19:27,422 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-20 00:19:27,422 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:19:27,422 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:19:27,423 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-20 00:19:27,437 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-20 00:19:27,845 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-12-20 00:19:27,845 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-20 00:19:27,848 INFO L262 TraceCheckSpWp]: Trace formula consists of 295 conjuncts, 104 conjunts are in the unsatisfiable core [2023-12-20 00:19:27,851 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:19:27,857 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:19:27,861 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:19:27,865 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:19:28,054 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:19:28,058 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:19:28,066 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:19:28,070 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 21 [2023-12-20 00:19:28,135 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 17 [2023-12-20 00:19:28,138 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2023-12-20 00:19:28,139 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2023-12-20 00:19:28,169 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2023-12-20 00:19:28,169 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-20 00:19:28,841 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:19:28,841 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2040637819] [2023-12-20 00:19:28,841 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:19:28,841 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [700740234] [2023-12-20 00:19:28,841 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [700740234] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-20 00:19:28,841 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-20 00:19:28,841 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2023-12-20 00:19:28,842 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [289379007] [2023-12-20 00:19:28,842 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-20 00:19:28,842 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-12-20 00:19:28,842 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:19:28,842 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-12-20 00:19:28,842 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=230, Unknown=0, NotChecked=0, Total=272 [2023-12-20 00:19:28,842 INFO L87 Difference]: Start difference. First operand 81 states and 97 transitions. Second operand has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (6), 4 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-12-20 00:19:29,304 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:19:29,304 INFO L93 Difference]: Finished difference Result 101 states and 121 transitions. [2023-12-20 00:19:29,304 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-12-20 00:19:29,305 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (6), 4 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 43 [2023-12-20 00:19:29,305 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:19:29,306 INFO L225 Difference]: With dead ends: 101 [2023-12-20 00:19:29,306 INFO L226 Difference]: Without dead ends: 99 [2023-12-20 00:19:29,307 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 35 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=71, Invalid=349, Unknown=0, NotChecked=0, Total=420 [2023-12-20 00:19:29,308 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 32 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 243 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 253 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 243 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-20 00:19:29,308 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 193 Invalid, 253 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 243 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-20 00:19:29,310 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2023-12-20 00:19:29,329 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 95. [2023-12-20 00:19:29,329 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 62 states have (on average 1.1451612903225807) internal successors, (71), 65 states have internal predecessors, (71), 15 states have call successors, (15), 13 states have call predecessors, (15), 17 states have return successors, (28), 16 states have call predecessors, (28), 13 states have call successors, (28) [2023-12-20 00:19:29,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 114 transitions. [2023-12-20 00:19:29,331 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 114 transitions. Word has length 43 [2023-12-20 00:19:29,332 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:19:29,332 INFO L495 AbstractCegarLoop]: Abstraction has 95 states and 114 transitions. [2023-12-20 00:19:29,332 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (6), 4 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-12-20 00:19:29,332 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 114 transitions. [2023-12-20 00:19:29,340 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-12-20 00:19:29,340 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:19:29,340 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:19:29,346 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-20 00:19:29,546 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:19:29,546 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:19:29,546 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:19:29,546 INFO L85 PathProgramCache]: Analyzing trace with hash 812410990, now seen corresponding path program 1 times [2023-12-20 00:19:29,546 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:19:29,547 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1936570376] [2023-12-20 00:19:29,547 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:19:29,547 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:19:29,561 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:19:29,561 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1164522191] [2023-12-20 00:19:29,561 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:19:29,561 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:19:29,561 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:19:29,562 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-20 00:19:29,585 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-20 00:19:29,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-20 00:19:29,672 INFO L262 TraceCheckSpWp]: Trace formula consists of 314 conjuncts, 95 conjunts are in the unsatisfiable core [2023-12-20 00:19:29,675 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:19:29,680 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:19:29,685 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:19:29,691 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:19:29,703 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:19:29,772 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:19:33,779 WARN L876 $PredicateComparison]: unable to prove that (exists ((|v_ULTIMATE.start_main_~#r~0#1.base_BEFORE_CALL_16| Int) (|v_ULTIMATE.start_main_~#A~0#1.base_BEFORE_CALL_16| Int) (|v_ULTIMATE.start_main_~#A~0#1.offset_BEFORE_CALL_16| Int)) (= (select (select |c_#memory_int#2| |v_ULTIMATE.start_main_~#r~0#1.base_BEFORE_CALL_16|) 0) (select (select |c_#memory_int#5| |v_ULTIMATE.start_main_~#A~0#1.base_BEFORE_CALL_16|) |v_ULTIMATE.start_main_~#A~0#1.offset_BEFORE_CALL_16|))) is different from true [2023-12-20 00:19:33,803 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 19 [2023-12-20 00:19:33,837 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:19:33,838 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 38 treesize of output 34 [2023-12-20 00:19:37,933 WARN L876 $PredicateComparison]: unable to prove that (exists ((|v_ULTIMATE.start_main_~#A~0#1.base_BEFORE_CALL_17| Int) (|v_ULTIMATE.start_main_~#A~0#1.offset_BEFORE_CALL_17| Int) (|v_ULTIMATE.start_main_~#B~0#1.base_BEFORE_CALL_8| Int)) (<= (mod (select (select |c_#memory_int#1| |v_ULTIMATE.start_main_~#B~0#1.base_BEFORE_CALL_8|) 0) 4294967296) (mod (select (select |c_#memory_int#5| |v_ULTIMATE.start_main_~#A~0#1.base_BEFORE_CALL_17|) |v_ULTIMATE.start_main_~#A~0#1.offset_BEFORE_CALL_17|) 4294967296))) is different from true [2023-12-20 00:19:37,975 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:20:02,344 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 25 [2023-12-20 00:20:02,393 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 7 refuted. 0 times theorem prover too weak. 4 trivial. 5 not checked. [2023-12-20 00:20:02,393 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-20 00:20:02,866 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:20:03,451 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:20:03,451 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1936570376] [2023-12-20 00:20:03,451 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:20:03,451 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1164522191] [2023-12-20 00:20:03,451 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1164522191] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-20 00:20:03,451 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-20 00:20:03,451 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2023-12-20 00:20:03,451 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1986129685] [2023-12-20 00:20:03,452 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-20 00:20:03,452 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2023-12-20 00:20:03,452 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:20:03,452 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2023-12-20 00:20:03,452 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=713, Unknown=8, NotChecked=110, Total=930 [2023-12-20 00:20:03,453 INFO L87 Difference]: Start difference. First operand 95 states and 114 transitions. Second operand has 19 states, 16 states have (on average 1.6875) internal successors, (27), 14 states have internal predecessors, (27), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-20 00:20:07,507 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:20:11,538 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:20:15,568 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:20:19,591 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:20:23,616 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:20:27,631 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:20:35,710 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:20:39,770 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:20:43,805 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:20:47,826 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:20:51,855 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:20:55,880 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:20:59,900 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:21:03,922 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:21:07,945 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:21:12,451 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:21:16,473 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:21:20,479 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:21:24,674 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-20 00:21:28,693 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-20 00:21:32,702 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-20 00:21:36,729 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:21:40,746 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:21:44,750 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:21:48,772 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:21:52,791 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:21:56,796 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:22:00,820 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:22:04,840 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:22:08,844 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:22:13,164 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-20 00:22:17,184 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-20 00:22:21,187 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-20 00:22:25,210 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:22:29,224 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:22:33,233 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:22:37,259 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:22:41,287 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:22:45,293 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:22:45,407 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:22:45,407 INFO L93 Difference]: Finished difference Result 110 states and 130 transitions. [2023-12-20 00:22:45,409 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2023-12-20 00:22:45,409 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 16 states have (on average 1.6875) internal successors, (27), 14 states have internal predecessors, (27), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 43 [2023-12-20 00:22:45,409 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:22:45,410 INFO L225 Difference]: With dead ends: 110 [2023-12-20 00:22:45,410 INFO L226 Difference]: Without dead ends: 96 [2023-12-20 00:22:45,410 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 50 SyntacticMatches, 0 SemanticMatches, 42 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 228 ImplicationChecksByTransitivity, 37.6s TimeCoverageRelationStatistics Valid=250, Invalid=1471, Unknown=9, NotChecked=162, Total=1892 [2023-12-20 00:22:45,411 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 48 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 371 mSolverCounterSat, 23 mSolverCounterUnsat, 40 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 156.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 109 SdHoareTripleChecker+Invalid, 553 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 371 IncrementalHoareTripleChecker+Invalid, 40 IncrementalHoareTripleChecker+Unknown, 119 IncrementalHoareTripleChecker+Unchecked, 157.3s IncrementalHoareTripleChecker+Time [2023-12-20 00:22:45,411 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 109 Invalid, 553 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 371 Invalid, 40 Unknown, 119 Unchecked, 157.3s Time] [2023-12-20 00:22:45,411 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2023-12-20 00:22:45,444 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 87. [2023-12-20 00:22:45,444 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 57 states have (on average 1.1403508771929824) internal successors, (65), 60 states have internal predecessors, (65), 14 states have call successors, (14), 12 states have call predecessors, (14), 15 states have return successors, (24), 14 states have call predecessors, (24), 13 states have call successors, (24) [2023-12-20 00:22:45,445 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 103 transitions. [2023-12-20 00:22:45,445 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 103 transitions. Word has length 43 [2023-12-20 00:22:45,445 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:22:45,445 INFO L495 AbstractCegarLoop]: Abstraction has 87 states and 103 transitions. [2023-12-20 00:22:45,445 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 16 states have (on average 1.6875) internal successors, (27), 14 states have internal predecessors, (27), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-20 00:22:45,445 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 103 transitions. [2023-12-20 00:22:45,446 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2023-12-20 00:22:45,446 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:22:45,446 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:22:45,455 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-20 00:22:45,658 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-12-20 00:22:45,658 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:22:45,658 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:22:45,659 INFO L85 PathProgramCache]: Analyzing trace with hash 1086099972, now seen corresponding path program 4 times [2023-12-20 00:22:45,659 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:22:45,659 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [545360511] [2023-12-20 00:22:45,659 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:22:45,659 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:22:45,679 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:22:45,680 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [365510685] [2023-12-20 00:22:45,680 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-20 00:22:45,680 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:22:45,680 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:22:45,681 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-20 00:22:45,722 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-20 00:22:45,860 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-20 00:22:45,860 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-20 00:22:45,863 INFO L262 TraceCheckSpWp]: Trace formula consists of 384 conjuncts, 171 conjunts are in the unsatisfiable core [2023-12-20 00:22:45,867 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:22:45,874 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:22:45,877 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:22:45,884 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:22:45,892 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:22:46,038 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:22:46,211 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:22:46,402 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:22:46,402 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 26 [2023-12-20 00:22:46,768 INFO L349 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2023-12-20 00:22:46,768 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 25 [2023-12-20 00:22:46,891 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:22:46,892 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 32 treesize of output 28 [2023-12-20 00:22:47,202 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2023-12-20 00:22:47,236 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 12 proven. 12 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-12-20 00:22:47,236 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-20 00:22:47,703 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:22:47,703 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [545360511] [2023-12-20 00:22:47,703 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:22:47,704 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [365510685] [2023-12-20 00:22:47,704 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [365510685] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-20 00:22:47,704 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-20 00:22:47,704 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2023-12-20 00:22:47,704 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [212801344] [2023-12-20 00:22:47,704 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-20 00:22:47,705 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2023-12-20 00:22:47,705 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:22:47,705 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2023-12-20 00:22:47,705 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=774, Unknown=0, NotChecked=0, Total=870 [2023-12-20 00:22:47,706 INFO L87 Difference]: Start difference. First operand 87 states and 103 transitions. Second operand has 24 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 18 states have internal predecessors, (29), 7 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-12-20 00:22:52,899 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:22:57,018 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-20 00:23:01,027 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:23:05,041 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:23:09,054 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:23:13,259 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-20 00:23:17,269 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:23:21,286 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:23:21,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:23:21,298 INFO L93 Difference]: Finished difference Result 164 states and 189 transitions. [2023-12-20 00:23:21,298 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2023-12-20 00:23:21,298 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 18 states have internal predecessors, (29), 7 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 42 [2023-12-20 00:23:21,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:23:21,299 INFO L225 Difference]: With dead ends: 164 [2023-12-20 00:23:21,299 INFO L226 Difference]: Without dead ends: 118 [2023-12-20 00:23:21,299 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 34 SyntacticMatches, 1 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 324 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=193, Invalid=1613, Unknown=0, NotChecked=0, Total=1806 [2023-12-20 00:23:21,300 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 32 mSDsluCounter, 150 mSDsCounter, 0 mSdLazyCounter, 506 mSolverCounterSat, 14 mSolverCounterUnsat, 10 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 32.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 167 SdHoareTripleChecker+Invalid, 530 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 506 IncrementalHoareTripleChecker+Invalid, 10 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 32.8s IncrementalHoareTripleChecker+Time [2023-12-20 00:23:21,300 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 167 Invalid, 530 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 506 Invalid, 10 Unknown, 0 Unchecked, 32.8s Time] [2023-12-20 00:23:21,300 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2023-12-20 00:23:21,318 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 116. [2023-12-20 00:23:21,318 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 77 states have (on average 1.103896103896104) internal successors, (85), 79 states have internal predecessors, (85), 19 states have call successors, (19), 17 states have call predecessors, (19), 19 states have return successors, (28), 19 states have call predecessors, (28), 17 states have call successors, (28) [2023-12-20 00:23:21,319 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 132 transitions. [2023-12-20 00:23:21,320 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 132 transitions. Word has length 42 [2023-12-20 00:23:21,320 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:23:21,320 INFO L495 AbstractCegarLoop]: Abstraction has 116 states and 132 transitions. [2023-12-20 00:23:21,320 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 18 states have internal predecessors, (29), 7 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-12-20 00:23:21,320 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 132 transitions. [2023-12-20 00:23:21,321 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-12-20 00:23:21,321 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:23:21,321 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:23:21,327 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-20 00:23:21,523 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-12-20 00:23:21,524 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:23:21,524 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:23:21,524 INFO L85 PathProgramCache]: Analyzing trace with hash 1630059440, now seen corresponding path program 1 times [2023-12-20 00:23:21,524 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:23:21,524 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1785182118] [2023-12-20 00:23:21,524 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:23:21,524 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:23:21,536 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:23:21,536 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [106919546] [2023-12-20 00:23:21,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:23:21,536 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:23:21,536 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:23:21,537 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-20 00:23:21,539 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-20 00:23:21,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-20 00:23:21,745 WARN L260 TraceCheckSpWp]: Trace formula consists of 322 conjuncts, 187 conjunts are in the unsatisfiable core [2023-12-20 00:23:21,749 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:23:21,760 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:23:21,767 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:23:21,770 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:23:21,777 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:23:21,956 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:23:22,168 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:23:22,168 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 49 treesize of output 41 [2023-12-20 00:23:22,183 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:23:34,673 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:23:34,681 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 13 [2023-12-20 00:23:35,371 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:23:35,439 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 15 [2023-12-20 00:23:35,441 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:23:35,449 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:23:35,449 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 22 [2023-12-20 00:23:35,546 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 13 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2023-12-20 00:23:35,546 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-20 00:24:31,832 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:24:31,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1785182118] [2023-12-20 00:24:31,832 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:24:31,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [106919546] [2023-12-20 00:24:31,832 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [106919546] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-20 00:24:31,832 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-20 00:24:31,832 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2023-12-20 00:24:31,832 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1632415385] [2023-12-20 00:24:31,833 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-20 00:24:31,833 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-12-20 00:24:31,833 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:24:31,833 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-12-20 00:24:31,833 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=1062, Unknown=12, NotChecked=0, Total=1190 [2023-12-20 00:24:31,834 INFO L87 Difference]: Start difference. First operand 116 states and 132 transitions. Second operand has 27 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 20 states have internal predecessors, (29), 7 states have call successors, (7), 5 states have call predecessors, (7), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-20 00:24:44,336 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-20 00:24:49,848 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-12-20 00:24:50,182 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:24:50,182 INFO L93 Difference]: Finished difference Result 118 states and 133 transitions. [2023-12-20 00:24:50,182 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2023-12-20 00:24:50,183 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 20 states have internal predecessors, (29), 7 states have call successors, (7), 5 states have call predecessors, (7), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 43 [2023-12-20 00:24:50,183 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:24:50,183 INFO L225 Difference]: With dead ends: 118 [2023-12-20 00:24:50,183 INFO L226 Difference]: Without dead ends: 87 [2023-12-20 00:24:50,184 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 507 ImplicationChecksByTransitivity, 63.8s TimeCoverageRelationStatistics Valid=235, Invalid=2007, Unknown=14, NotChecked=0, Total=2256 [2023-12-20 00:24:50,185 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 23 mSDsluCounter, 170 mSDsCounter, 0 mSdLazyCounter, 472 mSolverCounterSat, 11 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 487 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 472 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.3s IncrementalHoareTripleChecker+Time [2023-12-20 00:24:50,185 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 186 Invalid, 487 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 472 Invalid, 4 Unknown, 0 Unchecked, 9.3s Time] [2023-12-20 00:24:50,185 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2023-12-20 00:24:50,195 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 87. [2023-12-20 00:24:50,195 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 57 states have (on average 1.1403508771929824) internal successors, (65), 60 states have internal predecessors, (65), 14 states have call successors, (14), 12 states have call predecessors, (14), 15 states have return successors, (23), 14 states have call predecessors, (23), 13 states have call successors, (23) [2023-12-20 00:24:50,196 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 102 transitions. [2023-12-20 00:24:50,196 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 102 transitions. Word has length 43 [2023-12-20 00:24:50,196 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:24:50,196 INFO L495 AbstractCegarLoop]: Abstraction has 87 states and 102 transitions. [2023-12-20 00:24:50,196 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 20 states have internal predecessors, (29), 7 states have call successors, (7), 5 states have call predecessors, (7), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-20 00:24:50,196 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 102 transitions. [2023-12-20 00:24:50,196 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2023-12-20 00:24:50,196 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:24:50,196 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:24:50,201 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-20 00:24:50,401 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-12-20 00:24:50,401 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:24:50,402 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:24:50,402 INFO L85 PathProgramCache]: Analyzing trace with hash -608422709, now seen corresponding path program 5 times [2023-12-20 00:24:50,402 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:24:50,402 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [976873619] [2023-12-20 00:24:50,402 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:24:50,402 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:24:50,416 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:24:50,416 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [991105858] [2023-12-20 00:24:50,416 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2023-12-20 00:24:50,417 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:24:50,417 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:24:50,417 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-20 00:24:50,419 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-20 00:24:51,094 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2023-12-20 00:24:51,094 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-20 00:24:51,099 WARN L260 TraceCheckSpWp]: Trace formula consists of 413 conjuncts, 293 conjunts are in the unsatisfiable core [2023-12-20 00:24:51,103 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:24:51,114 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:24:51,116 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:24:51,123 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:24:51,130 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:24:51,140 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:24:51,333 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:24:51,789 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:24:52,763 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:24:52,785 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2023-12-20 00:24:52,785 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 21 [2023-12-20 00:24:52,940 INFO L349 Elim1Store]: treesize reduction 14, result has 58.8 percent of original size [2023-12-20 00:24:52,940 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 58 treesize of output 53 [2023-12-20 00:24:52,991 INFO L349 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2023-12-20 00:24:52,992 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 25 [2023-12-20 00:24:54,461 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:24:54,469 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:24:54,643 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:24:54,700 INFO L349 Elim1Store]: treesize reduction 36, result has 52.0 percent of original size [2023-12-20 00:24:54,700 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 82 treesize of output 100 [2023-12-20 00:24:55,565 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:24:55,565 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 7 select indices, 7 select index equivalence classes, 0 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 178 treesize of output 266 [2023-12-20 00:24:55,716 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:24:55,716 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 7 select indices, 7 select index equivalence classes, 0 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 238 treesize of output 310 [2023-12-20 00:24:56,408 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 0 proven. 31 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-12-20 00:24:56,408 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-20 00:25:35,560 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:25:35,560 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [976873619] [2023-12-20 00:25:35,560 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:25:35,560 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [991105858] [2023-12-20 00:25:35,560 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [991105858] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-20 00:25:35,560 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-20 00:25:35,560 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2023-12-20 00:25:35,560 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [228679776] [2023-12-20 00:25:35,560 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-20 00:25:35,561 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2023-12-20 00:25:35,561 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:25:35,561 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2023-12-20 00:25:35,561 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=144, Invalid=1832, Unknown=4, NotChecked=0, Total=1980 [2023-12-20 00:25:35,562 INFO L87 Difference]: Start difference. First operand 87 states and 102 transitions. Second operand has 30 states, 24 states have (on average 1.3333333333333333) internal successors, (32), 22 states have internal predecessors, (32), 8 states have call successors, (9), 7 states have call predecessors, (9), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-12-20 00:25:48,746 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:25:48,746 INFO L93 Difference]: Finished difference Result 111 states and 131 transitions. [2023-12-20 00:25:48,746 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2023-12-20 00:25:48,747 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 24 states have (on average 1.3333333333333333) internal successors, (32), 22 states have internal predecessors, (32), 8 states have call successors, (9), 7 states have call predecessors, (9), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Word has length 48 [2023-12-20 00:25:48,747 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:25:48,747 INFO L225 Difference]: With dead ends: 111 [2023-12-20 00:25:48,747 INFO L226 Difference]: Without dead ends: 99 [2023-12-20 00:25:48,748 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 35 SyntacticMatches, 2 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 601 ImplicationChecksByTransitivity, 47.7s TimeCoverageRelationStatistics Valid=266, Invalid=3035, Unknown=5, NotChecked=0, Total=3306 [2023-12-20 00:25:48,748 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 35 mSDsluCounter, 375 mSDsCounter, 0 mSdLazyCounter, 1082 mSolverCounterSat, 12 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 405 SdHoareTripleChecker+Invalid, 1095 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 1082 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.6s IncrementalHoareTripleChecker+Time [2023-12-20 00:25:48,749 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 405 Invalid, 1095 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 1082 Invalid, 1 Unknown, 0 Unchecked, 2.6s Time] [2023-12-20 00:25:48,749 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2023-12-20 00:25:48,766 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 98. [2023-12-20 00:25:48,767 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 65 states have (on average 1.1384615384615384) internal successors, (74), 68 states have internal predecessors, (74), 16 states have call successors, (16), 14 states have call predecessors, (16), 16 states have return successors, (25), 15 states have call predecessors, (25), 15 states have call successors, (25) [2023-12-20 00:25:48,767 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 115 transitions. [2023-12-20 00:25:48,767 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 115 transitions. Word has length 48 [2023-12-20 00:25:48,767 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:25:48,767 INFO L495 AbstractCegarLoop]: Abstraction has 98 states and 115 transitions. [2023-12-20 00:25:48,768 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 24 states have (on average 1.3333333333333333) internal successors, (32), 22 states have internal predecessors, (32), 8 states have call successors, (9), 7 states have call predecessors, (9), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-12-20 00:25:48,768 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 115 transitions. [2023-12-20 00:25:48,769 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2023-12-20 00:25:48,774 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:25:48,774 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:25:48,782 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-20 00:25:48,979 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-12-20 00:25:48,980 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:25:48,980 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:25:48,980 INFO L85 PathProgramCache]: Analyzing trace with hash -1417769335, now seen corresponding path program 1 times [2023-12-20 00:25:48,980 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:25:48,980 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2090893222] [2023-12-20 00:25:48,980 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:25:48,981 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:25:49,020 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:25:49,021 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2031936146] [2023-12-20 00:25:49,021 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:25:49,021 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:25:49,021 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:25:49,028 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-20 00:25:49,047 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-20 00:25:49,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-20 00:25:49,379 WARN L260 TraceCheckSpWp]: Trace formula consists of 405 conjuncts, 294 conjunts are in the unsatisfiable core [2023-12-20 00:25:49,383 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:25:49,391 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:25:49,397 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:25:49,415 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:25:49,422 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:25:49,428 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:25:49,686 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:25:49,796 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:25:50,183 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:25:50,761 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:25:50,792 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2023-12-20 00:25:50,792 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 21 [2023-12-20 00:25:50,932 INFO L349 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2023-12-20 00:25:50,933 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 25 [2023-12-20 00:25:50,969 INFO L349 Elim1Store]: treesize reduction 14, result has 58.8 percent of original size [2023-12-20 00:25:50,970 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 58 treesize of output 53 [2023-12-20 00:25:52,753 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:25:52,779 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:25:53,220 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:25:53,220 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 90 treesize of output 98 [2023-12-20 00:25:53,240 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:25:53,240 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 120 treesize of output 100 [2023-12-20 00:25:53,482 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 0 proven. 29 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-12-20 00:25:53,482 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-20 00:28:20,570 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:28:20,571 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2090893222] [2023-12-20 00:28:20,571 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:28:20,571 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2031936146] [2023-12-20 00:28:20,571 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2031936146] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-20 00:28:20,571 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-20 00:28:20,571 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27] total 27 [2023-12-20 00:28:20,571 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [921409905] [2023-12-20 00:28:20,571 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-20 00:28:20,571 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-12-20 00:28:20,572 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:28:20,572 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-12-20 00:28:20,572 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=165, Invalid=1897, Unknown=8, NotChecked=0, Total=2070 [2023-12-20 00:28:20,572 INFO L87 Difference]: Start difference. First operand 98 states and 115 transitions. Second operand has 28 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 20 states have internal predecessors, (30), 8 states have call successors, (8), 7 states have call predecessors, (8), 5 states have return successors, (5), 5 states have call predecessors, (5), 4 states have call successors, (5) [2023-12-20 00:28:59,108 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:28:59,108 INFO L93 Difference]: Finished difference Result 156 states and 183 transitions. [2023-12-20 00:28:59,108 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2023-12-20 00:28:59,109 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 20 states have internal predecessors, (30), 8 states have call successors, (8), 7 states have call predecessors, (8), 5 states have return successors, (5), 5 states have call predecessors, (5), 4 states have call successors, (5) Word has length 48 [2023-12-20 00:28:59,109 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:28:59,109 INFO L225 Difference]: With dead ends: 156 [2023-12-20 00:28:59,109 INFO L226 Difference]: Without dead ends: 112 [2023-12-20 00:28:59,110 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 34 SyntacticMatches, 2 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 622 ImplicationChecksByTransitivity, 159.3s TimeCoverageRelationStatistics Valid=305, Invalid=3106, Unknown=11, NotChecked=0, Total=3422 [2023-12-20 00:28:59,111 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 39 mSDsluCounter, 363 mSDsCounter, 0 mSdLazyCounter, 1033 mSolverCounterSat, 14 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 390 SdHoareTripleChecker+Invalid, 1048 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 1033 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.0s IncrementalHoareTripleChecker+Time [2023-12-20 00:28:59,111 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 390 Invalid, 1048 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 1033 Invalid, 1 Unknown, 0 Unchecked, 3.0s Time] [2023-12-20 00:28:59,111 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2023-12-20 00:28:59,126 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 98. [2023-12-20 00:28:59,126 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 65 states have (on average 1.123076923076923) internal successors, (73), 68 states have internal predecessors, (73), 16 states have call successors, (16), 14 states have call predecessors, (16), 16 states have return successors, (25), 15 states have call predecessors, (25), 15 states have call successors, (25) [2023-12-20 00:28:59,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 114 transitions. [2023-12-20 00:28:59,127 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 114 transitions. Word has length 48 [2023-12-20 00:28:59,128 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:28:59,128 INFO L495 AbstractCegarLoop]: Abstraction has 98 states and 114 transitions. [2023-12-20 00:28:59,128 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 20 states have internal predecessors, (30), 8 states have call successors, (8), 7 states have call predecessors, (8), 5 states have return successors, (5), 5 states have call predecessors, (5), 4 states have call successors, (5) [2023-12-20 00:28:59,128 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 114 transitions. [2023-12-20 00:28:59,129 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2023-12-20 00:28:59,129 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:28:59,129 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:28:59,135 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2023-12-20 00:28:59,335 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:28:59,335 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:28:59,335 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:28:59,336 INFO L85 PathProgramCache]: Analyzing trace with hash -967732526, now seen corresponding path program 6 times [2023-12-20 00:28:59,336 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:28:59,336 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [412075173] [2023-12-20 00:28:59,336 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:28:59,336 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:28:59,351 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:28:59,351 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1995973794] [2023-12-20 00:28:59,351 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2023-12-20 00:28:59,351 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:28:59,351 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:28:59,354 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-20 00:28:59,376 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-20 00:28:59,909 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2023-12-20 00:28:59,909 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-20 00:28:59,914 WARN L260 TraceCheckSpWp]: Trace formula consists of 442 conjuncts, 293 conjunts are in the unsatisfiable core [2023-12-20 00:28:59,919 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:28:59,928 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:28:59,932 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:28:59,935 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:28:59,939 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:29:00,334 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:29:00,724 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:29:01,178 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2023-12-20 00:29:01,179 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 21 [2023-12-20 00:29:01,188 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:29:01,281 INFO L349 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2023-12-20 00:29:01,281 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 25 [2023-12-20 00:29:01,304 INFO L349 Elim1Store]: treesize reduction 14, result has 58.8 percent of original size [2023-12-20 00:29:01,304 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 58 treesize of output 53 [2023-12-20 00:29:02,751 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:29:02,775 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:29:02,903 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:29:02,954 INFO L349 Elim1Store]: treesize reduction 36, result has 52.0 percent of original size [2023-12-20 00:29:02,954 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 91 treesize of output 105 [2023-12-20 00:29:03,780 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:29:03,780 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 8 select indices, 8 select index equivalence classes, 0 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 194 treesize of output 350 [2023-12-20 00:29:03,958 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:29:03,958 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 8 select indices, 8 select index equivalence classes, 0 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 131 treesize of output 299 [2023-12-20 00:29:05,422 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 4 proven. 36 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-12-20 00:29:05,422 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-20 00:30:05,629 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-20 00:30:05,630 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [412075173] [2023-12-20 00:30:05,630 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-20 00:30:05,630 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1995973794] [2023-12-20 00:30:05,630 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1995973794] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-20 00:30:05,630 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-20 00:30:05,630 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2023-12-20 00:30:05,630 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [704808663] [2023-12-20 00:30:05,630 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-20 00:30:05,630 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2023-12-20 00:30:05,630 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-20 00:30:05,631 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2023-12-20 00:30:05,631 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=148, Invalid=1827, Unknown=5, NotChecked=0, Total=1980 [2023-12-20 00:30:05,631 INFO L87 Difference]: Start difference. First operand 98 states and 114 transitions. Second operand has 30 states, 24 states have (on average 1.375) internal successors, (33), 22 states have internal predecessors, (33), 9 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2023-12-20 00:30:22,565 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-20 00:30:22,565 INFO L93 Difference]: Finished difference Result 192 states and 223 transitions. [2023-12-20 00:30:22,566 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2023-12-20 00:30:22,566 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 24 states have (on average 1.375) internal successors, (33), 22 states have internal predecessors, (33), 9 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) Word has length 54 [2023-12-20 00:30:22,566 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-20 00:30:22,567 INFO L225 Difference]: With dead ends: 192 [2023-12-20 00:30:22,567 INFO L226 Difference]: Without dead ends: 146 [2023-12-20 00:30:22,568 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 41 SyntacticMatches, 2 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 575 ImplicationChecksByTransitivity, 62.9s TimeCoverageRelationStatistics Valid=251, Invalid=2823, Unknown=6, NotChecked=0, Total=3080 [2023-12-20 00:30:22,568 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 42 mSDsluCounter, 477 mSDsCounter, 0 mSdLazyCounter, 1426 mSolverCounterSat, 15 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 514 SdHoareTripleChecker+Invalid, 1442 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 1426 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.2s IncrementalHoareTripleChecker+Time [2023-12-20 00:30:22,568 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 514 Invalid, 1442 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 1426 Invalid, 1 Unknown, 0 Unchecked, 4.2s Time] [2023-12-20 00:30:22,568 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2023-12-20 00:30:22,593 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 144. [2023-12-20 00:30:22,593 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 96 states have (on average 1.1145833333333333) internal successors, (107), 99 states have internal predecessors, (107), 23 states have call successors, (23), 21 states have call predecessors, (23), 24 states have return successors, (37), 23 states have call predecessors, (37), 21 states have call successors, (37) [2023-12-20 00:30:22,594 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 167 transitions. [2023-12-20 00:30:22,594 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 167 transitions. Word has length 54 [2023-12-20 00:30:22,594 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-20 00:30:22,594 INFO L495 AbstractCegarLoop]: Abstraction has 144 states and 167 transitions. [2023-12-20 00:30:22,595 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 24 states have (on average 1.375) internal successors, (33), 22 states have internal predecessors, (33), 9 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2023-12-20 00:30:22,595 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 167 transitions. [2023-12-20 00:30:22,595 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2023-12-20 00:30:22,595 INFO L187 NwaCegarLoop]: Found error trace [2023-12-20 00:30:22,595 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:30:22,602 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-20 00:30:22,802 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-12-20 00:30:22,803 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-20 00:30:22,803 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-20 00:30:22,803 INFO L85 PathProgramCache]: Analyzing trace with hash -1777079152, now seen corresponding path program 2 times [2023-12-20 00:30:22,803 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-20 00:30:22,803 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [155307525] [2023-12-20 00:30:22,803 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-20 00:30:22,803 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-20 00:30:22,832 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-20 00:30:22,832 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1813293727] [2023-12-20 00:30:22,832 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-20 00:30:22,832 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-20 00:30:22,832 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-20 00:30:22,840 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-20 00:30:22,852 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2023-12-20 00:30:23,339 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-20 00:30:23,340 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-20 00:30:23,344 WARN L260 TraceCheckSpWp]: Trace formula consists of 434 conjuncts, 275 conjunts are in the unsatisfiable core [2023-12-20 00:30:23,349 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-20 00:30:23,355 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-20 00:30:23,358 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:30:23,369 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:30:23,378 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-20 00:30:23,677 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-20 00:30:24,011 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:30:24,448 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2023-12-20 00:30:24,448 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 21 [2023-12-20 00:30:24,458 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:30:24,543 INFO L349 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2023-12-20 00:30:24,544 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 25 [2023-12-20 00:30:24,563 INFO L349 Elim1Store]: treesize reduction 14, result has 58.8 percent of original size [2023-12-20 00:30:24,563 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 58 treesize of output 53 [2023-12-20 00:30:25,821 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:30:25,838 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-20 00:30:26,219 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:30:26,219 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 90 treesize of output 98 [2023-12-20 00:30:26,235 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-20 00:30:26,235 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 120 treesize of output 100 [2023-12-20 00:30:26,411 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 4 proven. 36 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-12-20 00:30:26,411 INFO L327 TraceCheckSpWp]: Computing backward predicates... Received shutdown request... [2023-12-20 00:30:48,047 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2023-12-20 00:30:48,059 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2023-12-20 00:30:48,104 INFO L805 garLoopResultBuilder]: Registering result TIMEOUT for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-12-20 00:30:48,112 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2023-12-20 00:30:48,305 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2023-12-20 00:30:48,305 WARN L619 AbstractCegarLoop]: Verification canceled: while NwaCegarLoop was analyzing trace of length 55 with TraceHistMax 4,while TraceCheckSpWp was constructing backward predicates,while PolyPacSimplificationTermWalker was simplifying a ∨-2-1 term,while PolyPacSimplificationTermWalker was simplifying 2 xjuncts wrt. a ATOM-1 context. [2023-12-20 00:30:48,309 INFO L445 BasicCegarLoop]: Path program histogram: [6, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-20 00:30:48,311 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2023-12-20 00:30:48,312 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.12 12:30:48 BoogieIcfgContainer [2023-12-20 00:30:48,312 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-12-20 00:30:48,313 INFO L158 Benchmark]: Toolchain (without parser) took 879809.19ms. Allocated memory was 249.6MB in the beginning and 420.5MB in the end (delta: 170.9MB). Free memory was 183.5MB in the beginning and 139.5MB in the end (delta: 44.0MB). Peak memory consumption was 216.5MB. Max. memory is 8.0GB. [2023-12-20 00:30:48,313 INFO L158 Benchmark]: CDTParser took 0.10ms. Allocated memory is still 249.6MB. Free memory is still 197.7MB. There was no memory consumed. Max. memory is 8.0GB. [2023-12-20 00:30:48,313 INFO L158 Benchmark]: CACSL2BoogieTranslator took 163.13ms. Allocated memory is still 249.6MB. Free memory was 183.2MB in the beginning and 171.5MB in the end (delta: 11.7MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2023-12-20 00:30:48,313 INFO L158 Benchmark]: Boogie Procedure Inliner took 19.31ms. Allocated memory is still 249.6MB. Free memory was 171.5MB in the beginning and 170.0MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2023-12-20 00:30:48,313 INFO L158 Benchmark]: Boogie Preprocessor took 30.29ms. Allocated memory is still 249.6MB. Free memory was 169.8MB in the beginning and 167.8MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2023-12-20 00:30:48,313 INFO L158 Benchmark]: RCFGBuilder took 279.42ms. Allocated memory is still 249.6MB. Free memory was 167.5MB in the beginning and 151.0MB in the end (delta: 16.5MB). Peak memory consumption was 15.7MB. Max. memory is 8.0GB. [2023-12-20 00:30:48,314 INFO L158 Benchmark]: TraceAbstraction took 879313.12ms. Allocated memory was 249.6MB in the beginning and 420.5MB in the end (delta: 170.9MB). Free memory was 150.1MB in the beginning and 139.5MB in the end (delta: 10.6MB). Peak memory consumption was 182.9MB. Max. memory is 8.0GB. [2023-12-20 00:30:48,314 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.10ms. Allocated memory is still 249.6MB. Free memory is still 197.7MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 163.13ms. Allocated memory is still 249.6MB. Free memory was 183.2MB in the beginning and 171.5MB in the end (delta: 11.7MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Procedure Inliner took 19.31ms. Allocated memory is still 249.6MB. Free memory was 171.5MB in the beginning and 170.0MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * Boogie Preprocessor took 30.29ms. Allocated memory is still 249.6MB. Free memory was 169.8MB in the beginning and 167.8MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 279.42ms. Allocated memory is still 249.6MB. Free memory was 167.5MB in the beginning and 151.0MB in the end (delta: 16.5MB). Peak memory consumption was 15.7MB. Max. memory is 8.0GB. * TraceAbstraction took 879313.12ms. Allocated memory was 249.6MB in the beginning and 420.5MB in the end (delta: 170.9MB). Free memory was 150.1MB in the beginning and 139.5MB in the end (delta: 10.6MB). Peak memory consumption was 182.9MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - TimeoutResultAtElement [Line: 53]: Timeout (TraceAbstraction) Unable to prove that a call to reach_error is unreachable (line 53). Cancelled while NwaCegarLoop was analyzing trace of length 55 with TraceHistMax 4,while TraceCheckSpWp was constructing backward predicates,while PolyPacSimplificationTermWalker was simplifying a ∨-2-1 term,while PolyPacSimplificationTermWalker was simplifying 2 xjuncts wrt. a ATOM-1 context. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 28 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 879.2s, OverallIterations: 16, TraceHistogramMax: 4, PathProgramHistogramMax: 6, EmptinessCheckTime: 0.0s, AutomataDifference: 398.4s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 84 mSolverCounterUnknown, 497 SdHoareTripleChecker+Valid, 297.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 489 mSDsluCounter, 3054 SdHoareTripleChecker+Invalid, 295.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 161 IncrementalHoareTripleChecker+Unchecked, 2715 mSDsCounter, 180 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 7391 IncrementalHoareTripleChecker+Invalid, 7816 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 180 mSolverCounterUnsat, 339 mSDtfsCounter, 7391 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 84 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 886 GetRequests, 370 SyntacticMatches, 16 SemanticMatches, 500 ConstructedPredicates, 3 IntricatePredicates, 0 DeprecatedPredicates, 3972 ImplicationChecksByTransitivity, 475.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=144occurred in iteration=15, InterpolantAutomatonStates: 285, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 15 MinimizatonAttempts, 119 StatesRemovedByMinimization, 12 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.3s SsaConstructionTime, 2.6s SatisfiabilityAnalysisTime, 447.7s InterpolantComputationTime, 528 NumberOfCodeBlocks, 516 NumberOfCodeBlocksAsserted, 24 NumberOfCheckSat, 500 ConstructedInterpolants, 382 QuantifiedInterpolants, 23679 SizeOfPredicates, 582 NumberOfNonLiveVariables, 4449 ConjunctsInSsa, 2154 ConjunctsInUnsatCore, 15 InterpolantComputations, 3 PerfectInterpolantSequences, 117/282 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown