/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_valuebound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 16:59:59,430 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 16:59:59,431 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 16:59:59,493 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 16:59:59,493 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 16:59:59,494 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 16:59:59,494 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 16:59:59,495 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 16:59:59,496 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 16:59:59,497 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 16:59:59,498 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 16:59:59,498 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 16:59:59,498 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 16:59:59,515 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 16:59:59,516 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 16:59:59,516 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 16:59:59,517 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 16:59:59,517 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 16:59:59,518 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 16:59:59,519 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 16:59:59,520 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 16:59:59,523 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 16:59:59,523 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 16:59:59,524 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 16:59:59,524 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 16:59:59,526 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 16:59:59,526 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 16:59:59,526 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 16:59:59,527 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 16:59:59,527 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 16:59:59,528 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 16:59:59,528 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 16:59:59,528 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 16:59:59,529 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 16:59:59,529 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 16:59:59,530 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 16:59:59,530 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 16:59:59,530 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 16:59:59,531 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 16:59:59,531 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 16:59:59,531 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 16:59:59,536 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 16:59:59,536 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-03-20 16:59:59,542 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 16:59:59,542 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 16:59:59,543 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 16:59:59,548 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-20 16:59:59,548 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 16:59:59,548 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-20 16:59:59,548 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 16:59:59,548 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 16:59:59,548 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 16:59:59,549 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 16:59:59,549 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-20 16:59:59,549 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 16:59:59,549 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 16:59:59,549 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 16:59:59,549 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 16:59:59,549 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 16:59:59,550 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-20 16:59:59,550 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 16:59:59,550 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 16:59:59,550 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 16:59:59,550 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-03-20 16:59:59,550 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-03-20 16:59:59,550 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-03-20 16:59:59,550 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-20 16:59:59,550 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-03-20 16:59:59,551 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 16:59:59,735 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 16:59:59,747 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 16:59:59,748 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 16:59:59,749 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 16:59:59,775 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 16:59:59,776 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_valuebound100.c [2022-03-20 16:59:59,817 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f708c2e40/ef6ff450d32b4b4db3d7660a94af484b/FLAGd64254116 [2022-03-20 17:00:00,190 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 17:00:00,190 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_valuebound100.c [2022-03-20 17:00:00,197 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f708c2e40/ef6ff450d32b4b4db3d7660a94af484b/FLAGd64254116 [2022-03-20 17:00:00,206 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f708c2e40/ef6ff450d32b4b4db3d7660a94af484b [2022-03-20 17:00:00,208 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 17:00:00,208 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-03-20 17:00:00,213 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 17:00:00,213 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 17:00:00,216 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 17:00:00,216 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 05:00:00" (1/1) ... [2022-03-20 17:00:00,217 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6be08fd7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 05:00:00, skipping insertion in model container [2022-03-20 17:00:00,217 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 05:00:00" (1/1) ... [2022-03-20 17:00:00,223 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 17:00:00,231 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 17:00:00,349 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_valuebound100.c[458,471] [2022-03-20 17:00:00,380 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 17:00:00,386 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 17:00:00,417 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_valuebound100.c[458,471] [2022-03-20 17:00:00,421 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 17:00:00,429 INFO L208 MainTranslator]: Completed translation [2022-03-20 17:00:00,430 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 05:00:00 WrapperNode [2022-03-20 17:00:00,430 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 17:00:00,430 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 17:00:00,430 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 17:00:00,431 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 17:00:00,451 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 05:00:00" (1/1) ... [2022-03-20 17:00:00,452 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 05:00:00" (1/1) ... [2022-03-20 17:00:00,466 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 05:00:00" (1/1) ... [2022-03-20 17:00:00,467 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 05:00:00" (1/1) ... [2022-03-20 17:00:00,482 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 05:00:00" (1/1) ... [2022-03-20 17:00:00,493 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 05:00:00" (1/1) ... [2022-03-20 17:00:00,494 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 05:00:00" (1/1) ... [2022-03-20 17:00:00,500 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 17:00:00,512 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 17:00:00,512 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 17:00:00,512 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 17:00:00,513 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 05:00:00" (1/1) ... [2022-03-20 17:00:00,517 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 17:00:00,523 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:00,532 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 17:00:00,561 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 17:00:00,569 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 17:00:00,569 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 17:00:00,569 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 17:00:00,569 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 17:00:00,569 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 17:00:00,569 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 17:00:00,570 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 17:00:00,570 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 17:00:00,570 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 17:00:00,570 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 17:00:00,570 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_short [2022-03-20 17:00:00,571 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 17:00:00,571 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 17:00:00,572 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 17:00:00,572 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 17:00:00,572 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 17:00:00,572 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 17:00:00,572 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 17:00:00,572 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 17:00:00,572 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 17:00:00,616 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 17:00:00,617 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 17:00:00,727 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 17:00:00,730 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 17:00:00,730 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-03-20 17:00:00,731 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 05:00:00 BoogieIcfgContainer [2022-03-20 17:00:00,732 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 17:00:00,733 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 17:00:00,733 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 17:00:00,735 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 17:00:00,735 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 05:00:00" (1/3) ... [2022-03-20 17:00:00,736 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@10021e4d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 05:00:00, skipping insertion in model container [2022-03-20 17:00:00,736 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 05:00:00" (2/3) ... [2022-03-20 17:00:00,736 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@10021e4d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 05:00:00, skipping insertion in model container [2022-03-20 17:00:00,736 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 05:00:00" (3/3) ... [2022-03-20 17:00:00,737 INFO L111 eAbstractionObserver]: Analyzing ICFG ps6-ll_valuebound100.c [2022-03-20 17:00:00,740 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-03-20 17:00:00,740 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 17:00:00,765 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 17:00:00,769 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 17:00:00,769 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 17:00:00,778 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 17:00:00,782 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-03-20 17:00:00,783 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:00,783 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 17:00:00,783 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:00,786 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:00,787 INFO L85 PathProgramCache]: Analyzing trace with hash 1098891495, now seen corresponding path program 1 times [2022-03-20 17:00:00,791 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:00,792 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1419747674] [2022-03-20 17:00:00,798 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:00,798 INFO L85 PathProgramCache]: Analyzing trace with hash 1098891495, now seen corresponding path program 2 times [2022-03-20 17:00:00,800 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:00,800 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [650528456] [2022-03-20 17:00:00,800 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:00,801 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:00,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 17:00:00,890 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 17:00:00,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 17:00:00,898 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 17:00:00,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 17:00:00,904 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-03-20 17:00:00,905 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 17:00:00,909 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 17:00:00,910 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:00,910 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [650528456] [2022-03-20 17:00:00,910 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [650528456] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:00,911 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:00,911 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 17:00:00,912 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:00,913 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1419747674] [2022-03-20 17:00:00,913 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1419747674] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:00,913 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:00,913 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 17:00:00,913 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1387476702] [2022-03-20 17:00:00,914 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:00,916 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-20 17:00:00,916 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:00,932 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-20 17:00:00,933 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 17:00:00,934 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 17:00:00,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:00,977 INFO L93 Difference]: Finished difference Result 51 states and 69 transitions. [2022-03-20 17:00:00,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-20 17:00:00,979 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 17:00:00,979 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:00,983 INFO L225 Difference]: With dead ends: 51 [2022-03-20 17:00:00,983 INFO L226 Difference]: Without dead ends: 24 [2022-03-20 17:00:00,985 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 17:00:00,987 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 17:00:00,988 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 17:00:00,998 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2022-03-20 17:00:01,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2022-03-20 17:00:01,009 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 17:00:01,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2022-03-20 17:00:01,011 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 22 [2022-03-20 17:00:01,011 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:01,011 INFO L478 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2022-03-20 17:00:01,012 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 17:00:01,012 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2022-03-20 17:00:01,013 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-03-20 17:00:01,013 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:01,013 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 17:00:01,013 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 17:00:01,013 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:01,014 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:01,014 INFO L85 PathProgramCache]: Analyzing trace with hash 769620075, now seen corresponding path program 1 times [2022-03-20 17:00:01,014 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:01,014 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [288149937] [2022-03-20 17:00:01,015 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:01,015 INFO L85 PathProgramCache]: Analyzing trace with hash 769620075, now seen corresponding path program 2 times [2022-03-20 17:00:01,015 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:01,016 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [843534677] [2022-03-20 17:00:01,016 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:01,016 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:01,030 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:01,030 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [926605879] [2022-03-20 17:00:01,030 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 17:00:01,030 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:01,031 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:01,032 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 17:00:01,050 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 17:00:01,090 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-03-20 17:00:01,090 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 17:00:01,091 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 17:00:01,095 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 17:00:01,170 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 17:00:01,170 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 17:00:01,171 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:01,171 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [843534677] [2022-03-20 17:00:01,171 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 17:00:01,171 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [926605879] [2022-03-20 17:00:01,171 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [926605879] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:01,171 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:01,172 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 17:00:01,172 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:01,172 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [288149937] [2022-03-20 17:00:01,172 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [288149937] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:01,173 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:01,173 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 17:00:01,173 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [395060740] [2022-03-20 17:00:01,173 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:01,173 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 17:00:01,173 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:01,174 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 17:00:01,174 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 17:00:01,174 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 17:00:01,222 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:01,222 INFO L93 Difference]: Finished difference Result 35 states and 40 transitions. [2022-03-20 17:00:01,223 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 17:00:01,223 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 17:00:01,223 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:01,224 INFO L225 Difference]: With dead ends: 35 [2022-03-20 17:00:01,224 INFO L226 Difference]: Without dead ends: 31 [2022-03-20 17:00:01,224 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 17:00:01,225 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 17:00:01,226 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 17:00:01,226 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-03-20 17:00:01,232 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2022-03-20 17:00:01,232 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 17:00:01,233 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 34 transitions. [2022-03-20 17:00:01,233 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 34 transitions. Word has length 22 [2022-03-20 17:00:01,233 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:01,233 INFO L478 AbstractCegarLoop]: Abstraction has 31 states and 34 transitions. [2022-03-20 17:00:01,234 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 17:00:01,234 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 34 transitions. [2022-03-20 17:00:01,234 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-03-20 17:00:01,234 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:01,235 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 17:00:01,262 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-03-20 17:00:01,465 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 17:00:01,465 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:01,466 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:01,466 INFO L85 PathProgramCache]: Analyzing trace with hash 645812411, now seen corresponding path program 1 times [2022-03-20 17:00:01,466 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:01,466 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [15309052] [2022-03-20 17:00:01,467 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:01,467 INFO L85 PathProgramCache]: Analyzing trace with hash 645812411, now seen corresponding path program 2 times [2022-03-20 17:00:01,467 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:01,467 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1280199252] [2022-03-20 17:00:01,468 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:01,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:01,477 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:01,478 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [404433473] [2022-03-20 17:00:01,478 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 17:00:01,478 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:01,478 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:01,479 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 17:00:01,482 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 17:00:01,510 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 17:00:01,511 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 17:00:01,520 INFO L263 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-20 17:00:01,521 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 17:00:01,701 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 17:00:01,701 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 17:00:02,406 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 17:00:02,406 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:02,406 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1280199252] [2022-03-20 17:00:02,406 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 17:00:02,406 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [404433473] [2022-03-20 17:00:02,407 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [404433473] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 17:00:02,407 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 17:00:02,407 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-03-20 17:00:02,407 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:02,407 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [15309052] [2022-03-20 17:00:02,408 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [15309052] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:02,408 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:02,408 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 17:00:02,408 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [698086675] [2022-03-20 17:00:02,408 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:02,408 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 17:00:02,408 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:02,409 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 17:00:02,409 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-20 17:00:02,409 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 17:00:02,439 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:02,439 INFO L93 Difference]: Finished difference Result 37 states and 39 transitions. [2022-03-20 17:00:02,439 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 17:00:02,439 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 17:00:02,440 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:02,440 INFO L225 Difference]: With dead ends: 37 [2022-03-20 17:00:02,440 INFO L226 Difference]: Without dead ends: 33 [2022-03-20 17:00:02,441 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 50 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-03-20 17:00:02,441 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 17:00:02,442 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 17:00:02,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-03-20 17:00:02,448 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-03-20 17:00:02,449 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 17:00:02,450 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 35 transitions. [2022-03-20 17:00:02,450 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 35 transitions. Word has length 29 [2022-03-20 17:00:02,450 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:02,450 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 35 transitions. [2022-03-20 17:00:02,450 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 17:00:02,451 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 35 transitions. [2022-03-20 17:00:02,451 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-03-20 17:00:02,451 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:02,451 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 17:00:02,486 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 17:00:02,665 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 17:00:02,665 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:02,666 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:02,666 INFO L85 PathProgramCache]: Analyzing trace with hash 463554397, now seen corresponding path program 1 times [2022-03-20 17:00:02,666 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:02,666 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1422979174] [2022-03-20 17:00:02,673 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:02,673 INFO L85 PathProgramCache]: Analyzing trace with hash 463554397, now seen corresponding path program 2 times [2022-03-20 17:00:02,673 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:02,674 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [952259783] [2022-03-20 17:00:02,674 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:02,674 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:02,686 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:02,686 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1509278320] [2022-03-20 17:00:02,686 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 17:00:02,687 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:02,706 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:02,707 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 17:00:02,716 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 17:00:02,760 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 17:00:02,761 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 17:00:02,762 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-20 17:00:02,764 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 17:00:02,906 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 17:00:02,906 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 17:00:03,050 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:03,050 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [952259783] [2022-03-20 17:00:03,050 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 17:00:03,050 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1509278320] [2022-03-20 17:00:03,051 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1509278320] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 17:00:03,051 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 17:00:03,051 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-03-20 17:00:03,051 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:03,051 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1422979174] [2022-03-20 17:00:03,051 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1422979174] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:03,051 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:03,051 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-03-20 17:00:03,052 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [287776606] [2022-03-20 17:00:03,052 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:03,052 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-20 17:00:03,052 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:03,052 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-20 17:00:03,052 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-03-20 17:00:03,053 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 17:00:03,108 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:03,108 INFO L93 Difference]: Finished difference Result 42 states and 46 transitions. [2022-03-20 17:00:03,108 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 17:00:03,109 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 17:00:03,109 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:03,109 INFO L225 Difference]: With dead ends: 42 [2022-03-20 17:00:03,109 INFO L226 Difference]: Without dead ends: 36 [2022-03-20 17:00:03,110 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 17:00:03,110 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 17:00:03,111 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 17:00:03,111 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-03-20 17:00:03,116 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2022-03-20 17:00:03,116 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 17:00:03,117 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 39 transitions. [2022-03-20 17:00:03,117 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 39 transitions. Word has length 40 [2022-03-20 17:00:03,117 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:03,117 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 39 transitions. [2022-03-20 17:00:03,118 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 17:00:03,118 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 39 transitions. [2022-03-20 17:00:03,120 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-03-20 17:00:03,120 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:03,120 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 17:00:03,137 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 17:00:03,337 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 17:00:03,338 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:03,338 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:03,338 INFO L85 PathProgramCache]: Analyzing trace with hash 1886956461, now seen corresponding path program 3 times [2022-03-20 17:00:03,338 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:03,338 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1643088917] [2022-03-20 17:00:03,339 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:03,339 INFO L85 PathProgramCache]: Analyzing trace with hash 1886956461, now seen corresponding path program 4 times [2022-03-20 17:00:03,339 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:03,339 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1233895120] [2022-03-20 17:00:03,339 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:03,339 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:03,348 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:03,348 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [223324502] [2022-03-20 17:00:03,348 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 17:00:03,348 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:03,348 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:03,365 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 17:00:03,366 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 17:00:03,393 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 17:00:03,393 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 17:00:03,394 INFO L263 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 16 conjunts are in the unsatisfiable core [2022-03-20 17:00:03,403 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 17:00:03,562 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 17:00:03,562 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 17:00:03,796 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:03,796 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1233895120] [2022-03-20 17:00:03,797 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 17:00:03,797 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [223324502] [2022-03-20 17:00:03,797 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [223324502] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 17:00:03,797 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 17:00:03,797 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-03-20 17:00:03,797 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:03,797 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1643088917] [2022-03-20 17:00:03,798 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1643088917] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:03,798 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:03,798 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-03-20 17:00:03,798 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1151843343] [2022-03-20 17:00:03,798 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:03,798 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-20 17:00:03,798 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:03,799 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-20 17:00:03,799 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-03-20 17:00:03,799 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 17:00:03,865 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:03,865 INFO L93 Difference]: Finished difference Result 45 states and 50 transitions. [2022-03-20 17:00:03,865 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-20 17:00:03,865 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 17:00:03,866 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:03,866 INFO L225 Difference]: With dead ends: 45 [2022-03-20 17:00:03,866 INFO L226 Difference]: Without dead ends: 39 [2022-03-20 17:00:03,866 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 54 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2022-03-20 17:00:03,867 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 17:00:03,867 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 17:00:03,868 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-03-20 17:00:03,873 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2022-03-20 17:00:03,873 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 17:00:03,873 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 43 transitions. [2022-03-20 17:00:03,874 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 43 transitions. Word has length 47 [2022-03-20 17:00:03,874 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:03,874 INFO L478 AbstractCegarLoop]: Abstraction has 39 states and 43 transitions. [2022-03-20 17:00:03,874 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 17:00:03,874 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 43 transitions. [2022-03-20 17:00:03,875 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2022-03-20 17:00:03,875 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:03,875 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 17:00:03,909 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 17:00:04,091 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 17:00:04,091 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:04,092 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:04,092 INFO L85 PathProgramCache]: Analyzing trace with hash -1213805219, now seen corresponding path program 5 times [2022-03-20 17:00:04,092 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:04,092 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1581600960] [2022-03-20 17:00:04,092 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:04,093 INFO L85 PathProgramCache]: Analyzing trace with hash -1213805219, now seen corresponding path program 6 times [2022-03-20 17:00:04,093 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:04,093 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1839284491] [2022-03-20 17:00:04,093 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:04,093 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:04,101 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:04,101 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1590547391] [2022-03-20 17:00:04,101 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 17:00:04,101 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:04,101 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:04,102 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 17:00:04,103 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 17:00:04,243 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-03-20 17:00:04,243 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 17:00:04,244 INFO L263 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 20 conjunts are in the unsatisfiable core [2022-03-20 17:00:04,246 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 17:00:04,427 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 17:00:04,434 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 17:00:04,536 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:04,537 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1839284491] [2022-03-20 17:00:04,537 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 17:00:04,537 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1590547391] [2022-03-20 17:00:04,537 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1590547391] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 17:00:04,537 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 17:00:04,537 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-03-20 17:00:04,537 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:04,537 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1581600960] [2022-03-20 17:00:04,537 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1581600960] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:04,537 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:04,537 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-03-20 17:00:04,537 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [850593891] [2022-03-20 17:00:04,538 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:04,538 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 17:00:04,538 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:04,538 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 17:00:04,538 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-03-20 17:00:04,538 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 17:00:04,611 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:04,611 INFO L93 Difference]: Finished difference Result 48 states and 54 transitions. [2022-03-20 17:00:04,611 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 17:00:04,611 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 17:00:04,612 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:04,612 INFO L225 Difference]: With dead ends: 48 [2022-03-20 17:00:04,612 INFO L226 Difference]: Without dead ends: 42 [2022-03-20 17:00:04,612 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 17:00:04,613 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.0s IncrementalHoareTripleChecker+Time [2022-03-20 17:00:04,613 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.0s Time] [2022-03-20 17:00:04,614 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2022-03-20 17:00:04,619 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2022-03-20 17:00:04,619 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 17:00:04,620 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 47 transitions. [2022-03-20 17:00:04,620 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 47 transitions. Word has length 54 [2022-03-20 17:00:04,620 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:04,620 INFO L478 AbstractCegarLoop]: Abstraction has 42 states and 47 transitions. [2022-03-20 17:00:04,620 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 17:00:04,620 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 47 transitions. [2022-03-20 17:00:04,621 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2022-03-20 17:00:04,621 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:04,621 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 17:00:04,627 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 17:00:04,825 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 17:00:04,826 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:04,826 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:04,826 INFO L85 PathProgramCache]: Analyzing trace with hash 307258797, now seen corresponding path program 7 times [2022-03-20 17:00:04,826 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:04,826 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1628773224] [2022-03-20 17:00:04,827 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:04,827 INFO L85 PathProgramCache]: Analyzing trace with hash 307258797, now seen corresponding path program 8 times [2022-03-20 17:00:04,827 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:04,827 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [94815624] [2022-03-20 17:00:04,827 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:04,827 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:04,853 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:04,853 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2101114300] [2022-03-20 17:00:04,853 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 17:00:04,853 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:04,853 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:04,868 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 17:00:04,868 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 17:00:05,094 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 17:00:05,095 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 17:00:05,096 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 24 conjunts are in the unsatisfiable core [2022-03-20 17:00:05,098 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 17:00:05,270 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 17:00:05,270 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 17:00:05,422 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:05,423 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [94815624] [2022-03-20 17:00:05,423 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 17:00:05,423 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2101114300] [2022-03-20 17:00:05,423 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2101114300] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 17:00:05,423 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 17:00:05,423 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-03-20 17:00:05,423 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:05,423 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1628773224] [2022-03-20 17:00:05,423 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1628773224] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:05,423 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:05,423 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-03-20 17:00:05,423 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [956151850] [2022-03-20 17:00:05,424 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:05,425 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-20 17:00:05,425 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:05,425 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-20 17:00:05,425 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2022-03-20 17:00:05,425 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 17:00:05,516 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:05,516 INFO L93 Difference]: Finished difference Result 51 states and 58 transitions. [2022-03-20 17:00:05,516 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 17:00:05,516 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 17:00:05,517 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:05,517 INFO L225 Difference]: With dead ends: 51 [2022-03-20 17:00:05,517 INFO L226 Difference]: Without dead ends: 45 [2022-03-20 17:00:05,517 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 17:00:05,518 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 17:00:05,518 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 17:00:05,518 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-03-20 17:00:05,524 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2022-03-20 17:00:05,524 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 17:00:05,525 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 51 transitions. [2022-03-20 17:00:05,525 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 51 transitions. Word has length 61 [2022-03-20 17:00:05,525 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:05,525 INFO L478 AbstractCegarLoop]: Abstraction has 45 states and 51 transitions. [2022-03-20 17:00:05,525 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 17:00:05,525 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 51 transitions. [2022-03-20 17:00:05,526 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2022-03-20 17:00:05,526 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:05,526 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 17:00:05,541 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 17:00:05,731 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 17:00:05,732 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:05,732 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:05,733 INFO L85 PathProgramCache]: Analyzing trace with hash 1082774365, now seen corresponding path program 9 times [2022-03-20 17:00:05,733 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:05,733 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [172762933] [2022-03-20 17:00:05,733 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:05,733 INFO L85 PathProgramCache]: Analyzing trace with hash 1082774365, now seen corresponding path program 10 times [2022-03-20 17:00:05,733 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:05,733 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1666916168] [2022-03-20 17:00:05,733 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:05,733 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:05,744 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:05,745 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [240592997] [2022-03-20 17:00:05,745 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 17:00:05,745 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:05,745 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:05,746 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 17:00:05,747 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 17:00:05,783 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 17:00:05,783 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 17:00:05,784 INFO L263 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 28 conjunts are in the unsatisfiable core [2022-03-20 17:00:05,785 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 17:00:05,980 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 17:00:05,980 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 17:00:06,129 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:06,129 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1666916168] [2022-03-20 17:00:06,129 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 17:00:06,130 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [240592997] [2022-03-20 17:00:06,130 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [240592997] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 17:00:06,130 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 17:00:06,130 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-03-20 17:00:06,130 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:06,130 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [172762933] [2022-03-20 17:00:06,130 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [172762933] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:06,130 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:06,130 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-03-20 17:00:06,130 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1699692354] [2022-03-20 17:00:06,130 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:06,131 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-20 17:00:06,131 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:06,131 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-20 17:00:06,131 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2022-03-20 17:00:06,131 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 17:00:06,234 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:06,234 INFO L93 Difference]: Finished difference Result 54 states and 62 transitions. [2022-03-20 17:00:06,234 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-20 17:00:06,234 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 17:00:06,235 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:06,235 INFO L225 Difference]: With dead ends: 54 [2022-03-20 17:00:06,235 INFO L226 Difference]: Without dead ends: 48 [2022-03-20 17:00:06,235 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 17:00:06,236 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 17:00:06,236 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 17:00:06,236 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-03-20 17:00:06,242 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2022-03-20 17:00:06,242 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 17:00:06,243 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 55 transitions. [2022-03-20 17:00:06,243 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 55 transitions. Word has length 68 [2022-03-20 17:00:06,243 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:06,243 INFO L478 AbstractCegarLoop]: Abstraction has 48 states and 55 transitions. [2022-03-20 17:00:06,243 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 17:00:06,243 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 55 transitions. [2022-03-20 17:00:06,244 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-03-20 17:00:06,244 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:06,244 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 17:00:06,260 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2022-03-20 17:00:06,455 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 17:00:06,455 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:06,456 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:06,456 INFO L85 PathProgramCache]: Analyzing trace with hash -1692754003, now seen corresponding path program 11 times [2022-03-20 17:00:06,456 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:06,456 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1479041039] [2022-03-20 17:00:06,456 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:06,456 INFO L85 PathProgramCache]: Analyzing trace with hash -1692754003, now seen corresponding path program 12 times [2022-03-20 17:00:06,457 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:06,457 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1097695215] [2022-03-20 17:00:06,457 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:06,457 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:06,463 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:06,463 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1799910735] [2022-03-20 17:00:06,464 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 17:00:06,464 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:06,464 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:06,465 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 17:00:06,466 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 17:00:06,843 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-03-20 17:00:06,843 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 17:00:06,844 INFO L263 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 34 conjunts are in the unsatisfiable core [2022-03-20 17:00:06,846 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 17:00:07,111 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 16 proven. 63 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2022-03-20 17:00:07,111 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 17:00:07,502 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:07,502 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1097695215] [2022-03-20 17:00:07,502 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 17:00:07,503 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1799910735] [2022-03-20 17:00:07,503 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1799910735] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 17:00:07,503 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 17:00:07,503 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-03-20 17:00:07,503 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:07,503 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1479041039] [2022-03-20 17:00:07,503 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1479041039] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:07,503 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:07,503 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-03-20 17:00:07,503 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1842057974] [2022-03-20 17:00:07,503 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:07,504 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-20 17:00:07,504 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:07,504 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-20 17:00:07,504 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=299, Unknown=0, NotChecked=0, Total=380 [2022-03-20 17:00:07,504 INFO L87 Difference]: Start difference. First operand 48 states and 55 transitions. Second operand has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 9 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) [2022-03-20 17:00:07,632 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:07,632 INFO L93 Difference]: Finished difference Result 57 states and 66 transitions. [2022-03-20 17:00:07,632 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-20 17:00:07,633 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 9 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) Word has length 75 [2022-03-20 17:00:07,633 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:07,633 INFO L225 Difference]: With dead ends: 57 [2022-03-20 17:00:07,633 INFO L226 Difference]: Without dead ends: 51 [2022-03-20 17:00:07,634 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 108 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=91, Invalid=371, Unknown=0, NotChecked=0, Total=462 [2022-03-20 17:00:07,634 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 2 mSDsluCounter, 350 mSDsCounter, 0 mSdLazyCounter, 174 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 395 SdHoareTripleChecker+Invalid, 175 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 17:00:07,634 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 395 Invalid, 175 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 174 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 17:00:07,635 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-03-20 17:00:07,641 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2022-03-20 17:00:07,641 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 17:00:07,642 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 59 transitions. [2022-03-20 17:00:07,642 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 59 transitions. Word has length 75 [2022-03-20 17:00:07,642 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:07,642 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 59 transitions. [2022-03-20 17:00:07,642 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 9 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) [2022-03-20 17:00:07,642 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2022-03-20 17:00:07,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-03-20 17:00:07,667 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:07,667 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 17:00:07,678 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 17:00:07,872 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 17:00:07,872 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:07,873 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:07,873 INFO L85 PathProgramCache]: Analyzing trace with hash 615143773, now seen corresponding path program 13 times [2022-03-20 17:00:07,873 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:07,873 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1226547922] [2022-03-20 17:00:07,873 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:07,874 INFO L85 PathProgramCache]: Analyzing trace with hash 615143773, now seen corresponding path program 14 times [2022-03-20 17:00:07,874 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:07,874 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [31608494] [2022-03-20 17:00:07,874 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:07,874 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:07,881 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:07,881 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2002331537] [2022-03-20 17:00:07,881 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 17:00:07,881 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:07,881 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:07,891 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 17:00:07,913 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 17:00:08,621 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 17:00:08,621 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 17:00:08,623 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 36 conjunts are in the unsatisfiable core [2022-03-20 17:00:08,624 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 17:00:08,865 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 17:00:08,866 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 17:00:08,992 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:08,993 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [31608494] [2022-03-20 17:00:08,993 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 17:00:08,993 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2002331537] [2022-03-20 17:00:08,993 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2002331537] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 17:00:08,993 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 17:00:08,993 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-03-20 17:00:08,993 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:08,993 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1226547922] [2022-03-20 17:00:08,994 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1226547922] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:08,994 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:08,994 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-03-20 17:00:08,994 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [519119587] [2022-03-20 17:00:08,994 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:08,994 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-20 17:00:08,994 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:08,994 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-20 17:00:08,994 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2022-03-20 17:00:08,995 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 17:00:09,131 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:09,131 INFO L93 Difference]: Finished difference Result 60 states and 70 transitions. [2022-03-20 17:00:09,132 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-20 17:00:09,132 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 17:00:09,132 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:09,132 INFO L225 Difference]: With dead ends: 60 [2022-03-20 17:00:09,132 INFO L226 Difference]: Without dead ends: 54 [2022-03-20 17:00:09,133 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 17:00:09,133 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 17:00:09,133 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 17:00:09,134 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-03-20 17:00:09,142 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-03-20 17:00:09,142 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 17:00:09,142 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 63 transitions. [2022-03-20 17:00:09,142 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 63 transitions. Word has length 82 [2022-03-20 17:00:09,142 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:09,142 INFO L478 AbstractCegarLoop]: Abstraction has 54 states and 63 transitions. [2022-03-20 17:00:09,143 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 17:00:09,143 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 63 transitions. [2022-03-20 17:00:09,143 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2022-03-20 17:00:09,143 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:09,143 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 17:00:09,149 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 17:00:09,349 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 17:00:09,349 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:09,350 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:09,350 INFO L85 PathProgramCache]: Analyzing trace with hash -1334355539, now seen corresponding path program 15 times [2022-03-20 17:00:09,350 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:09,350 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2074392168] [2022-03-20 17:00:09,350 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:09,350 INFO L85 PathProgramCache]: Analyzing trace with hash -1334355539, now seen corresponding path program 16 times [2022-03-20 17:00:09,350 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:09,351 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [811891550] [2022-03-20 17:00:09,351 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:09,351 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:09,357 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:09,357 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1407043202] [2022-03-20 17:00:09,357 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 17:00:09,358 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:09,358 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:09,360 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 17:00:09,362 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 17:00:09,395 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 17:00:09,395 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 17:00:09,396 INFO L263 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 40 conjunts are in the unsatisfiable core [2022-03-20 17:00:09,397 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 17:00:09,667 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 17:00:09,667 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 17:00:10,181 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:10,182 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [811891550] [2022-03-20 17:00:10,182 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 17:00:10,182 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1407043202] [2022-03-20 17:00:10,182 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1407043202] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 17:00:10,182 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 17:00:10,182 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2022-03-20 17:00:10,182 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:10,182 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2074392168] [2022-03-20 17:00:10,182 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2074392168] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:10,183 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:10,183 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14] imperfect sequences [] total 14 [2022-03-20 17:00:10,183 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [399388832] [2022-03-20 17:00:10,183 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:10,183 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-20 17:00:10,183 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:10,183 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-20 17:00:10,183 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2022-03-20 17:00:10,184 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 17:00:10,335 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:10,335 INFO L93 Difference]: Finished difference Result 63 states and 74 transitions. [2022-03-20 17:00:10,335 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-03-20 17:00:10,336 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 17:00:10,336 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:10,336 INFO L225 Difference]: With dead ends: 63 [2022-03-20 17:00:10,336 INFO L226 Difference]: Without dead ends: 57 [2022-03-20 17:00:10,337 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 90 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2022-03-20 17:00:10,337 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.1s IncrementalHoareTripleChecker+Time [2022-03-20 17:00:10,337 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.1s Time] [2022-03-20 17:00:10,338 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2022-03-20 17:00:10,365 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2022-03-20 17:00:10,365 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 17:00:10,365 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 67 transitions. [2022-03-20 17:00:10,366 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 67 transitions. Word has length 89 [2022-03-20 17:00:10,366 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:10,366 INFO L478 AbstractCegarLoop]: Abstraction has 57 states and 67 transitions. [2022-03-20 17:00:10,366 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 17:00:10,366 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 67 transitions. [2022-03-20 17:00:10,367 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2022-03-20 17:00:10,367 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:10,367 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 17:00:10,393 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 17:00:10,583 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 17:00:10,583 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:10,584 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:10,584 INFO L85 PathProgramCache]: Analyzing trace with hash 711483229, now seen corresponding path program 17 times [2022-03-20 17:00:10,584 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:10,584 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1103973613] [2022-03-20 17:00:10,584 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:10,584 INFO L85 PathProgramCache]: Analyzing trace with hash 711483229, now seen corresponding path program 18 times [2022-03-20 17:00:10,584 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:10,585 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [894869434] [2022-03-20 17:00:10,585 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:10,585 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:10,593 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:10,593 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1812764769] [2022-03-20 17:00:10,593 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 17:00:10,593 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:10,593 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:10,594 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 17:00:10,635 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 17:00:11,522 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) [2022-03-20 17:00:11,522 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 17:00:11,525 INFO L263 TraceCheckSpWp]: Trace formula consists of 249 conjuncts, 45 conjunts are in the unsatisfiable core [2022-03-20 17:00:11,527 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 17:00:11,901 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 17:00:11,901 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 17:00:12,376 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:12,377 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [894869434] [2022-03-20 17:00:12,377 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 17:00:12,377 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1812764769] [2022-03-20 17:00:12,377 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1812764769] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 17:00:12,377 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 17:00:12,377 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2022-03-20 17:00:12,377 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:12,377 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1103973613] [2022-03-20 17:00:12,377 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1103973613] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:12,377 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:12,378 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-03-20 17:00:12,378 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1130100726] [2022-03-20 17:00:12,378 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:12,378 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-20 17:00:12,378 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:12,378 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-20 17:00:12,378 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=437, Unknown=0, NotChecked=0, Total=552 [2022-03-20 17:00:12,379 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 17:00:12,578 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:12,578 INFO L93 Difference]: Finished difference Result 66 states and 78 transitions. [2022-03-20 17:00:12,579 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-20 17:00:12,579 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 17:00:12,579 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:12,580 INFO L225 Difference]: With dead ends: 66 [2022-03-20 17:00:12,580 INFO L226 Difference]: Without dead ends: 60 [2022-03-20 17:00:12,580 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 132 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=125, Invalid=525, Unknown=0, NotChecked=0, Total=650 [2022-03-20 17:00:12,581 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 17:00:12,581 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 17:00:12,581 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2022-03-20 17:00:12,592 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 60. [2022-03-20 17:00:12,592 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 17:00:12,592 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 71 transitions. [2022-03-20 17:00:12,592 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 71 transitions. Word has length 96 [2022-03-20 17:00:12,593 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:12,593 INFO L478 AbstractCegarLoop]: Abstraction has 60 states and 71 transitions. [2022-03-20 17:00:12,593 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 17:00:12,593 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 71 transitions. [2022-03-20 17:00:12,593 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2022-03-20 17:00:12,593 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:12,593 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 17:00:12,603 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 17:00:12,803 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 17:00:12,803 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:12,804 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:12,804 INFO L85 PathProgramCache]: Analyzing trace with hash -1610181715, now seen corresponding path program 19 times [2022-03-20 17:00:12,804 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:12,804 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [444174461] [2022-03-20 17:00:12,804 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:12,804 INFO L85 PathProgramCache]: Analyzing trace with hash -1610181715, now seen corresponding path program 20 times [2022-03-20 17:00:12,805 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:12,805 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [957069007] [2022-03-20 17:00:12,805 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:12,805 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:12,812 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:12,812 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1359497024] [2022-03-20 17:00:12,812 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 17:00:12,812 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:12,812 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:12,813 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 17:00:12,814 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 17:00:13,826 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 17:00:13,827 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 17:00:13,829 INFO L263 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 48 conjunts are in the unsatisfiable core [2022-03-20 17:00:13,831 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 17:00:14,196 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 17:00:14,197 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 17:00:14,364 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:14,364 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [957069007] [2022-03-20 17:00:14,364 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 17:00:14,364 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1359497024] [2022-03-20 17:00:14,364 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1359497024] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 17:00:14,364 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 17:00:14,364 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2022-03-20 17:00:14,365 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:14,365 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [444174461] [2022-03-20 17:00:14,365 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [444174461] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:14,365 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:14,365 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [16] imperfect sequences [] total 16 [2022-03-20 17:00:14,365 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [355682812] [2022-03-20 17:00:14,365 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:14,365 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-20 17:00:14,365 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:14,365 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-20 17:00:14,366 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=291, Unknown=0, NotChecked=0, Total=342 [2022-03-20 17:00:14,366 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 17:00:14,586 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:14,586 INFO L93 Difference]: Finished difference Result 69 states and 82 transitions. [2022-03-20 17:00:14,586 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-03-20 17:00:14,587 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 17:00:14,587 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:14,587 INFO L225 Difference]: With dead ends: 69 [2022-03-20 17:00:14,587 INFO L226 Difference]: Without dead ends: 63 [2022-03-20 17:00:14,588 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 17:00:14,588 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 17:00:14,588 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 17:00:14,588 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-03-20 17:00:14,600 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2022-03-20 17:00:14,601 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 17:00:14,601 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 75 transitions. [2022-03-20 17:00:14,602 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 75 transitions. Word has length 103 [2022-03-20 17:00:14,602 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:14,602 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 75 transitions. [2022-03-20 17:00:14,602 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 17:00:14,602 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 75 transitions. [2022-03-20 17:00:14,604 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2022-03-20 17:00:14,604 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:14,604 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 17:00:14,610 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-03-20 17:00:14,805 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 17:00:14,805 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:14,805 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:14,805 INFO L85 PathProgramCache]: Analyzing trace with hash 1881400669, now seen corresponding path program 21 times [2022-03-20 17:00:14,806 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:14,806 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [30141730] [2022-03-20 17:00:14,806 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:14,806 INFO L85 PathProgramCache]: Analyzing trace with hash 1881400669, now seen corresponding path program 22 times [2022-03-20 17:00:14,806 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:14,806 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [521081088] [2022-03-20 17:00:14,806 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:14,806 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:14,813 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:14,813 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1148206451] [2022-03-20 17:00:14,814 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 17:00:14,814 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:14,814 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:14,822 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 17:00:14,823 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 17:00:14,864 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 17:00:14,865 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 17:00:14,866 INFO L263 TraceCheckSpWp]: Trace formula consists of 196 conjuncts, 52 conjunts are in the unsatisfiable core [2022-03-20 17:00:14,868 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 17:00:15,214 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 17:00:15,214 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 17:00:15,334 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 17:00:15,334 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [521081088] [2022-03-20 17:00:15,335 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 17:00:15,335 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1148206451] [2022-03-20 17:00:15,335 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1148206451] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 17:00:15,335 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 17:00:15,335 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2022-03-20 17:00:15,335 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 17:00:15,335 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [30141730] [2022-03-20 17:00:15,335 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [30141730] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 17:00:15,335 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 17:00:15,335 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [17] imperfect sequences [] total 17 [2022-03-20 17:00:15,335 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [207436233] [2022-03-20 17:00:15,335 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 17:00:15,336 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-03-20 17:00:15,336 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:15,336 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-03-20 17:00:15,336 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=326, Unknown=0, NotChecked=0, Total=380 [2022-03-20 17:00:15,336 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 17:00:15,592 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 17:00:15,593 INFO L93 Difference]: Finished difference Result 72 states and 86 transitions. [2022-03-20 17:00:15,593 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-03-20 17:00:15,593 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 17:00:15,593 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 17:00:15,594 INFO L225 Difference]: With dead ends: 72 [2022-03-20 17:00:15,594 INFO L226 Difference]: Without dead ends: 66 [2022-03-20 17:00:15,594 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 17:00:15,595 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 17:00:15,595 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 17:00:15,595 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-03-20 17:00:15,608 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 66. [2022-03-20 17:00:15,608 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 17:00:15,609 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 79 transitions. [2022-03-20 17:00:15,609 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 79 transitions. Word has length 110 [2022-03-20 17:00:15,609 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 17:00:15,609 INFO L478 AbstractCegarLoop]: Abstraction has 66 states and 79 transitions. [2022-03-20 17:00:15,609 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 17:00:15,609 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 79 transitions. [2022-03-20 17:00:15,610 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2022-03-20 17:00:15,610 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 17:00:15,610 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 17:00:15,631 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 17:00:15,827 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 17:00:15,828 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 17:00:15,828 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 17:00:15,828 INFO L85 PathProgramCache]: Analyzing trace with hash 1600671149, now seen corresponding path program 23 times [2022-03-20 17:00:15,828 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 17:00:15,828 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1095375921] [2022-03-20 17:00:15,828 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 17:00:15,829 INFO L85 PathProgramCache]: Analyzing trace with hash 1600671149, now seen corresponding path program 24 times [2022-03-20 17:00:15,829 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 17:00:15,829 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1132463664] [2022-03-20 17:00:15,829 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 17:00:15,829 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 17:00:15,835 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 17:00:15,835 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [584148103] [2022-03-20 17:00:15,835 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 17:00:15,835 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 17:00:15,835 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 17:00:15,844 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 17:00:15,845 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process