/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 15:27:25,677 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 15:27:25,679 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 15:27:25,714 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 15:27:25,714 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 15:27:25,716 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 15:27:25,721 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 15:27:25,727 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 15:27:25,728 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 15:27:25,733 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 15:27:25,734 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 15:27:25,735 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 15:27:25,735 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 15:27:25,735 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 15:27:25,736 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 15:27:25,737 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 15:27:25,737 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 15:27:25,738 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 15:27:25,739 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 15:27:25,741 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 15:27:25,742 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 15:27:25,744 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 15:27:25,746 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 15:27:25,748 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 15:27:25,749 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 15:27:25,757 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 15:27:25,757 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 15:27:25,757 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 15:27:25,758 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 15:27:25,758 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 15:27:25,758 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 15:27:25,759 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 15:27:25,759 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 15:27:25,760 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 15:27:25,760 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 15:27:25,761 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 15:27:25,761 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 15:27:25,762 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 15:27:25,762 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 15:27:25,762 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 15:27:25,763 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 15:27:25,767 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 15:27:25,767 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-03-20 15:27:25,780 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 15:27:25,780 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 15:27:25,781 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 15:27:25,781 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-20 15:27:25,782 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 15:27:25,782 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-20 15:27:25,782 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 15:27:25,782 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 15:27:25,782 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 15:27:25,783 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 15:27:25,783 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-20 15:27:25,783 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 15:27:25,784 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 15:27:25,784 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 15:27:25,784 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 15:27:25,784 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 15:27:25,784 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-20 15:27:25,784 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 15:27:25,784 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 15:27:25,784 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 15:27:25,785 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-03-20 15:27:25,785 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-03-20 15:27:25,785 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-03-20 15:27:25,785 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-20 15:27:25,785 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-03-20 15:27:25,785 INFO L138 SettingsManager]: * Use separate solver for trace checks=false 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.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-03-20 15:27:26,015 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 15:27:26,045 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 15:27:26,047 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 15:27:26,047 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 15:27:26,048 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 15:27:26,049 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c [2022-03-20 15:27:26,102 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1c25928e4/c7a2a03288104eceb036661bf498a370/FLAG5d2c5529f [2022-03-20 15:27:26,496 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 15:27:26,496 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c [2022-03-20 15:27:26,502 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1c25928e4/c7a2a03288104eceb036661bf498a370/FLAG5d2c5529f [2022-03-20 15:27:26,517 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1c25928e4/c7a2a03288104eceb036661bf498a370 [2022-03-20 15:27:26,519 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 15:27:26,520 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-03-20 15:27:26,523 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 15:27:26,523 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 15:27:26,526 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 15:27:26,527 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 03:27:26" (1/1) ... [2022-03-20 15:27:26,528 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@15eb37ff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 03:27:26, skipping insertion in model container [2022-03-20 15:27:26,528 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 03:27:26" (1/1) ... [2022-03-20 15:27:26,533 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 15:27:26,544 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 15:27:26,746 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c[538,551] [2022-03-20 15:27:26,771 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 15:27:26,781 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 15:27:26,791 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c[538,551] [2022-03-20 15:27:26,808 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 15:27:26,820 INFO L208 MainTranslator]: Completed translation [2022-03-20 15:27:26,821 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 03:27:26 WrapperNode [2022-03-20 15:27:26,821 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 15:27:26,823 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 15:27:26,823 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 15:27:26,823 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 15:27:26,832 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 03:27:26" (1/1) ... [2022-03-20 15:27:26,832 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 03:27:26" (1/1) ... [2022-03-20 15:27:26,839 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 03:27:26" (1/1) ... [2022-03-20 15:27:26,839 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 03:27:26" (1/1) ... [2022-03-20 15:27:26,849 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 03:27:26" (1/1) ... [2022-03-20 15:27:26,854 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 03:27:26" (1/1) ... [2022-03-20 15:27:26,862 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 03:27:26" (1/1) ... [2022-03-20 15:27:26,863 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 15:27:26,864 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 15:27:26,864 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 15:27:26,864 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 15:27:26,865 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 03:27:26" (1/1) ... [2022-03-20 15:27:26,872 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 15:27:26,881 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:27:26,896 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-03-20 15:27:26,927 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-03-20 15:27:26,938 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 15:27:26,939 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 15:27:26,939 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 15:27:26,939 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 15:27:26,939 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 15:27:26,939 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 15:27:26,939 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 15:27:26,940 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 15:27:26,940 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 15:27:26,940 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 15:27:26,940 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-03-20 15:27:26,941 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 15:27:26,941 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 15:27:26,942 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 15:27:26,942 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 15:27:26,942 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 15:27:26,942 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 15:27:26,942 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 15:27:26,942 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 15:27:26,942 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 15:27:26,999 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 15:27:27,000 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 15:27:27,160 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 15:27:27,165 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 15:27:27,166 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-20 15:27:27,174 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 03:27:27 BoogieIcfgContainer [2022-03-20 15:27:27,175 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 15:27:27,176 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 15:27:27,177 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 15:27:27,179 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 15:27:27,179 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 03:27:26" (1/3) ... [2022-03-20 15:27:27,180 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@597e78d8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 03:27:27, skipping insertion in model container [2022-03-20 15:27:27,180 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 03:27:26" (2/3) ... [2022-03-20 15:27:27,180 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@597e78d8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 03:27:27, skipping insertion in model container [2022-03-20 15:27:27,180 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 03:27:27" (3/3) ... [2022-03-20 15:27:27,181 INFO L111 eAbstractionObserver]: Analyzing ICFG hard-ll_valuebound20.c [2022-03-20 15:27:27,185 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-03-20 15:27:27,185 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 15:27:27,246 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 15:27:27,252 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, 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 [2022-03-20 15:27:27,252 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 15:27:27,266 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 15:27:27,275 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-20 15:27:27,275 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:27:27,276 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:27:27,277 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:27:27,284 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:27:27,285 INFO L85 PathProgramCache]: Analyzing trace with hash -1784424332, now seen corresponding path program 1 times [2022-03-20 15:27:27,292 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:27,293 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1447799141] [2022-03-20 15:27:27,303 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:27:27,303 INFO L85 PathProgramCache]: Analyzing trace with hash -1784424332, now seen corresponding path program 2 times [2022-03-20 15:27:27,305 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:27:27,306 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1172668115] [2022-03-20 15:27:27,306 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:27:27,306 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:27:27,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:27,479 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 15:27:27,485 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:27,499 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 15:27:27,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:27,505 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-20 15:27:27,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:27,510 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-20 15:27:27,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:27,518 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 15:27:27,519 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:27:27,519 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1172668115] [2022-03-20 15:27:27,519 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1172668115] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:27,520 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:27,520 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 15:27:27,522 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:27:27,522 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1447799141] [2022-03-20 15:27:27,522 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1447799141] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:27,522 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:27,523 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 15:27:27,523 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1297271292] [2022-03-20 15:27:27,523 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:27:27,526 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-20 15:27:27,527 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:27,553 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-20 15:27:27,553 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 15:27:27,554 INFO L87 Difference]: Start difference. First operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 15:27:27,623 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:27:27,623 INFO L93 Difference]: Finished difference Result 69 states and 110 transitions. [2022-03-20 15:27:27,624 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-20 15:27:27,626 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-03-20 15:27:27,626 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:27:27,632 INFO L225 Difference]: With dead ends: 69 [2022-03-20 15:27:27,632 INFO L226 Difference]: Without dead ends: 33 [2022-03-20 15:27:27,636 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 15:27:27,643 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 21 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 15:27:27,645 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 41 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 15:27:27,659 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-03-20 15:27:27,689 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-03-20 15:27:27,691 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-20 15:27:27,695 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2022-03-20 15:27:27,696 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 28 [2022-03-20 15:27:27,696 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:27:27,697 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2022-03-20 15:27:27,697 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 15:27:27,697 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-03-20 15:27:27,699 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-20 15:27:27,699 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:27:27,699 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:27:27,700 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 15:27:27,700 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:27:27,701 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:27:27,701 INFO L85 PathProgramCache]: Analyzing trace with hash 1361835634, now seen corresponding path program 1 times [2022-03-20 15:27:27,701 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:27,701 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [147886260] [2022-03-20 15:27:27,702 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:27:27,702 INFO L85 PathProgramCache]: Analyzing trace with hash 1361835634, now seen corresponding path program 2 times [2022-03-20 15:27:27,703 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:27:27,704 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2123138338] [2022-03-20 15:27:27,704 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:27:27,704 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:27:27,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:27,841 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 15:27:27,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:27,855 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 15:27:27,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:27,862 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-20 15:27:27,864 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:27,869 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-20 15:27:27,870 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:27,877 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 15:27:27,877 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:27:27,877 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2123138338] [2022-03-20 15:27:27,877 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2123138338] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:27,878 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:27,878 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 15:27:27,878 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:27:27,878 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [147886260] [2022-03-20 15:27:27,878 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [147886260] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:27,879 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:27,879 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 15:27:27,879 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1646380299] [2022-03-20 15:27:27,879 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:27:27,880 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 15:27:27,880 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:27,880 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 15:27:27,880 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 15:27:27,881 INFO L87 Difference]: Start difference. First operand 33 states and 43 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-03-20 15:27:28,105 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:27:28,105 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-03-20 15:27:28,105 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 15:27:28,105 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2022-03-20 15:27:28,106 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:27:28,108 INFO L225 Difference]: With dead ends: 46 [2022-03-20 15:27:28,108 INFO L226 Difference]: Without dead ends: 44 [2022-03-20 15:27:28,108 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-20 15:27:28,111 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 38 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 155 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 15:27:28,112 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 48 Invalid, 155 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 15:27:28,114 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-03-20 15:27:28,132 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-03-20 15:27:28,133 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-20 15:27:28,135 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 46 transitions. [2022-03-20 15:27:28,135 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 46 transitions. Word has length 28 [2022-03-20 15:27:28,135 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:27:28,135 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 46 transitions. [2022-03-20 15:27:28,136 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-03-20 15:27:28,136 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 46 transitions. [2022-03-20 15:27:28,136 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-03-20 15:27:28,137 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:27:28,137 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:27:28,137 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-20 15:27:28,138 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:27:28,138 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:27:28,138 INFO L85 PathProgramCache]: Analyzing trace with hash 1382067636, now seen corresponding path program 1 times [2022-03-20 15:27:28,138 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:28,141 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1917246699] [2022-03-20 15:27:28,142 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:27:28,142 INFO L85 PathProgramCache]: Analyzing trace with hash 1382067636, now seen corresponding path program 2 times [2022-03-20 15:27:28,142 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:27:28,142 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1815079311] [2022-03-20 15:27:28,143 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:27:28,143 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:27:28,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:28,250 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 15:27:28,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:28,270 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 15:27:28,272 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:28,276 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-20 15:27:28,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:28,285 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-20 15:27:28,286 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:28,296 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2022-03-20 15:27:28,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 15:27:28,309 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 15:27:28,310 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:27:28,310 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1815079311] [2022-03-20 15:27:28,310 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1815079311] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:28,310 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:28,310 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 15:27:28,311 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:27:28,311 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1917246699] [2022-03-20 15:27:28,311 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1917246699] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:28,311 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:28,311 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 15:27:28,312 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1260614250] [2022-03-20 15:27:28,312 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:27:28,312 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 15:27:28,312 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:28,313 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 15:27:28,313 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 15:27:28,313 INFO L87 Difference]: Start difference. First operand 37 states and 46 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 15:27:28,479 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:27:28,480 INFO L93 Difference]: Finished difference Result 50 states and 63 transitions. [2022-03-20 15:27:28,480 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 15:27:28,480 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-03-20 15:27:28,480 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:27:28,481 INFO L225 Difference]: With dead ends: 50 [2022-03-20 15:27:28,481 INFO L226 Difference]: Without dead ends: 48 [2022-03-20 15:27:28,482 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-20 15:27:28,482 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 33 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 15:27:28,483 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 48 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 132 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 15:27:28,483 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-03-20 15:27:28,490 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 41. [2022-03-20 15:27:28,491 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-20 15:27:28,491 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2022-03-20 15:27:28,492 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 33 [2022-03-20 15:27:28,492 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:27:28,492 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2022-03-20 15:27:28,492 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 15:27:28,492 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2022-03-20 15:27:28,493 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-03-20 15:27:28,493 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:27:28,493 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:27:28,494 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-03-20 15:27:28,494 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:27:28,494 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:27:28,494 INFO L85 PathProgramCache]: Analyzing trace with hash -1455208590, now seen corresponding path program 1 times [2022-03-20 15:27:28,494 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:28,494 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1771360800] [2022-03-20 15:27:28,495 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:27:28,495 INFO L85 PathProgramCache]: Analyzing trace with hash -1455208590, now seen corresponding path program 2 times [2022-03-20 15:27:28,495 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:27:28,495 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1990176687] [2022-03-20 15:27:28,495 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:27:28,496 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:27:28,505 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:27:28,506 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2034198731] [2022-03-20 15:27:28,506 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 15:27:28,506 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:28,506 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:27:28,523 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) [2022-03-20 15:27:28,579 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-20 15:27:28,623 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 15:27:28,623 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:27:28,625 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 15:27:28,629 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:27:28,758 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-03-20 15:27:28,758 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 15:27:28,759 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:27:28,759 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1990176687] [2022-03-20 15:27:28,759 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:27:28,759 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2034198731] [2022-03-20 15:27:28,759 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2034198731] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:28,760 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:28,760 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 15:27:28,760 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:27:28,760 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1771360800] [2022-03-20 15:27:28,760 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1771360800] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:28,761 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:28,761 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 15:27:28,761 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [960984691] [2022-03-20 15:27:28,761 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:27:28,761 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 15:27:28,761 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:28,762 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 15:27:28,762 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 15:27:28,762 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-20 15:27:28,814 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:27:28,815 INFO L93 Difference]: Finished difference Result 69 states and 89 transitions. [2022-03-20 15:27:28,815 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 15:27:28,815 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 38 [2022-03-20 15:27:28,816 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:27:28,816 INFO L225 Difference]: With dead ends: 69 [2022-03-20 15:27:28,817 INFO L226 Difference]: Without dead ends: 55 [2022-03-20 15:27:28,817 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 15:27:28,818 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 8 mSDsluCounter, 112 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 15:27:28,818 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 157 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 15:27:28,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-03-20 15:27:28,830 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-03-20 15:27:28,831 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 30 states have (on average 1.1666666666666667) internal successors, (35), 32 states have internal predecessors, (35), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-03-20 15:27:28,832 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-03-20 15:27:28,832 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 38 [2022-03-20 15:27:28,832 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:27:28,832 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-03-20 15:27:28,833 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-20 15:27:28,833 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-03-20 15:27:28,834 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-03-20 15:27:28,834 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:27:28,834 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:27:28,864 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-20 15:27:29,059 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:29,060 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:27:29,060 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:27:29,060 INFO L85 PathProgramCache]: Analyzing trace with hash -1688067263, now seen corresponding path program 1 times [2022-03-20 15:27:29,060 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:29,060 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1316455236] [2022-03-20 15:27:29,061 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:27:29,061 INFO L85 PathProgramCache]: Analyzing trace with hash -1688067263, now seen corresponding path program 2 times [2022-03-20 15:27:29,061 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:27:29,061 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1334306464] [2022-03-20 15:27:29,062 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:27:29,062 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:27:29,072 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:27:29,072 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [113293270] [2022-03-20 15:27:29,073 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 15:27:29,073 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:29,073 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:27:29,074 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) [2022-03-20 15:27:29,076 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-20 15:27:29,117 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 15:27:29,118 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:27:29,119 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-20 15:27:29,121 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:27:29,418 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 9 proven. 3 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-03-20 15:27:29,419 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 15:27:29,574 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-20 15:27:29,575 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:27:29,575 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1334306464] [2022-03-20 15:27:29,575 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:27:29,575 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [113293270] [2022-03-20 15:27:29,575 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [113293270] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 15:27:29,575 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 15:27:29,576 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [9] total 11 [2022-03-20 15:27:29,576 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:27:29,576 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1316455236] [2022-03-20 15:27:29,576 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1316455236] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:29,576 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:29,576 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 15:27:29,576 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1889579738] [2022-03-20 15:27:29,577 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:27:29,577 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 15:27:29,577 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:29,577 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 15:27:29,578 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-03-20 15:27:29,578 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 15:27:29,633 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:27:29,633 INFO L93 Difference]: Finished difference Result 68 states and 85 transitions. [2022-03-20 15:27:29,633 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 15:27:29,634 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 45 [2022-03-20 15:27:29,634 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:27:29,635 INFO L225 Difference]: With dead ends: 68 [2022-03-20 15:27:29,635 INFO L226 Difference]: Without dead ends: 66 [2022-03-20 15:27:29,635 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-03-20 15:27:29,636 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 12 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 178 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 15:27:29,637 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [18 Valid, 178 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 15:27:29,637 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-03-20 15:27:29,650 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 64. [2022-03-20 15:27:29,651 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 36 states have (on average 1.1944444444444444) internal successors, (43), 38 states have internal predecessors, (43), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-03-20 15:27:29,652 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 80 transitions. [2022-03-20 15:27:29,652 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 80 transitions. Word has length 45 [2022-03-20 15:27:29,652 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:27:29,652 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 80 transitions. [2022-03-20 15:27:29,652 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 15:27:29,653 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 80 transitions. [2022-03-20 15:27:29,654 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-03-20 15:27:29,654 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:27:29,654 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:27:29,679 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-20 15:27:29,871 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:29,872 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:27:29,872 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:27:29,872 INFO L85 PathProgramCache]: Analyzing trace with hash -1471734606, now seen corresponding path program 1 times [2022-03-20 15:27:29,872 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:29,873 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1420949937] [2022-03-20 15:27:29,873 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:27:29,873 INFO L85 PathProgramCache]: Analyzing trace with hash -1471734606, now seen corresponding path program 2 times [2022-03-20 15:27:29,873 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:27:29,873 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [309357047] [2022-03-20 15:27:29,873 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:27:29,874 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:27:29,886 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:27:29,886 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1816206886] [2022-03-20 15:27:29,886 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 15:27:29,886 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:29,886 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:27:29,889 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) [2022-03-20 15:27:29,894 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-20 15:27:29,945 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 15:27:29,945 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:27:29,946 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 18 conjunts are in the unsatisfiable core [2022-03-20 15:27:29,948 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:27:30,176 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 16 proven. 4 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2022-03-20 15:27:30,176 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 15:27:30,318 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2022-03-20 15:27:30,318 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:27:30,318 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [309357047] [2022-03-20 15:27:30,318 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:27:30,319 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1816206886] [2022-03-20 15:27:30,319 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1816206886] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 15:27:30,319 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 15:27:30,319 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-03-20 15:27:30,319 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:27:30,320 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1420949937] [2022-03-20 15:27:30,320 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1420949937] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:30,320 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:30,320 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 15:27:30,320 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1498943546] [2022-03-20 15:27:30,320 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:27:30,321 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 15:27:30,321 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:30,321 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 15:27:30,321 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-03-20 15:27:30,321 INFO L87 Difference]: Start difference. First operand 64 states and 80 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 15:27:30,373 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:27:30,374 INFO L93 Difference]: Finished difference Result 76 states and 95 transitions. [2022-03-20 15:27:30,374 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 15:27:30,374 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 55 [2022-03-20 15:27:30,374 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:27:30,375 INFO L225 Difference]: With dead ends: 76 [2022-03-20 15:27:30,375 INFO L226 Difference]: Without dead ends: 74 [2022-03-20 15:27:30,376 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 99 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-03-20 15:27:30,377 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 8 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 15:27:30,377 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 141 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 15:27:30,377 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2022-03-20 15:27:30,392 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2022-03-20 15:27:30,394 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 40 states have (on average 1.175) internal successors, (47), 43 states have internal predecessors, (47), 22 states have call successors, (22), 9 states have call predecessors, (22), 8 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-03-20 15:27:30,399 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 88 transitions. [2022-03-20 15:27:30,400 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 88 transitions. Word has length 55 [2022-03-20 15:27:30,400 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:27:30,400 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 88 transitions. [2022-03-20 15:27:30,400 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 15:27:30,400 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 88 transitions. [2022-03-20 15:27:30,401 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-03-20 15:27:30,402 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:27:30,402 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:27:30,426 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-20 15:27:30,602 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:30,602 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:27:30,603 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:27:30,603 INFO L85 PathProgramCache]: Analyzing trace with hash -682689219, now seen corresponding path program 1 times [2022-03-20 15:27:30,603 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:30,603 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [829516062] [2022-03-20 15:27:30,603 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:27:30,604 INFO L85 PathProgramCache]: Analyzing trace with hash -682689219, now seen corresponding path program 2 times [2022-03-20 15:27:30,604 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:27:30,604 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1998245127] [2022-03-20 15:27:30,604 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:27:30,604 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:27:30,612 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:27:30,612 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [519181939] [2022-03-20 15:27:30,613 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 15:27:30,613 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:30,613 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:27:30,614 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) [2022-03-20 15:27:30,616 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-20 15:27:30,654 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 15:27:30,655 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:27:30,655 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 15:27:30,657 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:27:30,782 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-03-20 15:27:30,783 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 15:27:30,783 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:27:30,783 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1998245127] [2022-03-20 15:27:30,783 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:27:30,783 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [519181939] [2022-03-20 15:27:30,783 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [519181939] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:30,783 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:30,784 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 15:27:30,784 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:27:30,784 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [829516062] [2022-03-20 15:27:30,784 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [829516062] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:30,784 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:30,784 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 15:27:30,784 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1237632644] [2022-03-20 15:27:30,784 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:27:30,785 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 15:27:30,785 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:30,785 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 15:27:30,785 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 15:27:30,785 INFO L87 Difference]: Start difference. First operand 71 states and 88 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-03-20 15:27:30,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:27:30,838 INFO L93 Difference]: Finished difference Result 79 states and 96 transitions. [2022-03-20 15:27:30,839 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 15:27:30,839 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 56 [2022-03-20 15:27:30,840 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:27:30,841 INFO L225 Difference]: With dead ends: 79 [2022-03-20 15:27:30,841 INFO L226 Difference]: Without dead ends: 72 [2022-03-20 15:27:30,842 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 52 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 15:27:30,842 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 8 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 15:27:30,843 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 132 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 15:27:30,843 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2022-03-20 15:27:30,854 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 71. [2022-03-20 15:27:30,855 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 41 states have (on average 1.146341463414634) internal successors, (47), 44 states have internal predecessors, (47), 20 states have call successors, (20), 10 states have call predecessors, (20), 9 states have return successors, (18), 16 states have call predecessors, (18), 18 states have call successors, (18) [2022-03-20 15:27:30,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 85 transitions. [2022-03-20 15:27:30,855 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 85 transitions. Word has length 56 [2022-03-20 15:27:30,856 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:27:30,856 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 85 transitions. [2022-03-20 15:27:30,856 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-03-20 15:27:30,856 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 85 transitions. [2022-03-20 15:27:30,858 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-03-20 15:27:30,858 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:27:30,858 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 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, 1, 1, 1, 1, 1] [2022-03-20 15:27:30,885 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-20 15:27:31,079 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:31,080 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:27:31,080 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:27:31,080 INFO L85 PathProgramCache]: Analyzing trace with hash 680531353, now seen corresponding path program 1 times [2022-03-20 15:27:31,080 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:31,080 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1302443969] [2022-03-20 15:27:31,081 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:27:31,081 INFO L85 PathProgramCache]: Analyzing trace with hash 680531353, now seen corresponding path program 2 times [2022-03-20 15:27:31,081 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:27:31,081 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1407795165] [2022-03-20 15:27:31,081 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:27:31,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:27:31,090 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:27:31,090 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1069531528] [2022-03-20 15:27:31,090 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 15:27:31,091 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:31,091 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:27:31,095 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) [2022-03-20 15:27:31,097 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-20 15:27:31,172 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 15:27:31,172 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:27:31,174 INFO L263 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 25 conjunts are in the unsatisfiable core [2022-03-20 15:27:31,176 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:27:31,877 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2022-03-20 15:27:31,878 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 15:27:33,216 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2022-03-20 15:27:33,217 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:27:33,217 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1407795165] [2022-03-20 15:27:33,217 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:27:33,217 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1069531528] [2022-03-20 15:27:33,217 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1069531528] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 15:27:33,218 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 15:27:33,218 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2022-03-20 15:27:33,218 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:27:33,218 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1302443969] [2022-03-20 15:27:33,218 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1302443969] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:33,218 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:33,218 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-03-20 15:27:33,218 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1151055493] [2022-03-20 15:27:33,218 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:27:33,219 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 15:27:33,219 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:33,219 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 15:27:33,219 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2022-03-20 15:27:33,219 INFO L87 Difference]: Start difference. First operand 71 states and 85 transitions. Second operand has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 5 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2022-03-20 15:27:33,391 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:27:33,391 INFO L93 Difference]: Finished difference Result 135 states and 165 transitions. [2022-03-20 15:27:33,391 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 15:27:33,392 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 5 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 75 [2022-03-20 15:27:33,392 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:27:33,393 INFO L225 Difference]: With dead ends: 135 [2022-03-20 15:27:33,394 INFO L226 Difference]: Without dead ends: 108 [2022-03-20 15:27:33,394 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 136 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 36 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2022-03-20 15:27:33,395 INFO L913 BasicCegarLoop]: 47 mSDtfsCounter, 10 mSDsluCounter, 279 mSDsCounter, 0 mSdLazyCounter, 168 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 326 SdHoareTripleChecker+Invalid, 181 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 168 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 15:27:33,395 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 326 Invalid, 181 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 168 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 15:27:33,396 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2022-03-20 15:27:33,412 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 106. [2022-03-20 15:27:33,412 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 64 states have (on average 1.140625) internal successors, (73), 67 states have internal predecessors, (73), 27 states have call successors, (27), 15 states have call predecessors, (27), 14 states have return successors, (25), 23 states have call predecessors, (25), 25 states have call successors, (25) [2022-03-20 15:27:33,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 125 transitions. [2022-03-20 15:27:33,413 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 125 transitions. Word has length 75 [2022-03-20 15:27:33,413 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:27:33,413 INFO L478 AbstractCegarLoop]: Abstraction has 106 states and 125 transitions. [2022-03-20 15:27:33,414 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 5 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2022-03-20 15:27:33,414 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 125 transitions. [2022-03-20 15:27:33,415 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2022-03-20 15:27:33,415 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:27:33,415 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 3, 3, 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, 1, 1, 1] [2022-03-20 15:27:33,439 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-20 15:27:33,638 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:33,639 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:27:33,639 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:27:33,639 INFO L85 PathProgramCache]: Analyzing trace with hash -1566820819, now seen corresponding path program 3 times [2022-03-20 15:27:33,639 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:33,639 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [569303443] [2022-03-20 15:27:33,640 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:27:33,640 INFO L85 PathProgramCache]: Analyzing trace with hash -1566820819, now seen corresponding path program 4 times [2022-03-20 15:27:33,640 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:27:33,640 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [940398776] [2022-03-20 15:27:33,640 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:27:33,640 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:27:33,653 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:27:33,653 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [172615810] [2022-03-20 15:27:33,653 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 15:27:33,653 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:33,653 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:27:33,657 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) [2022-03-20 15:27:33,659 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-20 15:27:33,710 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 15:27:33,710 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:27:33,711 INFO L263 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 17 conjunts are in the unsatisfiable core [2022-03-20 15:27:33,713 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:27:33,958 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 18 proven. 8 refuted. 0 times theorem prover too weak. 156 trivial. 0 not checked. [2022-03-20 15:27:33,958 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 15:27:36,247 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 18 proven. 8 refuted. 0 times theorem prover too weak. 156 trivial. 0 not checked. [2022-03-20 15:27:36,248 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:27:36,248 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [940398776] [2022-03-20 15:27:36,248 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:27:36,248 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [172615810] [2022-03-20 15:27:36,248 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [172615810] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 15:27:36,248 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 15:27:36,248 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 12 [2022-03-20 15:27:36,249 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:27:36,249 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [569303443] [2022-03-20 15:27:36,249 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [569303443] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:36,249 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:36,249 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-03-20 15:27:36,249 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2065223152] [2022-03-20 15:27:36,249 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:27:36,250 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-20 15:27:36,250 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:36,250 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-20 15:27:36,250 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2022-03-20 15:27:36,251 INFO L87 Difference]: Start difference. First operand 106 states and 125 transitions. Second operand has 8 states, 8 states have (on average 2.75) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-03-20 15:27:36,424 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:27:36,424 INFO L93 Difference]: Finished difference Result 133 states and 159 transitions. [2022-03-20 15:27:36,424 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-20 15:27:36,425 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.75) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 80 [2022-03-20 15:27:36,425 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:27:36,426 INFO L225 Difference]: With dead ends: 133 [2022-03-20 15:27:36,426 INFO L226 Difference]: Without dead ends: 110 [2022-03-20 15:27:36,427 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 148 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=48, Invalid=134, Unknown=0, NotChecked=0, Total=182 [2022-03-20 15:27:36,427 INFO L913 BasicCegarLoop]: 53 mSDtfsCounter, 11 mSDsluCounter, 212 mSDsCounter, 0 mSdLazyCounter, 104 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 265 SdHoareTripleChecker+Invalid, 115 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 104 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 15:27:36,427 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 265 Invalid, 115 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 104 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 15:27:36,428 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2022-03-20 15:27:36,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 110. [2022-03-20 15:27:36,441 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 110 states, 66 states have (on average 1.106060606060606) internal successors, (73), 70 states have internal predecessors, (73), 28 states have call successors, (28), 16 states have call predecessors, (28), 15 states have return successors, (25), 23 states have call predecessors, (25), 25 states have call successors, (25) [2022-03-20 15:27:36,442 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 126 transitions. [2022-03-20 15:27:36,442 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 126 transitions. Word has length 80 [2022-03-20 15:27:36,443 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:27:36,443 INFO L478 AbstractCegarLoop]: Abstraction has 110 states and 126 transitions. [2022-03-20 15:27:36,443 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.75) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-03-20 15:27:36,443 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 126 transitions. [2022-03-20 15:27:36,444 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2022-03-20 15:27:36,444 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:27:36,444 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 2, 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, 1, 1, 1, 1] [2022-03-20 15:27:36,470 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-20 15:27:36,667 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:36,667 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:27:36,668 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:27:36,668 INFO L85 PathProgramCache]: Analyzing trace with hash -815356955, now seen corresponding path program 1 times [2022-03-20 15:27:36,668 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:36,668 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2045198022] [2022-03-20 15:27:36,668 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:27:36,668 INFO L85 PathProgramCache]: Analyzing trace with hash -815356955, now seen corresponding path program 2 times [2022-03-20 15:27:36,668 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:27:36,669 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2127046621] [2022-03-20 15:27:36,669 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:27:36,669 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:27:36,677 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:27:36,677 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [253714128] [2022-03-20 15:27:36,678 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 15:27:36,678 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:36,678 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:27:36,679 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) [2022-03-20 15:27:36,680 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-20 15:27:36,728 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 15:27:36,728 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:27:36,729 INFO L263 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 31 conjunts are in the unsatisfiable core [2022-03-20 15:27:36,731 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:27:38,030 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 45 proven. 32 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-03-20 15:27:38,030 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 15:27:51,844 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 45 proven. 32 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-03-20 15:27:51,844 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:27:51,844 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2127046621] [2022-03-20 15:27:51,844 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:27:51,844 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [253714128] [2022-03-20 15:27:51,845 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [253714128] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 15:27:51,845 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 15:27:51,845 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 23 [2022-03-20 15:27:51,845 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:27:51,845 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2045198022] [2022-03-20 15:27:51,845 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2045198022] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:27:51,845 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:27:51,845 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14] imperfect sequences [] total 14 [2022-03-20 15:27:51,845 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [404611223] [2022-03-20 15:27:51,846 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:27:51,846 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-20 15:27:51,846 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:51,846 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-20 15:27:51,847 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=410, Unknown=0, NotChecked=0, Total=506 [2022-03-20 15:27:51,847 INFO L87 Difference]: Start difference. First operand 110 states and 126 transitions. Second operand has 14 states, 13 states have (on average 2.0) internal successors, (26), 11 states have internal predecessors, (26), 7 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) [2022-03-20 15:27:52,958 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:27:52,958 INFO L93 Difference]: Finished difference Result 116 states and 131 transitions. [2022-03-20 15:27:52,958 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-20 15:27:52,959 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.0) internal successors, (26), 11 states have internal predecessors, (26), 7 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) Word has length 86 [2022-03-20 15:27:52,959 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:27:52,959 INFO L225 Difference]: With dead ends: 116 [2022-03-20 15:27:52,960 INFO L226 Difference]: Without dead ends: 88 [2022-03-20 15:27:52,960 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 149 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 109 ImplicationChecksByTransitivity, 6.9s TimeCoverageRelationStatistics Valid=135, Invalid=567, Unknown=0, NotChecked=0, Total=702 [2022-03-20 15:27:52,961 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 17 mSDsluCounter, 306 mSDsCounter, 0 mSdLazyCounter, 304 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 342 SdHoareTripleChecker+Invalid, 319 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 304 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-03-20 15:27:52,961 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [19 Valid, 342 Invalid, 319 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 304 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-03-20 15:27:52,961 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2022-03-20 15:27:52,971 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 88. [2022-03-20 15:27:52,972 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 52 states have (on average 1.1153846153846154) internal successors, (58), 55 states have internal predecessors, (58), 23 states have call successors, (23), 13 states have call predecessors, (23), 12 states have return successors, (21), 19 states have call predecessors, (21), 21 states have call successors, (21) [2022-03-20 15:27:52,972 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 102 transitions. [2022-03-20 15:27:52,972 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 102 transitions. Word has length 86 [2022-03-20 15:27:52,973 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:27:52,973 INFO L478 AbstractCegarLoop]: Abstraction has 88 states and 102 transitions. [2022-03-20 15:27:52,973 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.0) internal successors, (26), 11 states have internal predecessors, (26), 7 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) [2022-03-20 15:27:52,973 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 102 transitions. [2022-03-20 15:27:52,974 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2022-03-20 15:27:52,974 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:27:52,974 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:27:52,999 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-03-20 15:27:53,187 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:53,187 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:27:53,188 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:27:53,188 INFO L85 PathProgramCache]: Analyzing trace with hash 1885636697, now seen corresponding path program 5 times [2022-03-20 15:27:53,188 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:27:53,188 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [140662890] [2022-03-20 15:27:53,188 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:27:53,188 INFO L85 PathProgramCache]: Analyzing trace with hash 1885636697, now seen corresponding path program 6 times [2022-03-20 15:27:53,188 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:27:53,188 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [52256871] [2022-03-20 15:27:53,189 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:27:53,189 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:27:53,196 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:27:53,196 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1107377329] [2022-03-20 15:27:53,197 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 15:27:53,197 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:27:53,197 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:27:53,207 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) [2022-03-20 15:27:53,208 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-20 15:27:53,255 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-03-20 15:27:53,255 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:27:53,256 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 26 conjunts are in the unsatisfiable core [2022-03-20 15:27:53,258 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:28:06,089 INFO L134 CoverageAnalysis]: Checked inductivity of 271 backedges. 55 proven. 9 refuted. 0 times theorem prover too weak. 207 trivial. 0 not checked. [2022-03-20 15:28:06,089 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 15:28:56,898 WARN L232 SmtUtils]: Spent 26.70s on a formula simplification that was a NOOP. DAG size: 51 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 15:29:56,584 INFO L134 CoverageAnalysis]: Checked inductivity of 271 backedges. 45 proven. 19 refuted. 0 times theorem prover too weak. 207 trivial. 0 not checked. [2022-03-20 15:29:56,584 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:29:56,585 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [52256871] [2022-03-20 15:29:56,585 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:29:56,585 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1107377329] [2022-03-20 15:29:56,585 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1107377329] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 15:29:56,585 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 15:29:56,585 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 15 [2022-03-20 15:29:56,585 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:29:56,585 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [140662890] [2022-03-20 15:29:56,586 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [140662890] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:29:56,586 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:29:56,586 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-03-20 15:29:56,586 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [143427463] [2022-03-20 15:29:56,586 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:29:56,586 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-20 15:29:56,586 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:29:56,586 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-20 15:29:56,587 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=162, Unknown=2, NotChecked=0, Total=210 [2022-03-20 15:29:56,587 INFO L87 Difference]: Start difference. First operand 88 states and 102 transitions. Second operand has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 10 states have internal predecessors, (26), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2022-03-20 15:30:00,845 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:30:00,845 INFO L93 Difference]: Finished difference Result 112 states and 130 transitions. [2022-03-20 15:30:00,845 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 15:30:00,846 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 10 states have internal predecessors, (26), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 92 [2022-03-20 15:30:00,846 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:30:00,847 INFO L225 Difference]: With dead ends: 112 [2022-03-20 15:30:00,847 INFO L226 Difference]: Without dead ends: 100 [2022-03-20 15:30:00,847 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 185 GetRequests, 167 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 76 ImplicationChecksByTransitivity, 37.4s TimeCoverageRelationStatistics Valid=59, Invalid=210, Unknown=3, NotChecked=0, Total=272 [2022-03-20 15:30:00,848 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 25 mSDsluCounter, 224 mSDsCounter, 0 mSdLazyCounter, 210 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 259 SdHoareTripleChecker+Invalid, 234 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 210 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-03-20 15:30:00,848 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [37 Valid, 259 Invalid, 234 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 210 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-03-20 15:30:00,848 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2022-03-20 15:30:00,859 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 99. [2022-03-20 15:30:00,859 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 59 states have (on average 1.11864406779661) internal successors, (66), 63 states have internal predecessors, (66), 26 states have call successors, (26), 14 states have call predecessors, (26), 13 states have return successors, (24), 21 states have call predecessors, (24), 24 states have call successors, (24) [2022-03-20 15:30:00,860 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 116 transitions. [2022-03-20 15:30:00,860 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 116 transitions. Word has length 92 [2022-03-20 15:30:00,860 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:30:00,860 INFO L478 AbstractCegarLoop]: Abstraction has 99 states and 116 transitions. [2022-03-20 15:30:00,860 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 10 states have internal predecessors, (26), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2022-03-20 15:30:00,860 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 116 transitions. [2022-03-20 15:30:00,861 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2022-03-20 15:30:00,861 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:30:00,861 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:30:00,895 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-20 15:30:01,075 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-03-20 15:30:01,075 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:30:01,076 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:30:01,076 INFO L85 PathProgramCache]: Analyzing trace with hash -278824083, now seen corresponding path program 7 times [2022-03-20 15:30:01,076 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:30:01,076 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [503856937] [2022-03-20 15:30:01,076 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:30:01,077 INFO L85 PathProgramCache]: Analyzing trace with hash -278824083, now seen corresponding path program 8 times [2022-03-20 15:30:01,077 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:30:01,077 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [241805096] [2022-03-20 15:30:01,077 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:30:01,077 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:30:01,084 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:30:01,084 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1856383797] [2022-03-20 15:30:01,084 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 15:30:01,084 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:30:01,084 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:30:01,095 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) [2022-03-20 15:30:01,096 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-03-20 15:30:01,176 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 15:30:01,176 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:30:01,177 INFO L263 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 23 conjunts are in the unsatisfiable core [2022-03-20 15:30:01,179 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:30:01,590 INFO L134 CoverageAnalysis]: Checked inductivity of 318 backedges. 24 proven. 18 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2022-03-20 15:30:01,590 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 15:30:04,125 INFO L134 CoverageAnalysis]: Checked inductivity of 318 backedges. 24 proven. 18 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2022-03-20 15:30:04,125 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:30:04,125 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [241805096] [2022-03-20 15:30:04,126 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:30:04,126 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1856383797] [2022-03-20 15:30:04,126 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1856383797] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 15:30:04,126 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 15:30:04,126 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2022-03-20 15:30:04,126 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:30:04,126 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [503856937] [2022-03-20 15:30:04,126 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [503856937] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:30:04,126 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:30:04,126 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-03-20 15:30:04,127 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [211054923] [2022-03-20 15:30:04,127 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:30:04,127 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 15:30:04,127 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:30:04,127 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 15:30:04,128 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=131, Unknown=0, NotChecked=0, Total=182 [2022-03-20 15:30:04,128 INFO L87 Difference]: Start difference. First operand 99 states and 116 transitions. Second operand has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 6 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2022-03-20 15:30:04,448 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:30:04,448 INFO L93 Difference]: Finished difference Result 177 states and 223 transitions. [2022-03-20 15:30:04,448 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 15:30:04,448 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 6 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 97 [2022-03-20 15:30:04,450 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:30:04,451 INFO L225 Difference]: With dead ends: 177 [2022-03-20 15:30:04,451 INFO L226 Difference]: Without dead ends: 138 [2022-03-20 15:30:04,452 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 196 GetRequests, 180 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=73, Invalid=199, Unknown=0, NotChecked=0, Total=272 [2022-03-20 15:30:04,452 INFO L913 BasicCegarLoop]: 62 mSDtfsCounter, 13 mSDsluCounter, 338 mSDsCounter, 0 mSdLazyCounter, 198 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 400 SdHoareTripleChecker+Invalid, 215 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 198 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 15:30:04,453 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 400 Invalid, 215 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 198 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 15:30:04,453 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2022-03-20 15:30:04,477 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 138. [2022-03-20 15:30:04,478 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 82 states have (on average 1.1219512195121952) internal successors, (92), 88 states have internal predecessors, (92), 39 states have call successors, (39), 17 states have call predecessors, (39), 16 states have return successors, (36), 32 states have call predecessors, (36), 36 states have call successors, (36) [2022-03-20 15:30:04,480 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 167 transitions. [2022-03-20 15:30:04,480 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 167 transitions. Word has length 97 [2022-03-20 15:30:04,481 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:30:04,481 INFO L478 AbstractCegarLoop]: Abstraction has 138 states and 167 transitions. [2022-03-20 15:30:04,481 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 6 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2022-03-20 15:30:04,481 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 167 transitions. [2022-03-20 15:30:04,483 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2022-03-20 15:30:04,483 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:30:04,483 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:30:04,509 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-03-20 15:30:04,703 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:30:04,703 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:30:04,704 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:30:04,704 INFO L85 PathProgramCache]: Analyzing trace with hash -367001023, now seen corresponding path program 9 times [2022-03-20 15:30:04,704 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:30:04,704 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [960054804] [2022-03-20 15:30:04,704 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:30:04,704 INFO L85 PathProgramCache]: Analyzing trace with hash -367001023, now seen corresponding path program 10 times [2022-03-20 15:30:04,704 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:30:04,705 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1808653392] [2022-03-20 15:30:04,705 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:30:04,705 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:30:04,712 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:30:04,712 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [797275325] [2022-03-20 15:30:04,712 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 15:30:04,712 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:30:04,712 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:30:04,716 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) [2022-03-20 15:30:04,726 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-03-20 15:30:04,770 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 15:30:04,770 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:30:04,771 INFO L263 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 42 conjunts are in the unsatisfiable core [2022-03-20 15:30:04,773 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:30:06,159 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 58 proven. 28 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2022-03-20 15:30:06,160 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 15:30:52,383 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 58 proven. 28 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2022-03-20 15:30:52,383 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:30:52,383 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1808653392] [2022-03-20 15:30:52,383 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:30:52,383 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [797275325] [2022-03-20 15:30:52,384 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [797275325] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 15:30:52,384 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 15:30:52,384 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 25 [2022-03-20 15:30:52,384 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:30:52,384 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [960054804] [2022-03-20 15:30:52,384 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [960054804] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:30:52,384 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:30:52,384 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-03-20 15:30:52,385 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [425156847] [2022-03-20 15:30:52,385 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:30:52,385 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-20 15:30:52,385 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:30:52,385 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-20 15:30:52,386 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=494, Unknown=0, NotChecked=0, Total=600 [2022-03-20 15:30:52,386 INFO L87 Difference]: Start difference. First operand 138 states and 167 transitions. Second operand has 15 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 8 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 6 states have call predecessors, (17), 7 states have call successors, (17) [2022-03-20 15:30:53,599 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:30:53,600 INFO L93 Difference]: Finished difference Result 184 states and 208 transitions. [2022-03-20 15:30:53,600 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-20 15:30:53,600 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 8 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 6 states have call predecessors, (17), 7 states have call successors, (17) Word has length 105 [2022-03-20 15:30:53,600 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:30:53,601 INFO L225 Difference]: With dead ends: 184 [2022-03-20 15:30:53,601 INFO L226 Difference]: Without dead ends: 147 [2022-03-20 15:30:53,602 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 185 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 124 ImplicationChecksByTransitivity, 15.2s TimeCoverageRelationStatistics Valid=119, Invalid=583, Unknown=0, NotChecked=0, Total=702 [2022-03-20 15:30:53,603 INFO L913 BasicCegarLoop]: 47 mSDtfsCounter, 17 mSDsluCounter, 464 mSDsCounter, 0 mSdLazyCounter, 513 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 511 SdHoareTripleChecker+Invalid, 530 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 513 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-03-20 15:30:53,603 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 511 Invalid, 530 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 513 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2022-03-20 15:30:53,603 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 147 states. [2022-03-20 15:30:53,643 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 147 to 147. [2022-03-20 15:30:53,643 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 147 states, 90 states have (on average 1.0888888888888888) internal successors, (98), 95 states have internal predecessors, (98), 36 states have call successors, (36), 21 states have call predecessors, (36), 20 states have return successors, (33), 30 states have call predecessors, (33), 33 states have call successors, (33) [2022-03-20 15:30:53,644 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 147 states to 147 states and 167 transitions. [2022-03-20 15:30:53,644 INFO L78 Accepts]: Start accepts. Automaton has 147 states and 167 transitions. Word has length 105 [2022-03-20 15:30:53,645 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:30:53,645 INFO L478 AbstractCegarLoop]: Abstraction has 147 states and 167 transitions. [2022-03-20 15:30:53,645 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 8 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 6 states have call predecessors, (17), 7 states have call successors, (17) [2022-03-20 15:30:53,645 INFO L276 IsEmpty]: Start isEmpty. Operand 147 states and 167 transitions. [2022-03-20 15:30:53,646 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2022-03-20 15:30:53,646 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:30:53,646 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:30:53,668 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2022-03-20 15:30:53,867 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-03-20 15:30:53,868 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:30:53,868 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:30:53,868 INFO L85 PathProgramCache]: Analyzing trace with hash -1683530195, now seen corresponding path program 11 times [2022-03-20 15:30:53,868 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:30:53,868 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1470073649] [2022-03-20 15:30:53,869 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:30:53,869 INFO L85 PathProgramCache]: Analyzing trace with hash -1683530195, now seen corresponding path program 12 times [2022-03-20 15:30:53,869 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:30:53,869 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1833675271] [2022-03-20 15:30:53,869 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:30:53,869 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:30:53,876 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:30:53,876 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [434345091] [2022-03-20 15:30:53,877 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 15:30:53,877 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:30:53,877 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:30:53,878 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) [2022-03-20 15:30:53,882 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-03-20 15:30:53,957 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2022-03-20 15:30:53,958 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:30:53,959 INFO L263 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 22 conjunts are in the unsatisfiable core [2022-03-20 15:30:53,961 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:30:54,502 INFO L134 CoverageAnalysis]: Checked inductivity of 495 backedges. 96 proven. 4 refuted. 0 times theorem prover too weak. 395 trivial. 0 not checked. [2022-03-20 15:30:54,502 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 15:30:54,791 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:30:54,791 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1833675271] [2022-03-20 15:30:54,791 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:30:54,791 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [434345091] [2022-03-20 15:30:54,791 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [434345091] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 15:30:54,791 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 15:30:54,791 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-03-20 15:30:54,792 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:30:54,792 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1470073649] [2022-03-20 15:30:54,792 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1470073649] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:30:54,792 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:30:54,792 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-03-20 15:30:54,792 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [85836428] [2022-03-20 15:30:54,792 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:30:54,792 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-20 15:30:54,792 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:30:54,792 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-20 15:30:54,793 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2022-03-20 15:30:54,793 INFO L87 Difference]: Start difference. First operand 147 states and 167 transitions. Second operand has 11 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-03-20 15:30:55,141 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:30:55,141 INFO L93 Difference]: Finished difference Result 168 states and 190 transitions. [2022-03-20 15:30:55,141 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-20 15:30:55,142 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 114 [2022-03-20 15:30:55,142 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:30:55,143 INFO L225 Difference]: With dead ends: 168 [2022-03-20 15:30:55,143 INFO L226 Difference]: Without dead ends: 156 [2022-03-20 15:30:55,143 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 105 SyntacticMatches, 2 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2022-03-20 15:30:55,144 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 20 mSDsluCounter, 245 mSDsCounter, 0 mSdLazyCounter, 215 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 288 SdHoareTripleChecker+Invalid, 271 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 215 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 39 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 15:30:55,144 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [26 Valid, 288 Invalid, 271 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 215 Invalid, 0 Unknown, 39 Unchecked, 0.2s Time] [2022-03-20 15:30:55,144 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 156 states. [2022-03-20 15:30:55,161 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 156 to 155. [2022-03-20 15:30:55,162 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 155 states, 95 states have (on average 1.0842105263157895) internal successors, (103), 100 states have internal predecessors, (103), 38 states have call successors, (38), 22 states have call predecessors, (38), 21 states have return successors, (35), 32 states have call predecessors, (35), 35 states have call successors, (35) [2022-03-20 15:30:55,163 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 155 states to 155 states and 176 transitions. [2022-03-20 15:30:55,163 INFO L78 Accepts]: Start accepts. Automaton has 155 states and 176 transitions. Word has length 114 [2022-03-20 15:30:55,163 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:30:55,163 INFO L478 AbstractCegarLoop]: Abstraction has 155 states and 176 transitions. [2022-03-20 15:30:55,164 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-03-20 15:30:55,164 INFO L276 IsEmpty]: Start isEmpty. Operand 155 states and 176 transitions. [2022-03-20 15:30:55,165 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2022-03-20 15:30:55,165 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:30:55,165 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:30:55,191 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-03-20 15:30:55,384 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-03-20 15:30:55,385 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:30:55,385 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:30:55,385 INFO L85 PathProgramCache]: Analyzing trace with hash -1619018179, now seen corresponding path program 3 times [2022-03-20 15:30:55,385 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:30:55,385 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [663774507] [2022-03-20 15:30:55,385 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:30:55,385 INFO L85 PathProgramCache]: Analyzing trace with hash -1619018179, now seen corresponding path program 4 times [2022-03-20 15:30:55,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:30:55,386 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1178114244] [2022-03-20 15:30:55,386 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:30:55,386 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:30:55,398 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:30:55,398 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [398799054] [2022-03-20 15:30:55,398 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 15:30:55,398 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:30:55,398 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:30:55,401 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) [2022-03-20 15:30:55,403 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-03-20 15:30:55,462 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 15:30:55,463 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:30:55,464 INFO L263 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 43 conjunts are in the unsatisfiable core [2022-03-20 15:30:55,466 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:30:56,231 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 15:30:56,338 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 71 proven. 29 refuted. 0 times theorem prover too weak. 390 trivial. 0 not checked. [2022-03-20 15:30:56,338 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 15:30:56,424 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 15:31:07,135 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:31:07,135 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1178114244] [2022-03-20 15:31:07,135 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:31:07,136 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [398799054] [2022-03-20 15:31:07,136 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [398799054] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 15:31:07,136 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 15:31:07,136 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2022-03-20 15:31:07,136 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:31:07,136 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [663774507] [2022-03-20 15:31:07,136 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [663774507] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:31:07,136 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:31:07,136 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-03-20 15:31:07,136 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [236717248] [2022-03-20 15:31:07,136 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:31:07,137 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-20 15:31:07,137 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:31:07,137 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-20 15:31:07,137 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=147, Invalid=503, Unknown=0, NotChecked=0, Total=650 [2022-03-20 15:31:07,137 INFO L87 Difference]: Start difference. First operand 155 states and 176 transitions. Second operand has 15 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 14 states have internal predecessors, (31), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 7 states have call predecessors, (19), 7 states have call successors, (19) [2022-03-20 15:31:08,211 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:31:08,212 INFO L93 Difference]: Finished difference Result 161 states and 181 transitions. [2022-03-20 15:31:08,212 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-03-20 15:31:08,212 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 14 states have internal predecessors, (31), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 7 states have call predecessors, (19), 7 states have call successors, (19) Word has length 116 [2022-03-20 15:31:08,212 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:31:08,213 INFO L225 Difference]: With dead ends: 161 [2022-03-20 15:31:08,213 INFO L226 Difference]: Without dead ends: 124 [2022-03-20 15:31:08,214 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 195 GetRequests, 168 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 125 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=160, Invalid=596, Unknown=0, NotChecked=0, Total=756 [2022-03-20 15:31:08,214 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 15 mSDsluCounter, 395 mSDsCounter, 0 mSdLazyCounter, 436 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 438 SdHoareTripleChecker+Invalid, 450 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 436 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2022-03-20 15:31:08,216 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 438 Invalid, 450 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 436 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2022-03-20 15:31:08,216 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2022-03-20 15:31:08,228 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 124. [2022-03-20 15:31:08,228 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 75 states have (on average 1.0933333333333333) internal successors, (82), 79 states have internal predecessors, (82), 31 states have call successors, (31), 18 states have call predecessors, (31), 17 states have return successors, (29), 26 states have call predecessors, (29), 29 states have call successors, (29) [2022-03-20 15:31:08,228 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 142 transitions. [2022-03-20 15:31:08,229 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 142 transitions. Word has length 116 [2022-03-20 15:31:08,229 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:31:08,229 INFO L478 AbstractCegarLoop]: Abstraction has 124 states and 142 transitions. [2022-03-20 15:31:08,229 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 14 states have internal predecessors, (31), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 7 states have call predecessors, (19), 7 states have call successors, (19) [2022-03-20 15:31:08,229 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 142 transitions. [2022-03-20 15:31:08,231 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 121 [2022-03-20 15:31:08,231 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:31:08,231 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 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] [2022-03-20 15:31:08,255 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2022-03-20 15:31:08,454 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-03-20 15:31:08,454 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:31:08,454 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:31:08,455 INFO L85 PathProgramCache]: Analyzing trace with hash -1921791003, now seen corresponding path program 5 times [2022-03-20 15:31:08,455 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:31:08,455 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [142366807] [2022-03-20 15:31:08,455 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:31:08,455 INFO L85 PathProgramCache]: Analyzing trace with hash -1921791003, now seen corresponding path program 6 times [2022-03-20 15:31:08,455 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:31:08,456 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1753245772] [2022-03-20 15:31:08,456 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:31:08,456 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:31:08,462 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:31:08,462 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1365999117] [2022-03-20 15:31:08,463 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 15:31:08,463 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:31:08,463 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:31:08,466 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) [2022-03-20 15:31:08,488 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-03-20 15:31:08,548 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-03-20 15:31:08,548 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:31:08,549 INFO L263 TraceCheckSpWp]: Trace formula consists of 247 conjuncts, 6 conjunts are in the unsatisfiable core [2022-03-20 15:31:08,550 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:31:08,833 INFO L134 CoverageAnalysis]: Checked inductivity of 558 backedges. 62 proven. 4 refuted. 0 times theorem prover too weak. 492 trivial. 0 not checked. [2022-03-20 15:31:08,833 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 15:31:09,062 INFO L134 CoverageAnalysis]: Checked inductivity of 558 backedges. 57 proven. 4 refuted. 0 times theorem prover too weak. 497 trivial. 0 not checked. [2022-03-20 15:31:09,063 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:31:09,063 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1753245772] [2022-03-20 15:31:09,063 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:31:09,063 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1365999117] [2022-03-20 15:31:09,063 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1365999117] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 15:31:09,063 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 15:31:09,063 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 6 [2022-03-20 15:31:09,063 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:31:09,064 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [142366807] [2022-03-20 15:31:09,064 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [142366807] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:31:09,064 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:31:09,064 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 15:31:09,064 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1803864602] [2022-03-20 15:31:09,064 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:31:09,064 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 15:31:09,064 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:31:09,065 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 15:31:09,065 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2022-03-20 15:31:09,065 INFO L87 Difference]: Start difference. First operand 124 states and 142 transitions. Second operand has 6 states, 6 states have (on average 4.5) internal successors, (27), 6 states have internal predecessors, (27), 6 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) [2022-03-20 15:31:09,129 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:31:09,129 INFO L93 Difference]: Finished difference Result 150 states and 178 transitions. [2022-03-20 15:31:09,130 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-20 15:31:09,130 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.5) internal successors, (27), 6 states have internal predecessors, (27), 6 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) Word has length 120 [2022-03-20 15:31:09,130 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:31:09,131 INFO L225 Difference]: With dead ends: 150 [2022-03-20 15:31:09,131 INFO L226 Difference]: Without dead ends: 137 [2022-03-20 15:31:09,131 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 239 GetRequests, 230 SyntacticMatches, 5 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2022-03-20 15:31:09,132 INFO L913 BasicCegarLoop]: 66 mSDtfsCounter, 20 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 15:31:09,132 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [25 Valid, 112 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 15:31:09,133 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2022-03-20 15:31:09,146 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 137. [2022-03-20 15:31:09,147 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 137 states, 83 states have (on average 1.108433734939759) internal successors, (92), 87 states have internal predecessors, (92), 36 states have call successors, (36), 18 states have call predecessors, (36), 17 states have return successors, (34), 31 states have call predecessors, (34), 34 states have call successors, (34) [2022-03-20 15:31:09,148 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 162 transitions. [2022-03-20 15:31:09,148 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 162 transitions. Word has length 120 [2022-03-20 15:31:09,148 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:31:09,148 INFO L478 AbstractCegarLoop]: Abstraction has 137 states and 162 transitions. [2022-03-20 15:31:09,148 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.5) internal successors, (27), 6 states have internal predecessors, (27), 6 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) [2022-03-20 15:31:09,149 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 162 transitions. [2022-03-20 15:31:09,149 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2022-03-20 15:31:09,150 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:31:09,150 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:31:09,172 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2022-03-20 15:31:09,372 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-03-20 15:31:09,373 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:31:09,373 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:31:09,373 INFO L85 PathProgramCache]: Analyzing trace with hash 515319041, now seen corresponding path program 13 times [2022-03-20 15:31:09,373 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:31:09,373 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1807142133] [2022-03-20 15:31:09,374 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:31:09,374 INFO L85 PathProgramCache]: Analyzing trace with hash 515319041, now seen corresponding path program 14 times [2022-03-20 15:31:09,374 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:31:09,374 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2051429806] [2022-03-20 15:31:09,374 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:31:09,374 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:31:09,381 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:31:09,382 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1891882008] [2022-03-20 15:31:09,382 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 15:31:09,382 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:31:09,382 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:31:09,383 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) [2022-03-20 15:31:09,384 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-03-20 15:31:09,490 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 15:31:09,491 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:31:09,492 INFO L263 TraceCheckSpWp]: Trace formula consists of 274 conjuncts, 46 conjunts are in the unsatisfiable core [2022-03-20 15:31:09,494 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:31:10,363 INFO L134 CoverageAnalysis]: Checked inductivity of 563 backedges. 46 proven. 70 refuted. 0 times theorem prover too weak. 447 trivial. 0 not checked. [2022-03-20 15:31:10,364 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 15:31:47,148 WARN L232 SmtUtils]: Spent 9.70s on a formula simplification that was a NOOP. DAG size: 142 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 15:32:22,685 INFO L134 CoverageAnalysis]: Checked inductivity of 563 backedges. 46 proven. 70 refuted. 0 times theorem prover too weak. 447 trivial. 0 not checked. [2022-03-20 15:32:22,685 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:32:22,685 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2051429806] [2022-03-20 15:32:22,686 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:32:22,686 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1891882008] [2022-03-20 15:32:22,686 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1891882008] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 15:32:22,686 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 15:32:22,686 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 16] total 26 [2022-03-20 15:32:22,686 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:32:22,686 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1807142133] [2022-03-20 15:32:22,686 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1807142133] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:32:22,686 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:32:22,686 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-03-20 15:32:22,686 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [269397569] [2022-03-20 15:32:22,686 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:32:22,687 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-20 15:32:22,687 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:32:22,687 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-20 15:32:22,688 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=136, Invalid=514, Unknown=0, NotChecked=0, Total=650 [2022-03-20 15:32:22,688 INFO L87 Difference]: Start difference. First operand 137 states and 162 transitions. Second operand has 15 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 14 states have internal predecessors, (32), 8 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2022-03-20 15:32:23,595 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:32:23,595 INFO L93 Difference]: Finished difference Result 241 states and 293 transitions. [2022-03-20 15:32:23,596 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-20 15:32:23,596 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 14 states have internal predecessors, (32), 8 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) Word has length 122 [2022-03-20 15:32:23,596 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:32:23,597 INFO L225 Difference]: With dead ends: 241 [2022-03-20 15:32:23,597 INFO L226 Difference]: Without dead ends: 195 [2022-03-20 15:32:23,598 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 245 GetRequests, 217 SyntacticMatches, 2 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 108 ImplicationChecksByTransitivity, 21.9s TimeCoverageRelationStatistics Valid=149, Invalid=607, Unknown=0, NotChecked=0, Total=756 [2022-03-20 15:32:23,598 INFO L913 BasicCegarLoop]: 53 mSDtfsCounter, 18 mSDsluCounter, 465 mSDsCounter, 0 mSdLazyCounter, 569 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 518 SdHoareTripleChecker+Invalid, 592 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 569 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-03-20 15:32:23,598 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [23 Valid, 518 Invalid, 592 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 569 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-03-20 15:32:23,599 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 195 states. [2022-03-20 15:32:23,619 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 195 to 192. [2022-03-20 15:32:23,619 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 192 states, 118 states have (on average 1.1101694915254237) internal successors, (131), 123 states have internal predecessors, (131), 49 states have call successors, (49), 25 states have call predecessors, (49), 24 states have return successors, (47), 43 states have call predecessors, (47), 47 states have call successors, (47) [2022-03-20 15:32:23,620 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 192 states to 192 states and 227 transitions. [2022-03-20 15:32:23,621 INFO L78 Accepts]: Start accepts. Automaton has 192 states and 227 transitions. Word has length 122 [2022-03-20 15:32:23,621 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:32:23,621 INFO L478 AbstractCegarLoop]: Abstraction has 192 states and 227 transitions. [2022-03-20 15:32:23,621 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 14 states have internal predecessors, (32), 8 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2022-03-20 15:32:23,621 INFO L276 IsEmpty]: Start isEmpty. Operand 192 states and 227 transitions. [2022-03-20 15:32:23,622 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2022-03-20 15:32:23,622 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:32:23,622 INFO L499 BasicCegarLoop]: trace histogram [18, 17, 17, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:32:23,639 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-03-20 15:32:23,823 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:32:23,823 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:32:23,824 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:32:23,824 INFO L85 PathProgramCache]: Analyzing trace with hash -1224833083, now seen corresponding path program 15 times [2022-03-20 15:32:23,824 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:32:23,824 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2038441244] [2022-03-20 15:32:23,824 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:32:23,824 INFO L85 PathProgramCache]: Analyzing trace with hash -1224833083, now seen corresponding path program 16 times [2022-03-20 15:32:23,824 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:32:23,825 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1490293027] [2022-03-20 15:32:23,825 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:32:23,825 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:32:23,831 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:32:23,831 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1813076311] [2022-03-20 15:32:23,831 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 15:32:23,832 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:32:23,832 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:32:23,833 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) [2022-03-20 15:32:23,835 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-03-20 15:32:23,887 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 15:32:23,887 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:32:23,888 INFO L263 TraceCheckSpWp]: Trace formula consists of 283 conjuncts, 32 conjunts are in the unsatisfiable core [2022-03-20 15:32:23,891 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:32:24,291 INFO L134 CoverageAnalysis]: Checked inductivity of 631 backedges. 34 proven. 41 refuted. 0 times theorem prover too weak. 556 trivial. 0 not checked. [2022-03-20 15:32:24,291 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 15:32:39,570 INFO L134 CoverageAnalysis]: Checked inductivity of 631 backedges. 34 proven. 41 refuted. 0 times theorem prover too weak. 556 trivial. 0 not checked. [2022-03-20 15:32:39,571 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 15:32:39,571 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1490293027] [2022-03-20 15:32:39,571 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 15:32:39,571 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1813076311] [2022-03-20 15:32:39,571 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1813076311] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 15:32:39,571 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 15:32:39,571 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 19 [2022-03-20 15:32:39,571 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 15:32:39,571 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2038441244] [2022-03-20 15:32:39,571 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2038441244] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 15:32:39,571 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 15:32:39,571 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-03-20 15:32:39,572 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [765190486] [2022-03-20 15:32:39,572 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 15:32:39,572 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-20 15:32:39,572 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 15:32:39,572 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-20 15:32:39,572 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=251, Unknown=0, NotChecked=0, Total=342 [2022-03-20 15:32:39,572 INFO L87 Difference]: Start difference. First operand 192 states and 227 transitions. Second operand has 12 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (21), 8 states have call predecessors, (21), 8 states have call successors, (21) [2022-03-20 15:32:39,897 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 15:32:39,897 INFO L93 Difference]: Finished difference Result 238 states and 285 transitions. [2022-03-20 15:32:39,898 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-20 15:32:39,898 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (21), 8 states have call predecessors, (21), 8 states have call successors, (21) Word has length 127 [2022-03-20 15:32:39,898 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 15:32:39,899 INFO L225 Difference]: With dead ends: 238 [2022-03-20 15:32:39,899 INFO L226 Difference]: Without dead ends: 209 [2022-03-20 15:32:39,900 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 254 GetRequests, 235 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=95, Invalid=285, Unknown=0, NotChecked=0, Total=380 [2022-03-20 15:32:39,900 INFO L913 BasicCegarLoop]: 72 mSDtfsCounter, 12 mSDsluCounter, 502 mSDsCounter, 0 mSdLazyCounter, 337 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 574 SdHoareTripleChecker+Invalid, 351 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 337 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-20 15:32:39,901 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 574 Invalid, 351 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 337 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-20 15:32:39,901 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 209 states. [2022-03-20 15:32:39,922 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 209 to 207. [2022-03-20 15:32:39,922 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 207 states, 128 states have (on average 1.1015625) internal successors, (141), 135 states have internal predecessors, (141), 52 states have call successors, (52), 27 states have call predecessors, (52), 26 states have return successors, (49), 44 states have call predecessors, (49), 49 states have call successors, (49) [2022-03-20 15:32:39,923 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 207 states to 207 states and 242 transitions. [2022-03-20 15:32:39,923 INFO L78 Accepts]: Start accepts. Automaton has 207 states and 242 transitions. Word has length 127 [2022-03-20 15:32:39,923 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 15:32:39,923 INFO L478 AbstractCegarLoop]: Abstraction has 207 states and 242 transitions. [2022-03-20 15:32:39,923 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (21), 8 states have call predecessors, (21), 8 states have call successors, (21) [2022-03-20 15:32:39,924 INFO L276 IsEmpty]: Start isEmpty. Operand 207 states and 242 transitions. [2022-03-20 15:32:39,924 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2022-03-20 15:32:39,924 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 15:32:39,925 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 15:32:39,946 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-03-20 15:32:40,139 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-03-20 15:32:40,139 INFO L403 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 15:32:40,140 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 15:32:40,140 INFO L85 PathProgramCache]: Analyzing trace with hash -243845479, now seen corresponding path program 17 times [2022-03-20 15:32:40,140 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 15:32:40,140 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2131649177] [2022-03-20 15:32:40,140 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 15:32:40,140 INFO L85 PathProgramCache]: Analyzing trace with hash -243845479, now seen corresponding path program 18 times [2022-03-20 15:32:40,140 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 15:32:40,141 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [64744134] [2022-03-20 15:32:40,141 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 15:32:40,141 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 15:32:40,148 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 15:32:40,149 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1982464927] [2022-03-20 15:32:40,149 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 15:32:40,149 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 15:32:40,149 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 15:32:40,150 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) [2022-03-20 15:32:40,151 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-03-20 15:32:40,408 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2022-03-20 15:32:40,408 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 15:32:40,410 INFO L263 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 83 conjunts are in the unsatisfiable core [2022-03-20 15:32:40,413 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 15:32:42,759 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful