/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_valuebound50.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 23:21:47,512 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 23:21:47,514 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 23:21:47,549 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 23:21:47,550 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 23:21:47,550 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 23:21:47,551 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 23:21:47,552 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 23:21:47,554 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 23:21:47,554 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 23:21:47,555 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 23:21:47,556 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 23:21:47,556 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 23:21:47,557 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 23:21:47,558 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 23:21:47,558 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 23:21:47,559 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 23:21:47,560 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 23:21:47,561 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 23:21:47,563 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 23:21:47,564 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 23:21:47,565 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 23:21:47,565 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 23:21:47,566 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 23:21:47,567 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 23:21:47,569 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 23:21:47,569 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 23:21:47,569 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 23:21:47,570 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 23:21:47,570 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 23:21:47,571 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 23:21:47,571 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 23:21:47,571 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 23:21:47,572 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 23:21:47,572 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 23:21:47,573 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 23:21:47,573 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 23:21:47,573 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 23:21:47,573 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 23:21:47,574 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 23:21:47,574 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 23:21:47,583 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 23:21:47,583 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-03-20 23:21:47,589 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 23:21:47,589 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 23:21:47,589 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 23:21:47,590 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 23:21:47,590 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 23:21:47,590 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 23:21:47,590 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 23:21:47,590 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 23:21:47,590 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 23:21:47,590 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 23:21:47,590 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 23:21:47,591 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 23:21:47,591 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 23:21:47,591 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-20 23:21:47,591 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 23:21:47,591 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 23:21:47,591 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 23:21:47,591 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-03-20 23:21:47,591 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-03-20 23:21:47,592 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-03-20 23:21:47,592 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-20 23:21:47,592 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-03-20 23:21:47,592 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 23:21:47,779 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 23:21:47,799 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 23:21:47,801 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 23:21:47,802 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 23:21:47,802 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 23:21:47,803 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_valuebound50.c [2022-03-20 23:21:47,855 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a0ff8efba/411ce8f6745340b5b754bcbcb6061a4b/FLAG2846c1187 [2022-03-20 23:21:48,220 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 23:21:48,221 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_valuebound50.c [2022-03-20 23:21:48,229 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a0ff8efba/411ce8f6745340b5b754bcbcb6061a4b/FLAG2846c1187 [2022-03-20 23:21:48,238 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a0ff8efba/411ce8f6745340b5b754bcbcb6061a4b [2022-03-20 23:21:48,240 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 23:21:48,241 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-03-20 23:21:48,242 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 23:21:48,242 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 23:21:48,244 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 23:21:48,245 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 11:21:48" (1/1) ... [2022-03-20 23:21:48,246 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@23af6a92 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:21:48, skipping insertion in model container [2022-03-20 23:21:48,246 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 11:21:48" (1/1) ... [2022-03-20 23:21:48,252 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 23:21:48,261 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 23:21:48,414 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_valuebound50.c[458,471] [2022-03-20 23:21:48,426 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 23:21:48,430 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 23:21:48,438 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_valuebound50.c[458,471] [2022-03-20 23:21:48,443 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 23:21:48,451 INFO L208 MainTranslator]: Completed translation [2022-03-20 23:21:48,451 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:21:48 WrapperNode [2022-03-20 23:21:48,451 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 23:21:48,452 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 23:21:48,452 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 23:21:48,452 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 23:21:48,459 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:21:48" (1/1) ... [2022-03-20 23:21:48,459 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:21:48" (1/1) ... [2022-03-20 23:21:48,464 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:21:48" (1/1) ... [2022-03-20 23:21:48,464 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:21:48" (1/1) ... [2022-03-20 23:21:48,466 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:21:48" (1/1) ... [2022-03-20 23:21:48,469 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:21:48" (1/1) ... [2022-03-20 23:21:48,469 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:21:48" (1/1) ... [2022-03-20 23:21:48,470 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 23:21:48,471 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 23:21:48,471 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 23:21:48,471 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 23:21:48,472 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:21:48" (1/1) ... [2022-03-20 23:21:48,476 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 23:21:48,482 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:21:48,491 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 23:21:48,499 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 23:21:48,517 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 23:21:48,518 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 23:21:48,518 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 23:21:48,518 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 23:21:48,518 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 23:21:48,518 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 23:21:48,518 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 23:21:48,518 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 23:21:48,518 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 23:21:48,518 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 23:21:48,518 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_short [2022-03-20 23:21:48,519 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 23:21:48,519 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 23:21:48,519 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 23:21:48,519 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 23:21:48,519 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 23:21:48,519 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 23:21:48,519 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 23:21:48,519 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 23:21:48,519 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 23:21:48,569 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 23:21:48,570 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 23:21:48,647 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 23:21:48,651 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 23:21:48,671 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-03-20 23:21:48,673 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 11:21:48 BoogieIcfgContainer [2022-03-20 23:21:48,673 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 23:21:48,674 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 23:21:48,674 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 23:21:48,690 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 23:21:48,691 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 11:21:48" (1/3) ... [2022-03-20 23:21:48,691 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7de3b4db and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 11:21:48, skipping insertion in model container [2022-03-20 23:21:48,692 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:21:48" (2/3) ... [2022-03-20 23:21:48,692 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7de3b4db and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 11:21:48, skipping insertion in model container [2022-03-20 23:21:48,692 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 11:21:48" (3/3) ... [2022-03-20 23:21:48,693 INFO L111 eAbstractionObserver]: Analyzing ICFG ps6-ll_valuebound50.c [2022-03-20 23:21:48,696 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-03-20 23:21:48,696 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 23:21:48,733 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 23:21:48,745 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 23:21:48,745 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 23:21:48,757 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-20 23:21:48,763 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-03-20 23:21:48,763 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:21:48,764 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:21:48,764 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:21:48,768 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:21:48,769 INFO L85 PathProgramCache]: Analyzing trace with hash 1098891495, now seen corresponding path program 1 times [2022-03-20 23:21:48,775 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:48,775 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1243235140] [2022-03-20 23:21:48,783 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:21:48,783 INFO L85 PathProgramCache]: Analyzing trace with hash 1098891495, now seen corresponding path program 2 times [2022-03-20 23:21:48,785 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:21:48,785 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [492648549] [2022-03-20 23:21:48,786 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:21:48,786 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:21:48,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 23:21:48,926 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 23:21:48,935 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 23:21:48,945 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 23:21:48,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 23:21:48,950 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-03-20 23:21:48,951 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 23:21:48,955 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 23:21:48,956 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:21:48,956 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [492648549] [2022-03-20 23:21:48,956 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [492648549] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:21:48,956 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:21:48,957 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 23:21:48,959 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:21:48,959 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1243235140] [2022-03-20 23:21:48,959 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1243235140] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:21:48,959 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:21:48,959 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 23:21:48,960 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1263381627] [2022-03-20 23:21:48,960 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:21:48,962 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-20 23:21:48,963 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:48,979 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-20 23:21:48,979 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 23:21:48,980 INFO L87 Difference]: Start difference. First operand has 29 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) 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, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 23:21:49,028 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:21:49,028 INFO L93 Difference]: Finished difference Result 51 states and 69 transitions. [2022-03-20 23:21:49,029 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-20 23:21:49,030 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, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-03-20 23:21:49,030 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:21:49,035 INFO L225 Difference]: With dead ends: 51 [2022-03-20 23:21:49,035 INFO L226 Difference]: Without dead ends: 24 [2022-03-20 23:21:49,036 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 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 23:21:49,039 INFO L913 BasicCegarLoop]: 27 mSDtfsCounter, 15 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 30 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 23:21:49,039 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [20 Valid, 30 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 23:21:49,062 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2022-03-20 23:21:49,077 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2022-03-20 23:21:49,078 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-03-20 23:21:49,079 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2022-03-20 23:21:49,080 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 22 [2022-03-20 23:21:49,080 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:21:49,080 INFO L478 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2022-03-20 23:21:49,080 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, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 23:21:49,080 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2022-03-20 23:21:49,082 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-03-20 23:21:49,082 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:21:49,082 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:21:49,083 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 23:21:49,083 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:21:49,084 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:21:49,085 INFO L85 PathProgramCache]: Analyzing trace with hash 769620075, now seen corresponding path program 1 times [2022-03-20 23:21:49,085 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:49,085 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1524385136] [2022-03-20 23:21:49,087 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:21:49,087 INFO L85 PathProgramCache]: Analyzing trace with hash 769620075, now seen corresponding path program 2 times [2022-03-20 23:21:49,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:21:49,088 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2120267693] [2022-03-20 23:21:49,088 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:21:49,088 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:21:49,118 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:21:49,118 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1594185851] [2022-03-20 23:21:49,118 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 23:21:49,118 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:49,119 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:21:49,127 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 23:21:49,151 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 23:21:49,194 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-03-20 23:21:49,195 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:21:49,196 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 23:21:49,199 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:21:49,324 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 23:21:49,325 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 23:21:49,325 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:21:49,325 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2120267693] [2022-03-20 23:21:49,325 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:21:49,325 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1594185851] [2022-03-20 23:21:49,326 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1594185851] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:21:49,326 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:21:49,327 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 23:21:49,327 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:21:49,328 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1524385136] [2022-03-20 23:21:49,328 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1524385136] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:21:49,328 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:21:49,328 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 23:21:49,329 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2074049685] [2022-03-20 23:21:49,331 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:21:49,332 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 23:21:49,335 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:49,337 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 23:21:49,338 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 23:21:49,338 INFO L87 Difference]: Start difference. First operand 24 states and 27 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-03-20 23:21:49,407 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:21:49,408 INFO L93 Difference]: Finished difference Result 35 states and 40 transitions. [2022-03-20 23:21:49,408 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 23:21:49,408 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 22 [2022-03-20 23:21:49,408 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:21:49,409 INFO L225 Difference]: With dead ends: 35 [2022-03-20 23:21:49,409 INFO L226 Difference]: Without dead ends: 31 [2022-03-20 23:21:49,411 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 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 23:21:49,412 INFO L913 BasicCegarLoop]: 24 mSDtfsCounter, 6 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 23:21:49,415 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 91 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 23:21:49,417 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-03-20 23:21:49,437 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2022-03-20 23:21:49,438 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 19 states have internal predecessors, (20), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-03-20 23:21:49,440 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 34 transitions. [2022-03-20 23:21:49,440 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 34 transitions. Word has length 22 [2022-03-20 23:21:49,441 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:21:49,441 INFO L478 AbstractCegarLoop]: Abstraction has 31 states and 34 transitions. [2022-03-20 23:21:49,441 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-03-20 23:21:49,441 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 34 transitions. [2022-03-20 23:21:49,442 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-03-20 23:21:49,442 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:21:49,442 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:21:49,467 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 23:21:49,655 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:49,656 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:21:49,656 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:21:49,656 INFO L85 PathProgramCache]: Analyzing trace with hash 645812411, now seen corresponding path program 1 times [2022-03-20 23:21:49,656 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:49,656 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1792505684] [2022-03-20 23:21:49,657 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:21:49,657 INFO L85 PathProgramCache]: Analyzing trace with hash 645812411, now seen corresponding path program 2 times [2022-03-20 23:21:49,657 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:21:49,657 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [155293863] [2022-03-20 23:21:49,657 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:21:49,658 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:21:49,676 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:21:49,677 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1047661893] [2022-03-20 23:21:49,677 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 23:21:49,677 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:49,678 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:21:49,679 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 23:21:49,681 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 23:21:49,732 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 23:21:49,732 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:21:49,733 INFO L263 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-20 23:21:49,742 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:21:49,854 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 23:21:49,854 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:21:50,121 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-03-20 23:21:50,121 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:21:50,121 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [155293863] [2022-03-20 23:21:50,121 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:21:50,121 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1047661893] [2022-03-20 23:21:50,122 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1047661893] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 23:21:50,122 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:21:50,122 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-03-20 23:21:50,122 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:21:50,122 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1792505684] [2022-03-20 23:21:50,122 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1792505684] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:21:50,122 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:21:50,123 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 23:21:50,123 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [972206343] [2022-03-20 23:21:50,123 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:21:50,123 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 23:21:50,123 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:50,123 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 23:21:50,124 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-20 23:21:50,124 INFO L87 Difference]: Start difference. First operand 31 states and 34 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, (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 23:21:50,159 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:21:50,159 INFO L93 Difference]: Finished difference Result 37 states and 39 transitions. [2022-03-20 23:21:50,160 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 23:21:50,160 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, (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 29 [2022-03-20 23:21:50,160 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:21:50,162 INFO L225 Difference]: With dead ends: 37 [2022-03-20 23:21:50,162 INFO L226 Difference]: Without dead ends: 33 [2022-03-20 23:21:50,162 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 50 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-03-20 23:21:50,171 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 6 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 23:21:50,172 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 81 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 23:21:50,173 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-03-20 23:21:50,180 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-03-20 23:21:50,180 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 20 states have (on average 1.05) internal successors, (21), 20 states have internal predecessors, (21), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-03-20 23:21:50,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 35 transitions. [2022-03-20 23:21:50,181 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 35 transitions. Word has length 29 [2022-03-20 23:21:50,181 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:21:50,181 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 35 transitions. [2022-03-20 23:21:50,181 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, (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 23:21:50,181 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 35 transitions. [2022-03-20 23:21:50,182 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-03-20 23:21:50,182 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:21:50,182 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:21:50,201 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 23:21:50,394 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-03-20 23:21:50,395 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:21:50,395 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:21:50,396 INFO L85 PathProgramCache]: Analyzing trace with hash 463554397, now seen corresponding path program 1 times [2022-03-20 23:21:50,396 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:50,396 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2015593135] [2022-03-20 23:21:50,396 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:21:50,397 INFO L85 PathProgramCache]: Analyzing trace with hash 463554397, now seen corresponding path program 2 times [2022-03-20 23:21:50,397 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:21:50,397 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2001190317] [2022-03-20 23:21:50,397 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:21:50,397 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:21:50,407 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:21:50,407 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [973632403] [2022-03-20 23:21:50,407 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 23:21:50,408 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:50,408 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:21:50,409 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 23:21:50,410 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 23:21:50,446 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 23:21:50,446 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:21:50,447 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-20 23:21:50,448 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:21:50,591 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-03-20 23:21:50,591 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:21:50,827 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:21:50,827 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2001190317] [2022-03-20 23:21:50,828 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:21:50,828 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [973632403] [2022-03-20 23:21:50,828 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [973632403] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:21:50,828 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:21:50,828 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-03-20 23:21:50,828 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:21:50,828 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2015593135] [2022-03-20 23:21:50,828 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2015593135] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:21:50,829 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:21:50,829 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-03-20 23:21:50,829 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1119625259] [2022-03-20 23:21:50,829 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:21:50,829 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-20 23:21:50,829 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:50,829 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-20 23:21:50,830 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-03-20 23:21:50,830 INFO L87 Difference]: Start difference. First operand 33 states and 35 transitions. Second operand has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2022-03-20 23:21:50,912 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:21:50,912 INFO L93 Difference]: Finished difference Result 42 states and 46 transitions. [2022-03-20 23:21:50,912 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 23:21:50,913 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) Word has length 40 [2022-03-20 23:21:50,913 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:21:50,913 INFO L225 Difference]: With dead ends: 42 [2022-03-20 23:21:50,913 INFO L226 Difference]: Without dead ends: 36 [2022-03-20 23:21:50,914 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 48 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2022-03-20 23:21:50,914 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 2 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 155 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 23:21:50,915 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 155 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 23:21:50,915 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-03-20 23:21:50,921 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2022-03-20 23:21:50,921 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 22 states have internal predecessors, (23), 9 states have call successors, (9), 6 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-20 23:21:50,921 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 39 transitions. [2022-03-20 23:21:50,922 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 39 transitions. Word has length 40 [2022-03-20 23:21:50,922 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:21:50,922 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 39 transitions. [2022-03-20 23:21:50,922 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2022-03-20 23:21:50,922 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 39 transitions. [2022-03-20 23:21:50,923 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-03-20 23:21:50,923 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:21:50,923 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:21:50,950 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 23:21:51,134 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:51,134 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:21:51,135 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:21:51,135 INFO L85 PathProgramCache]: Analyzing trace with hash 1886956461, now seen corresponding path program 3 times [2022-03-20 23:21:51,135 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:51,135 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [902875431] [2022-03-20 23:21:51,135 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:21:51,135 INFO L85 PathProgramCache]: Analyzing trace with hash 1886956461, now seen corresponding path program 4 times [2022-03-20 23:21:51,136 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:21:51,136 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [455033089] [2022-03-20 23:21:51,136 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:21:51,136 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:21:51,145 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:21:51,146 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1740366604] [2022-03-20 23:21:51,146 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 23:21:51,146 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:51,146 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:21:51,147 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 23:21:51,148 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 23:21:51,191 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 23:21:51,191 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:21:51,192 INFO L263 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 16 conjunts are in the unsatisfiable core [2022-03-20 23:21:51,194 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:21:51,355 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 8 proven. 9 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-03-20 23:21:51,355 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:21:51,516 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:21:51,516 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [455033089] [2022-03-20 23:21:51,516 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:21:51,516 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1740366604] [2022-03-20 23:21:51,517 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1740366604] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:21:51,517 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:21:51,517 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-03-20 23:21:51,517 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:21:51,517 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [902875431] [2022-03-20 23:21:51,517 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [902875431] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:21:51,517 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:21:51,517 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-03-20 23:21:51,517 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1550434777] [2022-03-20 23:21:51,517 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:21:51,518 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-20 23:21:51,518 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:51,518 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-20 23:21:51,518 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-03-20 23:21:51,518 INFO L87 Difference]: Start difference. First operand 36 states and 39 transitions. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2022-03-20 23:21:51,585 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:21:51,586 INFO L93 Difference]: Finished difference Result 45 states and 50 transitions. [2022-03-20 23:21:51,586 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-20 23:21:51,586 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) Word has length 47 [2022-03-20 23:21:51,586 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:21:51,587 INFO L225 Difference]: With dead ends: 45 [2022-03-20 23:21:51,587 INFO L226 Difference]: Without dead ends: 39 [2022-03-20 23:21:51,587 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 54 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2022-03-20 23:21:51,588 INFO L913 BasicCegarLoop]: 33 mSDtfsCounter, 2 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 195 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 23:21:51,588 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 195 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 23:21:51,588 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-03-20 23:21:51,594 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2022-03-20 23:21:51,594 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 24 states have (on average 1.0416666666666667) internal successors, (25), 24 states have internal predecessors, (25), 10 states have call successors, (10), 6 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 23:21:51,594 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 43 transitions. [2022-03-20 23:21:51,594 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 43 transitions. Word has length 47 [2022-03-20 23:21:51,595 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:21:51,595 INFO L478 AbstractCegarLoop]: Abstraction has 39 states and 43 transitions. [2022-03-20 23:21:51,595 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2022-03-20 23:21:51,597 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 43 transitions. [2022-03-20 23:21:51,598 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2022-03-20 23:21:51,598 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:21:51,599 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:21:51,621 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 23:21:51,799 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:51,799 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:21:51,800 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:21:51,800 INFO L85 PathProgramCache]: Analyzing trace with hash -1213805219, now seen corresponding path program 5 times [2022-03-20 23:21:51,800 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:51,800 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [740563081] [2022-03-20 23:21:51,800 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:21:51,800 INFO L85 PathProgramCache]: Analyzing trace with hash -1213805219, now seen corresponding path program 6 times [2022-03-20 23:21:51,800 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:21:51,800 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1627821159] [2022-03-20 23:21:51,801 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:21:51,801 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:21:51,808 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:21:51,808 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2007887264] [2022-03-20 23:21:51,808 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 23:21:51,808 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:51,809 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:21:51,809 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 23:21:51,810 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 23:21:51,971 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-03-20 23:21:51,972 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:21:51,973 INFO L263 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 20 conjunts are in the unsatisfiable core [2022-03-20 23:21:51,976 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:21:52,174 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 10 proven. 18 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2022-03-20 23:21:52,174 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:21:52,326 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:21:52,327 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1627821159] [2022-03-20 23:21:52,327 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:21:52,327 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2007887264] [2022-03-20 23:21:52,328 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2007887264] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:21:52,328 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:21:52,328 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-03-20 23:21:52,328 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:21:52,328 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [740563081] [2022-03-20 23:21:52,328 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [740563081] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:21:52,328 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:21:52,328 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-03-20 23:21:52,328 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [380334386] [2022-03-20 23:21:52,328 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:21:52,329 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 23:21:52,329 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:52,329 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 23:21:52,329 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-03-20 23:21:52,330 INFO L87 Difference]: Start difference. First operand 39 states and 43 transitions. Second operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2022-03-20 23:21:52,417 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:21:52,417 INFO L93 Difference]: Finished difference Result 48 states and 54 transitions. [2022-03-20 23:21:52,418 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 23:21:52,419 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) Word has length 54 [2022-03-20 23:21:52,419 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:21:52,419 INFO L225 Difference]: With dead ends: 48 [2022-03-20 23:21:52,419 INFO L226 Difference]: Without dead ends: 42 [2022-03-20 23:21:52,420 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 60 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2022-03-20 23:21:52,420 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 2 mSDsluCounter, 203 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 239 SdHoareTripleChecker+Invalid, 82 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 81 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 23:21:52,420 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 239 Invalid, 82 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 81 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 23:21:52,421 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2022-03-20 23:21:52,426 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2022-03-20 23:21:52,426 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 11 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 23:21:52,428 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 47 transitions. [2022-03-20 23:21:52,429 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 47 transitions. Word has length 54 [2022-03-20 23:21:52,429 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:21:52,429 INFO L478 AbstractCegarLoop]: Abstraction has 42 states and 47 transitions. [2022-03-20 23:21:52,430 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2022-03-20 23:21:52,430 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 47 transitions. [2022-03-20 23:21:52,437 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2022-03-20 23:21:52,437 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:21:52,439 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:21:52,447 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-20 23:21:52,645 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:52,646 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:21:52,646 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:21:52,646 INFO L85 PathProgramCache]: Analyzing trace with hash 307258797, now seen corresponding path program 7 times [2022-03-20 23:21:52,646 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:52,646 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1398789174] [2022-03-20 23:21:52,647 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:21:52,647 INFO L85 PathProgramCache]: Analyzing trace with hash 307258797, now seen corresponding path program 8 times [2022-03-20 23:21:52,647 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:21:52,647 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [289617901] [2022-03-20 23:21:52,647 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:21:52,647 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:21:52,655 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:21:52,655 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1786595380] [2022-03-20 23:21:52,655 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 23:21:52,655 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:52,655 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:21:52,657 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 23:21:52,683 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 23:21:52,905 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 23:21:52,906 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:21:52,907 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 24 conjunts are in the unsatisfiable core [2022-03-20 23:21:52,909 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:21:53,096 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 12 proven. 30 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-03-20 23:21:53,096 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:21:53,220 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:21:53,220 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [289617901] [2022-03-20 23:21:53,220 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:21:53,220 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1786595380] [2022-03-20 23:21:53,220 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1786595380] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:21:53,220 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:21:53,220 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-03-20 23:21:53,220 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:21:53,221 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1398789174] [2022-03-20 23:21:53,221 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1398789174] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:21:53,221 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:21:53,221 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-03-20 23:21:53,221 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1460961600] [2022-03-20 23:21:53,221 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:21:53,222 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-20 23:21:53,222 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:53,222 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-20 23:21:53,223 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2022-03-20 23:21:53,223 INFO L87 Difference]: Start difference. First operand 42 states and 47 transitions. Second operand has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 7 states have call predecessors, (9), 7 states have call successors, (9) [2022-03-20 23:21:53,324 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:21:53,325 INFO L93 Difference]: Finished difference Result 51 states and 58 transitions. [2022-03-20 23:21:53,325 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 23:21:53,325 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 7 states have call predecessors, (9), 7 states have call successors, (9) Word has length 61 [2022-03-20 23:21:53,325 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:21:53,326 INFO L225 Difference]: With dead ends: 51 [2022-03-20 23:21:53,326 INFO L226 Difference]: Without dead ends: 45 [2022-03-20 23:21:53,326 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 66 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2022-03-20 23:21:53,327 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 2 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 108 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 287 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 108 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 23:21:53,327 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 287 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 108 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 23:21:53,327 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-03-20 23:21:53,333 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2022-03-20 23:21:53,333 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 28 states have (on average 1.0357142857142858) internal successors, (29), 28 states have internal predecessors, (29), 12 states have call successors, (12), 6 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-20 23:21:53,334 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 51 transitions. [2022-03-20 23:21:53,334 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 51 transitions. Word has length 61 [2022-03-20 23:21:53,334 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:21:53,334 INFO L478 AbstractCegarLoop]: Abstraction has 45 states and 51 transitions. [2022-03-20 23:21:53,334 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 7 states have call predecessors, (9), 7 states have call successors, (9) [2022-03-20 23:21:53,334 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 51 transitions. [2022-03-20 23:21:53,339 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2022-03-20 23:21:53,339 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:21:53,339 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:21:53,355 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2022-03-20 23:21:53,544 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:53,545 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:21:53,545 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:21:53,545 INFO L85 PathProgramCache]: Analyzing trace with hash 1082774365, now seen corresponding path program 9 times [2022-03-20 23:21:53,545 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:53,545 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [422406022] [2022-03-20 23:21:53,545 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:21:53,545 INFO L85 PathProgramCache]: Analyzing trace with hash 1082774365, now seen corresponding path program 10 times [2022-03-20 23:21:53,546 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:21:53,546 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1297015881] [2022-03-20 23:21:53,546 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:21:53,546 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:21:53,565 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:21:53,565 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [604445335] [2022-03-20 23:21:53,565 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 23:21:53,565 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:53,566 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:21:53,567 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 23:21:53,568 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 23:21:53,602 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 23:21:53,602 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:21:53,603 INFO L263 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 28 conjunts are in the unsatisfiable core [2022-03-20 23:21:53,608 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:21:53,786 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 14 proven. 45 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-03-20 23:21:53,786 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:21:53,954 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:21:53,954 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1297015881] [2022-03-20 23:21:53,954 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:21:53,954 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [604445335] [2022-03-20 23:21:53,954 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [604445335] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:21:53,955 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:21:53,955 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-03-20 23:21:53,955 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:21:53,955 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [422406022] [2022-03-20 23:21:53,955 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [422406022] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:21:53,955 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:21:53,955 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-03-20 23:21:53,955 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [217715004] [2022-03-20 23:21:53,955 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:21:53,956 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-20 23:21:53,956 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:53,956 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-20 23:21:53,956 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2022-03-20 23:21:53,956 INFO L87 Difference]: Start difference. First operand 45 states and 51 transitions. Second operand has 11 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 8 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) [2022-03-20 23:21:54,073 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:21:54,073 INFO L93 Difference]: Finished difference Result 54 states and 62 transitions. [2022-03-20 23:21:54,074 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-20 23:21:54,074 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 8 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) Word has length 68 [2022-03-20 23:21:54,074 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:21:54,075 INFO L225 Difference]: With dead ends: 54 [2022-03-20 23:21:54,075 INFO L226 Difference]: Without dead ends: 48 [2022-03-20 23:21:54,075 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 72 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2022-03-20 23:21:54,076 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 2 mSDsluCounter, 297 mSDsCounter, 0 mSdLazyCounter, 139 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 339 SdHoareTripleChecker+Invalid, 140 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 139 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 23:21:54,076 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 339 Invalid, 140 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 139 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 23:21:54,076 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-03-20 23:21:54,082 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2022-03-20 23:21:54,083 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 30 states have (on average 1.0333333333333334) internal successors, (31), 30 states have internal predecessors, (31), 13 states have call successors, (13), 6 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-03-20 23:21:54,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 55 transitions. [2022-03-20 23:21:54,083 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 55 transitions. Word has length 68 [2022-03-20 23:21:54,083 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:21:54,083 INFO L478 AbstractCegarLoop]: Abstraction has 48 states and 55 transitions. [2022-03-20 23:21:54,084 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 8 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) [2022-03-20 23:21:54,084 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 55 transitions. [2022-03-20 23:21:54,084 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-03-20 23:21:54,084 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:21:54,084 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 7, 7, 7, 6, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:21:54,115 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 23:21:54,299 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:54,300 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:21:54,300 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:21:54,300 INFO L85 PathProgramCache]: Analyzing trace with hash -1692754003, now seen corresponding path program 11 times [2022-03-20 23:21:54,300 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:21:54,300 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [757672675] [2022-03-20 23:21:54,300 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:21:54,301 INFO L85 PathProgramCache]: Analyzing trace with hash -1692754003, now seen corresponding path program 12 times [2022-03-20 23:21:54,301 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:21:54,301 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [585113975] [2022-03-20 23:21:54,301 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:21:54,301 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:21:54,308 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:21:54,308 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [705562237] [2022-03-20 23:21:54,308 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 23:21:54,308 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:21:54,308 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:21:54,309 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 23:21:54,310 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 23:21:54,639 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-03-20 23:21:54,639 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:21:54,641 INFO L263 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 43 conjunts are in the unsatisfiable core [2022-03-20 23:21:54,643 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:21:55,039 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 47 proven. 68 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2022-03-20 23:21:55,039 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:21:59,278 WARN L833 $PredicateComparison]: unable to prove that (let ((.cse0 (* 2 c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0)) (.cse1 (* 18 c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0)) (.cse2 (* 119 c_main_~y~0 c_main_~y~0)) (.cse3 (* 65 c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0))) (or (not (<= (+ (* 10 (* c_main_~y~0 c_main_~y~0)) (* 5 (* c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0)) (* c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0) c_main_~x~0 1) (div (+ .cse0 .cse1 .cse2 12 .cse3) 12))) (not (= (mod (+ .cse0 .cse1 .cse2 .cse3 (* 120 c_main_~y~0 c_main_~y~0 c_main_~y~0)) 12) 0)) (forall ((main_~k~0 Int)) (or (< (+ c_main_~c~0 1) main_~k~0) (not (< c_main_~c~0 main_~k~0)) (let ((.cse4 (+ c_main_~y~0 1))) (= (* .cse4 .cse4) (* main_~k~0 .cse4))))))) is different from false [2022-03-20 23:22:03,376 WARN L833 $PredicateComparison]: unable to prove that (or (not (= (mod (+ (* (- 2) c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0) (* (- 5) c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0) (* (- 6) c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0) (* c_main_~y~0 c_main_~y~0)) 12) 0)) (forall ((main_~k~0 Int)) (or (< (+ c_main_~c~0 1) main_~k~0) (not (< c_main_~c~0 main_~k~0)) (let ((.cse0 (+ c_main_~y~0 1))) (= (* .cse0 .cse0) (* main_~k~0 .cse0)))))) is different from false [2022-03-20 23:22:03,379 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:22:03,379 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [585113975] [2022-03-20 23:22:03,379 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:22:03,379 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [705562237] [2022-03-20 23:22:03,380 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [705562237] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:22:03,380 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:22:03,380 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2022-03-20 23:22:03,380 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:22:03,380 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [757672675] [2022-03-20 23:22:03,380 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [757672675] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:22:03,380 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:22:03,380 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [16] imperfect sequences [] total 16 [2022-03-20 23:22:03,380 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1664890265] [2022-03-20 23:22:03,380 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:22:03,381 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-20 23:22:03,381 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:22:03,381 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-20 23:22:03,381 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=326, Unknown=2, NotChecked=74, Total=462 [2022-03-20 23:22:03,381 INFO L87 Difference]: Start difference. First operand 48 states and 55 transitions. Second operand has 16 states, 14 states have (on average 2.142857142857143) internal successors, (30), 13 states have internal predecessors, (30), 10 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) [2022-03-20 23:22:03,581 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:22:03,581 INFO L93 Difference]: Finished difference Result 57 states and 66 transitions. [2022-03-20 23:22:03,582 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-20 23:22:03,582 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.142857142857143) internal successors, (30), 13 states have internal predecessors, (30), 10 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) Word has length 75 [2022-03-20 23:22:03,582 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:22:03,583 INFO L225 Difference]: With dead ends: 57 [2022-03-20 23:22:03,583 INFO L226 Difference]: Without dead ends: 51 [2022-03-20 23:22:03,583 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 71 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=81, Invalid=431, Unknown=2, NotChecked=86, Total=600 [2022-03-20 23:22:03,583 INFO L913 BasicCegarLoop]: 33 mSDtfsCounter, 7 mSDsluCounter, 348 mSDsCounter, 0 mSdLazyCounter, 289 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 381 SdHoareTripleChecker+Invalid, 293 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 289 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 23:22:03,584 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 381 Invalid, 293 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 289 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 23:22:03,584 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-03-20 23:22:03,593 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2022-03-20 23:22:03,593 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 32 states have (on average 1.03125) internal successors, (33), 32 states have internal predecessors, (33), 14 states have call successors, (14), 6 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 23:22:03,595 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 59 transitions. [2022-03-20 23:22:03,596 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 59 transitions. Word has length 75 [2022-03-20 23:22:03,596 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:22:03,596 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 59 transitions. [2022-03-20 23:22:03,596 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.142857142857143) internal successors, (30), 13 states have internal predecessors, (30), 10 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) [2022-03-20 23:22:03,596 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2022-03-20 23:22:03,596 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-03-20 23:22:03,597 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:22:03,597 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 8, 8, 8, 7, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:22:03,603 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 23:22:03,797 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-03-20 23:22:03,797 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:22:03,798 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:22:03,798 INFO L85 PathProgramCache]: Analyzing trace with hash 615143773, now seen corresponding path program 13 times [2022-03-20 23:22:03,798 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:22:03,798 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2132064187] [2022-03-20 23:22:03,798 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:22:03,798 INFO L85 PathProgramCache]: Analyzing trace with hash 615143773, now seen corresponding path program 14 times [2022-03-20 23:22:03,799 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:22:03,799 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [98047110] [2022-03-20 23:22:03,799 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:22:03,799 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:22:03,806 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:22:03,806 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1486841954] [2022-03-20 23:22:03,806 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 23:22:03,806 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:22:03,806 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:22:03,813 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 23:22:03,814 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 23:22:04,594 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 23:22:04,595 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:22:04,596 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 36 conjunts are in the unsatisfiable core [2022-03-20 23:22:04,598 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:22:04,899 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 18 proven. 84 refuted. 0 times theorem prover too weak. 148 trivial. 0 not checked. [2022-03-20 23:22:04,900 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:22:05,046 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:22:05,046 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [98047110] [2022-03-20 23:22:05,046 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:22:05,046 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1486841954] [2022-03-20 23:22:05,047 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1486841954] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:22:05,047 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:22:05,047 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-03-20 23:22:05,047 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:22:05,047 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2132064187] [2022-03-20 23:22:05,047 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2132064187] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:22:05,047 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:22:05,047 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-03-20 23:22:05,047 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1792386481] [2022-03-20 23:22:05,047 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:22:05,048 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-20 23:22:05,048 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:22:05,048 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-20 23:22:05,048 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2022-03-20 23:22:05,048 INFO L87 Difference]: Start difference. First operand 51 states and 59 transitions. Second operand has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 12 states have internal predecessors, (29), 10 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) [2022-03-20 23:22:05,217 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:22:05,217 INFO L93 Difference]: Finished difference Result 60 states and 70 transitions. [2022-03-20 23:22:05,217 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-20 23:22:05,217 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 12 states have internal predecessors, (29), 10 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) Word has length 82 [2022-03-20 23:22:05,218 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:22:05,218 INFO L225 Difference]: With dead ends: 60 [2022-03-20 23:22:05,218 INFO L226 Difference]: Without dead ends: 54 [2022-03-20 23:22:05,219 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 84 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=52, Invalid=254, Unknown=0, NotChecked=0, Total=306 [2022-03-20 23:22:05,219 INFO L913 BasicCegarLoop]: 48 mSDtfsCounter, 2 mSDsluCounter, 407 mSDsCounter, 0 mSdLazyCounter, 213 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 455 SdHoareTripleChecker+Invalid, 214 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 213 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 23:22:05,219 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 455 Invalid, 214 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 213 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 23:22:05,219 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-03-20 23:22:05,226 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-03-20 23:22:05,226 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 34 states have (on average 1.0294117647058822) internal successors, (35), 34 states have internal predecessors, (35), 15 states have call successors, (15), 6 states have call predecessors, (15), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-03-20 23:22:05,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 63 transitions. [2022-03-20 23:22:05,227 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 63 transitions. Word has length 82 [2022-03-20 23:22:05,227 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:22:05,227 INFO L478 AbstractCegarLoop]: Abstraction has 54 states and 63 transitions. [2022-03-20 23:22:05,227 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 12 states have internal predecessors, (29), 10 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) [2022-03-20 23:22:05,227 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 63 transitions. [2022-03-20 23:22:05,228 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2022-03-20 23:22:05,228 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:22:05,228 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 9, 9, 9, 8, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:22:05,239 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 23:22:05,433 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-03-20 23:22:05,434 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:22:05,434 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:22:05,434 INFO L85 PathProgramCache]: Analyzing trace with hash -1334355539, now seen corresponding path program 15 times [2022-03-20 23:22:05,434 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:22:05,434 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [69473868] [2022-03-20 23:22:05,435 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:22:05,435 INFO L85 PathProgramCache]: Analyzing trace with hash -1334355539, now seen corresponding path program 16 times [2022-03-20 23:22:05,435 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:22:05,435 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [739011771] [2022-03-20 23:22:05,435 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:22:05,435 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:22:05,447 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:22:05,447 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [258749996] [2022-03-20 23:22:05,447 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 23:22:05,447 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:22:05,447 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:22:05,460 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 23:22:05,466 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 23:22:05,499 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 23:22:05,499 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:22:05,500 INFO L263 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 40 conjunts are in the unsatisfiable core [2022-03-20 23:22:05,503 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:22:05,786 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 20 proven. 108 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2022-03-20 23:22:05,786 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:22:05,979 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:22:05,980 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [739011771] [2022-03-20 23:22:05,980 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:22:05,980 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [258749996] [2022-03-20 23:22:05,980 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [258749996] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:22:05,980 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:22:05,980 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2022-03-20 23:22:05,980 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:22:05,980 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [69473868] [2022-03-20 23:22:05,980 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [69473868] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:22:05,980 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:22:05,980 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14] imperfect sequences [] total 14 [2022-03-20 23:22:05,981 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [296949639] [2022-03-20 23:22:05,981 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:22:05,981 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-20 23:22:05,981 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:22:05,981 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-20 23:22:05,981 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2022-03-20 23:22:05,982 INFO L87 Difference]: Start difference. First operand 54 states and 63 transitions. Second operand has 14 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 13 states have internal predecessors, (31), 11 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 11 states have call predecessors, (13), 11 states have call successors, (13) [2022-03-20 23:22:06,167 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:22:06,168 INFO L93 Difference]: Finished difference Result 63 states and 74 transitions. [2022-03-20 23:22:06,168 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-03-20 23:22:06,168 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 13 states have internal predecessors, (31), 11 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 11 states have call predecessors, (13), 11 states have call successors, (13) Word has length 89 [2022-03-20 23:22:06,169 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:22:06,169 INFO L225 Difference]: With dead ends: 63 [2022-03-20 23:22:06,169 INFO L226 Difference]: Without dead ends: 57 [2022-03-20 23:22:06,170 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 90 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2022-03-20 23:22:06,170 INFO L913 BasicCegarLoop]: 51 mSDtfsCounter, 2 mSDsluCounter, 468 mSDsCounter, 0 mSdLazyCounter, 256 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 519 SdHoareTripleChecker+Invalid, 257 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 256 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 23:22:06,170 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 519 Invalid, 257 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 256 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 23:22:06,171 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2022-03-20 23:22:06,179 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2022-03-20 23:22:06,179 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 36 states have (on average 1.0277777777777777) internal successors, (37), 36 states have internal predecessors, (37), 16 states have call successors, (16), 6 states have call predecessors, (16), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-20 23:22:06,180 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 67 transitions. [2022-03-20 23:22:06,180 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 67 transitions. Word has length 89 [2022-03-20 23:22:06,180 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:22:06,180 INFO L478 AbstractCegarLoop]: Abstraction has 57 states and 67 transitions. [2022-03-20 23:22:06,180 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 13 states have internal predecessors, (31), 11 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 11 states have call predecessors, (13), 11 states have call successors, (13) [2022-03-20 23:22:06,181 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 67 transitions. [2022-03-20 23:22:06,181 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2022-03-20 23:22:06,181 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:22:06,181 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 10, 10, 10, 9, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:22:06,198 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-03-20 23:22:06,384 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-03-20 23:22:06,384 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:22:06,384 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:22:06,384 INFO L85 PathProgramCache]: Analyzing trace with hash 711483229, now seen corresponding path program 17 times [2022-03-20 23:22:06,384 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:22:06,385 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [342842499] [2022-03-20 23:22:06,385 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:22:06,385 INFO L85 PathProgramCache]: Analyzing trace with hash 711483229, now seen corresponding path program 18 times [2022-03-20 23:22:06,385 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:22:06,385 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2016661352] [2022-03-20 23:22:06,385 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:22:06,385 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:22:06,402 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:22:06,402 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1872334259] [2022-03-20 23:22:06,402 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 23:22:06,403 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:22:06,403 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:22:06,409 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 23:22:06,410 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 23:22:07,055 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) [2022-03-20 23:22:07,056 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:22:07,058 INFO L263 TraceCheckSpWp]: Trace formula consists of 249 conjuncts, 44 conjunts are in the unsatisfiable core [2022-03-20 23:22:07,060 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:22:07,372 INFO L134 CoverageAnalysis]: Checked inductivity of 381 backedges. 22 proven. 135 refuted. 0 times theorem prover too weak. 224 trivial. 0 not checked. [2022-03-20 23:22:07,372 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:22:07,523 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:22:07,523 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2016661352] [2022-03-20 23:22:07,523 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:22:07,523 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1872334259] [2022-03-20 23:22:07,523 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1872334259] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:22:07,523 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:22:07,523 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2022-03-20 23:22:07,524 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:22:07,524 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [342842499] [2022-03-20 23:22:07,524 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [342842499] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:22:07,524 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:22:07,524 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-03-20 23:22:07,524 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1268439873] [2022-03-20 23:22:07,524 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:22:07,524 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-20 23:22:07,524 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:22:07,525 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-20 23:22:07,525 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=258, Unknown=0, NotChecked=0, Total=306 [2022-03-20 23:22:07,525 INFO L87 Difference]: Start difference. First operand 57 states and 67 transitions. Second operand has 15 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 12 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 12 states have call predecessors, (14), 12 states have call successors, (14) [2022-03-20 23:22:07,736 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:22:07,736 INFO L93 Difference]: Finished difference Result 66 states and 78 transitions. [2022-03-20 23:22:07,737 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-20 23:22:07,737 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 12 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 12 states have call predecessors, (14), 12 states have call successors, (14) Word has length 96 [2022-03-20 23:22:07,737 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:22:07,737 INFO L225 Difference]: With dead ends: 66 [2022-03-20 23:22:07,738 INFO L226 Difference]: Without dead ends: 60 [2022-03-20 23:22:07,738 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 96 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=58, Invalid=322, Unknown=0, NotChecked=0, Total=380 [2022-03-20 23:22:07,738 INFO L913 BasicCegarLoop]: 54 mSDtfsCounter, 2 mSDsluCounter, 533 mSDsCounter, 0 mSdLazyCounter, 303 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 587 SdHoareTripleChecker+Invalid, 304 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 303 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 23:22:07,738 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 587 Invalid, 304 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 303 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 23:22:07,739 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2022-03-20 23:22:07,745 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 60. [2022-03-20 23:22:07,745 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 38 states have (on average 1.0263157894736843) internal successors, (39), 38 states have internal predecessors, (39), 17 states have call successors, (17), 6 states have call predecessors, (17), 4 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-03-20 23:22:07,746 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 71 transitions. [2022-03-20 23:22:07,746 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 71 transitions. Word has length 96 [2022-03-20 23:22:07,746 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:22:07,746 INFO L478 AbstractCegarLoop]: Abstraction has 60 states and 71 transitions. [2022-03-20 23:22:07,746 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 12 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 12 states have call predecessors, (14), 12 states have call successors, (14) [2022-03-20 23:22:07,747 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 71 transitions. [2022-03-20 23:22:07,747 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2022-03-20 23:22:07,747 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:22:07,747 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 11, 11, 11, 10, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:22:07,761 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 23:22:07,955 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-03-20 23:22:07,956 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:22:07,956 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:22:07,956 INFO L85 PathProgramCache]: Analyzing trace with hash -1610181715, now seen corresponding path program 19 times [2022-03-20 23:22:07,956 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:22:07,956 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1264893985] [2022-03-20 23:22:07,957 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:22:07,957 INFO L85 PathProgramCache]: Analyzing trace with hash -1610181715, now seen corresponding path program 20 times [2022-03-20 23:22:07,957 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:22:07,957 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [494870764] [2022-03-20 23:22:07,957 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:22:07,957 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:22:07,965 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:22:07,965 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [352522175] [2022-03-20 23:22:07,965 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 23:22:07,966 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:22:07,966 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:22:07,979 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 23:22:08,006 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 23:22:08,607 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 23:22:08,607 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:22:08,610 INFO L263 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 48 conjunts are in the unsatisfiable core [2022-03-20 23:22:08,611 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:22:08,930 INFO L134 CoverageAnalysis]: Checked inductivity of 457 backedges. 24 proven. 165 refuted. 0 times theorem prover too weak. 268 trivial. 0 not checked. [2022-03-20 23:22:08,930 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:22:09,075 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:22:09,075 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [494870764] [2022-03-20 23:22:09,075 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:22:09,075 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [352522175] [2022-03-20 23:22:09,075 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [352522175] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:22:09,075 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:22:09,075 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2022-03-20 23:22:09,075 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:22:09,076 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1264893985] [2022-03-20 23:22:09,076 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1264893985] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:22:09,076 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:22:09,076 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [16] imperfect sequences [] total 16 [2022-03-20 23:22:09,076 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [799797839] [2022-03-20 23:22:09,076 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:22:09,076 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-20 23:22:09,076 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:22:09,076 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-20 23:22:09,077 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=291, Unknown=0, NotChecked=0, Total=342 [2022-03-20 23:22:09,077 INFO L87 Difference]: Start difference. First operand 60 states and 71 transitions. Second operand has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 13 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (15), 13 states have call predecessors, (15), 13 states have call successors, (15) [2022-03-20 23:22:09,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:22:09,318 INFO L93 Difference]: Finished difference Result 69 states and 82 transitions. [2022-03-20 23:22:09,318 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-03-20 23:22:09,318 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 13 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (15), 13 states have call predecessors, (15), 13 states have call successors, (15) Word has length 103 [2022-03-20 23:22:09,318 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:22:09,319 INFO L225 Difference]: With dead ends: 69 [2022-03-20 23:22:09,319 INFO L226 Difference]: Without dead ends: 63 [2022-03-20 23:22:09,319 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 102 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=61, Invalid=359, Unknown=0, NotChecked=0, Total=420 [2022-03-20 23:22:09,319 INFO L913 BasicCegarLoop]: 57 mSDtfsCounter, 2 mSDsluCounter, 602 mSDsCounter, 0 mSdLazyCounter, 354 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 659 SdHoareTripleChecker+Invalid, 355 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 354 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 23:22:09,320 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 659 Invalid, 355 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 354 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 23:22:09,320 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-03-20 23:22:09,327 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2022-03-20 23:22:09,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 40 states have (on average 1.025) internal successors, (41), 40 states have internal predecessors, (41), 18 states have call successors, (18), 6 states have call predecessors, (18), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-03-20 23:22:09,328 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 75 transitions. [2022-03-20 23:22:09,328 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 75 transitions. Word has length 103 [2022-03-20 23:22:09,328 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:22:09,328 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 75 transitions. [2022-03-20 23:22:09,329 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 13 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (15), 13 states have call predecessors, (15), 13 states have call successors, (15) [2022-03-20 23:22:09,329 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 75 transitions. [2022-03-20 23:22:09,329 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2022-03-20 23:22:09,329 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:22:09,329 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 12, 12, 12, 11, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:22:09,335 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2022-03-20 23:22:09,535 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-03-20 23:22:09,535 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:22:09,535 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:22:09,535 INFO L85 PathProgramCache]: Analyzing trace with hash 1881400669, now seen corresponding path program 21 times [2022-03-20 23:22:09,535 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:22:09,535 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1796285419] [2022-03-20 23:22:09,536 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:22:09,536 INFO L85 PathProgramCache]: Analyzing trace with hash 1881400669, now seen corresponding path program 22 times [2022-03-20 23:22:09,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:22:09,536 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1061225136] [2022-03-20 23:22:09,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:22:09,536 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:22:09,543 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:22:09,543 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [497326188] [2022-03-20 23:22:09,543 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 23:22:09,543 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:22:09,543 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:22:09,544 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 23:22:09,595 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 23:22:09,605 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 23:22:09,606 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:22:09,607 INFO L263 TraceCheckSpWp]: Trace formula consists of 196 conjuncts, 52 conjunts are in the unsatisfiable core [2022-03-20 23:22:09,609 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:22:09,980 INFO L134 CoverageAnalysis]: Checked inductivity of 540 backedges. 26 proven. 198 refuted. 0 times theorem prover too weak. 316 trivial. 0 not checked. [2022-03-20 23:22:09,980 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:22:10,136 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:22:10,136 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1061225136] [2022-03-20 23:22:10,136 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:22:10,136 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [497326188] [2022-03-20 23:22:10,136 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [497326188] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:22:10,136 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:22:10,136 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2022-03-20 23:22:10,136 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:22:10,136 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1796285419] [2022-03-20 23:22:10,136 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1796285419] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:22:10,137 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:22:10,137 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [17] imperfect sequences [] total 17 [2022-03-20 23:22:10,137 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1998962302] [2022-03-20 23:22:10,137 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:22:10,137 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-03-20 23:22:10,137 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:22:10,137 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-03-20 23:22:10,138 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=326, Unknown=0, NotChecked=0, Total=380 [2022-03-20 23:22:10,138 INFO L87 Difference]: Start difference. First operand 63 states and 75 transitions. Second operand has 17 states, 16 states have (on average 2.3125) internal successors, (37), 16 states have internal predecessors, (37), 14 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 14 states have call predecessors, (16), 14 states have call successors, (16) [2022-03-20 23:22:10,382 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:22:10,382 INFO L93 Difference]: Finished difference Result 72 states and 86 transitions. [2022-03-20 23:22:10,382 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-03-20 23:22:10,382 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 2.3125) internal successors, (37), 16 states have internal predecessors, (37), 14 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 14 states have call predecessors, (16), 14 states have call successors, (16) Word has length 110 [2022-03-20 23:22:10,383 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:22:10,383 INFO L225 Difference]: With dead ends: 72 [2022-03-20 23:22:10,383 INFO L226 Difference]: Without dead ends: 66 [2022-03-20 23:22:10,384 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 108 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=64, Invalid=398, Unknown=0, NotChecked=0, Total=462 [2022-03-20 23:22:10,384 INFO L913 BasicCegarLoop]: 60 mSDtfsCounter, 2 mSDsluCounter, 675 mSDsCounter, 0 mSdLazyCounter, 409 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 735 SdHoareTripleChecker+Invalid, 410 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 409 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 23:22:10,384 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 735 Invalid, 410 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 409 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 23:22:10,385 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-03-20 23:22:10,393 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 66. [2022-03-20 23:22:10,393 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 42 states have (on average 1.0238095238095237) internal successors, (43), 42 states have internal predecessors, (43), 19 states have call successors, (19), 6 states have call predecessors, (19), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-03-20 23:22:10,394 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 79 transitions. [2022-03-20 23:22:10,394 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 79 transitions. Word has length 110 [2022-03-20 23:22:10,394 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:22:10,394 INFO L478 AbstractCegarLoop]: Abstraction has 66 states and 79 transitions. [2022-03-20 23:22:10,394 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 2.3125) internal successors, (37), 16 states have internal predecessors, (37), 14 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 14 states have call predecessors, (16), 14 states have call successors, (16) [2022-03-20 23:22:10,394 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 79 transitions. [2022-03-20 23:22:10,395 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2022-03-20 23:22:10,395 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:22:10,395 INFO L499 BasicCegarLoop]: trace histogram [15, 14, 14, 13, 13, 13, 12, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 23:22:10,412 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 23:22:10,603 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-03-20 23:22:10,603 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:22:10,604 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:22:10,604 INFO L85 PathProgramCache]: Analyzing trace with hash 1600671149, now seen corresponding path program 23 times [2022-03-20 23:22:10,604 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:22:10,604 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1699682666] [2022-03-20 23:22:10,604 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:22:10,604 INFO L85 PathProgramCache]: Analyzing trace with hash 1600671149, now seen corresponding path program 24 times [2022-03-20 23:22:10,604 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:22:10,604 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [903825027] [2022-03-20 23:22:10,605 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:22:10,605 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:22:10,625 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:22:10,625 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2102454634] [2022-03-20 23:22:10,625 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 23:22:10,625 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:22:10,625 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:22:10,626 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 23:22:10,627 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process