/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/ps4-ll_unwindbound10.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 18:18:35,902 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 18:18:35,904 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 18:18:35,958 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 18:18:35,959 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 18:18:35,960 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 18:18:35,963 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 18:18:35,966 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 18:18:35,970 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 18:18:35,974 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 18:18:35,975 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 18:18:35,976 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 18:18:35,976 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 18:18:35,978 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 18:18:35,979 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 18:18:35,982 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 18:18:35,983 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 18:18:35,983 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 18:18:35,985 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 18:18:35,990 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 18:18:35,992 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 18:18:35,993 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 18:18:35,994 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 18:18:35,995 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 18:18:35,996 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 18:18:36,002 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 18:18:36,002 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 18:18:36,002 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 18:18:36,003 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 18:18:36,003 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 18:18:36,005 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 18:18:36,005 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 18:18:36,007 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 18:18:36,007 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 18:18:36,008 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 18:18:36,008 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 18:18:36,009 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 18:18:36,009 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 18:18:36,009 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 18:18:36,009 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 18:18:36,010 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 18:18:36,011 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 18:18:36,012 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-04-06 18:18:36,021 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 18:18:36,021 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 18:18:36,022 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 18:18:36,022 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-06 18:18:36,023 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 18:18:36,023 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-06 18:18:36,023 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 18:18:36,023 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 18:18:36,023 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 18:18:36,024 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 18:18:36,024 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-06 18:18:36,024 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 18:18:36,025 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 18:18:36,025 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 18:18:36,025 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 18:18:36,025 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 18:18:36,025 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-06 18:18:36,025 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 18:18:36,025 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 18:18:36,026 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 18:18:36,026 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-06 18:18:36,026 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-06 18:18:36,026 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-06 18:18:36,026 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-06 18:18:36,026 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-06 18:18:36,026 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-04-06 18:18:36,260 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 18:18:36,296 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 18:18:36,298 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 18:18:36,299 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 18:18:36,301 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 18:18:36,302 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_unwindbound10.c [2022-04-06 18:18:36,365 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8b5033440/015b8c1aebd14cd8acfe9acc89efd607/FLAGb0af1ea77 [2022-04-06 18:18:36,734 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 18:18:36,735 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_unwindbound10.c [2022-04-06 18:18:36,739 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8b5033440/015b8c1aebd14cd8acfe9acc89efd607/FLAGb0af1ea77 [2022-04-06 18:18:36,751 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8b5033440/015b8c1aebd14cd8acfe9acc89efd607 [2022-04-06 18:18:36,753 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 18:18:36,754 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-06 18:18:36,756 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 18:18:36,756 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 18:18:36,761 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 18:18:36,761 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 06:18:36" (1/1) ... [2022-04-06 18:18:36,762 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7bf3a88f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:36, skipping insertion in model container [2022-04-06 18:18:36,762 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 06:18:36" (1/1) ... [2022-04-06 18:18:36,769 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 18:18:36,778 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 18:18:36,914 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/ps4-ll_unwindbound10.c[458,471] [2022-04-06 18:18:36,930 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 18:18:36,937 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 18:18:36,947 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/ps4-ll_unwindbound10.c[458,471] [2022-04-06 18:18:36,952 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 18:18:36,963 INFO L208 MainTranslator]: Completed translation [2022-04-06 18:18:36,963 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:36 WrapperNode [2022-04-06 18:18:36,963 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 18:18:36,964 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 18:18:36,964 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 18:18:36,965 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 18:18:36,973 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:36" (1/1) ... [2022-04-06 18:18:36,973 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:36" (1/1) ... [2022-04-06 18:18:36,978 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:36" (1/1) ... [2022-04-06 18:18:36,979 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:36" (1/1) ... [2022-04-06 18:18:36,982 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:36" (1/1) ... [2022-04-06 18:18:36,985 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:36" (1/1) ... [2022-04-06 18:18:36,986 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:36" (1/1) ... [2022-04-06 18:18:36,987 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 18:18:36,988 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 18:18:36,988 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 18:18:36,988 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 18:18:36,989 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:36" (1/1) ... [2022-04-06 18:18:36,995 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 18:18:37,003 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:37,016 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-04-06 18:18:37,030 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-04-06 18:18:37,064 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 18:18:37,064 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 18:18:37,065 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 18:18:37,065 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 18:18:37,065 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 18:18:37,065 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 18:18:37,065 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 18:18:37,065 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 18:18:37,066 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 18:18:37,066 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 18:18:37,066 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_short [2022-04-06 18:18:37,067 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 18:18:37,067 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 18:18:37,067 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 18:18:37,068 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 18:18:37,068 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 18:18:37,068 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 18:18:37,068 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 18:18:37,068 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 18:18:37,068 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 18:18:37,128 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 18:18:37,129 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 18:18:37,269 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 18:18:37,275 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 18:18:37,275 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-06 18:18:37,283 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 06:18:37 BoogieIcfgContainer [2022-04-06 18:18:37,283 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 18:18:37,284 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 18:18:37,284 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 18:18:37,293 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 18:18:37,293 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 06:18:36" (1/3) ... [2022-04-06 18:18:37,294 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3fc27e70 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 06:18:37, skipping insertion in model container [2022-04-06 18:18:37,294 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:36" (2/3) ... [2022-04-06 18:18:37,294 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3fc27e70 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 06:18:37, skipping insertion in model container [2022-04-06 18:18:37,294 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 06:18:37" (3/3) ... [2022-04-06 18:18:37,295 INFO L111 eAbstractionObserver]: Analyzing ICFG ps4-ll_unwindbound10.c [2022-04-06 18:18:37,300 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-06 18:18:37,300 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 18:18:37,334 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 18:18:37,340 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-04-06 18:18:37,340 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 18:18:37,352 INFO L276 IsEmpty]: Start isEmpty. Operand has 23 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:18:37,357 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-04-06 18:18:37,358 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:37,358 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:37,359 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:37,367 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:37,367 INFO L85 PathProgramCache]: Analyzing trace with hash -2133548928, now seen corresponding path program 1 times [2022-04-06 18:18:37,373 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:37,373 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1506453898] [2022-04-06 18:18:37,382 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:18:37,382 INFO L85 PathProgramCache]: Analyzing trace with hash -2133548928, now seen corresponding path program 2 times [2022-04-06 18:18:37,384 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:37,384 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1157733047] [2022-04-06 18:18:37,384 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:37,385 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:37,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 18:18:37,503 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 18:18:37,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 18:18:37,515 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:37,516 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:37,516 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1157733047] [2022-04-06 18:18:37,516 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1157733047] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:37,517 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:37,517 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 18:18:37,519 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:37,519 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1506453898] [2022-04-06 18:18:37,519 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1506453898] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:37,519 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:37,520 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 18:18:37,520 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2112702101] [2022-04-06 18:18:37,520 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:37,524 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 18:18:37,524 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:37,553 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 18:18:37,554 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 18:18:37,556 INFO L87 Difference]: Start difference. First operand has 23 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 18:18:37,606 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:37,606 INFO L93 Difference]: Finished difference Result 41 states and 55 transitions. [2022-04-06 18:18:37,608 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 18:18:37,609 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2022-04-06 18:18:37,609 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:37,614 INFO L225 Difference]: With dead ends: 41 [2022-04-06 18:18:37,614 INFO L226 Difference]: Without dead ends: 19 [2022-04-06 18:18:37,616 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 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-04-06 18:18:37,619 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:37,620 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 29 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:37,634 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2022-04-06 18:18:37,647 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 18. [2022-04-06 18:18:37,649 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 5 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:37,650 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 21 transitions. [2022-04-06 18:18:37,651 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 21 transitions. Word has length 11 [2022-04-06 18:18:37,651 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:37,651 INFO L478 AbstractCegarLoop]: Abstraction has 18 states and 21 transitions. [2022-04-06 18:18:37,652 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 18:18:37,652 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 21 transitions. [2022-04-06 18:18:37,652 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-06 18:18:37,652 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:37,653 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:37,653 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 18:18:37,653 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:37,654 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:37,654 INFO L85 PathProgramCache]: Analyzing trace with hash -2118701623, now seen corresponding path program 1 times [2022-04-06 18:18:37,654 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:37,654 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [645620851] [2022-04-06 18:18:37,655 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:18:37,655 INFO L85 PathProgramCache]: Analyzing trace with hash -2118701623, now seen corresponding path program 2 times [2022-04-06 18:18:37,655 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:37,656 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1808899879] [2022-04-06 18:18:37,656 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:37,656 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:37,680 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:37,680 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2068821761] [2022-04-06 18:18:37,680 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:37,681 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:37,681 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:37,682 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-04-06 18:18:37,687 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-04-06 18:18:37,753 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-06 18:18:37,753 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:37,756 INFO L263 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-06 18:18:37,761 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:37,859 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:37,860 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 18:18:37,860 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:37,860 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1808899879] [2022-04-06 18:18:37,860 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:37,861 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2068821761] [2022-04-06 18:18:37,862 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2068821761] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:37,862 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:37,862 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-06 18:18:37,863 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:37,863 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [645620851] [2022-04-06 18:18:37,863 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [645620851] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:37,863 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:37,864 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-06 18:18:37,864 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [51418232] [2022-04-06 18:18:37,864 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:37,864 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-06 18:18:37,865 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:37,865 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-06 18:18:37,866 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-06 18:18:37,866 INFO L87 Difference]: Start difference. First operand 18 states and 21 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 18:18:37,884 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:37,884 INFO L93 Difference]: Finished difference Result 28 states and 32 transitions. [2022-04-06 18:18:37,884 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-06 18:18:37,885 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-06 18:18:37,885 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:37,885 INFO L225 Difference]: With dead ends: 28 [2022-04-06 18:18:37,885 INFO L226 Difference]: Without dead ends: 20 [2022-04-06 18:18:37,886 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-06 18:18:37,887 INFO L913 BasicCegarLoop]: 19 mSDtfsCounter, 0 mSDsluCounter, 32 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:37,887 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 51 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:37,888 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2022-04-06 18:18:37,892 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2022-04-06 18:18:37,893 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 5 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:37,894 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 23 transitions. [2022-04-06 18:18:37,894 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 23 transitions. Word has length 12 [2022-04-06 18:18:37,894 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:37,894 INFO L478 AbstractCegarLoop]: Abstraction has 20 states and 23 transitions. [2022-04-06 18:18:37,894 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 18:18:37,895 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 23 transitions. [2022-04-06 18:18:37,895 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-06 18:18:37,895 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:37,895 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:37,918 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-04-06 18:18:38,115 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:38,116 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:38,116 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:38,117 INFO L85 PathProgramCache]: Analyzing trace with hash -2116914163, now seen corresponding path program 1 times [2022-04-06 18:18:38,117 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:38,117 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1871920080] [2022-04-06 18:18:38,118 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:18:38,118 INFO L85 PathProgramCache]: Analyzing trace with hash -2116914163, now seen corresponding path program 2 times [2022-04-06 18:18:38,118 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:38,118 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [977184925] [2022-04-06 18:18:38,119 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:38,119 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:38,156 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:38,156 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1532581312] [2022-04-06 18:18:38,156 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:38,157 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:38,157 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:38,161 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-04-06 18:18:38,162 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-04-06 18:18:38,219 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-06 18:18:38,219 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:38,220 INFO L263 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 18:18:38,222 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:38,285 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:38,285 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 18:18:38,286 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:38,286 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [977184925] [2022-04-06 18:18:38,286 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:38,286 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1532581312] [2022-04-06 18:18:38,286 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1532581312] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:38,287 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:38,287 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 18:18:38,287 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:38,287 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1871920080] [2022-04-06 18:18:38,288 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1871920080] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:38,288 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:38,288 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 18:18:38,288 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [752214349] [2022-04-06 18:18:38,288 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:38,288 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 18:18:38,289 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:38,289 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 18:18:38,289 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 18:18:38,289 INFO L87 Difference]: Start difference. First operand 20 states and 23 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 18:18:38,351 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:38,352 INFO L93 Difference]: Finished difference Result 30 states and 35 transitions. [2022-04-06 18:18:38,352 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 18:18:38,352 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-06 18:18:38,353 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:38,353 INFO L225 Difference]: With dead ends: 30 [2022-04-06 18:18:38,353 INFO L226 Difference]: Without dead ends: 26 [2022-04-06 18:18:38,354 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 8 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-04-06 18:18:38,358 INFO L913 BasicCegarLoop]: 19 mSDtfsCounter, 6 mSDsluCounter, 45 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 64 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:38,359 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 64 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:38,360 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2022-04-06 18:18:38,366 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2022-04-06 18:18:38,366 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.1875) internal successors, (19), 17 states have internal predecessors, (19), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 18:18:38,367 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2022-04-06 18:18:38,367 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 12 [2022-04-06 18:18:38,367 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:38,368 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2022-04-06 18:18:38,368 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 18:18:38,368 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2022-04-06 18:18:38,369 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-04-06 18:18:38,369 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:38,369 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:38,399 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-06 18:18:38,596 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-04-06 18:18:38,597 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:38,597 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:38,597 INFO L85 PathProgramCache]: Analyzing trace with hash -263585780, now seen corresponding path program 1 times [2022-04-06 18:18:38,598 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:38,598 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [22302246] [2022-04-06 18:18:38,619 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:38,619 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:38,620 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:38,620 INFO L85 PathProgramCache]: Analyzing trace with hash -263585780, now seen corresponding path program 2 times [2022-04-06 18:18:38,621 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:38,622 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [589238282] [2022-04-06 18:18:38,622 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:38,622 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:38,662 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:38,662 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [861766569] [2022-04-06 18:18:38,662 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:38,663 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:38,663 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:38,665 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-04-06 18:18:38,666 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-04-06 18:18:38,710 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:38,711 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:38,712 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 18:18:38,713 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:38,795 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:38,795 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:38,886 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:38,886 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:38,886 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [589238282] [2022-04-06 18:18:38,886 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:38,887 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [861766569] [2022-04-06 18:18:38,887 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [861766569] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:38,890 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:38,891 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-04-06 18:18:38,894 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:38,896 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [22302246] [2022-04-06 18:18:38,897 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [22302246] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:38,897 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:38,897 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 18:18:38,897 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [393447932] [2022-04-06 18:18:38,898 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:38,898 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 18:18:38,898 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:38,898 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 18:18:38,899 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-04-06 18:18:38,899 INFO L87 Difference]: Start difference. First operand 26 states and 29 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 18:18:38,939 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:38,939 INFO L93 Difference]: Finished difference Result 36 states and 40 transitions. [2022-04-06 18:18:38,939 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 18:18:38,940 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-04-06 18:18:38,940 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:38,941 INFO L225 Difference]: With dead ends: 36 [2022-04-06 18:18:38,941 INFO L226 Difference]: Without dead ends: 28 [2022-04-06 18:18:38,943 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-04-06 18:18:38,947 INFO L913 BasicCegarLoop]: 20 mSDtfsCounter, 2 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 66 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:38,948 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 66 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:38,951 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2022-04-06 18:18:38,959 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2022-04-06 18:18:38,959 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 18:18:38,960 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 31 transitions. [2022-04-06 18:18:38,960 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 31 transitions. Word has length 20 [2022-04-06 18:18:38,960 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:38,961 INFO L478 AbstractCegarLoop]: Abstraction has 28 states and 31 transitions. [2022-04-06 18:18:38,961 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 18:18:38,961 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 31 transitions. [2022-04-06 18:18:38,961 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-04-06 18:18:38,961 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:38,961 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:38,986 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-04-06 18:18:39,162 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:39,162 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:39,163 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:39,163 INFO L85 PathProgramCache]: Analyzing trace with hash -261798320, now seen corresponding path program 1 times [2022-04-06 18:18:39,163 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:39,163 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1711833808] [2022-04-06 18:18:39,167 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:39,167 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:39,168 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:39,168 INFO L85 PathProgramCache]: Analyzing trace with hash -261798320, now seen corresponding path program 2 times [2022-04-06 18:18:39,168 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:39,168 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1031747683] [2022-04-06 18:18:39,168 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:39,168 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:39,179 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:39,179 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2084402765] [2022-04-06 18:18:39,179 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:39,179 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:39,180 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:39,181 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-04-06 18:18:39,182 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-04-06 18:18:39,221 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:39,221 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:39,222 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-06 18:18:39,224 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:39,323 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:39,323 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:39,537 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-04-06 18:18:39,538 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:39,538 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1031747683] [2022-04-06 18:18:39,538 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:39,538 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2084402765] [2022-04-06 18:18:39,538 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2084402765] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:39,539 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:39,539 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-06 18:18:39,539 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:39,539 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1711833808] [2022-04-06 18:18:39,539 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1711833808] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:39,539 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:39,540 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 18:18:39,540 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [44665068] [2022-04-06 18:18:39,540 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:39,540 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 18:18:39,540 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:39,540 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 18:18:39,541 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-06 18:18:39,541 INFO L87 Difference]: Start difference. First operand 28 states and 31 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 18:18:39,588 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:39,588 INFO L93 Difference]: Finished difference Result 34 states and 36 transitions. [2022-04-06 18:18:39,589 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 18:18:39,589 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-04-06 18:18:39,589 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:39,590 INFO L225 Difference]: With dead ends: 34 [2022-04-06 18:18:39,590 INFO L226 Difference]: Without dead ends: 29 [2022-04-06 18:18:39,590 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 32 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-06 18:18:39,591 INFO L913 BasicCegarLoop]: 17 mSDtfsCounter, 7 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:39,591 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 53 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:39,592 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2022-04-06 18:18:39,597 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2022-04-06 18:18:39,597 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 20 states have (on average 1.1) internal successors, (22), 20 states have internal predecessors, (22), 5 states have call successors, (5), 5 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:39,598 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2022-04-06 18:18:39,598 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 20 [2022-04-06 18:18:39,598 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:39,598 INFO L478 AbstractCegarLoop]: Abstraction has 29 states and 30 transitions. [2022-04-06 18:18:39,599 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 18:18:39,599 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 30 transitions. [2022-04-06 18:18:39,599 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-04-06 18:18:39,599 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:39,599 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:39,626 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-04-06 18:18:39,823 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:39,823 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:39,824 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:39,824 INFO L85 PathProgramCache]: Analyzing trace with hash 891414954, now seen corresponding path program 1 times [2022-04-06 18:18:39,824 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:39,824 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1684919314] [2022-04-06 18:18:39,828 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:39,828 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:39,828 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:39,828 INFO L85 PathProgramCache]: Analyzing trace with hash 891414954, now seen corresponding path program 2 times [2022-04-06 18:18:39,828 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:39,828 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [109773086] [2022-04-06 18:18:39,829 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:39,829 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:39,845 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:39,846 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [311534180] [2022-04-06 18:18:39,846 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:39,846 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:39,846 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:39,847 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-04-06 18:18:39,850 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-04-06 18:18:39,887 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:39,887 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:39,888 INFO L263 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-06 18:18:39,890 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:40,059 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 18:18:40,059 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:40,191 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:40,192 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [109773086] [2022-04-06 18:18:40,192 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:40,192 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [311534180] [2022-04-06 18:18:40,192 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [311534180] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:40,192 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:40,192 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-04-06 18:18:40,192 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:40,192 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1684919314] [2022-04-06 18:18:40,193 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1684919314] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:40,193 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:40,193 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-06 18:18:40,193 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [981443531] [2022-04-06 18:18:40,193 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:40,193 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-06 18:18:40,193 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:40,194 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-06 18:18:40,194 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-04-06 18:18:40,194 INFO L87 Difference]: Start difference. First operand 29 states and 30 transitions. Second operand has 7 states, 6 states have (on average 2.5) internal successors, (15), 6 states have internal predecessors, (15), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:40,256 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:40,256 INFO L93 Difference]: Finished difference Result 36 states and 38 transitions. [2022-04-06 18:18:40,256 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 18:18:40,257 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.5) internal successors, (15), 6 states have internal predecessors, (15), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 26 [2022-04-06 18:18:40,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:40,257 INFO L225 Difference]: With dead ends: 36 [2022-04-06 18:18:40,258 INFO L226 Difference]: Without dead ends: 31 [2022-04-06 18:18:40,258 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 30 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2022-04-06 18:18:40,258 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 2 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:40,259 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 100 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:40,259 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-04-06 18:18:40,265 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2022-04-06 18:18:40,265 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 21 states have (on average 1.0952380952380953) internal successors, (23), 21 states have internal predecessors, (23), 6 states have call successors, (6), 5 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 18:18:40,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 33 transitions. [2022-04-06 18:18:40,266 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 33 transitions. Word has length 26 [2022-04-06 18:18:40,266 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:40,266 INFO L478 AbstractCegarLoop]: Abstraction has 31 states and 33 transitions. [2022-04-06 18:18:40,267 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.5) internal successors, (15), 6 states have internal predecessors, (15), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:40,267 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 33 transitions. [2022-04-06 18:18:40,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-06 18:18:40,267 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:40,268 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:40,297 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-04-06 18:18:40,483 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:40,484 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:40,484 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:40,484 INFO L85 PathProgramCache]: Analyzing trace with hash -1647059121, now seen corresponding path program 3 times [2022-04-06 18:18:40,484 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:40,484 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1018166681] [2022-04-06 18:18:40,488 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:40,488 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:40,488 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:40,488 INFO L85 PathProgramCache]: Analyzing trace with hash -1647059121, now seen corresponding path program 4 times [2022-04-06 18:18:40,489 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:40,489 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [6418231] [2022-04-06 18:18:40,489 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:40,489 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:40,497 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:40,497 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [611666430] [2022-04-06 18:18:40,497 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:18:40,497 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:40,498 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:40,498 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-04-06 18:18:40,500 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-04-06 18:18:40,538 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:18:40,538 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:40,539 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 18:18:40,542 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:40,610 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:40,610 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:40,687 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 18:18:40,687 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:40,687 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [6418231] [2022-04-06 18:18:40,687 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:40,687 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [611666430] [2022-04-06 18:18:40,687 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [611666430] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:40,687 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:40,688 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2022-04-06 18:18:40,688 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:40,688 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1018166681] [2022-04-06 18:18:40,688 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1018166681] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:40,688 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:40,688 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 18:18:40,688 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [835834158] [2022-04-06 18:18:40,688 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:40,689 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 18:18:40,689 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:40,689 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 18:18:40,689 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-04-06 18:18:40,689 INFO L87 Difference]: Start difference. First operand 31 states and 33 transitions. Second operand has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 5 states have internal predecessors, (20), 5 states have call successors, (5), 5 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:40,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:40,724 INFO L93 Difference]: Finished difference Result 42 states and 43 transitions. [2022-04-06 18:18:40,724 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 18:18:40,724 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 5 states have internal predecessors, (20), 5 states have call successors, (5), 5 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 28 [2022-04-06 18:18:40,725 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:40,725 INFO L225 Difference]: With dead ends: 42 [2022-04-06 18:18:40,725 INFO L226 Difference]: Without dead ends: 37 [2022-04-06 18:18:40,726 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 47 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=51, Invalid=81, Unknown=0, NotChecked=0, Total=132 [2022-04-06 18:18:40,726 INFO L913 BasicCegarLoop]: 19 mSDtfsCounter, 4 mSDsluCounter, 45 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 64 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:40,726 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [4 Valid, 64 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:40,727 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2022-04-06 18:18:40,733 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2022-04-06 18:18:40,733 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 26 states have (on average 1.0769230769230769) internal successors, (28), 26 states have internal predecessors, (28), 6 states have call successors, (6), 6 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 18:18:40,734 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 38 transitions. [2022-04-06 18:18:40,734 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 38 transitions. Word has length 28 [2022-04-06 18:18:40,734 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:40,734 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 38 transitions. [2022-04-06 18:18:40,734 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 5 states have internal predecessors, (20), 5 states have call successors, (5), 5 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:40,734 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 38 transitions. [2022-04-06 18:18:40,735 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-04-06 18:18:40,735 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:40,735 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:40,756 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-04-06 18:18:40,947 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:40,947 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:40,948 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:40,948 INFO L85 PathProgramCache]: Analyzing trace with hash 1036651181, now seen corresponding path program 3 times [2022-04-06 18:18:40,948 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:40,948 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [109336509] [2022-04-06 18:18:40,952 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:40,952 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:40,953 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:40,953 INFO L85 PathProgramCache]: Analyzing trace with hash 1036651181, now seen corresponding path program 4 times [2022-04-06 18:18:40,953 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:40,953 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1415493191] [2022-04-06 18:18:40,953 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:40,953 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:40,972 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:40,972 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1618139483] [2022-04-06 18:18:40,972 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:18:40,973 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:40,973 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:40,978 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-04-06 18:18:40,979 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-04-06 18:18:41,054 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:18:41,054 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:41,055 INFO L263 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-06 18:18:41,057 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:41,251 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 12 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 18:18:41,252 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:41,528 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:41,528 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1415493191] [2022-04-06 18:18:41,528 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:41,528 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1618139483] [2022-04-06 18:18:41,528 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1618139483] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:41,528 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:41,528 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-04-06 18:18:41,529 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:41,529 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [109336509] [2022-04-06 18:18:41,529 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [109336509] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:41,529 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:41,529 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-06 18:18:41,529 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1619705857] [2022-04-06 18:18:41,529 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:41,529 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 18:18:41,530 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:41,530 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 18:18:41,530 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2022-04-06 18:18:41,530 INFO L87 Difference]: Start difference. First operand 37 states and 38 transitions. Second operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 18:18:41,612 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:41,613 INFO L93 Difference]: Finished difference Result 44 states and 46 transitions. [2022-04-06 18:18:41,613 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 18:18:41,613 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 34 [2022-04-06 18:18:41,613 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:41,614 INFO L225 Difference]: With dead ends: 44 [2022-04-06 18:18:41,614 INFO L226 Difference]: Without dead ends: 39 [2022-04-06 18:18:41,614 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 44 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2022-04-06 18:18:41,615 INFO L913 BasicCegarLoop]: 26 mSDtfsCounter, 2 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:41,615 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 132 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:18:41,616 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-04-06 18:18:41,621 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2022-04-06 18:18:41,622 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 27 states have (on average 1.0740740740740742) internal successors, (29), 27 states have internal predecessors, (29), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:18:41,622 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 41 transitions. [2022-04-06 18:18:41,622 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 41 transitions. Word has length 34 [2022-04-06 18:18:41,623 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:41,623 INFO L478 AbstractCegarLoop]: Abstraction has 39 states and 41 transitions. [2022-04-06 18:18:41,623 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 18:18:41,623 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 41 transitions. [2022-04-06 18:18:41,624 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-06 18:18:41,624 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:41,624 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:41,631 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-04-06 18:18:41,828 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:41,829 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:41,829 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:41,829 INFO L85 PathProgramCache]: Analyzing trace with hash 486001554, now seen corresponding path program 5 times [2022-04-06 18:18:41,829 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:41,829 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [328073318] [2022-04-06 18:18:41,833 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:41,833 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:41,833 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:41,833 INFO L85 PathProgramCache]: Analyzing trace with hash 486001554, now seen corresponding path program 6 times [2022-04-06 18:18:41,833 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:41,833 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1716350176] [2022-04-06 18:18:41,833 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:41,833 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:41,840 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:41,840 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [230853937] [2022-04-06 18:18:41,840 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:18:41,840 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:41,840 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:41,843 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-04-06 18:18:41,845 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-04-06 18:18:41,893 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-04-06 18:18:41,893 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:41,894 INFO L263 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-06 18:18:41,896 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:41,983 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 6 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:41,983 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:42,095 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 6 proven. 18 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 18:18:42,095 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:42,095 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1716350176] [2022-04-06 18:18:42,095 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:42,095 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [230853937] [2022-04-06 18:18:42,095 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [230853937] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:42,096 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:42,096 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2022-04-06 18:18:42,096 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:42,096 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [328073318] [2022-04-06 18:18:42,096 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [328073318] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:42,096 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:42,096 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-06 18:18:42,096 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2007738062] [2022-04-06 18:18:42,097 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:42,097 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-06 18:18:42,097 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:42,097 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-06 18:18:42,097 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2022-04-06 18:18:42,098 INFO L87 Difference]: Start difference. First operand 39 states and 41 transitions. Second operand has 7 states, 7 states have (on average 3.7142857142857144) internal successors, (26), 6 states have internal predecessors, (26), 6 states have call successors, (6), 6 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 18:18:42,151 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:42,151 INFO L93 Difference]: Finished difference Result 50 states and 51 transitions. [2022-04-06 18:18:42,152 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 18:18:42,152 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.7142857142857144) internal successors, (26), 6 states have internal predecessors, (26), 6 states have call successors, (6), 6 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 36 [2022-04-06 18:18:42,152 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:42,153 INFO L225 Difference]: With dead ends: 50 [2022-04-06 18:18:42,153 INFO L226 Difference]: Without dead ends: 45 [2022-04-06 18:18:42,154 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 61 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=83, Invalid=127, Unknown=0, NotChecked=0, Total=210 [2022-04-06 18:18:42,156 INFO L913 BasicCegarLoop]: 20 mSDtfsCounter, 4 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 70 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:42,156 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [4 Valid, 70 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:42,157 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-04-06 18:18:42,173 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2022-04-06 18:18:42,174 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 32 states have (on average 1.0625) internal successors, (34), 32 states have internal predecessors, (34), 7 states have call successors, (7), 7 states have call predecessors, (7), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:18:42,174 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 46 transitions. [2022-04-06 18:18:42,174 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 46 transitions. Word has length 36 [2022-04-06 18:18:42,175 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:42,175 INFO L478 AbstractCegarLoop]: Abstraction has 45 states and 46 transitions. [2022-04-06 18:18:42,175 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.7142857142857144) internal successors, (26), 6 states have internal predecessors, (26), 6 states have call successors, (6), 6 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 18:18:42,175 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 46 transitions. [2022-04-06 18:18:42,176 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-04-06 18:18:42,176 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:42,176 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:42,202 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-04-06 18:18:42,376 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,SelfDestructingSolverStorable8 [2022-04-06 18:18:42,377 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:42,377 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:42,377 INFO L85 PathProgramCache]: Analyzing trace with hash -1383171920, now seen corresponding path program 5 times [2022-04-06 18:18:42,377 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:42,377 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [52323591] [2022-04-06 18:18:42,380 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:42,380 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:42,380 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:42,380 INFO L85 PathProgramCache]: Analyzing trace with hash -1383171920, now seen corresponding path program 6 times [2022-04-06 18:18:42,380 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:42,381 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1343109752] [2022-04-06 18:18:42,381 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:42,381 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:42,387 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:42,388 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1630240824] [2022-04-06 18:18:42,388 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:18:42,388 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:42,388 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:42,389 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-04-06 18:18:42,390 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-04-06 18:18:42,484 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-04-06 18:18:42,484 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:42,485 INFO L263 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 20 conjunts are in the unsatisfiable core [2022-04-06 18:18:42,487 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:42,658 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 24 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-06 18:18:42,658 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:42,796 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:42,797 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1343109752] [2022-04-06 18:18:42,797 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:42,797 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1630240824] [2022-04-06 18:18:42,797 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1630240824] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:42,797 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:42,797 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-06 18:18:42,798 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:42,798 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [52323591] [2022-04-06 18:18:42,798 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [52323591] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:42,798 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:42,798 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 18:18:42,798 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [553539338] [2022-04-06 18:18:42,798 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:42,798 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 18:18:42,798 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:42,799 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 18:18:42,799 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-06 18:18:42,799 INFO L87 Difference]: Start difference. First operand 45 states and 46 transitions. Second operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:18:42,905 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:42,905 INFO L93 Difference]: Finished difference Result 52 states and 54 transitions. [2022-04-06 18:18:42,906 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 18:18:42,906 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Word has length 42 [2022-04-06 18:18:42,906 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:42,907 INFO L225 Difference]: With dead ends: 52 [2022-04-06 18:18:42,907 INFO L226 Difference]: Without dead ends: 47 [2022-04-06 18:18:42,907 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 44 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2022-04-06 18:18:42,908 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 2 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 102 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 168 SdHoareTripleChecker+Invalid, 102 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 102 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:42,908 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 168 Invalid, 102 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 102 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:18:42,908 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2022-04-06 18:18:42,914 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2022-04-06 18:18:42,914 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 33 states have (on average 1.0606060606060606) internal successors, (35), 33 states have internal predecessors, (35), 8 states have call successors, (8), 7 states have call predecessors, (8), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 18:18:42,915 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 49 transitions. [2022-04-06 18:18:42,915 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 49 transitions. Word has length 42 [2022-04-06 18:18:42,915 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:42,915 INFO L478 AbstractCegarLoop]: Abstraction has 47 states and 49 transitions. [2022-04-06 18:18:42,915 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:18:42,916 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 49 transitions. [2022-04-06 18:18:42,916 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-04-06 18:18:42,916 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:42,916 INFO L499 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:42,937 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-04-06 18:18:43,132 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-04-06 18:18:43,132 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:43,133 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:43,133 INFO L85 PathProgramCache]: Analyzing trace with hash -1386691371, now seen corresponding path program 7 times [2022-04-06 18:18:43,133 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:43,133 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1197317612] [2022-04-06 18:18:43,136 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:43,136 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:43,136 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:43,137 INFO L85 PathProgramCache]: Analyzing trace with hash -1386691371, now seen corresponding path program 8 times [2022-04-06 18:18:43,137 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:43,137 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1576285923] [2022-04-06 18:18:43,137 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:43,137 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:43,154 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:43,154 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1643382063] [2022-04-06 18:18:43,154 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:43,154 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:43,154 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:43,156 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-04-06 18:18:43,161 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-04-06 18:18:43,202 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:43,202 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:43,203 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 18:18:43,204 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:43,300 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:43,300 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:43,441 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-06 18:18:43,442 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:43,442 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1576285923] [2022-04-06 18:18:43,442 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:43,442 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1643382063] [2022-04-06 18:18:43,442 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1643382063] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:43,442 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:43,442 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-04-06 18:18:43,442 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:43,442 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1197317612] [2022-04-06 18:18:43,443 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1197317612] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:43,443 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:43,443 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-06 18:18:43,443 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1383176104] [2022-04-06 18:18:43,443 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:43,443 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 18:18:43,443 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:43,444 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 18:18:43,444 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-06 18:18:43,444 INFO L87 Difference]: Start difference. First operand 47 states and 49 transitions. Second operand has 8 states, 8 states have (on average 4.0) internal successors, (32), 7 states have internal predecessors, (32), 7 states have call successors, (7), 7 states have call predecessors, (7), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:18:43,507 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:43,507 INFO L93 Difference]: Finished difference Result 58 states and 59 transitions. [2022-04-06 18:18:43,509 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 18:18:43,509 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.0) internal successors, (32), 7 states have internal predecessors, (32), 7 states have call successors, (7), 7 states have call predecessors, (7), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Word has length 44 [2022-04-06 18:18:43,509 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:43,510 INFO L225 Difference]: With dead ends: 58 [2022-04-06 18:18:43,510 INFO L226 Difference]: Without dead ends: 53 [2022-04-06 18:18:43,510 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=123, Invalid=183, Unknown=0, NotChecked=0, Total=306 [2022-04-06 18:18:43,511 INFO L913 BasicCegarLoop]: 21 mSDtfsCounter, 8 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:43,511 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 69 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:43,511 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2022-04-06 18:18:43,518 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 53. [2022-04-06 18:18:43,518 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 38 states have (on average 1.0526315789473684) internal successors, (40), 38 states have internal predecessors, (40), 8 states have call successors, (8), 8 states have call predecessors, (8), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 18:18:43,519 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 54 transitions. [2022-04-06 18:18:43,519 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 54 transitions. Word has length 44 [2022-04-06 18:18:43,519 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:43,519 INFO L478 AbstractCegarLoop]: Abstraction has 53 states and 54 transitions. [2022-04-06 18:18:43,519 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.0) internal successors, (32), 7 states have internal predecessors, (32), 7 states have call successors, (7), 7 states have call predecessors, (7), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:18:43,519 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 54 transitions. [2022-04-06 18:18:43,520 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-04-06 18:18:43,520 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:43,520 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:43,546 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-04-06 18:18:43,734 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,SelfDestructingSolverStorable10 [2022-04-06 18:18:43,734 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:43,734 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:43,734 INFO L85 PathProgramCache]: Analyzing trace with hash 1037185971, now seen corresponding path program 7 times [2022-04-06 18:18:43,734 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:43,734 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [276790522] [2022-04-06 18:18:43,737 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:43,737 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:43,737 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:43,737 INFO L85 PathProgramCache]: Analyzing trace with hash 1037185971, now seen corresponding path program 8 times [2022-04-06 18:18:43,738 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:43,738 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1398214472] [2022-04-06 18:18:43,738 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:43,738 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:43,747 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:43,747 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [345143064] [2022-04-06 18:18:43,747 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:43,747 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:43,748 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:43,748 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-04-06 18:18:43,750 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-04-06 18:18:43,873 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:43,873 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:43,875 INFO L263 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 24 conjunts are in the unsatisfiable core [2022-04-06 18:18:43,876 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:44,069 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 10 proven. 40 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-06 18:18:44,070 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:44,213 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:44,214 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1398214472] [2022-04-06 18:18:44,214 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:44,214 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [345143064] [2022-04-06 18:18:44,214 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [345143064] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:44,214 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:44,214 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-04-06 18:18:44,215 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:44,215 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [276790522] [2022-04-06 18:18:44,215 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [276790522] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:44,215 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:44,215 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-04-06 18:18:44,215 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [105864480] [2022-04-06 18:18:44,215 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:44,215 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-06 18:18:44,216 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:44,216 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-06 18:18:44,216 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2022-04-06 18:18:44,216 INFO L87 Difference]: Start difference. First operand 53 states and 54 transitions. Second operand has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 7 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 18:18:44,343 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:44,343 INFO L93 Difference]: Finished difference Result 60 states and 62 transitions. [2022-04-06 18:18:44,343 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 18:18:44,343 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 7 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 50 [2022-04-06 18:18:44,344 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:44,344 INFO L225 Difference]: With dead ends: 60 [2022-04-06 18:18:44,344 INFO L226 Difference]: Without dead ends: 55 [2022-04-06 18:18:44,345 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 51 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2022-04-06 18:18:44,345 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 2 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 139 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 208 SdHoareTripleChecker+Invalid, 139 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 139 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:44,345 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 208 Invalid, 139 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 139 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:18:44,346 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-04-06 18:18:44,353 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-04-06 18:18:44,353 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 39 states have (on average 1.0512820512820513) internal successors, (41), 39 states have internal predecessors, (41), 9 states have call successors, (9), 8 states have call predecessors, (9), 6 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 18:18:44,354 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 57 transitions. [2022-04-06 18:18:44,354 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 57 transitions. Word has length 50 [2022-04-06 18:18:44,354 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:44,354 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 57 transitions. [2022-04-06 18:18:44,354 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 7 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 18:18:44,354 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 57 transitions. [2022-04-06 18:18:44,355 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2022-04-06 18:18:44,355 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:44,355 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:44,363 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-04-06 18:18:44,561 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,SelfDestructingSolverStorable11 [2022-04-06 18:18:44,562 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:44,562 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:44,562 INFO L85 PathProgramCache]: Analyzing trace with hash 999934744, now seen corresponding path program 9 times [2022-04-06 18:18:44,562 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:44,562 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1462745982] [2022-04-06 18:18:44,565 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:44,565 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:44,565 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:44,565 INFO L85 PathProgramCache]: Analyzing trace with hash 999934744, now seen corresponding path program 10 times [2022-04-06 18:18:44,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:44,565 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [190133450] [2022-04-06 18:18:44,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:44,565 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:44,577 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:44,578 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [214092875] [2022-04-06 18:18:44,578 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:18:44,578 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:44,579 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:44,579 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-04-06 18:18:44,581 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-04-06 18:18:44,761 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:18:44,762 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:44,763 INFO L263 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 15 conjunts are in the unsatisfiable core [2022-04-06 18:18:44,764 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:44,910 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 10 proven. 90 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:44,911 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:45,075 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 10 proven. 50 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-06 18:18:45,076 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:45,076 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [190133450] [2022-04-06 18:18:45,076 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:45,076 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [214092875] [2022-04-06 18:18:45,076 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [214092875] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:45,076 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:45,076 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2022-04-06 18:18:45,077 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:45,077 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1462745982] [2022-04-06 18:18:45,077 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1462745982] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:45,077 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:45,077 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 18:18:45,077 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1576692484] [2022-04-06 18:18:45,077 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:45,077 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 18:18:45,077 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:45,078 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 18:18:45,078 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-06 18:18:45,078 INFO L87 Difference]: Start difference. First operand 55 states and 57 transitions. Second operand has 9 states, 9 states have (on average 4.222222222222222) internal successors, (38), 8 states have internal predecessors, (38), 8 states have call successors, (8), 8 states have call predecessors, (8), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 18:18:45,154 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:45,155 INFO L93 Difference]: Finished difference Result 66 states and 67 transitions. [2022-04-06 18:18:45,155 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-06 18:18:45,155 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.222222222222222) internal successors, (38), 8 states have internal predecessors, (38), 8 states have call successors, (8), 8 states have call predecessors, (8), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 52 [2022-04-06 18:18:45,155 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:45,156 INFO L225 Difference]: With dead ends: 66 [2022-04-06 18:18:45,156 INFO L226 Difference]: Without dead ends: 61 [2022-04-06 18:18:45,156 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 90 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=136, Invalid=206, Unknown=0, NotChecked=0, Total=342 [2022-04-06 18:18:45,157 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 2 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:45,157 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 89 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:45,157 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2022-04-06 18:18:45,164 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 61. [2022-04-06 18:18:45,164 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 44 states have (on average 1.0454545454545454) internal successors, (46), 44 states have internal predecessors, (46), 9 states have call successors, (9), 9 states have call predecessors, (9), 7 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 18:18:45,165 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 62 transitions. [2022-04-06 18:18:45,165 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 62 transitions. Word has length 52 [2022-04-06 18:18:45,165 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:45,165 INFO L478 AbstractCegarLoop]: Abstraction has 61 states and 62 transitions. [2022-04-06 18:18:45,165 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.222222222222222) internal successors, (38), 8 states have internal predecessors, (38), 8 states have call successors, (8), 8 states have call predecessors, (8), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 18:18:45,165 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 62 transitions. [2022-04-06 18:18:45,166 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-04-06 18:18:45,166 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:45,166 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:45,179 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-04-06 18:18:45,371 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,SelfDestructingSolverStorable12 [2022-04-06 18:18:45,372 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:45,372 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:45,372 INFO L85 PathProgramCache]: Analyzing trace with hash -1795671114, now seen corresponding path program 9 times [2022-04-06 18:18:45,372 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:45,372 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [194292525] [2022-04-06 18:18:45,375 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:45,375 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:45,375 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:45,375 INFO L85 PathProgramCache]: Analyzing trace with hash -1795671114, now seen corresponding path program 10 times [2022-04-06 18:18:45,375 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:45,375 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1912467597] [2022-04-06 18:18:45,375 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:45,376 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:45,383 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:45,383 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [969463472] [2022-04-06 18:18:45,383 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:18:45,383 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:45,383 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:45,384 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-04-06 18:18:45,390 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-04-06 18:18:45,660 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:18:45,660 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:45,661 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 28 conjunts are in the unsatisfiable core [2022-04-06 18:18:45,663 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:45,900 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 12 proven. 60 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-06 18:18:45,900 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:46,080 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:46,081 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1912467597] [2022-04-06 18:18:46,081 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:46,081 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [969463472] [2022-04-06 18:18:46,081 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [969463472] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:46,081 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:46,081 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-04-06 18:18:46,082 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:46,082 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [194292525] [2022-04-06 18:18:46,082 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [194292525] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:46,082 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:46,082 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-04-06 18:18:46,082 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1063220102] [2022-04-06 18:18:46,082 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:46,083 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-06 18:18:46,083 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:46,083 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-06 18:18:46,083 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2022-04-06 18:18:46,083 INFO L87 Difference]: Start difference. First operand 61 states and 62 transitions. Second operand has 11 states, 10 states have (on average 2.7) internal successors, (27), 10 states have internal predecessors, (27), 8 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 18:18:46,229 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:46,229 INFO L93 Difference]: Finished difference Result 68 states and 70 transitions. [2022-04-06 18:18:46,229 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-06 18:18:46,230 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.7) internal successors, (27), 10 states have internal predecessors, (27), 8 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Word has length 58 [2022-04-06 18:18:46,230 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:46,230 INFO L225 Difference]: With dead ends: 68 [2022-04-06 18:18:46,231 INFO L226 Difference]: Without dead ends: 63 [2022-04-06 18:18:46,231 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 58 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2022-04-06 18:18:46,231 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 2 mSDsluCounter, 214 mSDsCounter, 0 mSdLazyCounter, 182 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 252 SdHoareTripleChecker+Invalid, 182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 182 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:46,232 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 252 Invalid, 182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 182 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:18:46,232 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-04-06 18:18:46,239 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2022-04-06 18:18:46,240 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 45 states have (on average 1.0444444444444445) internal successors, (47), 45 states have internal predecessors, (47), 10 states have call successors, (10), 9 states have call predecessors, (10), 7 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 18:18:46,240 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 65 transitions. [2022-04-06 18:18:46,240 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 65 transitions. Word has length 58 [2022-04-06 18:18:46,241 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:46,241 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 65 transitions. [2022-04-06 18:18:46,241 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.7) internal successors, (27), 10 states have internal predecessors, (27), 8 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 18:18:46,241 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 65 transitions. [2022-04-06 18:18:46,241 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2022-04-06 18:18:46,242 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:46,242 INFO L499 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:46,251 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-04-06 18:18:46,448 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,SelfDestructingSolverStorable13 [2022-04-06 18:18:46,449 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:46,449 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:46,449 INFO L85 PathProgramCache]: Analyzing trace with hash 1633541723, now seen corresponding path program 11 times [2022-04-06 18:18:46,449 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:46,449 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1211804423] [2022-04-06 18:18:46,451 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:46,451 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:46,451 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:46,452 INFO L85 PathProgramCache]: Analyzing trace with hash 1633541723, now seen corresponding path program 12 times [2022-04-06 18:18:46,452 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:46,452 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [325432931] [2022-04-06 18:18:46,452 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:46,452 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:46,459 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:46,459 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1278532410] [2022-04-06 18:18:46,460 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:18:46,460 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:46,460 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:46,461 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-04-06 18:18:46,462 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-04-06 18:18:46,653 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-04-06 18:18:46,654 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:46,657 INFO L263 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-06 18:18:46,659 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:46,819 INFO L134 CoverageAnalysis]: Checked inductivity of 144 backedges. 12 proven. 132 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:46,819 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:46,977 INFO L134 CoverageAnalysis]: Checked inductivity of 144 backedges. 12 proven. 72 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-06 18:18:46,977 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:46,977 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [325432931] [2022-04-06 18:18:46,978 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:46,978 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1278532410] [2022-04-06 18:18:46,978 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1278532410] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:46,978 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:46,978 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2022-04-06 18:18:46,978 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:46,978 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1211804423] [2022-04-06 18:18:46,978 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1211804423] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:46,978 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:46,978 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-04-06 18:18:46,979 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1758388890] [2022-04-06 18:18:46,979 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:46,979 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-06 18:18:46,979 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:46,979 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-06 18:18:46,980 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-06 18:18:46,980 INFO L87 Difference]: Start difference. First operand 63 states and 65 transitions. Second operand has 10 states, 10 states have (on average 4.4) internal successors, (44), 9 states have internal predecessors, (44), 9 states have call successors, (9), 9 states have call predecessors, (9), 7 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 18:18:47,072 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:47,072 INFO L93 Difference]: Finished difference Result 74 states and 75 transitions. [2022-04-06 18:18:47,072 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-04-06 18:18:47,072 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.4) internal successors, (44), 9 states have internal predecessors, (44), 9 states have call successors, (9), 9 states have call predecessors, (9), 7 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Word has length 60 [2022-04-06 18:18:47,073 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:47,073 INFO L225 Difference]: With dead ends: 74 [2022-04-06 18:18:47,073 INFO L226 Difference]: Without dead ends: 69 [2022-04-06 18:18:47,074 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 106 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=149, Invalid=231, Unknown=0, NotChecked=0, Total=380 [2022-04-06 18:18:47,074 INFO L913 BasicCegarLoop]: 23 mSDtfsCounter, 2 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 102 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-04-06 18:18:47,074 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 102 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:47,075 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2022-04-06 18:18:47,081 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 69. [2022-04-06 18:18:47,082 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 50 states have (on average 1.04) internal successors, (52), 50 states have internal predecessors, (52), 10 states have call successors, (10), 10 states have call predecessors, (10), 8 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 18:18:47,082 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 70 transitions. [2022-04-06 18:18:47,082 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 70 transitions. Word has length 60 [2022-04-06 18:18:47,082 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:47,083 INFO L478 AbstractCegarLoop]: Abstraction has 69 states and 70 transitions. [2022-04-06 18:18:47,083 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.4) internal successors, (44), 9 states have internal predecessors, (44), 9 states have call successors, (9), 9 states have call predecessors, (9), 7 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 18:18:47,083 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 70 transitions. [2022-04-06 18:18:47,083 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2022-04-06 18:18:47,083 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:47,083 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:47,092 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-04-06 18:18:47,289 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:47,289 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:47,290 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:47,290 INFO L85 PathProgramCache]: Analyzing trace with hash 1180930233, now seen corresponding path program 11 times [2022-04-06 18:18:47,290 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:47,290 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [586924270] [2022-04-06 18:18:47,292 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:47,292 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:47,292 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:47,292 INFO L85 PathProgramCache]: Analyzing trace with hash 1180930233, now seen corresponding path program 12 times [2022-04-06 18:18:47,292 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:47,292 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1433105010] [2022-04-06 18:18:47,292 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:47,292 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:47,299 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:47,299 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1423173371] [2022-04-06 18:18:47,300 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:18:47,300 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:47,300 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:47,304 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-04-06 18:18:47,305 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-04-06 18:18:47,681 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-04-06 18:18:47,682 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:47,683 INFO L263 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 32 conjunts are in the unsatisfiable core [2022-04-06 18:18:47,688 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:47,986 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 14 proven. 84 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-06 18:18:47,986 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:48,115 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:48,116 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1433105010] [2022-04-06 18:18:48,116 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:48,116 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1423173371] [2022-04-06 18:18:48,116 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1423173371] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:48,116 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:48,116 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-04-06 18:18:48,116 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:48,116 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [586924270] [2022-04-06 18:18:48,116 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [586924270] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:48,116 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:48,116 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-06 18:18:48,116 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [569328936] [2022-04-06 18:18:48,116 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:48,117 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-06 18:18:48,117 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:48,117 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-06 18:18:48,117 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2022-04-06 18:18:48,117 INFO L87 Difference]: Start difference. First operand 69 states and 70 transitions. Second operand has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 18:18:48,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:48,298 INFO L93 Difference]: Finished difference Result 76 states and 78 transitions. [2022-04-06 18:18:48,298 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 18:18:48,298 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Word has length 66 [2022-04-06 18:18:48,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:48,299 INFO L225 Difference]: With dead ends: 76 [2022-04-06 18:18:48,299 INFO L226 Difference]: Without dead ends: 71 [2022-04-06 18:18:48,300 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 65 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=49, Invalid=223, Unknown=0, NotChecked=0, Total=272 [2022-04-06 18:18:48,300 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 2 mSDsluCounter, 258 mSDsCounter, 0 mSdLazyCounter, 231 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 300 SdHoareTripleChecker+Invalid, 231 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 231 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:48,300 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 300 Invalid, 231 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 231 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:18:48,301 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2022-04-06 18:18:48,307 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2022-04-06 18:18:48,308 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 51 states have (on average 1.0392156862745099) internal successors, (53), 51 states have internal predecessors, (53), 11 states have call successors, (11), 10 states have call predecessors, (11), 8 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 18:18:48,308 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 73 transitions. [2022-04-06 18:18:48,308 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 73 transitions. Word has length 66 [2022-04-06 18:18:48,309 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:48,309 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 73 transitions. [2022-04-06 18:18:48,309 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 18:18:48,309 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 73 transitions. [2022-04-06 18:18:48,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2022-04-06 18:18:48,310 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:48,310 INFO L499 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:48,316 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-04-06 18:18:48,516 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,SelfDestructingSolverStorable15 [2022-04-06 18:18:48,516 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:48,516 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:48,516 INFO L85 PathProgramCache]: Analyzing trace with hash 1699217054, now seen corresponding path program 13 times [2022-04-06 18:18:48,516 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:48,516 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1243522534] [2022-04-06 18:18:48,518 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:48,519 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:48,519 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:48,519 INFO L85 PathProgramCache]: Analyzing trace with hash 1699217054, now seen corresponding path program 14 times [2022-04-06 18:18:48,519 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:48,519 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [964951403] [2022-04-06 18:18:48,519 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:48,519 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:48,527 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:48,527 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [180267630] [2022-04-06 18:18:48,527 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:48,527 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:48,528 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:48,529 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-04-06 18:18:48,532 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-04-06 18:18:48,578 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:48,579 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:48,580 INFO L263 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-06 18:18:48,581 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:48,729 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 14 proven. 182 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:48,729 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:48,869 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 14 proven. 98 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-06 18:18:48,869 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:48,869 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [964951403] [2022-04-06 18:18:48,869 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:48,870 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [180267630] [2022-04-06 18:18:48,870 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [180267630] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:48,870 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:48,870 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 14 [2022-04-06 18:18:48,870 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:48,870 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1243522534] [2022-04-06 18:18:48,870 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1243522534] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:48,870 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:48,870 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-04-06 18:18:48,871 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1507543316] [2022-04-06 18:18:48,871 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:48,871 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-06 18:18:48,871 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:48,871 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-06 18:18:48,872 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-06 18:18:48,872 INFO L87 Difference]: Start difference. First operand 71 states and 73 transitions. Second operand has 11 states, 11 states have (on average 4.545454545454546) internal successors, (50), 10 states have internal predecessors, (50), 10 states have call successors, (10), 10 states have call predecessors, (10), 8 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 18:18:48,965 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:48,966 INFO L93 Difference]: Finished difference Result 82 states and 83 transitions. [2022-04-06 18:18:48,966 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-04-06 18:18:48,966 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 4.545454545454546) internal successors, (50), 10 states have internal predecessors, (50), 10 states have call successors, (10), 10 states have call predecessors, (10), 8 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Word has length 68 [2022-04-06 18:18:48,966 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:48,967 INFO L225 Difference]: With dead ends: 82 [2022-04-06 18:18:48,967 INFO L226 Difference]: Without dead ends: 77 [2022-04-06 18:18:48,967 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 122 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=162, Invalid=258, Unknown=0, NotChecked=0, Total=420 [2022-04-06 18:18:48,968 INFO L913 BasicCegarLoop]: 24 mSDtfsCounter, 4 mSDsluCounter, 77 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 45 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:48,968 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [4 Valid, 101 Invalid, 45 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:48,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2022-04-06 18:18:48,975 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2022-04-06 18:18:48,975 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 56 states have (on average 1.0357142857142858) internal successors, (58), 56 states have internal predecessors, (58), 11 states have call successors, (11), 11 states have call predecessors, (11), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 18:18:48,976 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 78 transitions. [2022-04-06 18:18:48,976 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 78 transitions. Word has length 68 [2022-04-06 18:18:48,976 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:48,976 INFO L478 AbstractCegarLoop]: Abstraction has 77 states and 78 transitions. [2022-04-06 18:18:48,977 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 4.545454545454546) internal successors, (50), 10 states have internal predecessors, (50), 10 states have call successors, (10), 10 states have call predecessors, (10), 8 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 18:18:48,977 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 78 transitions. [2022-04-06 18:18:48,977 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2022-04-06 18:18:48,977 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:48,977 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:48,999 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-04-06 18:18:49,191 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-04-06 18:18:49,192 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:49,192 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:49,192 INFO L85 PathProgramCache]: Analyzing trace with hash -763940164, now seen corresponding path program 13 times [2022-04-06 18:18:49,192 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:49,192 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [684649097] [2022-04-06 18:18:49,194 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:49,194 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:49,194 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:49,194 INFO L85 PathProgramCache]: Analyzing trace with hash -763940164, now seen corresponding path program 14 times [2022-04-06 18:18:49,194 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:49,194 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [453504063] [2022-04-06 18:18:49,194 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:49,194 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:49,208 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:49,209 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [564794971] [2022-04-06 18:18:49,209 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:49,209 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:49,209 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:49,210 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:49,211 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-04-06 18:18:49,628 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:49,628 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:49,630 INFO L263 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 36 conjunts are in the unsatisfiable core [2022-04-06 18:18:49,631 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:49,927 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 16 proven. 112 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-06 18:18:49,928 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:50,109 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:50,109 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [453504063] [2022-04-06 18:18:50,109 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:50,109 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [564794971] [2022-04-06 18:18:50,109 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [564794971] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:50,109 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:50,110 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-04-06 18:18:50,110 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:50,110 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [684649097] [2022-04-06 18:18:50,110 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [684649097] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:50,110 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:50,110 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-04-06 18:18:50,110 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1209781386] [2022-04-06 18:18:50,110 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:50,111 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-06 18:18:50,111 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:50,111 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-06 18:18:50,111 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2022-04-06 18:18:50,111 INFO L87 Difference]: Start difference. First operand 77 states and 78 transitions. Second operand has 13 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 10 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 18:18:50,316 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:50,317 INFO L93 Difference]: Finished difference Result 84 states and 86 transitions. [2022-04-06 18:18:50,317 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-06 18:18:50,317 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 10 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 74 [2022-04-06 18:18:50,318 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:50,318 INFO L225 Difference]: With dead ends: 84 [2022-04-06 18:18:50,318 INFO L226 Difference]: Without dead ends: 79 [2022-04-06 18:18:50,319 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 72 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=52, Invalid=254, Unknown=0, NotChecked=0, Total=306 [2022-04-06 18:18:50,319 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 2 mSDsluCounter, 306 mSDsCounter, 0 mSdLazyCounter, 286 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 352 SdHoareTripleChecker+Invalid, 286 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 286 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:50,320 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 352 Invalid, 286 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 286 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 18:18:50,320 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2022-04-06 18:18:50,327 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 79. [2022-04-06 18:18:50,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 57 states have (on average 1.0350877192982457) internal successors, (59), 57 states have internal predecessors, (59), 12 states have call successors, (12), 11 states have call predecessors, (12), 9 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 18:18:50,328 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 81 transitions. [2022-04-06 18:18:50,329 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 81 transitions. Word has length 74 [2022-04-06 18:18:50,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:50,329 INFO L478 AbstractCegarLoop]: Abstraction has 79 states and 81 transitions. [2022-04-06 18:18:50,329 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 10 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 18:18:50,329 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 81 transitions. [2022-04-06 18:18:50,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2022-04-06 18:18:50,330 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:50,330 INFO L499 BasicCegarLoop]: trace histogram [9, 9, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:50,337 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-04-06 18:18:50,537 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-04-06 18:18:50,538 INFO L403 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:50,538 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:50,538 INFO L85 PathProgramCache]: Analyzing trace with hash 989539297, now seen corresponding path program 15 times [2022-04-06 18:18:50,538 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:50,538 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [622394170] [2022-04-06 18:18:50,540 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:50,541 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:50,541 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:50,541 INFO L85 PathProgramCache]: Analyzing trace with hash 989539297, now seen corresponding path program 16 times [2022-04-06 18:18:50,541 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:50,541 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [104895297] [2022-04-06 18:18:50,541 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:50,541 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:50,547 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:50,547 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1439933632] [2022-04-06 18:18:50,547 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:18:50,547 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:50,548 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:50,548 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:50,576 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-04-06 18:18:51,363 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:18:51,363 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:51,365 INFO L263 TraceCheckSpWp]: Trace formula consists of 239 conjuncts, 21 conjunts are in the unsatisfiable core [2022-04-06 18:18:51,366 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:51,524 INFO L134 CoverageAnalysis]: Checked inductivity of 256 backedges. 16 proven. 240 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:51,524 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:51,683 INFO L134 CoverageAnalysis]: Checked inductivity of 256 backedges. 16 proven. 128 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-06 18:18:51,683 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:51,683 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [104895297] [2022-04-06 18:18:51,683 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:51,683 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1439933632] [2022-04-06 18:18:51,684 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1439933632] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:51,684 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:51,684 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 14 [2022-04-06 18:18:51,684 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:51,684 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [622394170] [2022-04-06 18:18:51,684 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [622394170] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:51,684 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:51,684 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-06 18:18:51,684 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1597417037] [2022-04-06 18:18:51,684 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:51,685 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-06 18:18:51,685 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:51,685 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-06 18:18:51,685 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-06 18:18:51,685 INFO L87 Difference]: Start difference. First operand 79 states and 81 transitions. Second operand has 12 states, 12 states have (on average 4.666666666666667) internal successors, (56), 11 states have internal predecessors, (56), 11 states have call successors, (11), 11 states have call predecessors, (11), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 18:18:51,812 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:51,812 INFO L93 Difference]: Finished difference Result 90 states and 91 transitions. [2022-04-06 18:18:51,812 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-04-06 18:18:51,812 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 4.666666666666667) internal successors, (56), 11 states have internal predecessors, (56), 11 states have call successors, (11), 11 states have call predecessors, (11), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 76 [2022-04-06 18:18:51,813 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:51,813 INFO L225 Difference]: With dead ends: 90 [2022-04-06 18:18:51,813 INFO L226 Difference]: Without dead ends: 85 [2022-04-06 18:18:51,813 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 159 GetRequests, 138 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=175, Invalid=287, Unknown=0, NotChecked=0, Total=462 [2022-04-06 18:18:51,814 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 4 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:51,814 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [4 Valid, 128 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:18:51,814 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2022-04-06 18:18:51,822 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 85. [2022-04-06 18:18:51,823 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 62 states have (on average 1.032258064516129) internal successors, (64), 62 states have internal predecessors, (64), 12 states have call successors, (12), 12 states have call predecessors, (12), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 18:18:51,823 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 86 transitions. [2022-04-06 18:18:51,824 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 86 transitions. Word has length 76 [2022-04-06 18:18:51,824 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:51,824 INFO L478 AbstractCegarLoop]: Abstraction has 85 states and 86 transitions. [2022-04-06 18:18:51,824 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 4.666666666666667) internal successors, (56), 11 states have internal predecessors, (56), 11 states have call successors, (11), 11 states have call predecessors, (11), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 18:18:51,824 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 86 transitions. [2022-04-06 18:18:51,825 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-04-06 18:18:51,825 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:51,825 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:51,831 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2022-04-06 18:18:52,031 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:52,032 INFO L403 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:52,032 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:52,032 INFO L85 PathProgramCache]: Analyzing trace with hash -1500110401, now seen corresponding path program 15 times [2022-04-06 18:18:52,032 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:52,032 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [497555994] [2022-04-06 18:18:52,034 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:52,034 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:52,034 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:52,034 INFO L85 PathProgramCache]: Analyzing trace with hash -1500110401, now seen corresponding path program 16 times [2022-04-06 18:18:52,034 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:52,034 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [544386724] [2022-04-06 18:18:52,034 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:52,035 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:52,041 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:52,041 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1934158023] [2022-04-06 18:18:52,041 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:18:52,041 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:52,042 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:52,042 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:52,049 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2022-04-06 18:18:52,627 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:18:52,627 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:52,629 INFO L263 TraceCheckSpWp]: Trace formula consists of 249 conjuncts, 40 conjunts are in the unsatisfiable core [2022-04-06 18:18:52,631 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:52,949 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 18 proven. 144 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-04-06 18:18:52,949 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:53,085 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:53,086 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [544386724] [2022-04-06 18:18:53,086 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:53,086 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1934158023] [2022-04-06 18:18:53,086 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1934158023] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:53,086 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:53,086 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2022-04-06 18:18:53,086 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:53,087 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [497555994] [2022-04-06 18:18:53,087 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [497555994] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:53,087 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:53,087 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14] imperfect sequences [] total 14 [2022-04-06 18:18:53,087 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [410001510] [2022-04-06 18:18:53,087 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:53,087 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-06 18:18:53,087 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:53,087 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-06 18:18:53,088 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2022-04-06 18:18:53,088 INFO L87 Difference]: Start difference. First operand 85 states and 86 transitions. Second operand has 14 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 11 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 18:18:53,334 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:53,334 INFO L93 Difference]: Finished difference Result 92 states and 94 transitions. [2022-04-06 18:18:53,334 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-06 18:18:53,334 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 11 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 82 [2022-04-06 18:18:53,334 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:53,335 INFO L225 Difference]: With dead ends: 92 [2022-04-06 18:18:53,335 INFO L226 Difference]: Without dead ends: 87 [2022-04-06 18:18:53,336 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2022-04-06 18:18:53,336 INFO L913 BasicCegarLoop]: 50 mSDtfsCounter, 2 mSDsluCounter, 358 mSDsCounter, 0 mSdLazyCounter, 347 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 408 SdHoareTripleChecker+Invalid, 347 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 347 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:53,336 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 408 Invalid, 347 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 347 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 18:18:53,337 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2022-04-06 18:18:53,344 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 87. [2022-04-06 18:18:53,345 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 63 states have (on average 1.0317460317460319) internal successors, (65), 63 states have internal predecessors, (65), 13 states have call successors, (13), 12 states have call predecessors, (13), 10 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-06 18:18:53,345 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 89 transitions. [2022-04-06 18:18:53,346 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 89 transitions. Word has length 82 [2022-04-06 18:18:53,346 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:53,346 INFO L478 AbstractCegarLoop]: Abstraction has 87 states and 89 transitions. [2022-04-06 18:18:53,346 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 11 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 18:18:53,346 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 89 transitions. [2022-04-06 18:18:53,347 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2022-04-06 18:18:53,347 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:53,347 INFO L499 BasicCegarLoop]: trace histogram [10, 10, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:53,356 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2022-04-06 18:18:53,551 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:53,552 INFO L403 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:53,552 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:53,552 INFO L85 PathProgramCache]: Analyzing trace with hash -2095421916, now seen corresponding path program 17 times [2022-04-06 18:18:53,552 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:53,552 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1149354254] [2022-04-06 18:18:53,554 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:53,554 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:53,554 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:53,554 INFO L85 PathProgramCache]: Analyzing trace with hash -2095421916, now seen corresponding path program 18 times [2022-04-06 18:18:53,554 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:53,554 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1941841762] [2022-04-06 18:18:53,554 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:53,554 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:53,560 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:53,560 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [466442405] [2022-04-06 18:18:53,560 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:18:53,561 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:53,561 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:53,562 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:53,572 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process