/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf -i ../../../trunk/examples/svcomp/nla-digbench/hard-ll.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 13:43:04,638 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 13:43:04,640 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 13:43:04,664 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 13:43:04,664 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 13:43:04,665 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 13:43:04,666 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 13:43:04,668 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 13:43:04,669 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 13:43:04,670 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 13:43:04,670 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 13:43:04,671 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 13:43:04,672 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 13:43:04,672 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 13:43:04,673 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 13:43:04,674 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 13:43:04,675 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 13:43:04,675 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 13:43:04,676 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 13:43:04,678 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 13:43:04,679 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 13:43:04,683 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 13:43:04,684 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 13:43:04,685 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 13:43:04,685 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 13:43:04,691 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 13:43:04,691 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 13:43:04,691 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 13:43:04,692 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 13:43:04,692 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 13:43:04,693 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 13:43:04,693 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 13:43:04,693 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 13:43:04,694 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 13:43:04,694 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 13:43:04,695 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 13:43:04,695 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 13:43:04,696 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 13:43:04,696 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 13:43:04,696 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 13:43:04,697 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 13:43:04,706 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 13:43:04,706 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-03-20 13:43:04,713 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 13:43:04,714 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 13:43:04,715 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 13:43:04,715 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-20 13:43:04,715 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 13:43:04,715 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-20 13:43:04,715 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 13:43:04,715 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 13:43:04,716 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 13:43:04,716 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 13:43:04,716 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-20 13:43:04,716 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 13:43:04,716 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 13:43:04,716 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 13:43:04,717 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 13:43:04,717 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 13:43:04,717 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-20 13:43:04,717 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 13:43:04,717 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 13:43:04,717 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 13:43:04,718 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-03-20 13:43:04,718 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-03-20 13:43:04,718 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-03-20 13:43:04,718 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-20 13:43:04,718 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-03-20 13:43:04,718 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-03-20 13:43:04,931 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 13:43:04,951 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 13:43:04,953 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 13:43:04,954 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 13:43:04,954 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 13:43:04,955 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench/hard-ll.c [2022-03-20 13:43:05,012 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f12230e11/d1aef5391a9748b7a470b6d71df94b02/FLAG8aed4ab18 [2022-03-20 13:43:05,326 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 13:43:05,327 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench/hard-ll.c [2022-03-20 13:43:05,332 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f12230e11/d1aef5391a9748b7a470b6d71df94b02/FLAG8aed4ab18 [2022-03-20 13:43:05,749 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f12230e11/d1aef5391a9748b7a470b6d71df94b02 [2022-03-20 13:43:05,751 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 13:43:05,752 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-03-20 13:43:05,754 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 13:43:05,754 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 13:43:05,757 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 13:43:05,758 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 01:43:05" (1/1) ... [2022-03-20 13:43:05,758 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@e0575df and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 01:43:05, skipping insertion in model container [2022-03-20 13:43:05,759 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 01:43:05" (1/1) ... [2022-03-20 13:43:05,765 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 13:43:05,779 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 13:43:05,906 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/hard-ll.c[538,551] [2022-03-20 13:43:05,919 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 13:43:05,925 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 13:43:05,934 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/hard-ll.c[538,551] [2022-03-20 13:43:05,939 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 13:43:05,948 INFO L208 MainTranslator]: Completed translation [2022-03-20 13:43:05,948 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 01:43:05 WrapperNode [2022-03-20 13:43:05,948 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 13:43:05,949 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 13:43:05,949 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 13:43:05,949 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 13:43:05,957 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 01:43:05" (1/1) ... [2022-03-20 13:43:05,957 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 01:43:05" (1/1) ... [2022-03-20 13:43:05,962 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 01:43:05" (1/1) ... [2022-03-20 13:43:05,962 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 01:43:05" (1/1) ... [2022-03-20 13:43:05,966 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 01:43:05" (1/1) ... [2022-03-20 13:43:05,969 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 01:43:05" (1/1) ... [2022-03-20 13:43:05,970 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 01:43:05" (1/1) ... [2022-03-20 13:43:05,971 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 13:43:05,972 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 13:43:05,972 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 13:43:05,972 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 13:43:05,973 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 01:43:05" (1/1) ... [2022-03-20 13:43:05,978 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 13:43:05,986 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:43:05,995 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-03-20 13:43:06,004 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-03-20 13:43:06,029 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 13:43:06,029 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 13:43:06,029 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 13:43:06,029 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 13:43:06,029 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 13:43:06,029 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 13:43:06,030 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 13:43:06,030 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 13:43:06,030 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 13:43:06,030 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 13:43:06,030 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-03-20 13:43:06,030 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 13:43:06,035 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 13:43:06,035 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 13:43:06,035 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 13:43:06,036 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 13:43:06,036 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 13:43:06,036 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 13:43:06,036 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 13:43:06,036 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 13:43:06,084 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 13:43:06,085 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 13:43:06,190 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 13:43:06,195 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 13:43:06,195 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-20 13:43:06,196 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 01:43:06 BoogieIcfgContainer [2022-03-20 13:43:06,196 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 13:43:06,211 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 13:43:06,211 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 13:43:06,229 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 13:43:06,230 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 01:43:05" (1/3) ... [2022-03-20 13:43:06,230 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@67deb93a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 01:43:06, skipping insertion in model container [2022-03-20 13:43:06,231 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 01:43:05" (2/3) ... [2022-03-20 13:43:06,231 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@67deb93a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 01:43:06, skipping insertion in model container [2022-03-20 13:43:06,231 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 01:43:06" (3/3) ... [2022-03-20 13:43:06,232 INFO L111 eAbstractionObserver]: Analyzing ICFG hard-ll.c [2022-03-20 13:43:06,236 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-03-20 13:43:06,236 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 13:43:06,271 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 13:43:06,279 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-03-20 13:43:06,280 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 13:43:06,293 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-20 13:43:06,299 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-20 13:43:06,299 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:43:06,300 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:43:06,300 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:43:06,305 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:43:06,305 INFO L85 PathProgramCache]: Analyzing trace with hash -977830905, now seen corresponding path program 1 times [2022-03-20 13:43:06,311 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:06,312 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [75007580] [2022-03-20 13:43:06,321 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 13:43:06,321 INFO L85 PathProgramCache]: Analyzing trace with hash -977830905, now seen corresponding path program 2 times [2022-03-20 13:43:06,324 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:43:06,324 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [422735801] [2022-03-20 13:43:06,324 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:43:06,325 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:43:06,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 13:43:06,497 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 13:43:06,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 13:43:06,511 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 13:43:06,513 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 13:43:06,524 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 13:43:06,524 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:43:06,524 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [422735801] [2022-03-20 13:43:06,525 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [422735801] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:06,525 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:06,525 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 13:43:06,527 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:43:06,527 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [75007580] [2022-03-20 13:43:06,528 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [75007580] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:06,528 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:06,528 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 13:43:06,528 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1291247358] [2022-03-20 13:43:06,529 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:43:06,532 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-20 13:43:06,532 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:06,559 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-20 13:43:06,560 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 13:43:06,561 INFO L87 Difference]: Start difference. First operand has 35 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 13:43:06,681 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:43:06,681 INFO L93 Difference]: Finished difference Result 61 states and 95 transitions. [2022-03-20 13:43:06,682 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-20 13:43:06,683 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-03-20 13:43:06,684 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:43:06,692 INFO L225 Difference]: With dead ends: 61 [2022-03-20 13:43:06,692 INFO L226 Difference]: Without dead ends: 30 [2022-03-20 13:43:06,696 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 13:43:06,700 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 38 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 13:43:06,701 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [28 Valid, 38 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 13:43:06,714 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2022-03-20 13:43:06,738 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2022-03-20 13:43:06,740 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-20 13:43:06,742 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 38 transitions. [2022-03-20 13:43:06,743 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 38 transitions. Word has length 17 [2022-03-20 13:43:06,744 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:43:06,744 INFO L478 AbstractCegarLoop]: Abstraction has 30 states and 38 transitions. [2022-03-20 13:43:06,744 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 13:43:06,744 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 38 transitions. [2022-03-20 13:43:06,745 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-20 13:43:06,745 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:43:06,745 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:43:06,746 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 13:43:06,746 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:43:06,747 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:43:06,747 INFO L85 PathProgramCache]: Analyzing trace with hash -297772535, now seen corresponding path program 1 times [2022-03-20 13:43:06,748 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:06,748 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [633752654] [2022-03-20 13:43:06,754 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 13:43:06,754 INFO L85 PathProgramCache]: Analyzing trace with hash -297772535, now seen corresponding path program 2 times [2022-03-20 13:43:06,754 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:43:06,754 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [755160988] [2022-03-20 13:43:06,755 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:43:06,755 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:43:06,782 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 13:43:06,852 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 13:43:06,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 13:43:06,860 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 13:43:06,861 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 13:43:06,865 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 13:43:06,866 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:43:06,866 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [755160988] [2022-03-20 13:43:06,866 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [755160988] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:06,866 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:06,867 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 13:43:06,867 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:43:06,867 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [633752654] [2022-03-20 13:43:06,867 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [633752654] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:06,867 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:06,868 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 13:43:06,868 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1422954689] [2022-03-20 13:43:06,868 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:43:06,869 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 13:43:06,869 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:06,870 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 13:43:06,870 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 13:43:06,870 INFO L87 Difference]: Start difference. First operand 30 states and 38 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 13:43:07,066 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:43:07,067 INFO L93 Difference]: Finished difference Result 43 states and 55 transitions. [2022-03-20 13:43:07,070 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 13:43:07,071 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-03-20 13:43:07,076 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:43:07,077 INFO L225 Difference]: With dead ends: 43 [2022-03-20 13:43:07,077 INFO L226 Difference]: Without dead ends: 41 [2022-03-20 13:43:07,078 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-20 13:43:07,079 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 37 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 13:43:07,079 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 45 Invalid, 136 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 13:43:07,080 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-03-20 13:43:07,092 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 34. [2022-03-20 13:43:07,093 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 20 states have internal predecessors, (23), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-20 13:43:07,096 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 41 transitions. [2022-03-20 13:43:07,096 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 41 transitions. Word has length 17 [2022-03-20 13:43:07,096 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:43:07,096 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 41 transitions. [2022-03-20 13:43:07,096 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 13:43:07,097 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 41 transitions. [2022-03-20 13:43:07,098 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-03-20 13:43:07,098 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:43:07,098 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:43:07,099 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-20 13:43:07,099 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:43:07,099 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:43:07,100 INFO L85 PathProgramCache]: Analyzing trace with hash -1294462534, now seen corresponding path program 1 times [2022-03-20 13:43:07,100 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:07,103 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [481590485] [2022-03-20 13:43:07,104 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 13:43:07,104 INFO L85 PathProgramCache]: Analyzing trace with hash -1294462534, now seen corresponding path program 2 times [2022-03-20 13:43:07,104 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:43:07,104 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1906789525] [2022-03-20 13:43:07,105 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:43:07,105 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:43:07,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 13:43:07,182 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 13:43:07,184 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 13:43:07,188 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 13:43:07,189 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 13:43:07,193 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-03-20 13:43:07,195 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 13:43:07,199 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 13:43:07,199 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:43:07,199 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1906789525] [2022-03-20 13:43:07,200 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1906789525] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:07,200 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:07,200 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 13:43:07,200 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:43:07,200 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [481590485] [2022-03-20 13:43:07,200 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [481590485] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:07,201 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:07,201 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 13:43:07,201 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [684128148] [2022-03-20 13:43:07,201 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:43:07,201 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 13:43:07,202 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:07,202 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 13:43:07,202 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 13:43:07,202 INFO L87 Difference]: Start difference. First operand 34 states and 41 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 13:43:07,372 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:43:07,372 INFO L93 Difference]: Finished difference Result 47 states and 58 transitions. [2022-03-20 13:43:07,372 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 13:43:07,372 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-03-20 13:43:07,373 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:43:07,376 INFO L225 Difference]: With dead ends: 47 [2022-03-20 13:43:07,376 INFO L226 Difference]: Without dead ends: 45 [2022-03-20 13:43:07,377 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-20 13:43:07,380 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 32 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 115 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 141 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 115 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 13:43:07,385 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [36 Valid, 45 Invalid, 141 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 115 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 13:43:07,387 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-03-20 13:43:07,400 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 38. [2022-03-20 13:43:07,401 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 23 states have internal predecessors, (26), 10 states have call successors, (10), 6 states have call predecessors, (10), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-20 13:43:07,401 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 44 transitions. [2022-03-20 13:43:07,401 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 44 transitions. Word has length 22 [2022-03-20 13:43:07,402 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:43:07,402 INFO L478 AbstractCegarLoop]: Abstraction has 38 states and 44 transitions. [2022-03-20 13:43:07,402 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 13:43:07,402 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 44 transitions. [2022-03-20 13:43:07,403 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-03-20 13:43:07,403 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:43:07,403 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:43:07,403 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-03-20 13:43:07,403 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:43:07,404 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:43:07,404 INFO L85 PathProgramCache]: Analyzing trace with hash -1449027479, now seen corresponding path program 1 times [2022-03-20 13:43:07,404 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:07,404 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1354084149] [2022-03-20 13:43:07,405 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 13:43:07,405 INFO L85 PathProgramCache]: Analyzing trace with hash -1449027479, now seen corresponding path program 2 times [2022-03-20 13:43:07,405 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:43:07,405 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1448504933] [2022-03-20 13:43:07,405 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:43:07,406 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:43:07,416 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:43:07,417 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [67114964] [2022-03-20 13:43:07,417 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 13:43:07,417 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:43:07,417 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:43:07,423 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:43:07,432 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-20 13:43:07,470 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 13:43:07,471 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:43:07,490 INFO L263 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 13:43:07,494 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:43:07,650 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 13:43:07,650 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 13:43:07,651 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:43:07,651 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1448504933] [2022-03-20 13:43:07,651 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 13:43:07,651 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [67114964] [2022-03-20 13:43:07,651 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [67114964] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:07,651 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:07,652 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 13:43:07,652 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:43:07,652 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1354084149] [2022-03-20 13:43:07,653 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1354084149] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:07,653 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:07,653 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 13:43:07,654 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1641517061] [2022-03-20 13:43:07,654 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:43:07,656 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 13:43:07,656 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:07,657 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 13:43:07,658 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 13:43:07,658 INFO L87 Difference]: Start difference. First operand 38 states and 44 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 13:43:07,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:43:07,731 INFO L93 Difference]: Finished difference Result 66 states and 84 transitions. [2022-03-20 13:43:07,732 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 13:43:07,733 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 27 [2022-03-20 13:43:07,736 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:43:07,738 INFO L225 Difference]: With dead ends: 66 [2022-03-20 13:43:07,739 INFO L226 Difference]: Without dead ends: 52 [2022-03-20 13:43:07,741 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 13:43:07,744 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 8 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 13:43:07,745 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 138 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 13:43:07,745 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-03-20 13:43:07,759 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2022-03-20 13:43:07,760 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 29 states have (on average 1.1724137931034482) internal successors, (34), 31 states have internal predecessors, (34), 16 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-03-20 13:43:07,760 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 63 transitions. [2022-03-20 13:43:07,761 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 63 transitions. Word has length 27 [2022-03-20 13:43:07,761 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:43:07,761 INFO L478 AbstractCegarLoop]: Abstraction has 52 states and 63 transitions. [2022-03-20 13:43:07,761 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 13:43:07,761 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 63 transitions. [2022-03-20 13:43:07,762 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-03-20 13:43:07,762 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:43:07,762 INFO L499 BasicCegarLoop]: trace histogram [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] [2022-03-20 13:43:07,788 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-20 13:43:07,963 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:43:07,963 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:43:07,964 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:43:07,964 INFO L85 PathProgramCache]: Analyzing trace with hash 905213191, now seen corresponding path program 1 times [2022-03-20 13:43:07,964 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:07,964 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [250745062] [2022-03-20 13:43:07,965 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 13:43:07,965 INFO L85 PathProgramCache]: Analyzing trace with hash 905213191, now seen corresponding path program 2 times [2022-03-20 13:43:07,965 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:43:07,965 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1636495804] [2022-03-20 13:43:07,965 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:43:07,965 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:43:07,979 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:43:07,980 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [350713108] [2022-03-20 13:43:07,980 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 13:43:07,980 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:43:07,980 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:43:07,982 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:43:07,984 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-20 13:43:08,025 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 13:43:08,025 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:43:08,026 INFO L263 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 13:43:08,028 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:43:08,129 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 13:43:08,129 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 13:43:08,129 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:43:08,129 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1636495804] [2022-03-20 13:43:08,129 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 13:43:08,129 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [350713108] [2022-03-20 13:43:08,129 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [350713108] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:08,130 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:08,130 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 13:43:08,130 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:43:08,130 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [250745062] [2022-03-20 13:43:08,130 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [250745062] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:08,130 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:08,130 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 13:43:08,130 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [167262163] [2022-03-20 13:43:08,130 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:43:08,131 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 13:43:08,131 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:08,131 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 13:43:08,131 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 13:43:08,131 INFO L87 Difference]: Start difference. First operand 52 states and 63 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 13:43:08,191 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:43:08,192 INFO L93 Difference]: Finished difference Result 65 states and 80 transitions. [2022-03-20 13:43:08,192 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 13:43:08,192 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2022-03-20 13:43:08,192 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:43:08,193 INFO L225 Difference]: With dead ends: 65 [2022-03-20 13:43:08,193 INFO L226 Difference]: Without dead ends: 58 [2022-03-20 13:43:08,194 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 13:43:08,194 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 9 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 13:43:08,195 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 112 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 13:43:08,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2022-03-20 13:43:08,207 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2022-03-20 13:43:08,208 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 33 states have (on average 1.1818181818181819) internal successors, (39), 35 states have internal predecessors, (39), 16 states have call successors, (16), 8 states have call predecessors, (16), 7 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-20 13:43:08,210 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 69 transitions. [2022-03-20 13:43:08,211 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 69 transitions. Word has length 34 [2022-03-20 13:43:08,211 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:43:08,212 INFO L478 AbstractCegarLoop]: Abstraction has 57 states and 69 transitions. [2022-03-20 13:43:08,213 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 13:43:08,213 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 69 transitions. [2022-03-20 13:43:08,214 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-03-20 13:43:08,214 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:43:08,215 INFO L499 BasicCegarLoop]: trace histogram [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] [2022-03-20 13:43:08,248 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-20 13:43:08,443 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:43:08,444 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:43:08,444 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:43:08,444 INFO L85 PathProgramCache]: Analyzing trace with hash -1576096488, now seen corresponding path program 1 times [2022-03-20 13:43:08,444 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:08,444 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2127454794] [2022-03-20 13:43:08,469 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 2 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 13:43:08,469 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-03-20 13:43:08,469 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 13:43:08,470 INFO L85 PathProgramCache]: Analyzing trace with hash -1576096488, now seen corresponding path program 2 times [2022-03-20 13:43:08,470 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:43:08,470 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1753039990] [2022-03-20 13:43:08,470 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:43:08,470 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:43:08,491 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:43:08,491 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1590316328] [2022-03-20 13:43:08,491 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 13:43:08,491 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:43:08,491 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:43:08,506 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:43:08,507 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-20 13:43:08,547 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 13:43:08,547 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:43:08,548 INFO L263 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 16 conjunts are in the unsatisfiable core [2022-03-20 13:43:08,550 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:43:08,781 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 10 proven. 4 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-03-20 13:43:08,781 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 13:43:08,909 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2022-03-20 13:43:08,909 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:43:08,909 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1753039990] [2022-03-20 13:43:08,909 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 13:43:08,909 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1590316328] [2022-03-20 13:43:08,910 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1590316328] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 13:43:08,910 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 13:43:08,910 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-03-20 13:43:08,910 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:43:08,910 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2127454794] [2022-03-20 13:43:08,910 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2127454794] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:08,910 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:08,910 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 13:43:08,910 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [134753686] [2022-03-20 13:43:08,911 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:43:08,911 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 13:43:08,911 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:08,911 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 13:43:08,911 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-03-20 13:43:08,912 INFO L87 Difference]: Start difference. First operand 57 states and 69 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 13:43:08,959 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:43:08,959 INFO L93 Difference]: Finished difference Result 69 states and 84 transitions. [2022-03-20 13:43:08,959 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 13:43:08,960 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 44 [2022-03-20 13:43:08,960 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:43:08,962 INFO L225 Difference]: With dead ends: 69 [2022-03-20 13:43:08,962 INFO L226 Difference]: Without dead ends: 67 [2022-03-20 13:43:08,962 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 77 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-03-20 13:43:08,963 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 8 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 13:43:08,963 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 122 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 13:43:08,963 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2022-03-20 13:43:08,974 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 64. [2022-03-20 13:43:08,974 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 37 states have (on average 1.162162162162162) internal successors, (43), 40 states have internal predecessors, (43), 18 states have call successors, (18), 9 states have call predecessors, (18), 8 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2022-03-20 13:43:08,975 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 77 transitions. [2022-03-20 13:43:08,975 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 77 transitions. Word has length 44 [2022-03-20 13:43:08,975 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:43:08,975 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 77 transitions. [2022-03-20 13:43:08,975 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 13:43:08,976 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 77 transitions. [2022-03-20 13:43:08,977 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2022-03-20 13:43:08,977 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:43:08,977 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:43:09,003 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-20 13:43:09,203 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:43:09,204 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:43:09,204 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:43:09,204 INFO L85 PathProgramCache]: Analyzing trace with hash 1615471943, now seen corresponding path program 1 times [2022-03-20 13:43:09,204 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:09,204 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2065298425] [2022-03-20 13:43:09,209 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 2 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 13:43:09,209 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-03-20 13:43:09,209 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 13:43:09,210 INFO L85 PathProgramCache]: Analyzing trace with hash 1615471943, now seen corresponding path program 2 times [2022-03-20 13:43:09,210 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:43:09,210 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1984263999] [2022-03-20 13:43:09,210 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:43:09,210 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:43:09,231 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:43:09,231 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1786601360] [2022-03-20 13:43:09,231 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 13:43:09,231 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:43:09,231 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:43:09,233 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:43:09,251 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-20 13:43:09,286 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 13:43:09,286 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:43:09,287 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 25 conjunts are in the unsatisfiable core [2022-03-20 13:43:09,290 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:43:09,874 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-03-20 13:43:09,874 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 13:43:11,101 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-03-20 13:43:11,102 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:43:11,102 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1984263999] [2022-03-20 13:43:11,102 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 13:43:11,102 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1786601360] [2022-03-20 13:43:11,102 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1786601360] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 13:43:11,102 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 13:43:11,102 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2022-03-20 13:43:11,102 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:43:11,103 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2065298425] [2022-03-20 13:43:11,103 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2065298425] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:11,103 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:11,103 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-03-20 13:43:11,103 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [437798581] [2022-03-20 13:43:11,103 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:43:11,103 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 13:43:11,103 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:11,104 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 13:43:11,104 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2022-03-20 13:43:11,104 INFO L87 Difference]: Start difference. First operand 64 states and 77 transitions. Second operand has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 5 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-03-20 13:43:11,261 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:43:11,261 INFO L93 Difference]: Finished difference Result 124 states and 154 transitions. [2022-03-20 13:43:11,262 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 13:43:11,262 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 5 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 64 [2022-03-20 13:43:11,262 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:43:11,263 INFO L225 Difference]: With dead ends: 124 [2022-03-20 13:43:11,264 INFO L226 Difference]: Without dead ends: 101 [2022-03-20 13:43:11,264 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 114 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 36 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2022-03-20 13:43:11,265 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 10 mSDsluCounter, 175 mSDsCounter, 0 mSdLazyCounter, 125 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 216 SdHoareTripleChecker+Invalid, 138 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 125 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 13:43:11,265 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 216 Invalid, 138 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 125 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 13:43:11,265 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2022-03-20 13:43:11,281 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 99. [2022-03-20 13:43:11,281 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 60 states have (on average 1.15) internal successors, (69), 63 states have internal predecessors, (69), 25 states have call successors, (25), 14 states have call predecessors, (25), 13 states have return successors, (23), 21 states have call predecessors, (23), 23 states have call successors, (23) [2022-03-20 13:43:11,282 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 117 transitions. [2022-03-20 13:43:11,282 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 117 transitions. Word has length 64 [2022-03-20 13:43:11,282 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:43:11,283 INFO L478 AbstractCegarLoop]: Abstraction has 99 states and 117 transitions. [2022-03-20 13:43:11,283 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 5 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-03-20 13:43:11,283 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 117 transitions. [2022-03-20 13:43:11,284 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2022-03-20 13:43:11,284 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:43:11,284 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:43:11,309 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-20 13:43:11,507 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:43:11,507 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:43:11,508 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:43:11,508 INFO L85 PathProgramCache]: Analyzing trace with hash -262609796, now seen corresponding path program 3 times [2022-03-20 13:43:11,508 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:11,508 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1416994332] [2022-03-20 13:43:11,511 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 2 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 13:43:11,511 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-03-20 13:43:11,511 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 13:43:11,511 INFO L85 PathProgramCache]: Analyzing trace with hash -262609796, now seen corresponding path program 4 times [2022-03-20 13:43:11,511 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:43:11,511 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1845151158] [2022-03-20 13:43:11,511 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:43:11,512 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:43:11,520 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:43:11,520 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [388608787] [2022-03-20 13:43:11,520 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 13:43:11,520 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:43:11,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:43:11,521 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:43:11,523 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-20 13:43:11,595 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 13:43:11,595 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:43:11,597 INFO L263 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 25 conjunts are in the unsatisfiable core [2022-03-20 13:43:11,599 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:43:11,996 INFO L134 CoverageAnalysis]: Checked inductivity of 170 backedges. 23 proven. 27 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2022-03-20 13:43:11,997 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 13:43:14,277 INFO L134 CoverageAnalysis]: Checked inductivity of 170 backedges. 27 proven. 23 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2022-03-20 13:43:14,277 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:43:14,277 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1845151158] [2022-03-20 13:43:14,277 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 13:43:14,277 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [388608787] [2022-03-20 13:43:14,278 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [388608787] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 13:43:14,278 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 13:43:14,278 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 17 [2022-03-20 13:43:14,278 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:43:14,278 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1416994332] [2022-03-20 13:43:14,278 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1416994332] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:14,278 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:14,278 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-03-20 13:43:14,278 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1621754469] [2022-03-20 13:43:14,278 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:43:14,280 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-20 13:43:14,280 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:14,280 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-20 13:43:14,280 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=217, Unknown=0, NotChecked=0, Total=272 [2022-03-20 13:43:14,280 INFO L87 Difference]: Start difference. First operand 99 states and 117 transitions. Second operand has 12 states, 12 states have (on average 2.0) internal successors, (24), 10 states have internal predecessors, (24), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2022-03-20 13:43:14,672 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:43:14,672 INFO L93 Difference]: Finished difference Result 126 states and 151 transitions. [2022-03-20 13:43:14,672 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-20 13:43:14,673 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.0) internal successors, (24), 10 states have internal predecessors, (24), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) Word has length 69 [2022-03-20 13:43:14,673 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:43:14,674 INFO L225 Difference]: With dead ends: 126 [2022-03-20 13:43:14,674 INFO L226 Difference]: Without dead ends: 103 [2022-03-20 13:43:14,675 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 140 GetRequests, 121 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 53 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=76, Invalid=304, Unknown=0, NotChecked=0, Total=380 [2022-03-20 13:43:14,675 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 15 mSDsluCounter, 195 mSDsCounter, 0 mSdLazyCounter, 261 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 226 SdHoareTripleChecker+Invalid, 276 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 261 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-20 13:43:14,675 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [19 Valid, 226 Invalid, 276 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 261 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-20 13:43:14,676 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2022-03-20 13:43:14,695 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2022-03-20 13:43:14,696 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 62 states have (on average 1.1129032258064515) internal successors, (69), 66 states have internal predecessors, (69), 26 states have call successors, (26), 15 states have call predecessors, (26), 14 states have return successors, (23), 21 states have call predecessors, (23), 23 states have call successors, (23) [2022-03-20 13:43:14,698 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 118 transitions. [2022-03-20 13:43:14,698 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 118 transitions. Word has length 69 [2022-03-20 13:43:14,698 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:43:14,698 INFO L478 AbstractCegarLoop]: Abstraction has 103 states and 118 transitions. [2022-03-20 13:43:14,699 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.0) internal successors, (24), 10 states have internal predecessors, (24), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2022-03-20 13:43:14,699 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 118 transitions. [2022-03-20 13:43:14,703 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-03-20 13:43:14,703 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:43:14,703 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:43:14,726 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-03-20 13:43:14,926 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:43:14,926 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:43:14,927 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:43:14,927 INFO L85 PathProgramCache]: Analyzing trace with hash -1554666020, now seen corresponding path program 1 times [2022-03-20 13:43:14,927 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:14,927 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1690265501] [2022-03-20 13:43:14,930 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 2 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 13:43:14,930 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-03-20 13:43:14,930 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 13:43:14,930 INFO L85 PathProgramCache]: Analyzing trace with hash -1554666020, now seen corresponding path program 2 times [2022-03-20 13:43:14,931 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:43:14,931 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1955344481] [2022-03-20 13:43:14,931 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:43:14,931 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:43:14,945 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:43:14,945 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [370626895] [2022-03-20 13:43:14,945 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 13:43:14,945 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:43:14,945 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:43:14,946 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:43:14,947 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-20 13:43:15,015 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 13:43:15,015 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:43:15,016 INFO L263 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-20 13:43:15,018 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:43:15,236 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 20 proven. 4 refuted. 0 times theorem prover too weak. 185 trivial. 0 not checked. [2022-03-20 13:43:15,237 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 13:43:15,493 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 20 proven. 4 refuted. 0 times theorem prover too weak. 185 trivial. 0 not checked. [2022-03-20 13:43:15,493 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:43:15,494 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1955344481] [2022-03-20 13:43:15,494 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 13:43:15,494 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [370626895] [2022-03-20 13:43:15,494 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [370626895] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 13:43:15,494 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 13:43:15,494 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2022-03-20 13:43:15,494 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:43:15,494 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1690265501] [2022-03-20 13:43:15,494 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1690265501] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:43:15,495 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:43:15,495 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-03-20 13:43:15,495 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1089467091] [2022-03-20 13:43:15,495 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:43:15,495 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-20 13:43:15,495 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:15,495 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-20 13:43:15,496 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2022-03-20 13:43:15,496 INFO L87 Difference]: Start difference. First operand 103 states and 118 transitions. Second operand has 7 states, 6 states have (on average 3.5) internal successors, (21), 6 states have internal predecessors, (21), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-03-20 13:43:15,685 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:43:15,686 INFO L93 Difference]: Finished difference Result 116 states and 134 transitions. [2022-03-20 13:43:15,687 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 13:43:15,687 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 3.5) internal successors, (21), 6 states have internal predecessors, (21), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 75 [2022-03-20 13:43:15,687 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:43:15,688 INFO L225 Difference]: With dead ends: 116 [2022-03-20 13:43:15,688 INFO L226 Difference]: Without dead ends: 92 [2022-03-20 13:43:15,689 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 140 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2022-03-20 13:43:15,689 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 8 mSDsluCounter, 153 mSDsCounter, 0 mSdLazyCounter, 91 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 191 SdHoareTripleChecker+Invalid, 97 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 91 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 13:43:15,689 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 191 Invalid, 97 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 91 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 13:43:15,690 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-03-20 13:43:15,700 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 90. [2022-03-20 13:43:15,700 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 53 states have (on average 1.1320754716981132) internal successors, (60), 57 states have internal predecessors, (60), 24 states have call successors, (24), 13 states have call predecessors, (24), 12 states have return successors, (22), 19 states have call predecessors, (22), 22 states have call successors, (22) [2022-03-20 13:43:15,701 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 106 transitions. [2022-03-20 13:43:15,701 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 106 transitions. Word has length 75 [2022-03-20 13:43:15,701 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:43:15,702 INFO L478 AbstractCegarLoop]: Abstraction has 90 states and 106 transitions. [2022-03-20 13:43:15,702 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 3.5) internal successors, (21), 6 states have internal predecessors, (21), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-03-20 13:43:15,702 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 106 transitions. [2022-03-20 13:43:15,702 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2022-03-20 13:43:15,702 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:43:15,703 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:43:15,728 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-20 13:43:15,923 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:43:15,924 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:43:15,924 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:43:15,924 INFO L85 PathProgramCache]: Analyzing trace with hash 330473976, now seen corresponding path program 5 times [2022-03-20 13:43:15,924 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:43:15,924 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [474809807] [2022-03-20 13:43:15,930 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 2 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 13:43:15,930 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-03-20 13:43:15,930 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 13:43:15,930 INFO L85 PathProgramCache]: Analyzing trace with hash 330473976, now seen corresponding path program 6 times [2022-03-20 13:43:15,930 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:43:15,930 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1350015393] [2022-03-20 13:43:15,930 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:43:15,930 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:43:15,937 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:43:15,937 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [989152129] [2022-03-20 13:43:15,938 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 13:43:15,938 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:43:15,938 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:43:15,944 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:43:15,964 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-20 13:43:15,996 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-03-20 13:43:15,996 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:43:15,997 INFO L263 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 26 conjunts are in the unsatisfiable core [2022-03-20 13:43:15,999 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:43:33,011 INFO L134 CoverageAnalysis]: Checked inductivity of 259 backedges. 55 proven. 9 refuted. 0 times theorem prover too weak. 195 trivial. 0 not checked. [2022-03-20 13:43:33,011 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 13:44:30,963 WARN L232 SmtUtils]: Spent 35.17s on a formula simplification that was a NOOP. DAG size: 51 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 13:45:28,684 INFO L134 CoverageAnalysis]: Checked inductivity of 259 backedges. 45 proven. 19 refuted. 0 times theorem prover too weak. 195 trivial. 0 not checked. [2022-03-20 13:45:28,685 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:45:28,685 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1350015393] [2022-03-20 13:45:28,685 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 13:45:28,685 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [989152129] [2022-03-20 13:45:28,685 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [989152129] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 13:45:28,685 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 13:45:28,685 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 15 [2022-03-20 13:45:28,686 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:45:28,686 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [474809807] [2022-03-20 13:45:28,686 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [474809807] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:45:28,686 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:45:28,686 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-03-20 13:45:28,686 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [271289002] [2022-03-20 13:45:28,686 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:45:28,687 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-20 13:45:28,687 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:45:28,687 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-20 13:45:28,687 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=162, Unknown=2, NotChecked=0, Total=210 [2022-03-20 13:45:28,688 INFO L87 Difference]: Start difference. First operand 90 states and 106 transitions. Second operand has 11 states, 11 states have (on average 2.272727272727273) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-03-20 13:45:29,510 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:45:29,510 INFO L93 Difference]: Finished difference Result 116 states and 137 transitions. [2022-03-20 13:45:29,511 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 13:45:29,511 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.272727272727273) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 81 [2022-03-20 13:45:29,511 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:45:29,512 INFO L225 Difference]: With dead ends: 116 [2022-03-20 13:45:29,512 INFO L226 Difference]: Without dead ends: 104 [2022-03-20 13:45:29,513 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 163 GetRequests, 145 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 44.2s TimeCoverageRelationStatistics Valid=59, Invalid=211, Unknown=2, NotChecked=0, Total=272 [2022-03-20 13:45:29,514 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 30 mSDsluCounter, 134 mSDsCounter, 0 mSdLazyCounter, 188 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 164 SdHoareTripleChecker+Invalid, 217 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 188 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-03-20 13:45:29,514 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [43 Valid, 164 Invalid, 217 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 188 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-03-20 13:45:29,514 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2022-03-20 13:45:29,528 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 103. [2022-03-20 13:45:29,528 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 61 states have (on average 1.1311475409836065) internal successors, (69), 67 states have internal predecessors, (69), 28 states have call successors, (28), 14 states have call predecessors, (28), 13 states have return successors, (26), 21 states have call predecessors, (26), 26 states have call successors, (26) [2022-03-20 13:45:29,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 123 transitions. [2022-03-20 13:45:29,529 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 123 transitions. Word has length 81 [2022-03-20 13:45:29,529 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:45:29,530 INFO L478 AbstractCegarLoop]: Abstraction has 103 states and 123 transitions. [2022-03-20 13:45:29,530 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.272727272727273) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-03-20 13:45:29,530 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 123 transitions. [2022-03-20 13:45:29,530 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2022-03-20 13:45:29,530 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:45:29,531 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:45:29,557 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-03-20 13:45:29,743 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:45:29,744 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:45:29,744 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:45:29,744 INFO L85 PathProgramCache]: Analyzing trace with hash -454578581, now seen corresponding path program 7 times [2022-03-20 13:45:29,744 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:45:29,744 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1368998551] [2022-03-20 13:45:29,748 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 2 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 13:45:29,748 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-03-20 13:45:29,748 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 13:45:29,748 INFO L85 PathProgramCache]: Analyzing trace with hash -454578581, now seen corresponding path program 8 times [2022-03-20 13:45:29,748 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:45:29,749 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [25983057] [2022-03-20 13:45:29,749 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:45:29,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:45:29,756 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:45:29,756 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [270087408] [2022-03-20 13:45:29,756 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 13:45:29,756 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:45:29,756 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:45:29,759 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:45:29,761 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-20 13:45:29,815 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 13:45:29,815 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:45:29,816 INFO L263 TraceCheckSpWp]: Trace formula consists of 203 conjuncts, 26 conjunts are in the unsatisfiable core [2022-03-20 13:45:29,818 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:45:30,207 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 24 proven. 18 refuted. 0 times theorem prover too weak. 264 trivial. 0 not checked. [2022-03-20 13:45:30,207 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 13:45:33,149 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 24 proven. 13 refuted. 0 times theorem prover too weak. 269 trivial. 0 not checked. [2022-03-20 13:45:33,149 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:45:33,149 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [25983057] [2022-03-20 13:45:33,149 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 13:45:33,149 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [270087408] [2022-03-20 13:45:33,150 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [270087408] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 13:45:33,150 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 13:45:33,150 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 15 [2022-03-20 13:45:33,150 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:45:33,150 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1368998551] [2022-03-20 13:45:33,150 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1368998551] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:45:33,150 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:45:33,150 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-03-20 13:45:33,150 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [280902353] [2022-03-20 13:45:33,150 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:45:33,151 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-20 13:45:33,151 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:45:33,151 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-20 13:45:33,151 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=162, Unknown=0, NotChecked=0, Total=210 [2022-03-20 13:45:33,151 INFO L87 Difference]: Start difference. First operand 103 states and 123 transitions. Second operand has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 9 states have internal predecessors, (23), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 6 states have call predecessors, (14), 5 states have call successors, (14) [2022-03-20 13:45:33,469 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:45:33,470 INFO L93 Difference]: Finished difference Result 191 states and 248 transitions. [2022-03-20 13:45:33,471 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 13:45:33,471 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 9 states have internal predecessors, (23), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 6 states have call predecessors, (14), 5 states have call successors, (14) Word has length 86 [2022-03-20 13:45:33,471 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:45:33,472 INFO L225 Difference]: With dead ends: 191 [2022-03-20 13:45:33,473 INFO L226 Difference]: Without dead ends: 144 [2022-03-20 13:45:33,473 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 155 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=56, Invalid=216, Unknown=0, NotChecked=0, Total=272 [2022-03-20 13:45:33,474 INFO L913 BasicCegarLoop]: 54 mSDtfsCounter, 32 mSDsluCounter, 327 mSDsCounter, 0 mSdLazyCounter, 249 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 381 SdHoareTripleChecker+Invalid, 276 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 249 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-20 13:45:33,474 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 381 Invalid, 276 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 249 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-20 13:45:33,474 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 144 states. [2022-03-20 13:45:33,495 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 144 to 144. [2022-03-20 13:45:33,496 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 85 states have (on average 1.1294117647058823) internal successors, (96), 94 states have internal predecessors, (96), 42 states have call successors, (42), 17 states have call predecessors, (42), 16 states have return successors, (38), 32 states have call predecessors, (38), 38 states have call successors, (38) [2022-03-20 13:45:33,497 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 176 transitions. [2022-03-20 13:45:33,497 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 176 transitions. Word has length 86 [2022-03-20 13:45:33,498 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:45:33,498 INFO L478 AbstractCegarLoop]: Abstraction has 144 states and 176 transitions. [2022-03-20 13:45:33,498 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 9 states have internal predecessors, (23), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 6 states have call predecessors, (14), 5 states have call successors, (14) [2022-03-20 13:45:33,498 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 176 transitions. [2022-03-20 13:45:33,503 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2022-03-20 13:45:33,503 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:45:33,503 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:45:33,529 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-20 13:45:33,718 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-03-20 13:45:33,718 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:45:33,718 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:45:33,719 INFO L85 PathProgramCache]: Analyzing trace with hash -132947769, now seen corresponding path program 9 times [2022-03-20 13:45:33,719 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:45:33,719 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [386497192] [2022-03-20 13:45:33,722 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 2 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 13:45:33,722 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-03-20 13:45:33,722 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 13:45:33,722 INFO L85 PathProgramCache]: Analyzing trace with hash -132947769, now seen corresponding path program 10 times [2022-03-20 13:45:33,723 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:45:33,723 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [86463268] [2022-03-20 13:45:33,723 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:45:33,723 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:45:33,729 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:45:33,729 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [126491729] [2022-03-20 13:45:33,729 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 13:45:33,729 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:45:33,729 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:45:33,730 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:45:33,736 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-03-20 13:45:33,835 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 13:45:33,835 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:45:33,837 INFO L263 TraceCheckSpWp]: Trace formula consists of 223 conjuncts, 42 conjunts are in the unsatisfiable core [2022-03-20 13:45:33,839 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:45:34,887 INFO L134 CoverageAnalysis]: Checked inductivity of 362 backedges. 61 proven. 25 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2022-03-20 13:45:34,887 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 13:46:01,093 WARN L232 SmtUtils]: Spent 14.14s on a formula simplification that was a NOOP. DAG size: 58 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 13:47:29,354 WARN L232 SmtUtils]: Spent 22.64s on a formula simplification that was a NOOP. DAG size: 60 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 13:48:52,483 WARN L232 SmtUtils]: Spent 43.76s on a formula simplification that was a NOOP. DAG size: 130 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 13:50:41,495 INFO L134 CoverageAnalysis]: Checked inductivity of 362 backedges. 61 proven. 25 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2022-03-20 13:50:41,495 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:50:41,495 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [86463268] [2022-03-20 13:50:41,495 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 13:50:41,495 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [126491729] [2022-03-20 13:50:41,496 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [126491729] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 13:50:41,496 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 13:50:41,496 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 25 [2022-03-20 13:50:41,496 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:50:41,496 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [386497192] [2022-03-20 13:50:41,496 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [386497192] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:50:41,496 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:50:41,496 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-03-20 13:50:41,496 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1706736106] [2022-03-20 13:50:41,496 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:50:41,497 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-20 13:50:41,497 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:50:41,497 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-20 13:50:41,507 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=486, Unknown=2, NotChecked=0, Total=600 [2022-03-20 13:50:41,507 INFO L87 Difference]: Start difference. First operand 144 states and 176 transitions. Second operand has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 7 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) [2022-03-20 13:50:43,423 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:50:43,423 INFO L93 Difference]: Finished difference Result 181 states and 207 transitions. [2022-03-20 13:50:43,424 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-20 13:50:43,424 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 7 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) Word has length 94 [2022-03-20 13:50:43,424 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:50:43,425 INFO L225 Difference]: With dead ends: 181 [2022-03-20 13:50:43,425 INFO L226 Difference]: Without dead ends: 151 [2022-03-20 13:50:43,426 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 189 GetRequests, 163 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 124 ImplicationChecksByTransitivity, 96.1s TimeCoverageRelationStatistics Valid=125, Invalid=575, Unknown=2, NotChecked=0, Total=702 [2022-03-20 13:50:43,426 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 18 mSDsluCounter, 315 mSDsCounter, 0 mSdLazyCounter, 389 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 357 SdHoareTripleChecker+Invalid, 418 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 389 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-03-20 13:50:43,427 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 357 Invalid, 418 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 389 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2022-03-20 13:50:43,427 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2022-03-20 13:50:43,446 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 151. [2022-03-20 13:50:43,446 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 151 states, 92 states have (on average 1.0978260869565217) internal successors, (101), 99 states have internal predecessors, (101), 38 states have call successors, (38), 21 states have call predecessors, (38), 20 states have return successors, (35), 30 states have call predecessors, (35), 35 states have call successors, (35) [2022-03-20 13:50:43,447 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 151 states to 151 states and 174 transitions. [2022-03-20 13:50:43,447 INFO L78 Accepts]: Start accepts. Automaton has 151 states and 174 transitions. Word has length 94 [2022-03-20 13:50:43,447 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:50:43,448 INFO L478 AbstractCegarLoop]: Abstraction has 151 states and 174 transitions. [2022-03-20 13:50:43,448 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 7 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) [2022-03-20 13:50:43,448 INFO L276 IsEmpty]: Start isEmpty. Operand 151 states and 174 transitions. [2022-03-20 13:50:43,449 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2022-03-20 13:50:43,449 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:50:43,449 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:50:43,466 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-03-20 13:50:43,651 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:50:43,651 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:50:43,652 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:50:43,652 INFO L85 PathProgramCache]: Analyzing trace with hash -321511332, now seen corresponding path program 11 times [2022-03-20 13:50:43,652 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:50:43,652 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [314999861] [2022-03-20 13:50:43,656 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 2 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 13:50:43,656 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-03-20 13:50:43,656 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 13:50:43,656 INFO L85 PathProgramCache]: Analyzing trace with hash -321511332, now seen corresponding path program 12 times [2022-03-20 13:50:43,656 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:50:43,656 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1024028717] [2022-03-20 13:50:43,656 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:50:43,656 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:50:43,668 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:50:43,668 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2026133918] [2022-03-20 13:50:43,669 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 13:50:43,669 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:50:43,669 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:50:43,670 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:50:43,672 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-03-20 13:50:43,775 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2022-03-20 13:50:43,775 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:50:43,776 INFO L263 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 24 conjunts are in the unsatisfiable core [2022-03-20 13:50:43,778 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:50:44,603 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 13:50:44,716 INFO L134 CoverageAnalysis]: Checked inductivity of 483 backedges. 70 proven. 22 refuted. 0 times theorem prover too weak. 391 trivial. 0 not checked. [2022-03-20 13:50:44,716 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 13:50:46,197 INFO L134 CoverageAnalysis]: Checked inductivity of 483 backedges. 69 proven. 23 refuted. 0 times theorem prover too weak. 391 trivial. 0 not checked. [2022-03-20 13:50:46,198 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:50:46,198 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1024028717] [2022-03-20 13:50:46,198 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 13:50:46,198 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2026133918] [2022-03-20 13:50:46,198 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2026133918] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 13:50:46,198 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 13:50:46,198 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 12 [2022-03-20 13:50:46,198 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:50:46,198 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [314999861] [2022-03-20 13:50:46,199 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [314999861] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:50:46,199 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:50:46,199 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-03-20 13:50:46,199 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [557102704] [2022-03-20 13:50:46,199 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:50:46,199 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-20 13:50:46,199 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:50:46,199 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-20 13:50:46,200 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2022-03-20 13:50:46,200 INFO L87 Difference]: Start difference. First operand 151 states and 174 transitions. Second operand has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 5 states have call predecessors, (12), 4 states have call successors, (12) [2022-03-20 13:50:47,474 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.22s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 13:50:49,407 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.60s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 13:50:51,965 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.81s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 13:50:54,422 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:50:54,422 INFO L93 Difference]: Finished difference Result 163 states and 185 transitions. [2022-03-20 13:50:54,423 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 13:50:54,423 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 5 states have call predecessors, (12), 4 states have call successors, (12) Word has length 103 [2022-03-20 13:50:54,423 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:50:54,424 INFO L225 Difference]: With dead ends: 163 [2022-03-20 13:50:54,424 INFO L226 Difference]: Without dead ends: 161 [2022-03-20 13:50:54,425 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 207 GetRequests, 193 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=44, Invalid=138, Unknown=0, NotChecked=0, Total=182 [2022-03-20 13:50:54,425 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 29 mSDsluCounter, 140 mSDsCounter, 0 mSdLazyCounter, 181 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 215 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 181 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.2s IncrementalHoareTripleChecker+Time [2022-03-20 13:50:54,425 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [38 Valid, 169 Invalid, 215 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 181 Invalid, 0 Unknown, 0 Unchecked, 8.2s Time] [2022-03-20 13:50:54,426 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2022-03-20 13:50:54,445 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 160. [2022-03-20 13:50:54,445 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 160 states, 98 states have (on average 1.0918367346938775) internal successors, (107), 105 states have internal predecessors, (107), 39 states have call successors, (39), 23 states have call predecessors, (39), 22 states have return successors, (36), 31 states have call predecessors, (36), 36 states have call successors, (36) [2022-03-20 13:50:54,446 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 160 states to 160 states and 182 transitions. [2022-03-20 13:50:54,446 INFO L78 Accepts]: Start accepts. Automaton has 160 states and 182 transitions. Word has length 103 [2022-03-20 13:50:54,447 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:50:54,447 INFO L478 AbstractCegarLoop]: Abstraction has 160 states and 182 transitions. [2022-03-20 13:50:54,447 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 5 states have call predecessors, (12), 4 states have call successors, (12) [2022-03-20 13:50:54,447 INFO L276 IsEmpty]: Start isEmpty. Operand 160 states and 182 transitions. [2022-03-20 13:50:54,448 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2022-03-20 13:50:54,448 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:50:54,448 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:50:54,470 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2022-03-20 13:50:54,663 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-03-20 13:50:54,664 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:50:54,664 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:50:54,664 INFO L85 PathProgramCache]: Analyzing trace with hash 1306280540, now seen corresponding path program 3 times [2022-03-20 13:50:54,664 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:50:54,664 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1496733001] [2022-03-20 13:50:54,667 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 2 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 13:50:54,667 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-03-20 13:50:54,667 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 13:50:54,667 INFO L85 PathProgramCache]: Analyzing trace with hash 1306280540, now seen corresponding path program 4 times [2022-03-20 13:50:54,667 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:50:54,667 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1477144729] [2022-03-20 13:50:54,667 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:50:54,668 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:50:54,674 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:50:54,674 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [963988949] [2022-03-20 13:50:54,674 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 13:50:54,674 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:50:54,674 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:50:54,676 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:50:54,685 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-03-20 13:50:54,802 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 13:50:54,802 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:50:54,803 INFO L263 TraceCheckSpWp]: Trace formula consists of 243 conjuncts, 48 conjunts are in the unsatisfiable core [2022-03-20 13:50:54,805 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:50:56,019 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 13:50:56,022 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 13:50:56,278 INFO L134 CoverageAnalysis]: Checked inductivity of 478 backedges. 106 proven. 30 refuted. 0 times theorem prover too weak. 342 trivial. 0 not checked. [2022-03-20 13:50:56,278 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 13:50:56,627 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 13:50:56,629 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 13:50:56,796 INFO L134 CoverageAnalysis]: Checked inductivity of 478 backedges. 110 proven. 2 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2022-03-20 13:50:56,797 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:50:56,797 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1477144729] [2022-03-20 13:50:56,797 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 13:50:56,797 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [963988949] [2022-03-20 13:50:56,797 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [963988949] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 13:50:56,797 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 13:50:56,797 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 9] total 20 [2022-03-20 13:50:56,797 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:50:56,797 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1496733001] [2022-03-20 13:50:56,797 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1496733001] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:50:56,798 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:50:56,798 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [16] imperfect sequences [] total 16 [2022-03-20 13:50:56,798 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [892716857] [2022-03-20 13:50:56,798 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:50:56,798 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-20 13:50:56,798 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:50:56,799 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-20 13:50:56,799 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=302, Unknown=0, NotChecked=0, Total=380 [2022-03-20 13:50:56,799 INFO L87 Difference]: Start difference. First operand 160 states and 182 transitions. Second operand has 16 states, 14 states have (on average 2.142857142857143) internal successors, (30), 14 states have internal predecessors, (30), 9 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 8 states have call predecessors, (17), 8 states have call successors, (17) [2022-03-20 13:50:57,833 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:50:57,833 INFO L93 Difference]: Finished difference Result 166 states and 187 transitions. [2022-03-20 13:50:57,833 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-20 13:50:57,834 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.142857142857143) internal successors, (30), 14 states have internal predecessors, (30), 9 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 8 states have call predecessors, (17), 8 states have call successors, (17) Word has length 105 [2022-03-20 13:50:57,834 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:50:57,835 INFO L225 Difference]: With dead ends: 166 [2022-03-20 13:50:57,835 INFO L226 Difference]: Without dead ends: 129 [2022-03-20 13:50:57,836 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 189 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 71 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=91, Invalid=371, Unknown=0, NotChecked=0, Total=462 [2022-03-20 13:50:57,836 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 16 mSDsluCounter, 321 mSDsCounter, 0 mSdLazyCounter, 390 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 359 SdHoareTripleChecker+Invalid, 413 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 390 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2022-03-20 13:50:57,836 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [18 Valid, 359 Invalid, 413 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 390 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2022-03-20 13:50:57,837 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2022-03-20 13:50:57,851 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 129. [2022-03-20 13:50:57,851 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 129 states, 78 states have (on average 1.1025641025641026) internal successors, (86), 84 states have internal predecessors, (86), 32 states have call successors, (32), 19 states have call predecessors, (32), 18 states have return successors, (30), 25 states have call predecessors, (30), 30 states have call successors, (30) [2022-03-20 13:50:57,852 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 148 transitions. [2022-03-20 13:50:57,852 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 148 transitions. Word has length 105 [2022-03-20 13:50:57,852 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:50:57,852 INFO L478 AbstractCegarLoop]: Abstraction has 129 states and 148 transitions. [2022-03-20 13:50:57,852 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.142857142857143) internal successors, (30), 14 states have internal predecessors, (30), 9 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 8 states have call predecessors, (17), 8 states have call successors, (17) [2022-03-20 13:50:57,852 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 148 transitions. [2022-03-20 13:50:57,853 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2022-03-20 13:50:57,853 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:50:57,854 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:50:57,879 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-03-20 13:50:58,067 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-03-20 13:50:58,067 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:50:58,068 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:50:58,068 INFO L85 PathProgramCache]: Analyzing trace with hash -76721736, now seen corresponding path program 13 times [2022-03-20 13:50:58,068 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:50:58,068 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1235263226] [2022-03-20 13:50:58,070 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 2 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 13:50:58,071 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-03-20 13:50:58,071 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 13:50:58,071 INFO L85 PathProgramCache]: Analyzing trace with hash -76721736, now seen corresponding path program 14 times [2022-03-20 13:50:58,071 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:50:58,071 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [258159647] [2022-03-20 13:50:58,071 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:50:58,071 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:50:58,080 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:50:58,080 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [656852561] [2022-03-20 13:50:58,080 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 13:50:58,080 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:50:58,080 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:50:58,085 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:50:58,086 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-03-20 13:50:58,195 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 13:50:58,195 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:50:58,196 INFO L263 TraceCheckSpWp]: Trace formula consists of 256 conjuncts, 48 conjunts are in the unsatisfiable core [2022-03-20 13:50:58,197 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:50:59,101 INFO L134 CoverageAnalysis]: Checked inductivity of 551 backedges. 32 proven. 39 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-03-20 13:50:59,102 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 13:51:34,621 WARN L232 SmtUtils]: Spent 6.66s on a formula simplification that was a NOOP. DAG size: 142 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 13:52:05,157 INFO L134 CoverageAnalysis]: Checked inductivity of 551 backedges. 32 proven. 39 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-03-20 13:52:05,157 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:52:05,157 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [258159647] [2022-03-20 13:52:05,157 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 13:52:05,157 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [656852561] [2022-03-20 13:52:05,158 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [656852561] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 13:52:05,158 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 13:52:05,158 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 25 [2022-03-20 13:52:05,158 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:52:05,158 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1235263226] [2022-03-20 13:52:05,158 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1235263226] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:52:05,158 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:52:05,158 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [16] imperfect sequences [] total 16 [2022-03-20 13:52:05,158 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [712993451] [2022-03-20 13:52:05,158 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:52:05,159 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-20 13:52:05,159 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:52:05,159 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-20 13:52:05,160 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=476, Unknown=0, NotChecked=0, Total=600 [2022-03-20 13:52:05,160 INFO L87 Difference]: Start difference. First operand 129 states and 148 transitions. Second operand has 16 states, 16 states have (on average 1.75) internal successors, (28), 14 states have internal predecessors, (28), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 8 states have call predecessors, (18), 7 states have call successors, (18) [2022-03-20 13:52:06,148 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:52:06,149 INFO L93 Difference]: Finished difference Result 230 states and 275 transitions. [2022-03-20 13:52:06,149 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-03-20 13:52:06,149 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 1.75) internal successors, (28), 14 states have internal predecessors, (28), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 8 states have call predecessors, (18), 7 states have call successors, (18) Word has length 111 [2022-03-20 13:52:06,150 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:52:06,151 INFO L225 Difference]: With dead ends: 230 [2022-03-20 13:52:06,151 INFO L226 Difference]: Without dead ends: 185 [2022-03-20 13:52:06,152 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 223 GetRequests, 197 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 174 ImplicationChecksByTransitivity, 16.1s TimeCoverageRelationStatistics Valid=132, Invalid=570, Unknown=0, NotChecked=0, Total=702 [2022-03-20 13:52:06,152 INFO L913 BasicCegarLoop]: 53 mSDtfsCounter, 30 mSDsluCounter, 480 mSDsCounter, 0 mSdLazyCounter, 544 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 533 SdHoareTripleChecker+Invalid, 594 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 544 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-03-20 13:52:06,152 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 533 Invalid, 594 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 544 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-03-20 13:52:06,153 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 185 states. [2022-03-20 13:52:06,173 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 185 to 183. [2022-03-20 13:52:06,174 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 183 states, 113 states have (on average 1.1061946902654867) internal successors, (125), 120 states have internal predecessors, (125), 44 states have call successors, (44), 26 states have call predecessors, (44), 25 states have return successors, (42), 36 states have call predecessors, (42), 42 states have call successors, (42) [2022-03-20 13:52:06,175 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 183 states to 183 states and 211 transitions. [2022-03-20 13:52:06,175 INFO L78 Accepts]: Start accepts. Automaton has 183 states and 211 transitions. Word has length 111 [2022-03-20 13:52:06,175 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:52:06,175 INFO L478 AbstractCegarLoop]: Abstraction has 183 states and 211 transitions. [2022-03-20 13:52:06,175 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 1.75) internal successors, (28), 14 states have internal predecessors, (28), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 8 states have call predecessors, (18), 7 states have call successors, (18) [2022-03-20 13:52:06,175 INFO L276 IsEmpty]: Start isEmpty. Operand 183 states and 211 transitions. [2022-03-20 13:52:06,176 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2022-03-20 13:52:06,176 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:52:06,177 INFO L499 BasicCegarLoop]: trace histogram [18, 17, 17, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:52:06,195 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-03-20 13:52:06,383 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-03-20 13:52:06,383 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:52:06,384 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:52:06,384 INFO L85 PathProgramCache]: Analyzing trace with hash -1457203541, now seen corresponding path program 15 times [2022-03-20 13:52:06,384 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:52:06,384 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1173553474] [2022-03-20 13:52:06,386 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 2 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 13:52:06,386 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-03-20 13:52:06,386 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 13:52:06,386 INFO L85 PathProgramCache]: Analyzing trace with hash -1457203541, now seen corresponding path program 16 times [2022-03-20 13:52:06,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:52:06,386 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [269633004] [2022-03-20 13:52:06,386 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:52:06,387 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:52:06,393 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:52:06,393 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [830101113] [2022-03-20 13:52:06,393 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 13:52:06,393 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:52:06,394 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:52:06,395 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:52:06,402 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-03-20 13:52:06,460 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 13:52:06,460 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:52:06,461 INFO L263 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 32 conjunts are in the unsatisfiable core [2022-03-20 13:52:06,462 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:52:06,847 INFO L134 CoverageAnalysis]: Checked inductivity of 619 backedges. 34 proven. 41 refuted. 0 times theorem prover too weak. 544 trivial. 0 not checked. [2022-03-20 13:52:06,848 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 13:52:19,508 INFO L134 CoverageAnalysis]: Checked inductivity of 619 backedges. 34 proven. 36 refuted. 0 times theorem prover too weak. 549 trivial. 0 not checked. [2022-03-20 13:52:19,509 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 13:52:19,509 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [269633004] [2022-03-20 13:52:19,509 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 13:52:19,509 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [830101113] [2022-03-20 13:52:19,509 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [830101113] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 13:52:19,509 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 13:52:19,509 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 12] total 21 [2022-03-20 13:52:19,509 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 13:52:19,509 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1173553474] [2022-03-20 13:52:19,510 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1173553474] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 13:52:19,510 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 13:52:19,510 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-03-20 13:52:19,510 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1002788161] [2022-03-20 13:52:19,510 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 13:52:19,510 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-20 13:52:19,510 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 13:52:19,510 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-20 13:52:19,511 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=311, Unknown=0, NotChecked=0, Total=420 [2022-03-20 13:52:19,511 INFO L87 Difference]: Start difference. First operand 183 states and 211 transitions. Second operand has 13 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 12 states have internal predecessors, (28), 8 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 8 states have call predecessors, (19), 8 states have call successors, (19) [2022-03-20 13:52:19,938 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 13:52:19,938 INFO L93 Difference]: Finished difference Result 230 states and 272 transitions. [2022-03-20 13:52:19,938 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-20 13:52:19,939 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 12 states have internal predecessors, (28), 8 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 8 states have call predecessors, (19), 8 states have call successors, (19) Word has length 116 [2022-03-20 13:52:19,939 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 13:52:19,940 INFO L225 Difference]: With dead ends: 230 [2022-03-20 13:52:19,940 INFO L226 Difference]: Without dead ends: 201 [2022-03-20 13:52:19,941 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 232 GetRequests, 210 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 136 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=113, Invalid=349, Unknown=0, NotChecked=0, Total=462 [2022-03-20 13:52:19,941 INFO L913 BasicCegarLoop]: 70 mSDtfsCounter, 15 mSDsluCounter, 533 mSDsCounter, 0 mSdLazyCounter, 364 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 603 SdHoareTripleChecker+Invalid, 384 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 364 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-20 13:52:19,941 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [20 Valid, 603 Invalid, 384 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 364 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-20 13:52:19,942 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 201 states. [2022-03-20 13:52:19,964 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 201 to 199. [2022-03-20 13:52:19,965 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 199 states, 123 states have (on average 1.0975609756097562) internal successors, (135), 132 states have internal predecessors, (135), 48 states have call successors, (48), 28 states have call predecessors, (48), 27 states have return successors, (45), 38 states have call predecessors, (45), 45 states have call successors, (45) [2022-03-20 13:52:19,966 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 228 transitions. [2022-03-20 13:52:19,966 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 228 transitions. Word has length 116 [2022-03-20 13:52:19,966 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 13:52:19,966 INFO L478 AbstractCegarLoop]: Abstraction has 199 states and 228 transitions. [2022-03-20 13:52:19,966 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 12 states have internal predecessors, (28), 8 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 8 states have call predecessors, (19), 8 states have call successors, (19) [2022-03-20 13:52:19,967 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 228 transitions. [2022-03-20 13:52:19,968 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2022-03-20 13:52:19,968 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 13:52:19,968 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 13:52:19,991 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-03-20 13:52:20,183 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-03-20 13:52:20,183 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 13:52:20,184 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 13:52:20,184 INFO L85 PathProgramCache]: Analyzing trace with hash -238794489, now seen corresponding path program 17 times [2022-03-20 13:52:20,184 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 13:52:20,184 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [546026774] [2022-03-20 13:52:20,187 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 2 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 13:52:20,187 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-03-20 13:52:20,187 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 13:52:20,187 INFO L85 PathProgramCache]: Analyzing trace with hash -238794489, now seen corresponding path program 18 times [2022-03-20 13:52:20,187 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 13:52:20,187 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1729381374] [2022-03-20 13:52:20,187 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 13:52:20,188 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 13:52:20,198 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 13:52:20,199 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1078494520] [2022-03-20 13:52:20,199 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 13:52:20,199 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 13:52:20,199 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 13:52:20,205 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 13:52:20,206 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-03-20 13:52:20,563 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) [2022-03-20 13:52:20,563 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 13:52:20,565 INFO L263 TraceCheckSpWp]: Trace formula consists of 285 conjuncts, 61 conjunts are in the unsatisfiable core [2022-03-20 13:52:20,567 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 13:52:21,736 INFO L134 CoverageAnalysis]: Checked inductivity of 699 backedges. 130 proven. 53 refuted. 0 times theorem prover too weak. 516 trivial. 0 not checked. [2022-03-20 13:52:21,736 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 13:53:09,601 WARN L232 SmtUtils]: Spent 31.71s on a formula simplification that was a NOOP. DAG size: 54 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 13:54:14,914 WARN L232 SmtUtils]: Spent 9.01s on a formula simplification that was a NOOP. DAG size: 98 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 13:55:19,713 WARN L232 SmtUtils]: Spent 15.50s on a formula simplification that was a NOOP. DAG size: 100 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 13:56:38,936 WARN L232 SmtUtils]: Spent 37.86s on a formula simplification that was a NOOP. DAG size: 208 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate)