/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/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound1.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 22:32:05,624 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 22:32:05,626 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 22:32:05,662 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 22:32:05,662 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 22:32:05,663 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 22:32:05,664 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 22:32:05,665 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 22:32:05,666 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 22:32:05,667 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 22:32:05,667 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 22:32:05,668 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 22:32:05,668 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 22:32:05,669 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 22:32:05,670 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 22:32:05,671 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 22:32:05,673 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 22:32:05,677 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 22:32:05,679 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 22:32:05,683 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 22:32:05,686 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 22:32:05,687 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 22:32:05,687 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 22:32:05,690 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 22:32:05,691 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 22:32:05,696 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 22:32:05,696 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 22:32:05,696 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 22:32:05,696 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 22:32:05,697 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 22:32:05,698 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 22:32:05,698 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 22:32:05,699 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 22:32:05,699 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 22:32:05,700 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 22:32:05,700 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 22:32:05,700 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 22:32:05,701 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 22:32:05,701 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 22:32:05,701 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 22:32:05,701 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 22:32:05,702 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 22:32:05,703 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-06 22:32:05,711 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 22:32:05,711 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 22:32:05,712 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 22:32:05,713 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 22:32:05,713 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 22:32:05,713 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 22:32:05,713 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 22:32:05,713 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 22:32:05,713 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 22:32:05,714 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 22:32:05,714 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 22:32:05,714 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 22:32:05,714 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 22:32:05,714 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-06 22:32:05,714 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 22:32:05,714 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 22:32:05,714 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 22:32:05,714 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-06 22:32:05,714 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-06 22:32:05,714 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-06 22:32:05,715 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-06 22:32:05,715 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-06 22:32:05,715 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 22:32:05,912 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 22:32:05,929 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 22:32:05,930 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 22:32:05,931 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 22:32:05,931 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 22:32:05,932 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound1.c [2022-04-06 22:32:05,976 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/266bb9122/20a8232aaeb947719ec5c5cf93e350a9/FLAG8eafc4c88 [2022-04-06 22:32:06,384 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 22:32:06,384 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound1.c [2022-04-06 22:32:06,390 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/266bb9122/20a8232aaeb947719ec5c5cf93e350a9/FLAG8eafc4c88 [2022-04-06 22:32:06,401 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/266bb9122/20a8232aaeb947719ec5c5cf93e350a9 [2022-04-06 22:32:06,402 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 22:32:06,403 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-06 22:32:06,405 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 22:32:06,405 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 22:32:06,407 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 22:32:06,407 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 10:32:06" (1/1) ... [2022-04-06 22:32:06,408 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@319705f6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 10:32:06, skipping insertion in model container [2022-04-06 22:32:06,408 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 10:32:06" (1/1) ... [2022-04-06 22:32:06,412 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 22:32:06,422 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 22:32:06,564 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/egcd2-ll_valuebound1.c[490,503] [2022-04-06 22:32:06,609 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 22:32:06,614 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 22:32:06,640 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/egcd2-ll_valuebound1.c[490,503] [2022-04-06 22:32:06,659 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 22:32:06,687 INFO L208 MainTranslator]: Completed translation [2022-04-06 22:32:06,687 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 10:32:06 WrapperNode [2022-04-06 22:32:06,687 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 22:32:06,688 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 22:32:06,688 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 22:32:06,689 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 22:32:06,696 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 10:32:06" (1/1) ... [2022-04-06 22:32:06,697 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 10:32:06" (1/1) ... [2022-04-06 22:32:06,707 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 10:32:06" (1/1) ... [2022-04-06 22:32:06,707 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 10:32:06" (1/1) ... [2022-04-06 22:32:06,718 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 10:32:06" (1/1) ... [2022-04-06 22:32:06,720 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 10:32:06" (1/1) ... [2022-04-06 22:32:06,721 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 10:32:06" (1/1) ... [2022-04-06 22:32:06,722 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 22:32:06,722 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 22:32:06,722 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 22:32:06,722 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 22:32:06,724 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 10:32:06" (1/1) ... [2022-04-06 22:32:06,728 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 22:32:06,734 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 22:32:06,743 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 22:32:06,750 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 22:32:06,786 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 22:32:06,786 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 22:32:06,787 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 22:32:06,787 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 22:32:06,787 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 22:32:06,787 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 22:32:06,787 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 22:32:06,787 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 22:32:06,787 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 22:32:06,787 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 22:32:06,787 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-06 22:32:06,787 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 22:32:06,787 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 22:32:06,788 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 22:32:06,788 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 22:32:06,788 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 22:32:06,788 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 22:32:06,788 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 22:32:06,788 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 22:32:06,788 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 22:32:06,836 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 22:32:06,837 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 22:32:07,013 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 22:32:07,025 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 22:32:07,025 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-06 22:32:07,026 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 10:32:07 BoogieIcfgContainer [2022-04-06 22:32:07,026 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 22:32:07,027 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 22:32:07,027 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 22:32:07,035 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 22:32:07,036 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 10:32:06" (1/3) ... [2022-04-06 22:32:07,036 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@39eecdf9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 10:32:07, skipping insertion in model container [2022-04-06 22:32:07,036 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 10:32:06" (2/3) ... [2022-04-06 22:32:07,036 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@39eecdf9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 10:32:07, skipping insertion in model container [2022-04-06 22:32:07,037 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 10:32:07" (3/3) ... [2022-04-06 22:32:07,037 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll_valuebound1.c [2022-04-06 22:32:07,040 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-06 22:32:07,041 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 22:32:07,072 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 22:32:07,077 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 22:32:07,077 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 22:32:07,085 INFO L276 IsEmpty]: Start isEmpty. Operand has 40 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-06 22:32:07,090 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-04-06 22:32:07,091 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 22:32:07,091 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 22:32:07,091 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 22:32:07,094 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 22:32:07,095 INFO L85 PathProgramCache]: Analyzing trace with hash -587582002, now seen corresponding path program 1 times [2022-04-06 22:32:07,100 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:07,100 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1673971224] [2022-04-06 22:32:07,106 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 22:32:07,107 INFO L85 PathProgramCache]: Analyzing trace with hash -587582002, now seen corresponding path program 2 times [2022-04-06 22:32:07,108 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 22:32:07,108 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [726829785] [2022-04-06 22:32:07,109 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 22:32:07,109 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 22:32:07,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 22:32:07,237 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 22:32:07,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 22:32:07,250 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 22:32:07,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 22:32:07,269 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-06 22:32:07,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 22:32:07,275 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-06 22:32:07,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 22:32:07,282 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-04-06 22:32:07,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 22:32:07,292 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2022-04-06 22:32:07,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 22:32:07,300 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2022-04-06 22:32:07,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 22:32:07,307 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-06 22:32:07,307 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 22:32:07,307 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [726829785] [2022-04-06 22:32:07,308 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [726829785] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:07,308 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:07,308 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 22:32:07,310 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 22:32:07,310 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1673971224] [2022-04-06 22:32:07,310 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1673971224] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:07,310 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:07,310 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 22:32:07,310 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [343871006] [2022-04-06 22:32:07,311 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 22:32:07,313 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 22:32:07,313 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:07,337 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 22:32:07,338 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 22:32:07,339 INFO L87 Difference]: Start difference. First operand has 40 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 22:32:07,430 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 22:32:07,430 INFO L93 Difference]: Finished difference Result 73 states and 118 transitions. [2022-04-06 22:32:07,431 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 22:32:07,432 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 43 [2022-04-06 22:32:07,433 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 22:32:07,437 INFO L225 Difference]: With dead ends: 73 [2022-04-06 22:32:07,437 INFO L226 Difference]: Without dead ends: 35 [2022-04-06 22:32:07,440 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 21 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 22:32:07,443 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 22:32:07,445 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 42 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 22:32:07,455 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-04-06 22:32:07,476 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2022-04-06 22:32:07,477 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 22:32:07,481 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 46 transitions. [2022-04-06 22:32:07,482 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 46 transitions. Word has length 43 [2022-04-06 22:32:07,482 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 22:32:07,483 INFO L478 AbstractCegarLoop]: Abstraction has 35 states and 46 transitions. [2022-04-06 22:32:07,483 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 22:32:07,483 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 46 transitions. [2022-04-06 22:32:07,484 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-04-06 22:32:07,484 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 22:32:07,485 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 22:32:07,486 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 22:32:07,486 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 22:32:07,487 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 22:32:07,487 INFO L85 PathProgramCache]: Analyzing trace with hash 987777007, now seen corresponding path program 1 times [2022-04-06 22:32:07,487 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:07,488 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1958468168] [2022-04-06 22:32:07,491 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 22:32:07,491 INFO L85 PathProgramCache]: Analyzing trace with hash 987777007, now seen corresponding path program 2 times [2022-04-06 22:32:07,491 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 22:32:07,491 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1317171782] [2022-04-06 22:32:07,492 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 22:32:07,492 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 22:32:07,516 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 22:32:07,516 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [371066940] [2022-04-06 22:32:07,516 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 22:32:07,516 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 22:32:07,516 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 22:32:07,518 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 22:32:07,519 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 22:32:07,580 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 22:32:07,581 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 22:32:07,582 INFO L263 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 22:32:07,587 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 22:32:07,721 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-06 22:32:07,721 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 22:32:07,823 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-06 22:32:07,823 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 22:32:07,824 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1317171782] [2022-04-06 22:32:07,824 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 22:32:07,824 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [371066940] [2022-04-06 22:32:07,824 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [371066940] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 22:32:07,824 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 22:32:07,824 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2022-04-06 22:32:07,825 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 22:32:07,825 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1958468168] [2022-04-06 22:32:07,825 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1958468168] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:07,825 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:07,825 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 22:32:07,825 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [336100900] [2022-04-06 22:32:07,825 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 22:32:07,826 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 22:32:07,826 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:07,826 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 22:32:07,826 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-06 22:32:07,827 INFO L87 Difference]: Start difference. First operand 35 states and 46 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 22:32:07,933 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 22:32:07,933 INFO L93 Difference]: Finished difference Result 52 states and 69 transitions. [2022-04-06 22:32:07,934 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 22:32:07,934 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 44 [2022-04-06 22:32:07,934 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 22:32:07,935 INFO L225 Difference]: With dead ends: 52 [2022-04-06 22:32:07,935 INFO L226 Difference]: Without dead ends: 44 [2022-04-06 22:32:07,935 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 81 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-04-06 22:32:07,936 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 19 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 22:32:07,936 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 128 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 22:32:07,937 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-06 22:32:07,944 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-04-06 22:32:07,944 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 19 states have (on average 1.1578947368421053) internal successors, (22), 20 states have internal predecessors, (22), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 22:32:07,945 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 48 transitions. [2022-04-06 22:32:07,945 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 48 transitions. Word has length 44 [2022-04-06 22:32:07,945 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 22:32:07,945 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 48 transitions. [2022-04-06 22:32:07,945 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 22:32:07,945 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 48 transitions. [2022-04-06 22:32:07,946 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-04-06 22:32:07,946 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 22:32:07,946 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 22:32:07,977 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 22:32:08,163 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 22:32:08,163 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 22:32:08,164 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 22:32:08,164 INFO L85 PathProgramCache]: Analyzing trace with hash 561616070, now seen corresponding path program 1 times [2022-04-06 22:32:08,164 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:08,164 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1700326795] [2022-04-06 22:32:08,164 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 22:32:08,165 INFO L85 PathProgramCache]: Analyzing trace with hash 561616070, now seen corresponding path program 2 times [2022-04-06 22:32:08,165 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 22:32:08,165 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1346751078] [2022-04-06 22:32:08,165 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 22:32:08,165 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 22:32:08,175 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 22:32:08,175 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1524164561] [2022-04-06 22:32:08,175 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 22:32:08,176 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 22:32:08,176 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 22:32:08,177 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 22:32:08,178 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 22:32:08,208 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-06 22:32:08,208 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 22:32:08,209 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 8 conjunts are in the unsatisfiable core [2022-04-06 22:32:08,210 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 22:32:08,321 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-06 22:32:08,321 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 22:32:08,321 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 22:32:08,321 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1346751078] [2022-04-06 22:32:08,321 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 22:32:08,322 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1524164561] [2022-04-06 22:32:08,322 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1524164561] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:08,322 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:08,322 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 22:32:08,322 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 22:32:08,322 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1700326795] [2022-04-06 22:32:08,323 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1700326795] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:08,323 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:08,323 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 22:32:08,323 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [609631006] [2022-04-06 22:32:08,323 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 22:32:08,323 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 22:32:08,323 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:08,324 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 22:32:08,324 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 22:32:08,324 INFO L87 Difference]: Start difference. First operand 37 states and 48 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2022-04-06 22:32:08,359 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 22:32:08,360 INFO L93 Difference]: Finished difference Result 50 states and 65 transitions. [2022-04-06 22:32:08,360 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 22:32:08,360 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) Word has length 45 [2022-04-06 22:32:08,360 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 22:32:08,361 INFO L225 Difference]: With dead ends: 50 [2022-04-06 22:32:08,361 INFO L226 Difference]: Without dead ends: 48 [2022-04-06 22:32:08,361 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 41 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 22:32:08,362 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 6 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 22:32:08,363 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 154 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 22:32:08,363 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-04-06 22:32:08,381 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 43. [2022-04-06 22:32:08,381 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 23 states have (on average 1.1304347826086956) internal successors, (26), 25 states have internal predecessors, (26), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-06 22:32:08,382 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 54 transitions. [2022-04-06 22:32:08,382 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 54 transitions. Word has length 45 [2022-04-06 22:32:08,383 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 22:32:08,383 INFO L478 AbstractCegarLoop]: Abstraction has 43 states and 54 transitions. [2022-04-06 22:32:08,383 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), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2022-04-06 22:32:08,383 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 54 transitions. [2022-04-06 22:32:08,384 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-04-06 22:32:08,384 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 22:32:08,384 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 22:32:08,406 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-06 22:32:08,606 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 22:32:08,606 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 22:32:08,606 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 22:32:08,607 INFO L85 PathProgramCache]: Analyzing trace with hash -680064098, now seen corresponding path program 1 times [2022-04-06 22:32:08,607 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:08,607 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1470963259] [2022-04-06 22:32:08,608 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 22:32:08,608 INFO L85 PathProgramCache]: Analyzing trace with hash -680064098, now seen corresponding path program 2 times [2022-04-06 22:32:08,608 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 22:32:08,608 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1243331993] [2022-04-06 22:32:08,608 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 22:32:08,608 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 22:32:08,617 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 22:32:08,618 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1703240095] [2022-04-06 22:32:08,618 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 22:32:08,618 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 22:32:08,618 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 22:32:08,632 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 22:32:08,633 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 22:32:08,696 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 22:32:08,697 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 22:32:08,698 INFO L263 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-06 22:32:08,706 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 22:32:09,002 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 5 proven. 21 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2022-04-06 22:32:09,003 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 22:32:09,049 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 22:32:09,050 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1243331993] [2022-04-06 22:32:09,050 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 22:32:09,050 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1703240095] [2022-04-06 22:32:09,050 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1703240095] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 22:32:09,050 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 22:32:09,050 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-06 22:32:09,051 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 22:32:09,051 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1470963259] [2022-04-06 22:32:09,051 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1470963259] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:09,051 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:09,051 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 22:32:09,051 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [753077536] [2022-04-06 22:32:09,051 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 22:32:09,051 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 22:32:09,052 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:09,052 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 22:32:09,052 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-04-06 22:32:09,052 INFO L87 Difference]: Start difference. First operand 43 states and 54 transitions. Second operand has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2022-04-06 22:32:09,150 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 22:32:09,150 INFO L93 Difference]: Finished difference Result 58 states and 74 transitions. [2022-04-06 22:32:09,150 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 22:32:09,151 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 50 [2022-04-06 22:32:09,151 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 22:32:09,152 INFO L225 Difference]: With dead ends: 58 [2022-04-06 22:32:09,152 INFO L226 Difference]: Without dead ends: 56 [2022-04-06 22:32:09,153 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 45 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2022-04-06 22:32:09,153 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 20 mSDsluCounter, 170 mSDsCounter, 0 mSdLazyCounter, 151 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 210 SdHoareTripleChecker+Invalid, 156 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 151 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 22:32:09,154 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 210 Invalid, 156 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 151 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 22:32:09,154 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2022-04-06 22:32:09,161 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2022-04-06 22:32:09,161 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 32 states have internal predecessors, (33), 20 states have call successors, (20), 6 states have call predecessors, (20), 5 states have return successors, (18), 16 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-06 22:32:09,162 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 71 transitions. [2022-04-06 22:32:09,162 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 71 transitions. Word has length 50 [2022-04-06 22:32:09,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 22:32:09,162 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 71 transitions. [2022-04-06 22:32:09,163 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2022-04-06 22:32:09,163 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 71 transitions. [2022-04-06 22:32:09,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-04-06 22:32:09,164 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 22:32:09,164 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 22:32:09,180 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2022-04-06 22:32:09,376 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 22:32:09,377 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 22:32:09,377 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 22:32:09,377 INFO L85 PathProgramCache]: Analyzing trace with hash 606548870, now seen corresponding path program 1 times [2022-04-06 22:32:09,377 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:09,378 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1489982929] [2022-04-06 22:32:09,378 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 22:32:09,378 INFO L85 PathProgramCache]: Analyzing trace with hash 606548870, now seen corresponding path program 2 times [2022-04-06 22:32:09,378 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 22:32:09,378 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1988389502] [2022-04-06 22:32:09,378 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 22:32:09,379 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 22:32:09,387 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 22:32:09,387 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [508225021] [2022-04-06 22:32:09,388 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 22:32:09,388 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 22:32:09,388 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 22:32:09,389 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 22:32:09,390 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 22:32:09,437 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 22:32:09,438 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 22:32:09,439 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 15 conjunts are in the unsatisfiable core [2022-04-06 22:32:09,440 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 22:32:09,661 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 7 proven. 12 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2022-04-06 22:32:09,661 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 22:32:09,695 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 22:32:09,695 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1988389502] [2022-04-06 22:32:09,695 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 22:32:09,695 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [508225021] [2022-04-06 22:32:09,695 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [508225021] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 22:32:09,695 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 22:32:09,695 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-06 22:32:09,696 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 22:32:09,696 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1489982929] [2022-04-06 22:32:09,696 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1489982929] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:09,696 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:09,696 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 22:32:09,696 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1421950705] [2022-04-06 22:32:09,696 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 22:32:09,696 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 22:32:09,696 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:09,697 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 22:32:09,697 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2022-04-06 22:32:09,697 INFO L87 Difference]: Start difference. First operand 55 states and 71 transitions. Second operand has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2022-04-06 22:32:09,805 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 22:32:09,805 INFO L93 Difference]: Finished difference Result 62 states and 77 transitions. [2022-04-06 22:32:09,805 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 22:32:09,806 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 55 [2022-04-06 22:32:09,806 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 22:32:09,806 INFO L225 Difference]: With dead ends: 62 [2022-04-06 22:32:09,807 INFO L226 Difference]: Without dead ends: 60 [2022-04-06 22:32:09,807 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 50 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-06 22:32:09,807 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 22 mSDsluCounter, 142 mSDsCounter, 0 mSdLazyCounter, 169 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 176 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 169 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 22:32:09,808 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 180 Invalid, 176 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 169 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 22:32:09,808 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2022-04-06 22:32:09,815 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2022-04-06 22:32:09,815 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 32 states have (on average 1.125) internal successors, (36), 35 states have internal predecessors, (36), 20 states have call successors, (20), 7 states have call predecessors, (20), 6 states have return successors, (18), 16 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-06 22:32:09,815 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 74 transitions. [2022-04-06 22:32:09,816 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 74 transitions. Word has length 55 [2022-04-06 22:32:09,816 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 22:32:09,816 INFO L478 AbstractCegarLoop]: Abstraction has 59 states and 74 transitions. [2022-04-06 22:32:09,816 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2022-04-06 22:32:09,816 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 74 transitions. [2022-04-06 22:32:09,817 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2022-04-06 22:32:09,817 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 22:32:09,817 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 22:32:09,855 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2022-04-06 22:32:10,033 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 22:32:10,034 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 22:32:10,034 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 22:32:10,034 INFO L85 PathProgramCache]: Analyzing trace with hash 1584976990, now seen corresponding path program 1 times [2022-04-06 22:32:10,034 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:10,034 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1825379882] [2022-04-06 22:32:10,035 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 22:32:10,035 INFO L85 PathProgramCache]: Analyzing trace with hash 1584976990, now seen corresponding path program 2 times [2022-04-06 22:32:10,035 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 22:32:10,035 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1014464985] [2022-04-06 22:32:10,035 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 22:32:10,035 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 22:32:10,043 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 22:32:10,043 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1352487669] [2022-04-06 22:32:10,043 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 22:32:10,043 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 22:32:10,044 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 22:32:10,044 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 22:32:10,065 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 22:32:10,102 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 22:32:10,102 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 22:32:10,103 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 37 conjunts are in the unsatisfiable core [2022-04-06 22:32:10,105 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 22:32:10,448 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 10 proven. 29 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2022-04-06 22:32:10,449 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 22:32:10,531 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 22:32:10,532 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1014464985] [2022-04-06 22:32:10,532 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 22:32:10,532 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1352487669] [2022-04-06 22:32:10,532 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1352487669] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 22:32:10,532 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 22:32:10,532 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-04-06 22:32:10,532 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 22:32:10,532 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1825379882] [2022-04-06 22:32:10,532 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1825379882] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:10,532 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:10,532 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-04-06 22:32:10,533 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1693557587] [2022-04-06 22:32:10,533 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 22:32:10,534 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-06 22:32:10,534 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:10,534 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-06 22:32:10,535 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2022-04-06 22:32:10,535 INFO L87 Difference]: Start difference. First operand 59 states and 74 transitions. Second operand has 13 states, 12 states have (on average 1.9166666666666667) internal successors, (23), 10 states have internal predecessors, (23), 6 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) [2022-04-06 22:32:10,690 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 22:32:10,691 INFO L93 Difference]: Finished difference Result 68 states and 82 transitions. [2022-04-06 22:32:10,691 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-06 22:32:10,691 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 1.9166666666666667) internal successors, (23), 10 states have internal predecessors, (23), 6 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) Word has length 60 [2022-04-06 22:32:10,693 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 22:32:10,695 INFO L225 Difference]: With dead ends: 68 [2022-04-06 22:32:10,695 INFO L226 Difference]: Without dead ends: 66 [2022-04-06 22:32:10,695 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 50 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=58, Invalid=248, Unknown=0, NotChecked=0, Total=306 [2022-04-06 22:32:10,697 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 36 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 312 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 331 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 312 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 22:32:10,698 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 161 Invalid, 331 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 312 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 22:32:10,698 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-04-06 22:32:10,718 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 63. [2022-04-06 22:32:10,718 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 35 states have (on average 1.1142857142857143) internal successors, (39), 38 states have internal predecessors, (39), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (18), 16 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-06 22:32:10,720 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 77 transitions. [2022-04-06 22:32:10,721 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 77 transitions. Word has length 60 [2022-04-06 22:32:10,721 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 22:32:10,721 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 77 transitions. [2022-04-06 22:32:10,721 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 1.9166666666666667) internal successors, (23), 10 states have internal predecessors, (23), 6 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) [2022-04-06 22:32:10,722 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 77 transitions. [2022-04-06 22:32:10,724 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2022-04-06 22:32:10,724 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 22:32:10,724 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 22:32:10,755 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 22:32:10,956 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 22:32:10,956 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 22:32:10,956 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 22:32:10,957 INFO L85 PathProgramCache]: Analyzing trace with hash -669670075, now seen corresponding path program 1 times [2022-04-06 22:32:10,957 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:10,957 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1952978576] [2022-04-06 22:32:10,957 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 22:32:10,957 INFO L85 PathProgramCache]: Analyzing trace with hash -669670075, now seen corresponding path program 2 times [2022-04-06 22:32:10,958 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 22:32:10,958 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2071977438] [2022-04-06 22:32:10,958 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 22:32:10,958 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 22:32:10,979 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 22:32:10,979 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1310467328] [2022-04-06 22:32:10,979 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 22:32:10,980 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 22:32:10,980 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 22:32:10,986 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 22:32:10,987 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 22:32:11,034 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 22:32:11,034 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 22:32:11,035 INFO L263 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 23 conjunts are in the unsatisfiable core [2022-04-06 22:32:11,037 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 22:32:11,203 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 17 proven. 17 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-06 22:32:11,204 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 22:32:11,336 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 86 trivial. 0 not checked. [2022-04-06 22:32:11,336 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 22:32:11,336 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2071977438] [2022-04-06 22:32:11,336 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 22:32:11,336 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1310467328] [2022-04-06 22:32:11,336 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1310467328] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 22:32:11,336 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 22:32:11,336 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [11] total 12 [2022-04-06 22:32:11,337 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 22:32:11,337 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1952978576] [2022-04-06 22:32:11,337 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1952978576] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:11,337 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:11,337 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 22:32:11,337 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1433612353] [2022-04-06 22:32:11,337 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 22:32:11,337 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 22:32:11,337 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:11,337 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 22:32:11,338 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2022-04-06 22:32:11,338 INFO L87 Difference]: Start difference. First operand 63 states and 77 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2022-04-06 22:32:11,372 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 22:32:11,372 INFO L93 Difference]: Finished difference Result 69 states and 82 transitions. [2022-04-06 22:32:11,372 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 22:32:11,372 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) Word has length 67 [2022-04-06 22:32:11,373 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 22:32:11,373 INFO L225 Difference]: With dead ends: 69 [2022-04-06 22:32:11,373 INFO L226 Difference]: Without dead ends: 67 [2022-04-06 22:32:11,373 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 121 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2022-04-06 22:32:11,374 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 137 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 22:32:11,374 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 137 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 22:32:11,374 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2022-04-06 22:32:11,380 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 59. [2022-04-06 22:32:11,380 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 33 states have (on average 1.121212121212121) internal successors, (37), 34 states have internal predecessors, (37), 18 states have call successors, (18), 8 states have call predecessors, (18), 7 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-06 22:32:11,380 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 71 transitions. [2022-04-06 22:32:11,380 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 71 transitions. Word has length 67 [2022-04-06 22:32:11,381 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 22:32:11,381 INFO L478 AbstractCegarLoop]: Abstraction has 59 states and 71 transitions. [2022-04-06 22:32:11,381 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2022-04-06 22:32:11,381 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 71 transitions. [2022-04-06 22:32:11,381 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2022-04-06 22:32:11,381 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 22:32:11,381 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 22:32:11,397 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2022-04-06 22:32:11,597 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 22:32:11,598 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 22:32:11,598 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 22:32:11,598 INFO L85 PathProgramCache]: Analyzing trace with hash -1682830289, now seen corresponding path program 1 times [2022-04-06 22:32:11,598 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:11,598 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [812711847] [2022-04-06 22:32:11,598 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 22:32:11,599 INFO L85 PathProgramCache]: Analyzing trace with hash -1682830289, now seen corresponding path program 2 times [2022-04-06 22:32:11,599 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 22:32:11,599 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2043746437] [2022-04-06 22:32:11,599 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 22:32:11,599 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 22:32:11,608 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 22:32:11,608 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1498652138] [2022-04-06 22:32:11,608 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 22:32:11,608 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 22:32:11,609 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 22:32:11,623 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 22:32:11,624 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 22:32:11,679 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 22:32:11,679 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 22:32:11,680 INFO L263 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 22:32:11,681 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 22:32:11,798 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-04-06 22:32:11,798 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 22:32:11,933 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-04-06 22:32:11,933 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 22:32:11,934 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2043746437] [2022-04-06 22:32:11,934 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 22:32:11,934 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1498652138] [2022-04-06 22:32:11,934 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1498652138] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 22:32:11,934 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 22:32:11,934 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-04-06 22:32:11,934 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 22:32:11,934 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [812711847] [2022-04-06 22:32:11,934 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [812711847] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:11,934 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:11,934 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-06 22:32:11,934 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [31735168] [2022-04-06 22:32:11,935 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 22:32:11,935 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 22:32:11,935 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:11,935 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 22:32:11,935 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-04-06 22:32:11,935 INFO L87 Difference]: Start difference. First operand 59 states and 71 transitions. Second operand has 8 states, 8 states have (on average 3.0) internal successors, (24), 7 states have internal predecessors, (24), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-04-06 22:32:12,087 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 22:32:12,087 INFO L93 Difference]: Finished difference Result 106 states and 146 transitions. [2022-04-06 22:32:12,087 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 22:32:12,087 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.0) internal successors, (24), 7 states have internal predecessors, (24), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) Word has length 69 [2022-04-06 22:32:12,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 22:32:12,088 INFO L225 Difference]: With dead ends: 106 [2022-04-06 22:32:12,088 INFO L226 Difference]: Without dead ends: 98 [2022-04-06 22:32:12,089 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 129 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2022-04-06 22:32:12,089 INFO L913 BasicCegarLoop]: 60 mSDtfsCounter, 30 mSDsluCounter, 199 mSDsCounter, 0 mSdLazyCounter, 174 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 259 SdHoareTripleChecker+Invalid, 227 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 22:32:12,089 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 259 Invalid, 227 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 174 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 22:32:12,089 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2022-04-06 22:32:12,100 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 89. [2022-04-06 22:32:12,100 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 47 states have (on average 1.1914893617021276) internal successors, (56), 48 states have internal predecessors, (56), 34 states have call successors, (34), 8 states have call predecessors, (34), 7 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2022-04-06 22:32:12,101 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 122 transitions. [2022-04-06 22:32:12,101 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 122 transitions. Word has length 69 [2022-04-06 22:32:12,101 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 22:32:12,101 INFO L478 AbstractCegarLoop]: Abstraction has 89 states and 122 transitions. [2022-04-06 22:32:12,101 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.0) internal successors, (24), 7 states have internal predecessors, (24), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-04-06 22:32:12,102 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 122 transitions. [2022-04-06 22:32:12,102 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-04-06 22:32:12,102 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 22:32:12,102 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 22:32:12,126 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2022-04-06 22:32:12,326 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 22:32:12,327 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 22:32:12,327 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 22:32:12,327 INFO L85 PathProgramCache]: Analyzing trace with hash 376741854, now seen corresponding path program 1 times [2022-04-06 22:32:12,327 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:12,327 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1658093290] [2022-04-06 22:32:12,327 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 22:32:12,328 INFO L85 PathProgramCache]: Analyzing trace with hash 376741854, now seen corresponding path program 2 times [2022-04-06 22:32:12,328 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 22:32:12,328 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1641287436] [2022-04-06 22:32:12,328 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 22:32:12,328 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 22:32:12,335 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 22:32:12,335 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2122006607] [2022-04-06 22:32:12,336 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 22:32:12,336 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 22:32:12,336 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 22:32:12,336 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 22:32:12,339 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 22:32:12,389 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 22:32:12,389 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 22:32:12,390 INFO L263 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-06 22:32:12,391 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 22:32:12,545 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 35 proven. 18 refuted. 0 times theorem prover too weak. 62 trivial. 0 not checked. [2022-04-06 22:32:12,545 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 22:32:12,725 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 21 proven. 18 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2022-04-06 22:32:12,725 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 22:32:12,725 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1641287436] [2022-04-06 22:32:12,725 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 22:32:12,725 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2122006607] [2022-04-06 22:32:12,725 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2122006607] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 22:32:12,725 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 22:32:12,725 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2022-04-06 22:32:12,726 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 22:32:12,726 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1658093290] [2022-04-06 22:32:12,726 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1658093290] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:12,726 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:12,726 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-06 22:32:12,726 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1802898238] [2022-04-06 22:32:12,726 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 22:32:12,726 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 22:32:12,726 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:12,727 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 22:32:12,727 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2022-04-06 22:32:12,727 INFO L87 Difference]: Start difference. First operand 89 states and 122 transitions. Second operand has 8 states, 7 states have (on average 3.857142857142857) internal successors, (27), 6 states have internal predecessors, (27), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) [2022-04-06 22:32:12,820 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 22:32:12,820 INFO L93 Difference]: Finished difference Result 111 states and 149 transitions. [2022-04-06 22:32:12,820 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 22:32:12,820 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 3.857142857142857) internal successors, (27), 6 states have internal predecessors, (27), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) Word has length 75 [2022-04-06 22:32:12,820 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 22:32:12,821 INFO L225 Difference]: With dead ends: 111 [2022-04-06 22:32:12,821 INFO L226 Difference]: Without dead ends: 66 [2022-04-06 22:32:12,821 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 152 GetRequests, 138 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=55, Invalid=185, Unknown=0, NotChecked=0, Total=240 [2022-04-06 22:32:12,822 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 21 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 129 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 178 SdHoareTripleChecker+Invalid, 151 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 129 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 22:32:12,822 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 178 Invalid, 151 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 129 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 22:32:12,822 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-04-06 22:32:12,828 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 65. [2022-04-06 22:32:12,828 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 35 states have (on average 1.1142857142857143) internal successors, (39), 36 states have internal predecessors, (39), 22 states have call successors, (22), 8 states have call predecessors, (22), 7 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2022-04-06 22:32:12,829 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 81 transitions. [2022-04-06 22:32:12,829 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 81 transitions. Word has length 75 [2022-04-06 22:32:12,829 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 22:32:12,829 INFO L478 AbstractCegarLoop]: Abstraction has 65 states and 81 transitions. [2022-04-06 22:32:12,829 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 3.857142857142857) internal successors, (27), 6 states have internal predecessors, (27), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) [2022-04-06 22:32:12,829 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 81 transitions. [2022-04-06 22:32:12,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-04-06 22:32:12,830 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 22:32:12,830 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 22:32:12,874 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 22:32:13,046 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 22:32:13,046 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 22:32:13,047 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 22:32:13,047 INFO L85 PathProgramCache]: Analyzing trace with hash -686534738, now seen corresponding path program 1 times [2022-04-06 22:32:13,047 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:13,048 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [601422870] [2022-04-06 22:32:13,048 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 22:32:13,048 INFO L85 PathProgramCache]: Analyzing trace with hash -686534738, now seen corresponding path program 2 times [2022-04-06 22:32:13,048 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 22:32:13,048 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1547810096] [2022-04-06 22:32:13,048 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 22:32:13,048 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 22:32:13,056 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 22:32:13,056 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [269279156] [2022-04-06 22:32:13,056 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 22:32:13,056 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 22:32:13,057 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 22:32:13,058 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 22:32:13,066 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 22:32:13,113 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 22:32:13,113 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 22:32:13,116 INFO L263 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 34 conjunts are in the unsatisfiable core [2022-04-06 22:32:13,118 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 22:32:13,712 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 19 proven. 20 refuted. 0 times theorem prover too weak. 157 trivial. 0 not checked. [2022-04-06 22:32:13,712 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 22:32:14,184 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 19 proven. 20 refuted. 0 times theorem prover too weak. 157 trivial. 0 not checked. [2022-04-06 22:32:14,184 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 22:32:14,184 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1547810096] [2022-04-06 22:32:14,184 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 22:32:14,184 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [269279156] [2022-04-06 22:32:14,184 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [269279156] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 22:32:14,184 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 22:32:14,185 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2022-04-06 22:32:14,185 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 22:32:14,185 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [601422870] [2022-04-06 22:32:14,185 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [601422870] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:14,185 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:14,185 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-06 22:32:14,185 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2043833835] [2022-04-06 22:32:14,185 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 22:32:14,185 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-06 22:32:14,185 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:14,186 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-06 22:32:14,186 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=286, Unknown=0, NotChecked=0, Total=342 [2022-04-06 22:32:14,186 INFO L87 Difference]: Start difference. First operand 65 states and 81 transitions. Second operand has 12 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 10 states have internal predecessors, (26), 6 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2022-04-06 22:32:14,546 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 22:32:14,546 INFO L93 Difference]: Finished difference Result 94 states and 120 transitions. [2022-04-06 22:32:14,547 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 22:32:14,547 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 10 states have internal predecessors, (26), 6 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) Word has length 91 [2022-04-06 22:32:14,547 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 22:32:14,548 INFO L225 Difference]: With dead ends: 94 [2022-04-06 22:32:14,548 INFO L226 Difference]: Without dead ends: 92 [2022-04-06 22:32:14,549 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 186 GetRequests, 163 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 89 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=92, Invalid=460, Unknown=0, NotChecked=0, Total=552 [2022-04-06 22:32:14,549 INFO L913 BasicCegarLoop]: 58 mSDtfsCounter, 41 mSDsluCounter, 197 mSDsCounter, 0 mSdLazyCounter, 339 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 255 SdHoareTripleChecker+Invalid, 377 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 339 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 22:32:14,549 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 255 Invalid, 377 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 339 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 22:32:14,550 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-04-06 22:32:14,562 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 83. [2022-04-06 22:32:14,563 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 46 states have (on average 1.1304347826086956) internal successors, (52), 48 states have internal predecessors, (52), 27 states have call successors, (27), 10 states have call predecessors, (27), 9 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2022-04-06 22:32:14,563 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 104 transitions. [2022-04-06 22:32:14,564 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 104 transitions. Word has length 91 [2022-04-06 22:32:14,564 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 22:32:14,564 INFO L478 AbstractCegarLoop]: Abstraction has 83 states and 104 transitions. [2022-04-06 22:32:14,564 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 10 states have internal predecessors, (26), 6 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2022-04-06 22:32:14,564 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 104 transitions. [2022-04-06 22:32:14,565 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2022-04-06 22:32:14,565 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 22:32:14,565 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 22:32:14,609 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 22:32:14,787 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 22:32:14,787 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 22:32:14,788 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 22:32:14,788 INFO L85 PathProgramCache]: Analyzing trace with hash -2082914122, now seen corresponding path program 1 times [2022-04-06 22:32:14,788 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:14,788 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [19569613] [2022-04-06 22:32:14,788 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 22:32:14,788 INFO L85 PathProgramCache]: Analyzing trace with hash -2082914122, now seen corresponding path program 2 times [2022-04-06 22:32:14,789 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 22:32:14,789 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [844468746] [2022-04-06 22:32:14,789 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 22:32:14,789 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 22:32:14,812 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 22:32:14,812 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1101400032] [2022-04-06 22:32:14,812 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 22:32:14,812 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 22:32:14,812 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 22:32:14,813 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 22:32:14,851 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 22:32:14,865 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 22:32:14,866 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 22:32:14,867 INFO L263 TraceCheckSpWp]: Trace formula consists of 242 conjuncts, 35 conjunts are in the unsatisfiable core [2022-04-06 22:32:14,871 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 22:32:15,318 INFO L134 CoverageAnalysis]: Checked inductivity of 230 backedges. 38 proven. 27 refuted. 0 times theorem prover too weak. 165 trivial. 0 not checked. [2022-04-06 22:32:15,318 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 22:32:15,515 INFO L134 CoverageAnalysis]: Checked inductivity of 230 backedges. 39 proven. 7 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2022-04-06 22:32:15,515 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 22:32:15,515 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [844468746] [2022-04-06 22:32:15,515 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 22:32:15,515 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1101400032] [2022-04-06 22:32:15,515 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1101400032] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 22:32:15,515 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 22:32:15,515 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 9] total 19 [2022-04-06 22:32:15,515 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 22:32:15,516 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [19569613] [2022-04-06 22:32:15,516 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [19569613] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:15,516 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:15,516 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-04-06 22:32:15,516 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1237134879] [2022-04-06 22:32:15,516 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 22:32:15,516 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-04-06 22:32:15,516 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:15,516 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-04-06 22:32:15,517 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=289, Unknown=0, NotChecked=0, Total=342 [2022-04-06 22:32:15,517 INFO L87 Difference]: Start difference. First operand 83 states and 104 transitions. Second operand has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 12 states have internal predecessors, (29), 7 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2022-04-06 22:32:16,145 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 22:32:16,146 INFO L93 Difference]: Finished difference Result 98 states and 123 transitions. [2022-04-06 22:32:16,146 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-04-06 22:32:16,146 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 12 states have internal predecessors, (29), 7 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) Word has length 96 [2022-04-06 22:32:16,146 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 22:32:16,147 INFO L225 Difference]: With dead ends: 98 [2022-04-06 22:32:16,147 INFO L226 Difference]: Without dead ends: 90 [2022-04-06 22:32:16,147 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 198 GetRequests, 173 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 104 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=101, Invalid=549, Unknown=0, NotChecked=0, Total=650 [2022-04-06 22:32:16,148 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 41 mSDsluCounter, 192 mSDsCounter, 0 mSdLazyCounter, 607 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 233 SdHoareTripleChecker+Invalid, 639 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 607 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-04-06 22:32:16,148 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [54 Valid, 233 Invalid, 639 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 607 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-04-06 22:32:16,148 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2022-04-06 22:32:16,170 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 88. [2022-04-06 22:32:16,170 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 48 states have (on average 1.125) internal successors, (54), 49 states have internal predecessors, (54), 30 states have call successors, (30), 10 states have call predecessors, (30), 9 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2022-04-06 22:32:16,171 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 112 transitions. [2022-04-06 22:32:16,171 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 112 transitions. Word has length 96 [2022-04-06 22:32:16,171 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 22:32:16,171 INFO L478 AbstractCegarLoop]: Abstraction has 88 states and 112 transitions. [2022-04-06 22:32:16,171 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 12 states have internal predecessors, (29), 7 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2022-04-06 22:32:16,171 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 112 transitions. [2022-04-06 22:32:16,172 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 103 [2022-04-06 22:32:16,172 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 22:32:16,172 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 6, 6, 6, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 22:32:16,205 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 22:32:16,388 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 22:32:16,388 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 22:32:16,389 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 22:32:16,389 INFO L85 PathProgramCache]: Analyzing trace with hash 948121191, now seen corresponding path program 1 times [2022-04-06 22:32:16,389 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:16,389 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1912743093] [2022-04-06 22:32:16,389 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 22:32:16,389 INFO L85 PathProgramCache]: Analyzing trace with hash 948121191, now seen corresponding path program 2 times [2022-04-06 22:32:16,389 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 22:32:16,389 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2079391756] [2022-04-06 22:32:16,390 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 22:32:16,390 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 22:32:16,396 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 22:32:16,396 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [562690024] [2022-04-06 22:32:16,397 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 22:32:16,397 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 22:32:16,397 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 22:32:16,404 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 22:32:16,404 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 22:32:16,466 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 22:32:16,466 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 22:32:16,467 INFO L263 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-06 22:32:16,469 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 22:32:16,614 INFO L134 CoverageAnalysis]: Checked inductivity of 276 backedges. 99 proven. 12 refuted. 0 times theorem prover too weak. 165 trivial. 0 not checked. [2022-04-06 22:32:16,615 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 22:32:16,796 INFO L134 CoverageAnalysis]: Checked inductivity of 276 backedges. 33 proven. 18 refuted. 0 times theorem prover too weak. 225 trivial. 0 not checked. [2022-04-06 22:32:16,796 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 22:32:16,796 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2079391756] [2022-04-06 22:32:16,796 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 22:32:16,796 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [562690024] [2022-04-06 22:32:16,796 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [562690024] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 22:32:16,797 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 22:32:16,797 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 12 [2022-04-06 22:32:16,797 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 22:32:16,797 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1912743093] [2022-04-06 22:32:16,797 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1912743093] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:16,797 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:16,797 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 22:32:16,797 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1454021491] [2022-04-06 22:32:16,797 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 22:32:16,797 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 22:32:16,798 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:16,798 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 22:32:16,798 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2022-04-06 22:32:16,798 INFO L87 Difference]: Start difference. First operand 88 states and 112 transitions. Second operand has 9 states, 9 states have (on average 3.2222222222222223) internal successors, (29), 8 states have internal predecessors, (29), 5 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-04-06 22:32:16,947 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 22:32:16,947 INFO L93 Difference]: Finished difference Result 103 states and 127 transitions. [2022-04-06 22:32:16,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 22:32:16,947 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.2222222222222223) internal successors, (29), 8 states have internal predecessors, (29), 5 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) Word has length 102 [2022-04-06 22:32:16,947 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 22:32:16,950 INFO L225 Difference]: With dead ends: 103 [2022-04-06 22:32:16,950 INFO L226 Difference]: Without dead ends: 69 [2022-04-06 22:32:16,951 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 208 GetRequests, 192 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=68, Invalid=204, Unknown=0, NotChecked=0, Total=272 [2022-04-06 22:32:16,952 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 15 mSDsluCounter, 148 mSDsCounter, 0 mSdLazyCounter, 184 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 191 SdHoareTripleChecker+Invalid, 208 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 184 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 22:32:16,953 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 191 Invalid, 208 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 184 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 22:32:16,953 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2022-04-06 22:32:16,964 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 69. [2022-04-06 22:32:16,965 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 38 states have (on average 1.0526315789473684) internal successors, (40), 39 states have internal predecessors, (40), 22 states have call successors, (22), 9 states have call predecessors, (22), 8 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2022-04-06 22:32:16,965 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 82 transitions. [2022-04-06 22:32:16,966 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 82 transitions. Word has length 102 [2022-04-06 22:32:16,967 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 22:32:16,967 INFO L478 AbstractCegarLoop]: Abstraction has 69 states and 82 transitions. [2022-04-06 22:32:16,967 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.2222222222222223) internal successors, (29), 8 states have internal predecessors, (29), 5 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-04-06 22:32:16,968 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 82 transitions. [2022-04-06 22:32:16,970 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2022-04-06 22:32:16,970 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 22:32:16,970 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 22:32:17,004 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 22:32:17,204 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 22:32:17,204 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 22:32:17,205 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 22:32:17,205 INFO L85 PathProgramCache]: Analyzing trace with hash 1185765869, now seen corresponding path program 3 times [2022-04-06 22:32:17,205 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:17,205 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [905572176] [2022-04-06 22:32:17,206 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 22:32:17,206 INFO L85 PathProgramCache]: Analyzing trace with hash 1185765869, now seen corresponding path program 4 times [2022-04-06 22:32:17,206 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 22:32:17,206 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [638639784] [2022-04-06 22:32:17,206 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 22:32:17,206 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 22:32:17,226 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 22:32:17,226 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [632914888] [2022-04-06 22:32:17,227 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 22:32:17,227 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 22:32:17,227 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 22:32:17,232 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 22:32:17,242 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 22:32:17,292 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 22:32:17,292 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 22:32:17,292 INFO L263 TraceCheckSpWp]: Trace formula consists of 236 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-06 22:32:17,294 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 22:32:17,423 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 26 proven. 33 refuted. 0 times theorem prover too weak. 309 trivial. 0 not checked. [2022-04-06 22:32:17,423 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 22:32:17,561 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 26 proven. 33 refuted. 0 times theorem prover too weak. 309 trivial. 0 not checked. [2022-04-06 22:32:17,561 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 22:32:17,562 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [638639784] [2022-04-06 22:32:17,562 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 22:32:17,562 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [632914888] [2022-04-06 22:32:17,562 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [632914888] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 22:32:17,562 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 22:32:17,562 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 13 [2022-04-06 22:32:17,562 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 22:32:17,562 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [905572176] [2022-04-06 22:32:17,562 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [905572176] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 22:32:17,562 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 22:32:17,562 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 22:32:17,562 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2101824710] [2022-04-06 22:32:17,563 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 22:32:17,563 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 22:32:17,563 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 22:32:17,563 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 22:32:17,563 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2022-04-06 22:32:17,563 INFO L87 Difference]: Start difference. First operand 69 states and 82 transitions. Second operand has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 9 states have internal predecessors, (28), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) [2022-04-06 22:32:17,664 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 22:32:17,665 INFO L93 Difference]: Finished difference Result 69 states and 82 transitions. [2022-04-06 22:32:17,665 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 22:32:17,665 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 9 states have internal predecessors, (28), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) Word has length 113 [2022-04-06 22:32:17,665 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 22:32:17,665 INFO L225 Difference]: With dead ends: 69 [2022-04-06 22:32:17,665 INFO L226 Difference]: Without dead ends: 0 [2022-04-06 22:32:17,666 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 229 GetRequests, 213 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=55, Invalid=217, Unknown=0, NotChecked=0, Total=272 [2022-04-06 22:32:17,667 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 11 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 201 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 239 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 201 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 22:32:17,667 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 184 Invalid, 239 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 201 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 22:32:17,667 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-06 22:32:17,667 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-06 22:32:17,667 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-06 22:32:17,667 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-06 22:32:17,667 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 113 [2022-04-06 22:32:17,667 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 22:32:17,668 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-06 22:32:17,668 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 9 states have internal predecessors, (28), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) [2022-04-06 22:32:17,668 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-06 22:32:17,668 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-06 22:32:17,669 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-06 22:32:17,701 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 22:32:17,870 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 22:32:17,872 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-04-06 22:32:19,383 INFO L882 garLoopResultBuilder]: For program point reach_errorEXIT(line 4) no Hoare annotation was computed. [2022-04-06 22:32:19,383 INFO L882 garLoopResultBuilder]: For program point reach_errorENTRY(line 4) no Hoare annotation was computed. [2022-04-06 22:32:19,383 INFO L882 garLoopResultBuilder]: For program point reach_errorFINAL(line 4) no Hoare annotation was computed. [2022-04-06 22:32:19,383 INFO L885 garLoopResultBuilder]: At program point assume_abort_if_notENTRY(lines 7 9) the Hoare annotation is: true [2022-04-06 22:32:19,383 INFO L878 garLoopResultBuilder]: At program point L8(line 8) the Hoare annotation is: (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|) [2022-04-06 22:32:19,383 INFO L878 garLoopResultBuilder]: At program point L8-2(lines 7 9) the Hoare annotation is: (and (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)) [2022-04-06 22:32:19,383 INFO L878 garLoopResultBuilder]: At program point assume_abort_if_notEXIT(lines 7 9) the Hoare annotation is: (and (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)) [2022-04-06 22:32:19,383 INFO L878 garLoopResultBuilder]: At program point L25(line 25) the Hoare annotation is: (and (<= 0 main_~y~0) (<= 1 main_~x~0) (<= main_~x~0 1) (<= main_~y~0 1)) [2022-04-06 22:32:19,383 INFO L885 garLoopResultBuilder]: At program point mainEXIT(lines 18 74) the Hoare annotation is: true [2022-04-06 22:32:19,383 INFO L878 garLoopResultBuilder]: At program point L50(line 50) the Hoare annotation is: (let ((.cse0 (= main_~r~0 0)) (.cse1 (= main_~s~0 1)) (.cse2 (<= 1 main_~a~0)) (.cse3 (= main_~b~0 main_~y~0)) (.cse4 (= main_~yy~0 (* main_~y~0 main_~y~0))) (.cse5 (= main_~q~0 0)) (.cse6 (<= 1 main_~y~0)) (.cse7 (= main_~a~0 main_~x~0)) (.cse8 (= main_~p~0 1))) (or (and .cse0 (<= (+ main_~c~0 main_~b~0) 1) .cse1 (<= main_~x~0 1) .cse2 (<= 0 main_~c~0) .cse3 (= main_~k~0 1) .cse4 .cse5 .cse6 .cse7 .cse8) (and .cse0 (= main_~k~0 0) .cse1 .cse2 .cse3 .cse4 .cse5 .cse6 .cse7 (<= main_~c~0 1) (= main_~c~0 main_~x~0) (<= main_~y~0 1) .cse8))) [2022-04-06 22:32:19,383 INFO L878 garLoopResultBuilder]: At program point L48(line 48) the Hoare annotation is: (let ((.cse0 (= main_~r~0 0)) (.cse1 (= main_~a~0 (+ main_~c~0 (* main_~b~0 main_~k~0)))) (.cse2 (= main_~s~0 1)) (.cse3 (= main_~b~0 main_~y~0)) (.cse4 (= main_~yy~0 (* main_~y~0 main_~y~0))) (.cse5 (= main_~q~0 0)) (.cse6 (<= 1 main_~y~0)) (.cse7 (= main_~a~0 main_~x~0)) (.cse8 (= main_~p~0 1))) (or (and .cse0 .cse1 .cse2 (<= 1 main_~a~0) .cse3 .cse4 .cse5 .cse6 .cse7 (<= main_~c~0 1) (= main_~c~0 main_~x~0) (<= main_~y~0 1) .cse8) (and .cse0 .cse1 .cse2 (<= main_~x~0 1) (<= 0 main_~c~0) .cse3 (= main_~k~0 1) .cse4 .cse5 .cse6 .cse7 .cse8))) [2022-04-06 22:32:19,384 INFO L878 garLoopResultBuilder]: At program point L48-1(line 48) the Hoare annotation is: (let ((.cse0 (= main_~r~0 0)) (.cse1 (= main_~s~0 1)) (.cse2 (<= 1 main_~a~0)) (.cse3 (= main_~b~0 main_~y~0)) (.cse4 (= main_~yy~0 (* main_~y~0 main_~y~0))) (.cse5 (= main_~q~0 0)) (.cse6 (<= 1 main_~y~0)) (.cse7 (= main_~a~0 main_~x~0)) (.cse8 (= main_~p~0 1))) (or (and .cse0 (<= (+ main_~c~0 main_~b~0) 1) .cse1 (<= main_~x~0 1) .cse2 (<= 0 main_~c~0) .cse3 (= main_~k~0 1) .cse4 .cse5 .cse6 .cse7 .cse8) (and .cse0 (= main_~k~0 0) .cse1 .cse2 .cse3 .cse4 .cse5 .cse6 .cse7 (<= main_~c~0 1) (= main_~c~0 main_~x~0) (<= main_~y~0 1) .cse8))) [2022-04-06 22:32:19,384 INFO L885 garLoopResultBuilder]: At program point mainFINAL(lines 18 74) the Hoare annotation is: true [2022-04-06 22:32:19,384 INFO L878 garLoopResultBuilder]: At program point L42(lines 42 43) the Hoare annotation is: (let ((.cse0 (< main_~c~0 1)) (.cse1 (<= 0 main_~c~0)) (.cse2 (<= main_~y~0 1))) (or (and (= main_~r~0 0) .cse0 (= main_~s~0 1) (<= main_~x~0 1) (<= 1 main_~a~0) .cse1 (= main_~b~0 main_~y~0) (= main_~yy~0 (* main_~y~0 main_~y~0)) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) .cse2 (= main_~p~0 1)) (let ((.cse3 (div (+ (- 1) (* (- 1) main_~x~0)) (- 2)))) (and .cse0 (< main_~b~0 1) (= main_~p~0 0) (= main_~a~0 (+ (* main_~y~0 main_~r~0) (* main_~p~0 main_~x~0))) (= main_~r~0 1) .cse1 (< .cse3 (+ main_~y~0 1)) (< .cse3 (+ main_~x~0 1)) (<= 0 main_~b~0) (= main_~q~0 1) (= (+ main_~s~0 1) 0) .cse2)))) [2022-04-06 22:32:19,384 INFO L878 garLoopResultBuilder]: At program point L71(line 71) the Hoare annotation is: (and (<= 1 main_~x~0) (= main_~p~0 0) (= main_~a~0 (+ (* main_~y~0 main_~r~0) (* main_~p~0 main_~x~0))) (<= main_~x~0 1) (= main_~r~0 1) (<= 1 main_~y~0) (<= main_~y~0 1)) [2022-04-06 22:32:19,384 INFO L878 garLoopResultBuilder]: At program point L38(line 38) the Hoare annotation is: (and (= main_~r~0 0) (< main_~c~0 1) (= main_~s~0 1) (<= main_~x~0 1) (<= 1 main_~a~0) (<= 0 main_~c~0) (= main_~b~0 main_~y~0) (= main_~yy~0 (* main_~y~0 main_~y~0)) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) (<= main_~y~0 1) (= main_~p~0 1)) [2022-04-06 22:32:19,384 INFO L878 garLoopResultBuilder]: At program point L38-1(line 38) the Hoare annotation is: (and (= main_~r~0 0) (< main_~c~0 1) (= main_~s~0 1) (<= main_~x~0 1) (<= 1 main_~a~0) (<= 0 main_~c~0) (= main_~b~0 main_~y~0) (= main_~yy~0 (* main_~y~0 main_~y~0)) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) (<= main_~y~0 1) (= main_~p~0 1)) [2022-04-06 22:32:19,384 INFO L885 garLoopResultBuilder]: At program point mainENTRY(lines 18 74) the Hoare annotation is: true [2022-04-06 22:32:19,384 INFO L878 garLoopResultBuilder]: At program point L26(line 26) the Hoare annotation is: (and (<= 1 main_~x~0) (<= main_~x~0 1) (<= 1 main_~y~0) (<= main_~y~0 1)) [2022-04-06 22:32:19,384 INFO L878 garLoopResultBuilder]: At program point L24(line 24) the Hoare annotation is: (and (<= 0 main_~x~0) (<= main_~x~0 1)) [2022-04-06 22:32:19,384 INFO L878 garLoopResultBuilder]: At program point L24-1(line 24) the Hoare annotation is: (and (<= 0 main_~y~0) (<= 0 main_~x~0) (<= main_~x~0 1) (<= main_~y~0 1)) [2022-04-06 22:32:19,384 INFO L885 garLoopResultBuilder]: At program point L22(line 22) the Hoare annotation is: true [2022-04-06 22:32:19,384 INFO L878 garLoopResultBuilder]: At program point L22-1(line 22) the Hoare annotation is: (and (<= 0 main_~x~0) (<= main_~x~0 1)) [2022-04-06 22:32:19,384 INFO L878 garLoopResultBuilder]: At program point L51(lines 47 56) the Hoare annotation is: (let ((.cse0 (= main_~r~0 0)) (.cse1 (= main_~s~0 1)) (.cse2 (<= 1 main_~a~0)) (.cse3 (= main_~b~0 main_~y~0)) (.cse4 (= main_~yy~0 (* main_~y~0 main_~y~0))) (.cse5 (= main_~q~0 0)) (.cse6 (<= 1 main_~y~0)) (.cse7 (= main_~a~0 main_~x~0)) (.cse8 (= main_~p~0 1))) (or (and .cse0 (<= (+ main_~c~0 main_~b~0) 1) .cse1 (<= main_~x~0 1) .cse2 (<= 0 main_~c~0) .cse3 (= main_~k~0 1) .cse4 .cse5 .cse6 .cse7 .cse8) (and .cse0 (= main_~k~0 0) .cse1 .cse2 .cse3 .cse4 .cse5 .cse6 .cse7 (<= main_~c~0 1) (= main_~c~0 main_~x~0) (<= main_~y~0 1) .cse8))) [2022-04-06 22:32:19,384 INFO L878 garLoopResultBuilder]: At program point L49(line 49) the Hoare annotation is: (let ((.cse0 (= main_~r~0 0)) (.cse1 (= main_~s~0 1)) (.cse2 (<= 1 main_~a~0)) (.cse3 (= main_~b~0 main_~y~0)) (.cse4 (= main_~yy~0 (* main_~y~0 main_~y~0))) (.cse5 (= main_~q~0 0)) (.cse6 (<= 1 main_~y~0)) (.cse7 (= main_~a~0 main_~x~0)) (.cse8 (= main_~p~0 1))) (or (and .cse0 (<= (+ main_~c~0 main_~b~0) 1) .cse1 (<= main_~x~0 1) .cse2 (<= 0 main_~c~0) .cse3 (= main_~k~0 1) .cse4 .cse5 .cse6 .cse7 .cse8) (and .cse0 (= main_~k~0 0) .cse1 .cse2 .cse3 .cse4 .cse5 .cse6 .cse7 (<= main_~c~0 1) (= main_~c~0 main_~x~0) (<= main_~y~0 1) .cse8))) [2022-04-06 22:32:19,385 INFO L878 garLoopResultBuilder]: At program point L47-2(lines 47 56) the Hoare annotation is: (let ((.cse0 (= main_~r~0 0)) (.cse1 (= main_~a~0 (+ main_~c~0 (* main_~b~0 main_~k~0)))) (.cse2 (= main_~s~0 1)) (.cse3 (= main_~b~0 main_~y~0)) (.cse4 (= main_~yy~0 (* main_~y~0 main_~y~0))) (.cse5 (= main_~q~0 0)) (.cse6 (<= 1 main_~y~0)) (.cse7 (= main_~a~0 main_~x~0)) (.cse8 (= main_~p~0 1))) (or (and .cse0 .cse1 .cse2 (<= 1 main_~a~0) .cse3 .cse4 .cse5 .cse6 .cse7 (<= main_~c~0 1) (= main_~c~0 main_~x~0) (<= main_~y~0 1) .cse8) (and .cse0 .cse1 .cse2 (<= main_~x~0 1) (<= 0 main_~c~0) .cse3 (= main_~k~0 1) .cse4 .cse5 .cse6 .cse7 .cse8))) [2022-04-06 22:32:19,385 INFO L878 garLoopResultBuilder]: At program point L47-3(lines 47 56) the Hoare annotation is: (and (= main_~r~0 0) (= main_~a~0 (+ main_~c~0 (* main_~b~0 main_~k~0))) (< main_~c~0 1) (<= 1 main_~x~0) (= main_~s~0 1) (= main_~k~0 1) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (= main_~a~0 main_~x~0) (<= main_~y~0 1) (= main_~p~0 1)) [2022-04-06 22:32:19,385 INFO L878 garLoopResultBuilder]: At program point L41-1(lines 39 68) the Hoare annotation is: (let ((.cse0 (< main_~c~0 1)) (.cse1 (<= 0 main_~c~0)) (.cse2 (<= main_~y~0 1))) (or (and (= main_~r~0 0) .cse0 (= main_~s~0 1) (<= main_~x~0 1) (<= 1 main_~a~0) .cse1 (= main_~b~0 main_~y~0) (= main_~yy~0 (* main_~y~0 main_~y~0)) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) .cse2 (= main_~p~0 1)) (let ((.cse3 (div (+ (- 1) (* (- 1) main_~x~0)) (- 2)))) (and .cse0 (< main_~b~0 1) (= main_~p~0 0) (= main_~a~0 (+ (* main_~y~0 main_~r~0) (* main_~p~0 main_~x~0))) (= main_~r~0 1) .cse1 (< .cse3 (+ main_~y~0 1)) (< .cse3 (+ main_~x~0 1)) (<= 0 main_~b~0) (= main_~q~0 1) (= (+ main_~s~0 1) 0) .cse2)))) [2022-04-06 22:32:19,385 INFO L885 garLoopResultBuilder]: At program point L72(line 72) the Hoare annotation is: true [2022-04-06 22:32:19,385 INFO L878 garLoopResultBuilder]: At program point L41-2(lines 41 68) the Hoare annotation is: (let ((.cse0 (div (+ (- 1) (* (- 1) main_~x~0)) (- 2)))) (and (= main_~p~0 0) (= main_~a~0 (+ (* main_~y~0 main_~r~0) (* main_~p~0 main_~x~0))) (= main_~r~0 1) (< .cse0 (+ main_~y~0 1)) (< .cse0 (+ main_~x~0 1)) (= main_~q~0 1) (= (+ main_~s~0 1) 0) (<= main_~y~0 1))) [2022-04-06 22:32:19,385 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.initFINAL(line -1) the Hoare annotation is: true [2022-04-06 22:32:19,385 INFO L878 garLoopResultBuilder]: At program point ULTIMATE.initENTRY(line -1) the Hoare annotation is: (and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|)) [2022-04-06 22:32:19,385 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.initEXIT(line -1) the Hoare annotation is: true [2022-04-06 22:32:19,385 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startEXIT(line -1) the Hoare annotation is: true [2022-04-06 22:32:19,385 INFO L885 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-04-06 22:32:19,385 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-04-06 22:32:19,385 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startFINAL(line -1) the Hoare annotation is: true [2022-04-06 22:32:19,385 INFO L885 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 10 16) the Hoare annotation is: true [2022-04-06 22:32:19,385 INFO L878 garLoopResultBuilder]: At program point L12(lines 12 13) the Hoare annotation is: (not (<= 1 |__VERIFIER_assert_#in~cond|)) [2022-04-06 22:32:19,385 INFO L878 garLoopResultBuilder]: At program point L11(lines 11 14) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-06 22:32:19,385 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertEXIT(lines 10 16) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-06 22:32:19,385 INFO L878 garLoopResultBuilder]: At program point L11-2(lines 10 16) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-06 22:32:19,386 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 13) the Hoare annotation is: (not (<= 1 |__VERIFIER_assert_#in~cond|)) [2022-04-06 22:32:19,387 INFO L719 BasicCegarLoop]: Path program histogram: [4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] [2022-04-06 22:32:19,388 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-04-06 22:32:19,410 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 10:32:19 BoogieIcfgContainer [2022-04-06 22:32:19,410 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-06 22:32:19,410 INFO L158 Benchmark]: Toolchain (without parser) took 13007.59ms. Allocated memory was 190.8MB in the beginning and 293.6MB in the end (delta: 102.8MB). Free memory was 142.9MB in the beginning and 120.6MB in the end (delta: 22.3MB). Peak memory consumption was 145.4MB. Max. memory is 8.0GB. [2022-04-06 22:32:19,411 INFO L158 Benchmark]: CDTParser took 0.12ms. Allocated memory is still 190.8MB. Free memory is still 159.2MB. There was no memory consumed. Max. memory is 8.0GB. [2022-04-06 22:32:19,411 INFO L158 Benchmark]: CACSL2BoogieTranslator took 282.79ms. Allocated memory is still 190.8MB. Free memory was 142.7MB in the beginning and 167.0MB in the end (delta: -24.3MB). Peak memory consumption was 10.9MB. Max. memory is 8.0GB. [2022-04-06 22:32:19,411 INFO L158 Benchmark]: Boogie Preprocessor took 33.70ms. Allocated memory is still 190.8MB. Free memory was 167.0MB in the beginning and 165.6MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-04-06 22:32:19,411 INFO L158 Benchmark]: RCFGBuilder took 304.01ms. Allocated memory is still 190.8MB. Free memory was 165.6MB in the beginning and 154.0MB in the end (delta: 11.6MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-06 22:32:19,411 INFO L158 Benchmark]: TraceAbstraction took 12382.97ms. Allocated memory was 190.8MB in the beginning and 293.6MB in the end (delta: 102.8MB). Free memory was 153.5MB in the beginning and 120.6MB in the end (delta: 32.9MB). Peak memory consumption was 155.5MB. Max. memory is 8.0GB. [2022-04-06 22:32:19,412 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.12ms. Allocated memory is still 190.8MB. Free memory is still 159.2MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 282.79ms. Allocated memory is still 190.8MB. Free memory was 142.7MB in the beginning and 167.0MB in the end (delta: -24.3MB). Peak memory consumption was 10.9MB. Max. memory is 8.0GB. * Boogie Preprocessor took 33.70ms. Allocated memory is still 190.8MB. Free memory was 167.0MB in the beginning and 165.6MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 304.01ms. Allocated memory is still 190.8MB. Free memory was 165.6MB in the beginning and 154.0MB in the end (delta: 11.6MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * TraceAbstraction took 12382.97ms. Allocated memory was 190.8MB in the beginning and 293.6MB in the end (delta: 102.8MB). Free memory was 153.5MB in the beginning and 120.6MB in the end (delta: 32.9MB). Peak memory consumption was 155.5MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 13]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 43 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 12.3s, OverallIterations: 13, TraceHistogramMax: 13, PathProgramHistogramMax: 4, EmptinessCheckTime: 0.0s, AutomataDifference: 2.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 1.5s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 371 SdHoareTripleChecker+Valid, 1.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 288 mSDsluCounter, 2312 SdHoareTripleChecker+Invalid, 1.3s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1755 mSDsCounter, 262 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2449 IncrementalHoareTripleChecker+Invalid, 2711 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 262 mSolverCounterUnsat, 557 mSDtfsCounter, 2449 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1589 GetRequests, 1417 SyntacticMatches, 11 SemanticMatches, 161 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 348 ImplicationChecksByTransitivity, 1.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=89occurred in iteration=8, InterpolantAutomatonStates: 112, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 13 MinimizatonAttempts, 46 StatesRemovedByMinimization, 10 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 40 LocationsWithAnnotation, 398 PreInvPairs, 497 NumberOfFragments, 1059 HoareAnnotationTreeSize, 398 FomulaSimplifications, 263 FormulaSimplificationTreeSizeReduction, 0.1s HoareSimplificationTime, 40 FomulaSimplificationsInter, 4050 FormulaSimplificationTreeSizeReductionInter, 1.4s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: No data available, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 47]: Loop Invariant Derived loop invariant: ((((((((((((r == 0 && a == c + b * k) && s == 1) && 1 <= a) && b == y) && yy == y * y) && q == 0) && 1 <= y) && a == x) && c <= 1) && c == x) && y <= 1) && p == 1) || (((((((((((r == 0 && a == c + b * k) && s == 1) && x <= 1) && 0 <= c) && b == y) && k == 1) && yy == y * y) && q == 0) && 1 <= y) && a == x) && p == 1) - InvariantResult [Line: 39]: Loop Invariant Derived loop invariant: ((((((((((((r == 0 && c < 1) && s == 1) && x <= 1) && 1 <= a) && 0 <= c) && b == y) && yy == y * y) && q == 0) && 1 <= y) && a == x) && y <= 1) && p == 1) || (((((((((((c < 1 && b < 1) && p == 0) && a == y * r + p * x) && r == 1) && 0 <= c) && (-1 + -1 * x) / -2 < y + 1) && (-1 + -1 * x) / -2 < x + 1) && 0 <= b) && q == 1) && s + 1 == 0) && y <= 1) - ProcedureContractResult [Line: 7]: Procedure Contract for assume_abort_if_not Derived contract for procedure assume_abort_if_not: !(\old(cond) == 0) && cond == \old(cond) - ProcedureContractResult [Line: 18]: Procedure Contract for main Derived contract for procedure main: 1 - ProcedureContractResult [Line: 10]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert: \old(cond) == cond || !(1 <= \old(cond)) RESULT: Ultimate proved your program to be correct! [2022-04-06 22:32:19,427 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...