/usr/bin/java -Xmx16000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/automizer/concurrent/svcomp-Reach-32bit-Automizer_Default-noMmResRef-FA-NoLbe.epf -tc ../../../trunk/examples/toolchains/AutomizerBplInline.xml -i ../../../trunk/examples/concurrent/bpl/weaver-benchmarks/generated/popl20-more/inc-subseq-array.wvr.bpl -------------------------------------------------------------------------------- This is Ultimate 0.2.1-dev-29289db [2021-06-05 06:30:48,411 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-06-05 06:30:48,413 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-06-05 06:30:48,452 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-06-05 06:30:48,453 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-06-05 06:30:48,455 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-06-05 06:30:48,457 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-06-05 06:30:48,462 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-06-05 06:30:48,464 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-06-05 06:30:48,468 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-06-05 06:30:48,468 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-06-05 06:30:48,469 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-06-05 06:30:48,470 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-06-05 06:30:48,471 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-06-05 06:30:48,473 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-06-05 06:30:48,474 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-06-05 06:30:48,476 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-06-05 06:30:48,477 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-06-05 06:30:48,479 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-06-05 06:30:48,484 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-06-05 06:30:48,485 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-06-05 06:30:48,486 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-06-05 06:30:48,487 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-06-05 06:30:48,489 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-06-05 06:30:48,495 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-06-05 06:30:48,495 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-06-05 06:30:48,495 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-06-05 06:30:48,497 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-06-05 06:30:48,497 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-06-05 06:30:48,498 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-06-05 06:30:48,498 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-06-05 06:30:48,499 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-06-05 06:30:48,500 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-06-05 06:30:48,500 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-06-05 06:30:48,501 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-06-05 06:30:48,502 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-06-05 06:30:48,502 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-06-05 06:30:48,502 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-06-05 06:30:48,502 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-06-05 06:30:48,503 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-06-05 06:30:48,504 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-06-05 06:30:48,507 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/concurrent/svcomp-Reach-32bit-Automizer_Default-noMmResRef-FA-NoLbe.epf [2021-06-05 06:30:48,542 INFO L113 SettingsManager]: Loading preferences was successful [2021-06-05 06:30:48,542 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-06-05 06:30:48,543 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-06-05 06:30:48,543 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-06-05 06:30:48,545 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-06-05 06:30:48,545 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-06-05 06:30:48,545 INFO L138 SettingsManager]: * Use SBE=true [2021-06-05 06:30:48,545 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-06-05 06:30:48,546 INFO L138 SettingsManager]: * sizeof long=4 [2021-06-05 06:30:48,546 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-06-05 06:30:48,546 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-06-05 06:30:48,547 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-06-05 06:30:48,547 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-06-05 06:30:48,547 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-06-05 06:30:48,547 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-06-05 06:30:48,547 INFO L138 SettingsManager]: * sizeof long double=12 [2021-06-05 06:30:48,547 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-06-05 06:30:48,547 INFO L138 SettingsManager]: * Use constant arrays=true [2021-06-05 06:30:48,547 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-06-05 06:30:48,547 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-06-05 06:30:48,548 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-06-05 06:30:48,548 INFO L138 SettingsManager]: * To the following directory=./dump/ [2021-06-05 06:30:48,548 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-06-05 06:30:48,548 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-06-05 06:30:48,548 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-06-05 06:30:48,548 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-06-05 06:30:48,548 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-06-05 06:30:48,548 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-06-05 06:30:48,548 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-06-05 06:30:48,549 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2021-06-05 06:30:48,549 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-06-05 06:30:48,549 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode 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 [2021-06-05 06:30:48,874 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-06-05 06:30:48,895 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-06-05 06:30:48,897 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-06-05 06:30:48,898 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2021-06-05 06:30:48,900 INFO L275 PluginConnector]: Boogie PL CUP Parser initialized [2021-06-05 06:30:48,901 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/concurrent/bpl/weaver-benchmarks/generated/popl20-more/inc-subseq-array.wvr.bpl [2021-06-05 06:30:48,901 INFO L110 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/concurrent/bpl/weaver-benchmarks/generated/popl20-more/inc-subseq-array.wvr.bpl' [2021-06-05 06:30:48,951 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-06-05 06:30:48,952 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2021-06-05 06:30:48,953 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-06-05 06:30:48,953 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-06-05 06:30:48,954 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-06-05 06:30:48,964 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 05.06 06:30:48" (1/1) ... [2021-06-05 06:30:48,971 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 05.06 06:30:48" (1/1) ... [2021-06-05 06:30:48,978 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-06-05 06:30:48,979 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-06-05 06:30:48,980 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-06-05 06:30:48,981 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-06-05 06:30:48,987 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 05.06 06:30:48" (1/1) ... [2021-06-05 06:30:48,987 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 05.06 06:30:48" (1/1) ... [2021-06-05 06:30:48,988 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 05.06 06:30:48" (1/1) ... [2021-06-05 06:30:48,989 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 05.06 06:30:48" (1/1) ... [2021-06-05 06:30:48,992 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 05.06 06:30:48" (1/1) ... [2021-06-05 06:30:48,995 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 05.06 06:30:48" (1/1) ... [2021-06-05 06:30:48,996 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 05.06 06:30:48" (1/1) ... [2021-06-05 06:30:48,997 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-06-05 06:30:48,998 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-06-05 06:30:48,998 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-06-05 06:30:48,998 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-06-05 06:30:49,000 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 05.06 06:30:48" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-06-05 06:30:49,070 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread1 given in one single declaration [2021-06-05 06:30:49,071 INFO L130 BoogieDeclarations]: Found specification of procedure thread1 [2021-06-05 06:30:49,071 INFO L138 BoogieDeclarations]: Found implementation of procedure thread1 [2021-06-05 06:30:49,071 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread2 given in one single declaration [2021-06-05 06:30:49,071 INFO L130 BoogieDeclarations]: Found specification of procedure thread2 [2021-06-05 06:30:49,071 INFO L138 BoogieDeclarations]: Found implementation of procedure thread2 [2021-06-05 06:30:49,071 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2021-06-05 06:30:49,071 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-06-05 06:30:49,071 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-06-05 06:30:49,072 WARN L209 CfgBuilder]: User set CodeBlockSize to SequenceOfStatements but program contains fork statements. Overwriting the user preferences and setting CodeBlockSize to SingleStatement [2021-06-05 06:30:49,301 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-06-05 06:30:49,302 INFO L299 CfgBuilder]: Removed 0 assume(true) statements. [2021-06-05 06:30:49,303 INFO L202 PluginConnector]: Adding new model inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.06 06:30:49 BoogieIcfgContainer [2021-06-05 06:30:49,303 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-06-05 06:30:49,318 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-06-05 06:30:49,318 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-06-05 06:30:49,320 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-06-05 06:30:49,320 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 05.06 06:30:48" (1/2) ... [2021-06-05 06:30:49,321 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6493db1e and model type inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.06 06:30:49, skipping insertion in model container [2021-06-05 06:30:49,321 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.06 06:30:49" (2/2) ... [2021-06-05 06:30:49,322 INFO L111 eAbstractionObserver]: Analyzing ICFG inc-subseq-array.wvr.bpl [2021-06-05 06:30:49,327 WARN L148 ceAbstractionStarter]: Switching off computation of Hoare annotation because input is a concurrent program [2021-06-05 06:30:49,327 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-06-05 06:30:49,327 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-06-05 06:30:49,328 INFO L510 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2021-06-05 06:30:49,386 INFO L149 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2021-06-05 06:30:49,413 INFO L255 AbstractCegarLoop]: Starting to check reachability of 3 error locations. [2021-06-05 06:30:49,429 INFO L378 AbstractCegarLoop]: Interprodecural is true [2021-06-05 06:30:49,430 INFO L379 AbstractCegarLoop]: Hoare is false [2021-06-05 06:30:49,430 INFO L380 AbstractCegarLoop]: Compute interpolants for FPandBP [2021-06-05 06:30:49,430 INFO L381 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2021-06-05 06:30:49,430 INFO L382 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2021-06-05 06:30:49,430 INFO L383 AbstractCegarLoop]: Difference is false [2021-06-05 06:30:49,430 INFO L384 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2021-06-05 06:30:49,430 INFO L388 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2021-06-05 06:30:49,438 INFO L100 iNet2FiniteAutomaton]: Start petriNet2FiniteAutomaton. Operand has 32 places, 28 transitions, 72 flow [2021-06-05 06:30:49,449 INFO L122 iNet2FiniteAutomaton]: Finished petriNet2FiniteAutomaton. Result has 65 states, 63 states have (on average 2.015873015873016) internal successors, (127), 64 states have internal predecessors, (127), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:49,451 INFO L276 IsEmpty]: Start isEmpty. Operand has 65 states, 63 states have (on average 2.015873015873016) internal successors, (127), 64 states have internal predecessors, (127), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:49,457 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2021-06-05 06:30:49,457 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:30:49,458 INFO L521 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:30:49,458 INFO L430 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:30:49,466 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:30:49,467 INFO L82 PathProgramCache]: Analyzing trace with hash 1034289359, now seen corresponding path program 1 times [2021-06-05 06:30:49,473 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:30:49,474 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1773718287] [2021-06-05 06:30:49,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:30:49,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:30:49,604 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:30:49,605 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:30:49,605 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1773718287] [2021-06-05 06:30:49,606 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1773718287] provided 1 perfect and 0 imperfect interpolant sequences [2021-06-05 06:30:49,606 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-06-05 06:30:49,607 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-06-05 06:30:49,607 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [832368921] [2021-06-05 06:30:49,611 INFO L462 AbstractCegarLoop]: Interpolant automaton has 3 states [2021-06-05 06:30:49,611 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:30:49,624 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-06-05 06:30:49,624 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-06-05 06:30:49,626 INFO L87 Difference]: Start difference. First operand has 65 states, 63 states have (on average 2.015873015873016) internal successors, (127), 64 states have internal predecessors, (127), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:49,656 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:30:49,657 INFO L93 Difference]: Finished difference Result 104 states and 211 transitions. [2021-06-05 06:30:49,657 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-06-05 06:30:49,658 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2021-06-05 06:30:49,659 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:30:49,672 INFO L225 Difference]: With dead ends: 104 [2021-06-05 06:30:49,672 INFO L226 Difference]: Without dead ends: 87 [2021-06-05 06:30:49,673 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 9.8ms TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-06-05 06:30:49,687 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2021-06-05 06:30:49,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 71. [2021-06-05 06:30:49,715 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 70 states have (on average 2.0285714285714285) internal successors, (142), 70 states have internal predecessors, (142), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:49,718 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 142 transitions. [2021-06-05 06:30:49,719 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 142 transitions. Word has length 14 [2021-06-05 06:30:49,719 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:30:49,719 INFO L482 AbstractCegarLoop]: Abstraction has 71 states and 142 transitions. [2021-06-05 06:30:49,719 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:49,719 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 142 transitions. [2021-06-05 06:30:49,721 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2021-06-05 06:30:49,721 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:30:49,721 INFO L521 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:30:49,721 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-06-05 06:30:49,721 INFO L430 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:30:49,725 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:30:49,725 INFO L82 PathProgramCache]: Analyzing trace with hash -690736212, now seen corresponding path program 1 times [2021-06-05 06:30:49,726 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:30:49,726 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [254558832] [2021-06-05 06:30:49,727 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:30:49,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:30:49,820 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:30:49,821 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:30:49,821 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [254558832] [2021-06-05 06:30:49,821 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [254558832] provided 1 perfect and 0 imperfect interpolant sequences [2021-06-05 06:30:49,822 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-06-05 06:30:49,822 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-06-05 06:30:49,822 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1769949103] [2021-06-05 06:30:49,823 INFO L462 AbstractCegarLoop]: Interpolant automaton has 4 states [2021-06-05 06:30:49,823 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:30:49,826 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-06-05 06:30:49,826 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2021-06-05 06:30:49,826 INFO L87 Difference]: Start difference. First operand 71 states and 142 transitions. Second operand has 4 states, 4 states have (on average 4.5) internal successors, (18), 3 states have internal predecessors, (18), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:49,854 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:30:49,854 INFO L93 Difference]: Finished difference Result 91 states and 175 transitions. [2021-06-05 06:30:49,855 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-06-05 06:30:49,855 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 3 states have internal predecessors, (18), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 18 [2021-06-05 06:30:49,855 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:30:49,856 INFO L225 Difference]: With dead ends: 91 [2021-06-05 06:30:49,856 INFO L226 Difference]: Without dead ends: 83 [2021-06-05 06:30:49,857 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 25.9ms TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2021-06-05 06:30:49,857 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2021-06-05 06:30:49,863 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 83. [2021-06-05 06:30:49,864 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 82 states have (on average 2.0121951219512195) internal successors, (165), 82 states have internal predecessors, (165), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:49,865 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 165 transitions. [2021-06-05 06:30:49,865 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 165 transitions. Word has length 18 [2021-06-05 06:30:49,865 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:30:49,865 INFO L482 AbstractCegarLoop]: Abstraction has 83 states and 165 transitions. [2021-06-05 06:30:49,865 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 3 states have internal predecessors, (18), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:49,865 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 165 transitions. [2021-06-05 06:30:49,866 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2021-06-05 06:30:49,866 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:30:49,866 INFO L521 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:30:49,867 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2021-06-05 06:30:49,867 INFO L430 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:30:49,867 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:30:49,867 INFO L82 PathProgramCache]: Analyzing trace with hash 1451962588, now seen corresponding path program 1 times [2021-06-05 06:30:49,868 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:30:49,868 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1961988604] [2021-06-05 06:30:49,868 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:30:49,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:30:50,034 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:30:50,035 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:30:50,035 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1961988604] [2021-06-05 06:30:50,035 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1961988604] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:30:50,035 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [985122405] [2021-06-05 06:30:50,036 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:30:50,085 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:30:50,087 INFO L263 TraceCheckSpWp]: Trace formula consists of 49 conjuncts, 11 conjunts are in the unsatisfiable core [2021-06-05 06:30:50,093 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:30:50,270 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2021-06-05 06:30:50,275 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:30:50,283 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:50,284 INFO L550 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:30:50,284 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:14, output treesize:7 [2021-06-05 06:30:50,347 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2021-06-05 06:30:50,349 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:30:50,353 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:50,354 INFO L550 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:30:50,354 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:12, output treesize:5 [2021-06-05 06:30:50,371 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:30:50,371 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [985122405] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:30:50,371 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:30:50,371 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 11 [2021-06-05 06:30:50,372 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [941299477] [2021-06-05 06:30:50,372 INFO L462 AbstractCegarLoop]: Interpolant automaton has 12 states [2021-06-05 06:30:50,372 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:30:50,373 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-06-05 06:30:50,373 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2021-06-05 06:30:50,373 INFO L87 Difference]: Start difference. First operand 83 states and 165 transitions. Second operand has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 11 states have internal predecessors, (32), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:50,515 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:30:50,515 INFO L93 Difference]: Finished difference Result 154 states and 314 transitions. [2021-06-05 06:30:50,516 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2021-06-05 06:30:50,516 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 11 states have internal predecessors, (32), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 23 [2021-06-05 06:30:50,516 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:30:50,519 INFO L225 Difference]: With dead ends: 154 [2021-06-05 06:30:50,519 INFO L226 Difference]: Without dead ends: 137 [2021-06-05 06:30:50,520 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 122.8ms TimeCoverageRelationStatistics Valid=47, Invalid=109, Unknown=0, NotChecked=0, Total=156 [2021-06-05 06:30:50,520 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2021-06-05 06:30:50,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 115. [2021-06-05 06:30:50,527 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 114 states have (on average 2.043859649122807) internal successors, (233), 114 states have internal predecessors, (233), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:50,528 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 233 transitions. [2021-06-05 06:30:50,528 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 233 transitions. Word has length 23 [2021-06-05 06:30:50,528 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:30:50,528 INFO L482 AbstractCegarLoop]: Abstraction has 115 states and 233 transitions. [2021-06-05 06:30:50,528 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 11 states have internal predecessors, (32), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:50,528 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 233 transitions. [2021-06-05 06:30:50,529 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2021-06-05 06:30:50,529 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:30:50,529 INFO L521 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:30:50,745 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2021-06-05 06:30:50,745 INFO L430 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:30:50,745 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:30:50,745 INFO L82 PathProgramCache]: Analyzing trace with hash -1705470663, now seen corresponding path program 2 times [2021-06-05 06:30:50,746 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:30:50,746 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1608085966] [2021-06-05 06:30:50,746 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:30:50,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:30:50,800 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:30:50,800 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:30:50,800 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1608085966] [2021-06-05 06:30:50,800 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1608085966] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:30:50,800 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [960437836] [2021-06-05 06:30:50,800 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:30:50,831 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-06-05 06:30:50,831 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:30:50,831 INFO L263 TraceCheckSpWp]: Trace formula consists of 58 conjuncts, 4 conjunts are in the unsatisfiable core [2021-06-05 06:30:50,833 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:30:50,890 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:30:50,890 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [960437836] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:30:50,890 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:30:50,890 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 3] total 6 [2021-06-05 06:30:50,890 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [823096972] [2021-06-05 06:30:50,891 INFO L462 AbstractCegarLoop]: Interpolant automaton has 7 states [2021-06-05 06:30:50,891 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:30:50,891 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-06-05 06:30:50,891 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2021-06-05 06:30:50,892 INFO L87 Difference]: Start difference. First operand 115 states and 233 transitions. Second operand has 7 states, 7 states have (on average 6.428571428571429) internal successors, (45), 6 states have internal predecessors, (45), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:50,962 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:30:50,962 INFO L93 Difference]: Finished difference Result 284 states and 566 transitions. [2021-06-05 06:30:50,962 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-06-05 06:30:50,963 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 6.428571428571429) internal successors, (45), 6 states have internal predecessors, (45), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 27 [2021-06-05 06:30:50,963 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:30:50,965 INFO L225 Difference]: With dead ends: 284 [2021-06-05 06:30:50,965 INFO L226 Difference]: Without dead ends: 264 [2021-06-05 06:30:50,965 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 31.4ms TimeCoverageRelationStatistics Valid=25, Invalid=31, Unknown=0, NotChecked=0, Total=56 [2021-06-05 06:30:50,966 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 264 states. [2021-06-05 06:30:50,979 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 264 to 230. [2021-06-05 06:30:50,980 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 230 states, 229 states have (on average 2.1222707423580784) internal successors, (486), 229 states have internal predecessors, (486), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:50,981 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 230 states to 230 states and 486 transitions. [2021-06-05 06:30:50,981 INFO L78 Accepts]: Start accepts. Automaton has 230 states and 486 transitions. Word has length 27 [2021-06-05 06:30:50,981 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:30:50,982 INFO L482 AbstractCegarLoop]: Abstraction has 230 states and 486 transitions. [2021-06-05 06:30:50,982 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 7 states, 7 states have (on average 6.428571428571429) internal successors, (45), 6 states have internal predecessors, (45), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:50,982 INFO L276 IsEmpty]: Start isEmpty. Operand 230 states and 486 transitions. [2021-06-05 06:30:50,984 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2021-06-05 06:30:50,984 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:30:50,984 INFO L521 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:30:51,196 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:30:51,197 INFO L430 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:30:51,197 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:30:51,198 INFO L82 PathProgramCache]: Analyzing trace with hash -906793463, now seen corresponding path program 3 times [2021-06-05 06:30:51,198 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:30:51,198 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1482030238] [2021-06-05 06:30:51,198 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:30:51,223 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:30:51,503 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:30:51,503 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:30:51,503 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1482030238] [2021-06-05 06:30:51,503 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1482030238] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:30:51,503 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1160437447] [2021-06-05 06:30:51,503 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:30:51,547 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2021-06-05 06:30:51,547 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:30:51,548 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 22 conjunts are in the unsatisfiable core [2021-06-05 06:30:51,551 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:30:51,770 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:51,771 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 27 [2021-06-05 06:30:51,781 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:30:51,787 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:51,788 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:30:51,789 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:30, output treesize:16 [2021-06-05 06:30:51,994 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:51,994 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 20 treesize of output 38 [2021-06-05 06:30:52,053 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 2 xjuncts. [2021-06-05 06:30:52,065 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:52,076 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:30:52,076 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:29, output treesize:21 [2021-06-05 06:30:52,170 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:30:52,170 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1160437447] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:30:52,171 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:30:52,171 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 27 [2021-06-05 06:30:52,171 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [673753584] [2021-06-05 06:30:52,171 INFO L462 AbstractCegarLoop]: Interpolant automaton has 28 states [2021-06-05 06:30:52,171 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:30:52,172 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2021-06-05 06:30:52,175 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=132, Invalid=624, Unknown=0, NotChecked=0, Total=756 [2021-06-05 06:30:52,175 INFO L87 Difference]: Start difference. First operand 230 states and 486 transitions. Second operand has 28 states, 28 states have (on average 2.107142857142857) internal successors, (59), 27 states have internal predecessors, (59), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:54,103 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:30:54,103 INFO L93 Difference]: Finished difference Result 650 states and 1347 transitions. [2021-06-05 06:30:54,104 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2021-06-05 06:30:54,104 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 2.107142857142857) internal successors, (59), 27 states have internal predecessors, (59), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 32 [2021-06-05 06:30:54,104 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:30:54,107 INFO L225 Difference]: With dead ends: 650 [2021-06-05 06:30:54,107 INFO L226 Difference]: Without dead ends: 573 [2021-06-05 06:30:54,108 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 989 ImplicationChecksByTransitivity, 1626.5ms TimeCoverageRelationStatistics Valid=665, Invalid=2875, Unknown=0, NotChecked=0, Total=3540 [2021-06-05 06:30:54,109 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 573 states. [2021-06-05 06:30:54,128 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 573 to 386. [2021-06-05 06:30:54,128 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 386 states, 385 states have (on average 2.1818181818181817) internal successors, (840), 385 states have internal predecessors, (840), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:54,130 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 386 states to 386 states and 840 transitions. [2021-06-05 06:30:54,130 INFO L78 Accepts]: Start accepts. Automaton has 386 states and 840 transitions. Word has length 32 [2021-06-05 06:30:54,130 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:30:54,130 INFO L482 AbstractCegarLoop]: Abstraction has 386 states and 840 transitions. [2021-06-05 06:30:54,131 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 28 states, 28 states have (on average 2.107142857142857) internal successors, (59), 27 states have internal predecessors, (59), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:54,131 INFO L276 IsEmpty]: Start isEmpty. Operand 386 states and 840 transitions. [2021-06-05 06:30:54,133 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2021-06-05 06:30:54,133 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:30:54,134 INFO L521 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:30:54,348 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:30:54,349 INFO L430 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:30:54,349 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:30:54,350 INFO L82 PathProgramCache]: Analyzing trace with hash -1731045687, now seen corresponding path program 4 times [2021-06-05 06:30:54,350 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:30:54,350 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [511770640] [2021-06-05 06:30:54,350 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:30:54,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:30:54,608 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-06-05 06:30:54,608 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:30:54,608 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [511770640] [2021-06-05 06:30:54,608 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [511770640] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:30:54,608 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1956084603] [2021-06-05 06:30:54,608 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:30:54,644 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-06-05 06:30:54,644 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:30:54,644 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 23 conjunts are in the unsatisfiable core [2021-06-05 06:30:54,646 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:30:54,949 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:54,949 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 26 [2021-06-05 06:30:54,955 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:30:54,963 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:54,970 INFO L550 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-06-05 06:30:54,970 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:44, output treesize:30 [2021-06-05 06:30:55,045 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:30:55,046 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:30:55,046 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 10 [2021-06-05 06:30:55,048 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:30:55,053 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:55,055 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:30:55,055 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:35, output treesize:5 [2021-06-05 06:30:55,066 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 1 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:30:55,066 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1956084603] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:30:55,066 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:30:55,066 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14] total 23 [2021-06-05 06:30:55,066 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1115955030] [2021-06-05 06:30:55,067 INFO L462 AbstractCegarLoop]: Interpolant automaton has 24 states [2021-06-05 06:30:55,067 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:30:55,067 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2021-06-05 06:30:55,068 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=444, Unknown=0, NotChecked=0, Total=552 [2021-06-05 06:30:55,068 INFO L87 Difference]: Start difference. First operand 386 states and 840 transitions. Second operand has 24 states, 24 states have (on average 2.2916666666666665) internal successors, (55), 23 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:55,811 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:30:55,812 INFO L93 Difference]: Finished difference Result 1023 states and 2148 transitions. [2021-06-05 06:30:55,812 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2021-06-05 06:30:55,812 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 2.2916666666666665) internal successors, (55), 23 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 32 [2021-06-05 06:30:55,812 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:30:55,816 INFO L225 Difference]: With dead ends: 1023 [2021-06-05 06:30:55,816 INFO L226 Difference]: Without dead ends: 878 [2021-06-05 06:30:55,817 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 23 SyntacticMatches, 2 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 501 ImplicationChecksByTransitivity, 669.5ms TimeCoverageRelationStatistics Valid=289, Invalid=1271, Unknown=0, NotChecked=0, Total=1560 [2021-06-05 06:30:55,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 878 states. [2021-06-05 06:30:55,831 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 878 to 432. [2021-06-05 06:30:55,832 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 432 states, 431 states have (on average 2.1786542923433876) internal successors, (939), 431 states have internal predecessors, (939), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:55,833 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 432 states to 432 states and 939 transitions. [2021-06-05 06:30:55,833 INFO L78 Accepts]: Start accepts. Automaton has 432 states and 939 transitions. Word has length 32 [2021-06-05 06:30:55,834 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:30:55,834 INFO L482 AbstractCegarLoop]: Abstraction has 432 states and 939 transitions. [2021-06-05 06:30:55,834 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 24 states, 24 states have (on average 2.2916666666666665) internal successors, (55), 23 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:55,834 INFO L276 IsEmpty]: Start isEmpty. Operand 432 states and 939 transitions. [2021-06-05 06:30:55,837 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2021-06-05 06:30:55,837 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:30:55,837 INFO L521 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:30:56,048 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,5 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:30:56,049 INFO L430 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:30:56,049 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:30:56,049 INFO L82 PathProgramCache]: Analyzing trace with hash 1528740313, now seen corresponding path program 5 times [2021-06-05 06:30:56,050 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:30:56,050 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [433088959] [2021-06-05 06:30:56,050 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:30:56,059 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:30:56,307 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:30:56,308 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:30:56,308 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [433088959] [2021-06-05 06:30:56,308 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [433088959] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:30:56,308 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [966576582] [2021-06-05 06:30:56,308 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:30:56,335 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2021-06-05 06:30:56,336 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:30:56,337 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 21 conjunts are in the unsatisfiable core [2021-06-05 06:30:56,344 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:30:56,586 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:56,586 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 24 [2021-06-05 06:30:56,590 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:30:56,598 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:56,599 INFO L550 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-06-05 06:30:56,599 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:38, output treesize:24 [2021-06-05 06:30:56,699 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:30:56,700 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:30:56,701 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2021-06-05 06:30:56,702 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:30:56,708 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:56,710 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:30:56,710 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:29, output treesize:5 [2021-06-05 06:30:56,720 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:30:56,720 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [966576582] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:30:56,721 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:30:56,721 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14] total 24 [2021-06-05 06:30:56,721 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1515490932] [2021-06-05 06:30:56,721 INFO L462 AbstractCegarLoop]: Interpolant automaton has 25 states [2021-06-05 06:30:56,721 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:30:56,722 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2021-06-05 06:30:56,722 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=492, Unknown=0, NotChecked=0, Total=600 [2021-06-05 06:30:56,722 INFO L87 Difference]: Start difference. First operand 432 states and 939 transitions. Second operand has 25 states, 25 states have (on average 2.2) internal successors, (55), 24 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:57,535 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:30:57,536 INFO L93 Difference]: Finished difference Result 1081 states and 2273 transitions. [2021-06-05 06:30:57,536 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2021-06-05 06:30:57,536 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 2.2) internal successors, (55), 24 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 32 [2021-06-05 06:30:57,537 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:30:57,540 INFO L225 Difference]: With dead ends: 1081 [2021-06-05 06:30:57,540 INFO L226 Difference]: Without dead ends: 927 [2021-06-05 06:30:57,541 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 498 ImplicationChecksByTransitivity, 715.4ms TimeCoverageRelationStatistics Valid=295, Invalid=1345, Unknown=0, NotChecked=0, Total=1640 [2021-06-05 06:30:57,543 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 927 states. [2021-06-05 06:30:57,555 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 927 to 450. [2021-06-05 06:30:57,556 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 450 states, 449 states have (on average 2.1848552338530065) internal successors, (981), 449 states have internal predecessors, (981), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:57,559 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 450 states to 450 states and 981 transitions. [2021-06-05 06:30:57,559 INFO L78 Accepts]: Start accepts. Automaton has 450 states and 981 transitions. Word has length 32 [2021-06-05 06:30:57,559 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:30:57,559 INFO L482 AbstractCegarLoop]: Abstraction has 450 states and 981 transitions. [2021-06-05 06:30:57,560 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 25 states, 25 states have (on average 2.2) internal successors, (55), 24 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:57,560 INFO L276 IsEmpty]: Start isEmpty. Operand 450 states and 981 transitions. [2021-06-05 06:30:57,561 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2021-06-05 06:30:57,561 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:30:57,561 INFO L521 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:30:57,784 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable22 [2021-06-05 06:30:57,784 INFO L430 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:30:57,784 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:30:57,785 INFO L82 PathProgramCache]: Analyzing trace with hash -897893841, now seen corresponding path program 6 times [2021-06-05 06:30:57,785 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:30:57,785 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [215271249] [2021-06-05 06:30:57,785 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:30:57,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:30:58,006 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-06-05 06:30:58,006 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:30:58,006 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [215271249] [2021-06-05 06:30:58,007 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [215271249] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:30:58,007 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [618873508] [2021-06-05 06:30:58,007 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:30:58,036 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2021-06-05 06:30:58,036 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:30:58,037 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 22 conjunts are in the unsatisfiable core [2021-06-05 06:30:58,038 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:30:58,291 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:58,292 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 24 [2021-06-05 06:30:58,295 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:30:58,300 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:58,301 INFO L550 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:30:58,301 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:32, output treesize:18 [2021-06-05 06:30:58,338 INFO L354 Elim1Store]: treesize reduction 9, result has 10.0 percent of original size [2021-06-05 06:30:58,338 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 22 treesize of output 10 [2021-06-05 06:30:58,342 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:30:58,345 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:58,345 INFO L550 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:30:58,345 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:23, output treesize:5 [2021-06-05 06:30:58,358 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:30:58,358 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [618873508] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:30:58,358 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:30:58,359 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14] total 25 [2021-06-05 06:30:58,359 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2058340813] [2021-06-05 06:30:58,359 INFO L462 AbstractCegarLoop]: Interpolant automaton has 26 states [2021-06-05 06:30:58,359 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:30:58,359 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2021-06-05 06:30:58,360 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=534, Unknown=0, NotChecked=0, Total=650 [2021-06-05 06:30:58,360 INFO L87 Difference]: Start difference. First operand 450 states and 981 transitions. Second operand has 26 states, 26 states have (on average 2.1538461538461537) internal successors, (56), 25 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:59,242 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:30:59,242 INFO L93 Difference]: Finished difference Result 1050 states and 2217 transitions. [2021-06-05 06:30:59,243 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2021-06-05 06:30:59,243 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 2.1538461538461537) internal successors, (56), 25 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 32 [2021-06-05 06:30:59,243 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:30:59,247 INFO L225 Difference]: With dead ends: 1050 [2021-06-05 06:30:59,247 INFO L226 Difference]: Without dead ends: 939 [2021-06-05 06:30:59,249 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 22 SyntacticMatches, 1 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 718 ImplicationChecksByTransitivity, 828.8ms TimeCoverageRelationStatistics Valid=378, Invalid=1974, Unknown=0, NotChecked=0, Total=2352 [2021-06-05 06:30:59,250 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 939 states. [2021-06-05 06:30:59,261 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 939 to 482. [2021-06-05 06:30:59,262 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 482 states, 481 states have (on average 2.176715176715177) internal successors, (1047), 481 states have internal predecessors, (1047), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:59,264 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 482 states to 482 states and 1047 transitions. [2021-06-05 06:30:59,264 INFO L78 Accepts]: Start accepts. Automaton has 482 states and 1047 transitions. Word has length 32 [2021-06-05 06:30:59,264 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:30:59,264 INFO L482 AbstractCegarLoop]: Abstraction has 482 states and 1047 transitions. [2021-06-05 06:30:59,264 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 26 states, 26 states have (on average 2.1538461538461537) internal successors, (56), 25 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:30:59,265 INFO L276 IsEmpty]: Start isEmpty. Operand 482 states and 1047 transitions. [2021-06-05 06:30:59,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2021-06-05 06:30:59,267 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:30:59,267 INFO L521 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:30:59,480 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable26,7 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:30:59,481 INFO L430 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:30:59,481 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:30:59,481 INFO L82 PathProgramCache]: Analyzing trace with hash -960521271, now seen corresponding path program 7 times [2021-06-05 06:30:59,481 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:30:59,481 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1666962092] [2021-06-05 06:30:59,482 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:30:59,491 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:30:59,672 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:30:59,672 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:30:59,673 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1666962092] [2021-06-05 06:30:59,673 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1666962092] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:30:59,673 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [363291689] [2021-06-05 06:30:59,673 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:30:59,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:30:59,717 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 23 conjunts are in the unsatisfiable core [2021-06-05 06:30:59,718 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:30:59,961 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:59,962 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 26 [2021-06-05 06:30:59,972 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:30:59,980 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:30:59,981 INFO L550 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-06-05 06:30:59,982 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:44, output treesize:30 [2021-06-05 06:31:00,102 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:00,103 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:00,103 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:00,104 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 10 [2021-06-05 06:31:00,106 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:00,112 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:00,114 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:31:00,114 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:35, output treesize:5 [2021-06-05 06:31:00,124 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:00,125 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [363291689] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:00,125 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:00,125 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14] total 24 [2021-06-05 06:31:00,127 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [731554564] [2021-06-05 06:31:00,128 INFO L462 AbstractCegarLoop]: Interpolant automaton has 25 states [2021-06-05 06:31:00,128 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:00,128 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2021-06-05 06:31:00,128 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=494, Unknown=0, NotChecked=0, Total=600 [2021-06-05 06:31:00,129 INFO L87 Difference]: Start difference. First operand 482 states and 1047 transitions. Second operand has 25 states, 25 states have (on average 2.2) internal successors, (55), 24 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:00,685 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:00,685 INFO L93 Difference]: Finished difference Result 1045 states and 2215 transitions. [2021-06-05 06:31:00,686 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2021-06-05 06:31:00,686 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 2.2) internal successors, (55), 24 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 32 [2021-06-05 06:31:00,686 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:00,689 INFO L225 Difference]: With dead ends: 1045 [2021-06-05 06:31:00,689 INFO L226 Difference]: Without dead ends: 947 [2021-06-05 06:31:00,690 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 294 ImplicationChecksByTransitivity, 530.4ms TimeCoverageRelationStatistics Valid=182, Invalid=810, Unknown=0, NotChecked=0, Total=992 [2021-06-05 06:31:00,694 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 947 states. [2021-06-05 06:31:00,700 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 947 to 464. [2021-06-05 06:31:00,701 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 464 states, 463 states have (on average 2.1576673866090714) internal successors, (999), 463 states have internal predecessors, (999), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:00,702 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 464 states to 464 states and 999 transitions. [2021-06-05 06:31:00,702 INFO L78 Accepts]: Start accepts. Automaton has 464 states and 999 transitions. Word has length 32 [2021-06-05 06:31:00,702 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:00,702 INFO L482 AbstractCegarLoop]: Abstraction has 464 states and 999 transitions. [2021-06-05 06:31:00,702 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 25 states, 25 states have (on average 2.2) internal successors, (55), 24 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:00,703 INFO L276 IsEmpty]: Start isEmpty. Operand 464 states and 999 transitions. [2021-06-05 06:31:00,704 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2021-06-05 06:31:00,704 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:00,704 INFO L521 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:00,927 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable29,8 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:00,927 INFO L430 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:00,927 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:00,927 INFO L82 PathProgramCache]: Analyzing trace with hash 2010412006, now seen corresponding path program 8 times [2021-06-05 06:31:00,927 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:00,927 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [675792421] [2021-06-05 06:31:00,927 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:00,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:01,003 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 15 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:01,003 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:31:01,003 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [675792421] [2021-06-05 06:31:01,003 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [675792421] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:01,003 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1939712482] [2021-06-05 06:31:01,003 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:01,029 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-06-05 06:31:01,029 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:31:01,029 INFO L263 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 6 conjunts are in the unsatisfiable core [2021-06-05 06:31:01,030 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:31:01,097 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 15 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:01,097 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1939712482] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:01,097 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:01,097 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 4] total 8 [2021-06-05 06:31:01,098 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [360558390] [2021-06-05 06:31:01,098 INFO L462 AbstractCegarLoop]: Interpolant automaton has 9 states [2021-06-05 06:31:01,098 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:01,098 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-06-05 06:31:01,099 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=42, Unknown=0, NotChecked=0, Total=72 [2021-06-05 06:31:01,099 INFO L87 Difference]: Start difference. First operand 464 states and 999 transitions. Second operand has 9 states, 9 states have (on average 6.444444444444445) internal successors, (58), 8 states have internal predecessors, (58), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:01,166 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:01,166 INFO L93 Difference]: Finished difference Result 882 states and 1900 transitions. [2021-06-05 06:31:01,167 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-06-05 06:31:01,167 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 6.444444444444445) internal successors, (58), 8 states have internal predecessors, (58), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 36 [2021-06-05 06:31:01,167 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:01,170 INFO L225 Difference]: With dead ends: 882 [2021-06-05 06:31:01,170 INFO L226 Difference]: Without dead ends: 844 [2021-06-05 06:31:01,170 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 39.7ms TimeCoverageRelationStatistics Valid=39, Invalid=51, Unknown=0, NotChecked=0, Total=90 [2021-06-05 06:31:01,171 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 844 states. [2021-06-05 06:31:01,182 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 844 to 713. [2021-06-05 06:31:01,183 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 713 states, 712 states have (on average 2.182584269662921) internal successors, (1554), 712 states have internal predecessors, (1554), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:01,185 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 713 states to 713 states and 1554 transitions. [2021-06-05 06:31:01,185 INFO L78 Accepts]: Start accepts. Automaton has 713 states and 1554 transitions. Word has length 36 [2021-06-05 06:31:01,185 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:01,185 INFO L482 AbstractCegarLoop]: Abstraction has 713 states and 1554 transitions. [2021-06-05 06:31:01,185 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 9 states, 9 states have (on average 6.444444444444445) internal successors, (58), 8 states have internal predecessors, (58), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:01,185 INFO L276 IsEmpty]: Start isEmpty. Operand 713 states and 1554 transitions. [2021-06-05 06:31:01,187 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-06-05 06:31:01,187 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:01,187 INFO L521 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:01,403 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable33 [2021-06-05 06:31:01,403 INFO L430 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:01,403 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:01,404 INFO L82 PathProgramCache]: Analyzing trace with hash -1466399466, now seen corresponding path program 9 times [2021-06-05 06:31:01,404 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:01,404 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [418841133] [2021-06-05 06:31:01,404 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:01,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:01,809 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:01,809 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:31:01,809 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [418841133] [2021-06-05 06:31:01,810 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [418841133] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:01,810 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [940598800] [2021-06-05 06:31:01,810 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:01,842 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2021-06-05 06:31:01,843 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:31:01,844 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 37 conjunts are in the unsatisfiable core [2021-06-05 06:31:01,845 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:31:02,212 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:02,212 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 45 treesize of output 53 [2021-06-05 06:31:02,222 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:02,263 INFO L628 ElimStorePlain]: treesize reduction 14, result has 83.5 percent of original size [2021-06-05 06:31:02,266 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:31:02,266 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:51, output treesize:52 [2021-06-05 06:31:02,522 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:02,522 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:02,523 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:02,534 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:02,534 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 35 treesize of output 43 [2021-06-05 06:31:02,552 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 2 xjuncts. [2021-06-05 06:31:02,563 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:02,566 INFO L550 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:31:02,566 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:44, output treesize:26 [2021-06-05 06:31:02,638 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:02,638 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [940598800] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:02,638 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:02,638 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 21] total 41 [2021-06-05 06:31:02,638 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [470483971] [2021-06-05 06:31:02,639 INFO L462 AbstractCegarLoop]: Interpolant automaton has 42 states [2021-06-05 06:31:02,639 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:02,639 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2021-06-05 06:31:02,640 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=236, Invalid=1486, Unknown=0, NotChecked=0, Total=1722 [2021-06-05 06:31:02,640 INFO L87 Difference]: Start difference. First operand 713 states and 1554 transitions. Second operand has 42 states, 42 states have (on average 1.8333333333333333) internal successors, (77), 41 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:06,327 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:06,327 INFO L93 Difference]: Finished difference Result 2812 states and 6023 transitions. [2021-06-05 06:31:06,328 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 76 states. [2021-06-05 06:31:06,328 INFO L78 Accepts]: Start accepts. Automaton has has 42 states, 42 states have (on average 1.8333333333333333) internal successors, (77), 41 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-06-05 06:31:06,328 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:06,337 INFO L225 Difference]: With dead ends: 2812 [2021-06-05 06:31:06,337 INFO L226 Difference]: Without dead ends: 2548 [2021-06-05 06:31:06,340 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 107 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3752 ImplicationChecksByTransitivity, 3091.1ms TimeCoverageRelationStatistics Valid=1451, Invalid=10321, Unknown=0, NotChecked=0, Total=11772 [2021-06-05 06:31:06,343 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2548 states. [2021-06-05 06:31:06,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2548 to 737. [2021-06-05 06:31:06,364 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 737 states, 736 states have (on average 2.1480978260869565) internal successors, (1581), 736 states have internal predecessors, (1581), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:06,366 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 737 states to 737 states and 1581 transitions. [2021-06-05 06:31:06,366 INFO L78 Accepts]: Start accepts. Automaton has 737 states and 1581 transitions. Word has length 41 [2021-06-05 06:31:06,366 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:06,366 INFO L482 AbstractCegarLoop]: Abstraction has 737 states and 1581 transitions. [2021-06-05 06:31:06,366 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 42 states, 42 states have (on average 1.8333333333333333) internal successors, (77), 41 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:06,366 INFO L276 IsEmpty]: Start isEmpty. Operand 737 states and 1581 transitions. [2021-06-05 06:31:06,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-06-05 06:31:06,368 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:06,368 INFO L521 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:06,590 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable34,10 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:06,590 INFO L430 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:06,590 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:06,590 INFO L82 PathProgramCache]: Analyzing trace with hash 1999894166, now seen corresponding path program 10 times [2021-06-05 06:31:06,590 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:06,590 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1099776780] [2021-06-05 06:31:06,591 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:06,604 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:06,951 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 32 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-06-05 06:31:06,951 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:31:06,951 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1099776780] [2021-06-05 06:31:06,951 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1099776780] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:06,951 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [161296164] [2021-06-05 06:31:06,951 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:06,985 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-06-05 06:31:06,985 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:31:06,986 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 35 conjunts are in the unsatisfiable core [2021-06-05 06:31:06,988 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:31:07,716 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:07,717 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 42 treesize of output 52 [2021-06-05 06:31:07,723 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:07,768 INFO L628 ElimStorePlain]: treesize reduction 16, result has 84.3 percent of original size [2021-06-05 06:31:07,781 INFO L550 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-06-05 06:31:07,781 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 5 variables, input treesize:60, output treesize:65 [2021-06-05 06:31:08,152 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:08,153 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:08,154 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:08,155 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:08,156 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:08,157 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:08,157 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:08,158 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:08,170 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:08,170 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:08,171 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 3 disjoint index pairs (out of 10 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 13 [2021-06-05 06:31:08,173 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:08,176 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:08,177 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:08,177 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:08,178 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:08,179 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:08,179 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:08,181 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:08,182 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:08,182 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 3 disjoint index pairs (out of 10 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 16 [2021-06-05 06:31:08,184 INFO L550 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:08,190 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:08,191 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:31:08,191 INFO L247 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:104, output treesize:5 [2021-06-05 06:31:08,200 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 1 proven. 32 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:08,200 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [161296164] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:08,200 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:08,200 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 20] total 35 [2021-06-05 06:31:08,200 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [385048957] [2021-06-05 06:31:08,201 INFO L462 AbstractCegarLoop]: Interpolant automaton has 36 states [2021-06-05 06:31:08,201 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:08,201 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2021-06-05 06:31:08,201 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=176, Invalid=1084, Unknown=0, NotChecked=0, Total=1260 [2021-06-05 06:31:08,201 INFO L87 Difference]: Start difference. First operand 737 states and 1581 transitions. Second operand has 36 states, 36 states have (on average 2.0277777777777777) internal successors, (73), 35 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:10,486 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:10,486 INFO L93 Difference]: Finished difference Result 2302 states and 4879 transitions. [2021-06-05 06:31:10,486 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 50 states. [2021-06-05 06:31:10,487 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 36 states have (on average 2.0277777777777777) internal successors, (73), 35 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-06-05 06:31:10,487 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:10,493 INFO L225 Difference]: With dead ends: 2302 [2021-06-05 06:31:10,494 INFO L226 Difference]: Without dead ends: 2145 [2021-06-05 06:31:10,495 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 21 SyntacticMatches, 8 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1950 ImplicationChecksByTransitivity, 1890.3ms TimeCoverageRelationStatistics Valid=673, Invalid=4297, Unknown=0, NotChecked=0, Total=4970 [2021-06-05 06:31:10,497 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2145 states. [2021-06-05 06:31:10,515 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2145 to 854. [2021-06-05 06:31:10,517 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 854 states, 853 states have (on average 2.138335287221571) internal successors, (1824), 853 states have internal predecessors, (1824), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:10,518 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 854 states to 854 states and 1824 transitions. [2021-06-05 06:31:10,519 INFO L78 Accepts]: Start accepts. Automaton has 854 states and 1824 transitions. Word has length 41 [2021-06-05 06:31:10,519 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:10,519 INFO L482 AbstractCegarLoop]: Abstraction has 854 states and 1824 transitions. [2021-06-05 06:31:10,519 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 36 states, 36 states have (on average 2.0277777777777777) internal successors, (73), 35 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:10,519 INFO L276 IsEmpty]: Start isEmpty. Operand 854 states and 1824 transitions. [2021-06-05 06:31:10,521 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-06-05 06:31:10,521 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:10,521 INFO L521 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:10,743 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable49 [2021-06-05 06:31:10,744 INFO L430 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:10,744 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:10,744 INFO L82 PathProgramCache]: Analyzing trace with hash -1038925816, now seen corresponding path program 11 times [2021-06-05 06:31:10,744 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:10,744 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [151102830] [2021-06-05 06:31:10,744 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:10,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:11,103 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:11,103 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:31:11,103 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [151102830] [2021-06-05 06:31:11,103 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [151102830] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:11,103 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [662776014] [2021-06-05 06:31:11,103 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:11,135 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2021-06-05 06:31:11,136 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:31:11,136 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 34 conjunts are in the unsatisfiable core [2021-06-05 06:31:11,137 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:31:11,686 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:11,687 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 40 treesize of output 50 [2021-06-05 06:31:11,692 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:11,730 INFO L628 ElimStorePlain]: treesize reduction 43, result has 58.7 percent of original size [2021-06-05 06:31:11,732 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:31:11,732 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:48, output treesize:29 [2021-06-05 06:31:11,816 INFO L354 Elim1Store]: treesize reduction 32, result has 3.0 percent of original size [2021-06-05 06:31:11,816 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 13 [2021-06-05 06:31:11,818 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:11,821 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:11,822 INFO L550 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:31:11,822 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:34, output treesize:5 [2021-06-05 06:31:11,833 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:11,833 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [662776014] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:11,833 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:11,834 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 20] total 38 [2021-06-05 06:31:11,834 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1353123283] [2021-06-05 06:31:11,834 INFO L462 AbstractCegarLoop]: Interpolant automaton has 39 states [2021-06-05 06:31:11,834 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:11,834 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2021-06-05 06:31:11,835 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=185, Invalid=1297, Unknown=0, NotChecked=0, Total=1482 [2021-06-05 06:31:11,835 INFO L87 Difference]: Start difference. First operand 854 states and 1824 transitions. Second operand has 39 states, 39 states have (on average 1.8974358974358974) internal successors, (74), 38 states have internal predecessors, (74), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:14,082 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:14,082 INFO L93 Difference]: Finished difference Result 2428 states and 5151 transitions. [2021-06-05 06:31:14,082 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2021-06-05 06:31:14,082 INFO L78 Accepts]: Start accepts. Automaton has has 39 states, 39 states have (on average 1.8974358974358974) internal successors, (74), 38 states have internal predecessors, (74), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-06-05 06:31:14,083 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:14,088 INFO L225 Difference]: With dead ends: 2428 [2021-06-05 06:31:14,088 INFO L226 Difference]: Without dead ends: 2232 [2021-06-05 06:31:14,089 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 70 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1693 ImplicationChecksByTransitivity, 1743.9ms TimeCoverageRelationStatistics Valid=593, Invalid=4519, Unknown=0, NotChecked=0, Total=5112 [2021-06-05 06:31:14,091 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2232 states. [2021-06-05 06:31:14,109 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2232 to 956. [2021-06-05 06:31:14,111 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 956 states, 955 states have (on average 2.1382198952879583) internal successors, (2042), 955 states have internal predecessors, (2042), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:14,113 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 956 states to 956 states and 2042 transitions. [2021-06-05 06:31:14,113 INFO L78 Accepts]: Start accepts. Automaton has 956 states and 2042 transitions. Word has length 41 [2021-06-05 06:31:14,113 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:14,113 INFO L482 AbstractCegarLoop]: Abstraction has 956 states and 2042 transitions. [2021-06-05 06:31:14,113 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 39 states, 39 states have (on average 1.8974358974358974) internal successors, (74), 38 states have internal predecessors, (74), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:14,114 INFO L276 IsEmpty]: Start isEmpty. Operand 956 states and 2042 transitions. [2021-06-05 06:31:14,115 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-06-05 06:31:14,115 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:14,115 INFO L521 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:14,340 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable69 [2021-06-05 06:31:14,340 INFO L430 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:14,341 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:14,341 INFO L82 PathProgramCache]: Analyzing trace with hash 1257871970, now seen corresponding path program 12 times [2021-06-05 06:31:14,341 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:14,341 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [947883512] [2021-06-05 06:31:14,341 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:14,351 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:14,699 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 32 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-06-05 06:31:14,699 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:31:14,699 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [947883512] [2021-06-05 06:31:14,699 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [947883512] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:14,699 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1365796389] [2021-06-05 06:31:14,699 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:14,731 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2021-06-05 06:31:14,731 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:31:14,732 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 36 conjunts are in the unsatisfiable core [2021-06-05 06:31:14,733 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:31:15,538 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:15,538 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 47 treesize of output 77 [2021-06-05 06:31:15,578 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:15,638 INFO L628 ElimStorePlain]: treesize reduction 197, result has 27.3 percent of original size [2021-06-05 06:31:15,648 INFO L550 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-06-05 06:31:15,648 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 5 variables, input treesize:53, output treesize:47 [2021-06-05 06:31:16,260 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:16,288 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:16,289 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 1 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 5 case distinctions, treesize of input 29 treesize of output 63 [2021-06-05 06:31:16,349 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 3 xjuncts. [2021-06-05 06:31:16,352 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:16,360 INFO L354 Elim1Store]: treesize reduction 50, result has 2.0 percent of original size [2021-06-05 06:31:16,360 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 1 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 5 case distinctions, treesize of input 40 treesize of output 1 [2021-06-05 06:31:16,361 INFO L550 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:16,385 INFO L628 ElimStorePlain]: treesize reduction 21, result has 54.3 percent of original size [2021-06-05 06:31:16,389 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:31:16,389 INFO L247 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:88, output treesize:21 [2021-06-05 06:31:16,468 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:16,468 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1365796389] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:16,468 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:16,468 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 39 [2021-06-05 06:31:16,469 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [738300642] [2021-06-05 06:31:16,469 INFO L462 AbstractCegarLoop]: Interpolant automaton has 40 states [2021-06-05 06:31:16,469 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:16,470 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2021-06-05 06:31:16,470 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=206, Invalid=1354, Unknown=0, NotChecked=0, Total=1560 [2021-06-05 06:31:16,470 INFO L87 Difference]: Start difference. First operand 956 states and 2042 transitions. Second operand has 40 states, 40 states have (on average 1.925) internal successors, (77), 39 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:18,440 WARN L205 SmtUtils]: Spent 314.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 37 [2021-06-05 06:31:19,026 WARN L205 SmtUtils]: Spent 127.00 ms on a formula simplification that was a NOOP. DAG size: 47 [2021-06-05 06:31:20,117 WARN L205 SmtUtils]: Spent 132.00 ms on a formula simplification that was a NOOP. DAG size: 58 [2021-06-05 06:31:30,555 WARN L205 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 58 [2021-06-05 06:31:31,166 WARN L205 SmtUtils]: Spent 118.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 58 [2021-06-05 06:31:31,725 WARN L205 SmtUtils]: Spent 101.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 54 [2021-06-05 06:31:31,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:31,946 INFO L93 Difference]: Finished difference Result 4013 states and 8575 transitions. [2021-06-05 06:31:31,946 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 143 states. [2021-06-05 06:31:31,946 INFO L78 Accepts]: Start accepts. Automaton has has 40 states, 40 states have (on average 1.925) internal successors, (77), 39 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-06-05 06:31:31,946 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:31,959 INFO L225 Difference]: With dead ends: 4013 [2021-06-05 06:31:31,959 INFO L226 Difference]: Without dead ends: 3813 [2021-06-05 06:31:31,963 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 18 SyntacticMatches, 7 SemanticMatches, 172 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11305 ImplicationChecksByTransitivity, 12047.5ms TimeCoverageRelationStatistics Valid=3722, Invalid=26380, Unknown=0, NotChecked=0, Total=30102 [2021-06-05 06:31:31,966 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3813 states. [2021-06-05 06:31:31,989 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3813 to 1122. [2021-06-05 06:31:31,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1122 states, 1121 states have (on average 2.145405887600357) internal successors, (2405), 1121 states have internal predecessors, (2405), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:31,992 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1122 states to 1122 states and 2405 transitions. [2021-06-05 06:31:31,992 INFO L78 Accepts]: Start accepts. Automaton has 1122 states and 2405 transitions. Word has length 41 [2021-06-05 06:31:31,993 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:31,993 INFO L482 AbstractCegarLoop]: Abstraction has 1122 states and 2405 transitions. [2021-06-05 06:31:31,993 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 40 states, 40 states have (on average 1.925) internal successors, (77), 39 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:31,993 INFO L276 IsEmpty]: Start isEmpty. Operand 1122 states and 2405 transitions. [2021-06-05 06:31:31,995 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-06-05 06:31:31,995 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:31,995 INFO L521 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:32,208 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable74,13 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:32,209 INFO L430 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:32,209 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:32,209 INFO L82 PathProgramCache]: Analyzing trace with hash -2064541460, now seen corresponding path program 13 times [2021-06-05 06:31:32,209 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:32,209 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [968059572] [2021-06-05 06:31:32,209 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:32,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:32,555 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 32 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-06-05 06:31:32,555 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:31:32,555 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [968059572] [2021-06-05 06:31:32,555 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [968059572] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:32,555 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [252641387] [2021-06-05 06:31:32,555 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:32,586 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:32,586 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 35 conjunts are in the unsatisfiable core [2021-06-05 06:31:32,588 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:31:33,285 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:33,285 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 42 treesize of output 52 [2021-06-05 06:31:33,291 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:33,341 INFO L628 ElimStorePlain]: treesize reduction 47, result has 60.8 percent of original size [2021-06-05 06:31:33,347 INFO L550 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-06-05 06:31:33,347 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 5 variables, input treesize:60, output treesize:41 [2021-06-05 06:31:33,437 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:33,437 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:33,438 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:33,439 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:33,439 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:33,440 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:33,440 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:33,441 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 3 disjoint index pairs (out of 10 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 13 [2021-06-05 06:31:33,442 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:33,447 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:33,448 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:31:33,448 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:46, output treesize:5 [2021-06-05 06:31:33,458 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 1 proven. 32 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:33,458 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [252641387] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:33,458 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:33,458 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 20] total 35 [2021-06-05 06:31:33,458 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [383217292] [2021-06-05 06:31:33,459 INFO L462 AbstractCegarLoop]: Interpolant automaton has 36 states [2021-06-05 06:31:33,459 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:33,459 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2021-06-05 06:31:33,459 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=173, Invalid=1087, Unknown=0, NotChecked=0, Total=1260 [2021-06-05 06:31:33,460 INFO L87 Difference]: Start difference. First operand 1122 states and 2405 transitions. Second operand has 36 states, 36 states have (on average 2.0277777777777777) internal successors, (73), 35 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:35,637 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:35,637 INFO L93 Difference]: Finished difference Result 4028 states and 8625 transitions. [2021-06-05 06:31:35,637 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2021-06-05 06:31:35,637 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 36 states have (on average 2.0277777777777777) internal successors, (73), 35 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-06-05 06:31:35,637 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:35,649 INFO L225 Difference]: With dead ends: 4028 [2021-06-05 06:31:35,649 INFO L226 Difference]: Without dead ends: 3805 [2021-06-05 06:31:35,650 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 27 SyntacticMatches, 2 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1398 ImplicationChecksByTransitivity, 1622.9ms TimeCoverageRelationStatistics Valid=578, Invalid=3582, Unknown=0, NotChecked=0, Total=4160 [2021-06-05 06:31:35,654 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3805 states. [2021-06-05 06:31:35,677 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3805 to 1424. [2021-06-05 06:31:35,679 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1424 states, 1423 states have (on average 2.1377371749824317) internal successors, (3042), 1423 states have internal predecessors, (3042), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:35,682 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1424 states to 1424 states and 3042 transitions. [2021-06-05 06:31:35,683 INFO L78 Accepts]: Start accepts. Automaton has 1424 states and 3042 transitions. Word has length 41 [2021-06-05 06:31:35,683 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:35,683 INFO L482 AbstractCegarLoop]: Abstraction has 1424 states and 3042 transitions. [2021-06-05 06:31:35,683 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 36 states, 36 states have (on average 2.0277777777777777) internal successors, (73), 35 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:35,683 INFO L276 IsEmpty]: Start isEmpty. Operand 1424 states and 3042 transitions. [2021-06-05 06:31:35,685 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-06-05 06:31:35,686 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:35,686 INFO L521 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:35,908 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable129 [2021-06-05 06:31:35,908 INFO L430 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:35,908 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:35,908 INFO L82 PathProgramCache]: Analyzing trace with hash 1195244540, now seen corresponding path program 14 times [2021-06-05 06:31:35,908 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:35,908 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [285972538] [2021-06-05 06:31:35,908 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:35,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:36,318 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:36,318 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:31:36,318 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [285972538] [2021-06-05 06:31:36,318 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [285972538] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:36,318 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [996313610] [2021-06-05 06:31:36,318 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:36,364 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-06-05 06:31:36,365 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:31:36,365 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 35 conjunts are in the unsatisfiable core [2021-06-05 06:31:36,366 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:31:37,008 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:37,009 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 42 treesize of output 52 [2021-06-05 06:31:37,015 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:37,061 INFO L628 ElimStorePlain]: treesize reduction 16, result has 84.3 percent of original size [2021-06-05 06:31:37,077 INFO L550 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-06-05 06:31:37,078 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 5 variables, input treesize:60, output treesize:65 [2021-06-05 06:31:37,251 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:37,252 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:37,253 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:37,254 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:37,255 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:37,255 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:37,256 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:37,256 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:37,258 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 3 disjoint index pairs (out of 10 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 13 [2021-06-05 06:31:37,259 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:37,265 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:37,267 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:31:37,267 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:46, output treesize:5 [2021-06-05 06:31:37,277 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:37,277 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [996313610] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:37,277 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:37,277 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 20] total 36 [2021-06-05 06:31:37,277 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1039815131] [2021-06-05 06:31:37,277 INFO L462 AbstractCegarLoop]: Interpolant automaton has 37 states [2021-06-05 06:31:37,277 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:37,278 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2021-06-05 06:31:37,278 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=1158, Unknown=0, NotChecked=0, Total=1332 [2021-06-05 06:31:37,278 INFO L87 Difference]: Start difference. First operand 1424 states and 3042 transitions. Second operand has 37 states, 37 states have (on average 1.972972972972973) internal successors, (73), 36 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:39,618 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:39,619 INFO L93 Difference]: Finished difference Result 4414 states and 9437 transitions. [2021-06-05 06:31:39,619 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2021-06-05 06:31:39,619 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 37 states have (on average 1.972972972972973) internal successors, (73), 36 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-06-05 06:31:39,619 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:39,628 INFO L225 Difference]: With dead ends: 4414 [2021-06-05 06:31:39,628 INFO L226 Difference]: Without dead ends: 4155 [2021-06-05 06:31:39,629 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 27 SyntacticMatches, 1 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1375 ImplicationChecksByTransitivity, 1918.4ms TimeCoverageRelationStatistics Valid=606, Invalid=3684, Unknown=0, NotChecked=0, Total=4290 [2021-06-05 06:31:39,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4155 states. [2021-06-05 06:31:39,663 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4155 to 1776. [2021-06-05 06:31:39,665 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1776 states, 1775 states have (on average 2.150985915492958) internal successors, (3818), 1775 states have internal predecessors, (3818), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:39,668 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1776 states to 1776 states and 3818 transitions. [2021-06-05 06:31:39,668 INFO L78 Accepts]: Start accepts. Automaton has 1776 states and 3818 transitions. Word has length 41 [2021-06-05 06:31:39,669 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:39,669 INFO L482 AbstractCegarLoop]: Abstraction has 1776 states and 3818 transitions. [2021-06-05 06:31:39,669 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 37 states, 37 states have (on average 1.972972972972973) internal successors, (73), 36 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:39,669 INFO L276 IsEmpty]: Start isEmpty. Operand 1776 states and 3818 transitions. [2021-06-05 06:31:39,672 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-06-05 06:31:39,672 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:39,672 INFO L521 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:39,894 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable136,15 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:39,895 INFO L430 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:39,895 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:39,895 INFO L82 PathProgramCache]: Analyzing trace with hash -920574034, now seen corresponding path program 15 times [2021-06-05 06:31:39,895 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:39,895 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2124976155] [2021-06-05 06:31:39,895 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:39,910 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:40,259 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:40,259 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:31:40,259 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2124976155] [2021-06-05 06:31:40,260 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2124976155] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:40,260 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1277191588] [2021-06-05 06:31:40,260 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:40,290 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2021-06-05 06:31:40,290 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:31:40,291 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 36 conjunts are in the unsatisfiable core [2021-06-05 06:31:40,291 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:31:40,803 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:40,803 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 40 treesize of output 50 [2021-06-05 06:31:40,809 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:40,849 INFO L628 ElimStorePlain]: treesize reduction 43, result has 60.2 percent of original size [2021-06-05 06:31:40,854 INFO L550 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-06-05 06:31:40,854 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 5 variables, input treesize:56, output treesize:37 [2021-06-05 06:31:41,196 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:41,197 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:41,198 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:41,201 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:41,202 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:41,229 INFO L354 Elim1Store]: treesize reduction 28, result has 45.1 percent of original size [2021-06-05 06:31:41,230 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 5 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 5 case distinctions, treesize of input 42 treesize of output 38 [2021-06-05 06:31:41,235 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:41,243 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:41,244 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:41,245 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:41,248 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:41,250 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:41,273 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:41,274 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 5 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 5 case distinctions, treesize of input 33 treesize of output 63 [2021-06-05 06:31:41,316 INFO L550 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 4 xjuncts. [2021-06-05 06:31:41,380 INFO L628 ElimStorePlain]: treesize reduction 43, result has 64.2 percent of original size [2021-06-05 06:31:41,406 INFO L550 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, End of recursive call: and 3 xjuncts. [2021-06-05 06:31:41,406 INFO L247 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:113, output treesize:36 [2021-06-05 06:31:41,535 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:41,536 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1277191588] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:41,536 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:41,536 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 21] total 39 [2021-06-05 06:31:41,536 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1087872553] [2021-06-05 06:31:41,536 INFO L462 AbstractCegarLoop]: Interpolant automaton has 40 states [2021-06-05 06:31:41,536 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:41,537 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2021-06-05 06:31:41,537 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=168, Invalid=1392, Unknown=0, NotChecked=0, Total=1560 [2021-06-05 06:31:41,537 INFO L87 Difference]: Start difference. First operand 1776 states and 3818 transitions. Second operand has 40 states, 40 states have (on average 1.9) internal successors, (76), 39 states have internal predecessors, (76), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:44,545 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:44,545 INFO L93 Difference]: Finished difference Result 3956 states and 8497 transitions. [2021-06-05 06:31:44,545 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2021-06-05 06:31:44,546 INFO L78 Accepts]: Start accepts. Automaton has has 40 states, 40 states have (on average 1.9) internal successors, (76), 39 states have internal predecessors, (76), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-06-05 06:31:44,546 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:44,552 INFO L225 Difference]: With dead ends: 3956 [2021-06-05 06:31:44,552 INFO L226 Difference]: Without dead ends: 3795 [2021-06-05 06:31:44,552 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1179 ImplicationChecksByTransitivity, 2591.0ms TimeCoverageRelationStatistics Valid=656, Invalid=3900, Unknown=0, NotChecked=0, Total=4556 [2021-06-05 06:31:44,556 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3795 states. [2021-06-05 06:31:44,581 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3795 to 1886. [2021-06-05 06:31:44,584 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1886 states, 1885 states have (on average 2.1527851458885943) internal successors, (4058), 1885 states have internal predecessors, (4058), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:44,588 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1886 states to 1886 states and 4058 transitions. [2021-06-05 06:31:44,588 INFO L78 Accepts]: Start accepts. Automaton has 1886 states and 4058 transitions. Word has length 41 [2021-06-05 06:31:44,588 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:44,588 INFO L482 AbstractCegarLoop]: Abstraction has 1886 states and 4058 transitions. [2021-06-05 06:31:44,588 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 40 states, 40 states have (on average 1.9) internal successors, (76), 39 states have internal predecessors, (76), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:44,588 INFO L276 IsEmpty]: Start isEmpty. Operand 1886 states and 4058 transitions. [2021-06-05 06:31:44,591 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2021-06-05 06:31:44,591 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:44,592 INFO L521 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:44,804 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable147 [2021-06-05 06:31:44,805 INFO L430 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:44,805 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:44,805 INFO L82 PathProgramCache]: Analyzing trace with hash -1060291469, now seen corresponding path program 16 times [2021-06-05 06:31:44,805 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:44,805 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1401510003] [2021-06-05 06:31:44,805 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:44,809 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:44,862 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 28 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:44,862 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:31:44,862 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1401510003] [2021-06-05 06:31:44,862 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1401510003] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:44,862 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [613879627] [2021-06-05 06:31:44,862 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:44,891 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-06-05 06:31:44,891 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:31:44,891 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 8 conjunts are in the unsatisfiable core [2021-06-05 06:31:44,892 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:31:44,956 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 28 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:44,956 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [613879627] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:44,956 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:44,956 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 5] total 10 [2021-06-05 06:31:44,956 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1639510977] [2021-06-05 06:31:44,956 INFO L462 AbstractCegarLoop]: Interpolant automaton has 11 states [2021-06-05 06:31:44,957 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:44,957 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-06-05 06:31:44,957 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=65, Unknown=0, NotChecked=0, Total=110 [2021-06-05 06:31:44,957 INFO L87 Difference]: Start difference. First operand 1886 states and 4058 transitions. Second operand has 11 states, 11 states have (on average 6.454545454545454) internal successors, (71), 10 states have internal predecessors, (71), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:45,051 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:45,051 INFO L93 Difference]: Finished difference Result 2387 states and 5133 transitions. [2021-06-05 06:31:45,051 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-06-05 06:31:45,052 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 6.454545454545454) internal successors, (71), 10 states have internal predecessors, (71), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 45 [2021-06-05 06:31:45,052 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:45,055 INFO L225 Difference]: With dead ends: 2387 [2021-06-05 06:31:45,056 INFO L226 Difference]: Without dead ends: 2337 [2021-06-05 06:31:45,056 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 56.1ms TimeCoverageRelationStatistics Valid=56, Invalid=76, Unknown=0, NotChecked=0, Total=132 [2021-06-05 06:31:45,058 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2337 states. [2021-06-05 06:31:45,078 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2337 to 2028. [2021-06-05 06:31:45,081 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2028 states, 2027 states have (on average 2.163295510606808) internal successors, (4385), 2027 states have internal predecessors, (4385), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:45,084 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2028 states to 2028 states and 4385 transitions. [2021-06-05 06:31:45,085 INFO L78 Accepts]: Start accepts. Automaton has 2028 states and 4385 transitions. Word has length 45 [2021-06-05 06:31:45,085 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:45,085 INFO L482 AbstractCegarLoop]: Abstraction has 2028 states and 4385 transitions. [2021-06-05 06:31:45,085 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 11 states, 11 states have (on average 6.454545454545454) internal successors, (71), 10 states have internal predecessors, (71), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:45,085 INFO L276 IsEmpty]: Start isEmpty. Operand 2028 states and 4385 transitions. [2021-06-05 06:31:45,088 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2021-06-05 06:31:45,088 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:45,088 INFO L521 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:45,300 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable189 [2021-06-05 06:31:45,301 INFO L430 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:45,301 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:45,301 INFO L82 PathProgramCache]: Analyzing trace with hash 1067334948, now seen corresponding path program 17 times [2021-06-05 06:31:45,301 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:45,301 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [799285609] [2021-06-05 06:31:45,301 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:45,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:45,327 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 15 proven. 18 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2021-06-05 06:31:45,328 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:31:45,328 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [799285609] [2021-06-05 06:31:45,328 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [799285609] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:45,328 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1190929155] [2021-06-05 06:31:45,328 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:45,357 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2021-06-05 06:31:45,357 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:31:45,357 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 9 conjunts are in the unsatisfiable core [2021-06-05 06:31:45,358 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:31:45,413 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 23 proven. 8 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2021-06-05 06:31:45,414 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1190929155] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:45,414 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:45,414 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4] total 5 [2021-06-05 06:31:45,414 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2065120932] [2021-06-05 06:31:45,414 INFO L462 AbstractCegarLoop]: Interpolant automaton has 6 states [2021-06-05 06:31:45,414 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:45,414 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-06-05 06:31:45,414 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2021-06-05 06:31:45,415 INFO L87 Difference]: Start difference. First operand 2028 states and 4385 transitions. Second operand has 6 states, 6 states have (on average 6.833333333333333) internal successors, (41), 5 states have internal predecessors, (41), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:45,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:45,434 INFO L93 Difference]: Finished difference Result 2477 states and 5328 transitions. [2021-06-05 06:31:45,435 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-06-05 06:31:45,435 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 6.833333333333333) internal successors, (41), 5 states have internal predecessors, (41), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 46 [2021-06-05 06:31:45,435 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:45,437 INFO L225 Difference]: With dead ends: 2477 [2021-06-05 06:31:45,438 INFO L226 Difference]: Without dead ends: 2477 [2021-06-05 06:31:45,438 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 50 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 11.5ms TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2021-06-05 06:31:45,440 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2477 states. [2021-06-05 06:31:45,460 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2477 to 1590. [2021-06-05 06:31:45,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1590 states, 1589 states have (on average 2.1648835745752044) internal successors, (3440), 1589 states have internal predecessors, (3440), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:45,465 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1590 states to 1590 states and 3440 transitions. [2021-06-05 06:31:45,465 INFO L78 Accepts]: Start accepts. Automaton has 1590 states and 3440 transitions. Word has length 46 [2021-06-05 06:31:45,465 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:45,465 INFO L482 AbstractCegarLoop]: Abstraction has 1590 states and 3440 transitions. [2021-06-05 06:31:45,465 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 6 states, 6 states have (on average 6.833333333333333) internal successors, (41), 5 states have internal predecessors, (41), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:45,465 INFO L276 IsEmpty]: Start isEmpty. Operand 1590 states and 3440 transitions. [2021-06-05 06:31:45,468 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2021-06-05 06:31:45,468 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:45,468 INFO L521 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:45,691 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable190 [2021-06-05 06:31:45,691 INFO L430 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:45,691 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:45,692 INFO L82 PathProgramCache]: Analyzing trace with hash 1691572838, now seen corresponding path program 18 times [2021-06-05 06:31:45,692 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:45,692 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1030815458] [2021-06-05 06:31:45,692 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:45,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:45,739 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 28 proven. 16 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2021-06-05 06:31:45,739 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:31:45,739 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1030815458] [2021-06-05 06:31:45,739 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1030815458] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:45,739 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [211663295] [2021-06-05 06:31:45,739 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:45,768 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2021-06-05 06:31:45,769 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:31:45,769 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 9 conjunts are in the unsatisfiable core [2021-06-05 06:31:45,770 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:31:45,825 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 37 proven. 6 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2021-06-05 06:31:45,825 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [211663295] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:45,825 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:45,825 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 6 [2021-06-05 06:31:45,825 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2135041381] [2021-06-05 06:31:45,825 INFO L462 AbstractCegarLoop]: Interpolant automaton has 7 states [2021-06-05 06:31:45,825 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:45,826 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-06-05 06:31:45,826 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2021-06-05 06:31:45,826 INFO L87 Difference]: Start difference. First operand 1590 states and 3440 transitions. Second operand has 7 states, 7 states have (on average 7.142857142857143) internal successors, (50), 6 states have internal predecessors, (50), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:45,856 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:45,856 INFO L93 Difference]: Finished difference Result 1749 states and 3746 transitions. [2021-06-05 06:31:45,856 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-06-05 06:31:45,856 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 7.142857142857143) internal successors, (50), 6 states have internal predecessors, (50), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 46 [2021-06-05 06:31:45,856 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:45,859 INFO L225 Difference]: With dead ends: 1749 [2021-06-05 06:31:45,859 INFO L226 Difference]: Without dead ends: 1749 [2021-06-05 06:31:45,859 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 15.7ms TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2021-06-05 06:31:45,861 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1749 states. [2021-06-05 06:31:45,875 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1749 to 1386. [2021-06-05 06:31:45,877 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1386 states, 1385 states have (on average 2.1494584837545125) internal successors, (2977), 1385 states have internal predecessors, (2977), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:45,880 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1386 states to 1386 states and 2977 transitions. [2021-06-05 06:31:45,880 INFO L78 Accepts]: Start accepts. Automaton has 1386 states and 2977 transitions. Word has length 46 [2021-06-05 06:31:45,880 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:45,880 INFO L482 AbstractCegarLoop]: Abstraction has 1386 states and 2977 transitions. [2021-06-05 06:31:45,880 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 7 states, 7 states have (on average 7.142857142857143) internal successors, (50), 6 states have internal predecessors, (50), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:45,880 INFO L276 IsEmpty]: Start isEmpty. Operand 1386 states and 2977 transitions. [2021-06-05 06:31:45,883 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2021-06-05 06:31:45,883 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:45,883 INFO L521 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:46,096 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable191 [2021-06-05 06:31:46,097 INFO L430 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:46,097 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:46,097 INFO L82 PathProgramCache]: Analyzing trace with hash -623804093, now seen corresponding path program 19 times [2021-06-05 06:31:46,097 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:46,097 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1529777393] [2021-06-05 06:31:46,097 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:46,109 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:46,700 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 0 proven. 62 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:46,700 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:31:46,700 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1529777393] [2021-06-05 06:31:46,700 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1529777393] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:46,700 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [331295133] [2021-06-05 06:31:46,700 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:46,732 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:46,733 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 47 conjunts are in the unsatisfiable core [2021-06-05 06:31:46,733 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:31:47,253 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:47,253 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 61 treesize of output 87 [2021-06-05 06:31:47,268 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:47,353 INFO L628 ElimStorePlain]: treesize reduction 69, result has 66.8 percent of original size [2021-06-05 06:31:47,371 INFO L550 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-06-05 06:31:47,371 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 6 variables, input treesize:72, output treesize:72 [2021-06-05 06:31:47,803 INFO L354 Elim1Store]: treesize reduction 66, result has 1.5 percent of original size [2021-06-05 06:31:47,803 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 44 treesize of output 16 [2021-06-05 06:31:47,804 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:47,807 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:47,807 INFO L550 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:31:47,807 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:45, output treesize:5 [2021-06-05 06:31:47,815 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 0 proven. 62 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:47,816 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [331295133] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:47,816 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:47,816 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 26] total 49 [2021-06-05 06:31:47,816 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [338310368] [2021-06-05 06:31:47,816 INFO L462 AbstractCegarLoop]: Interpolant automaton has 50 states [2021-06-05 06:31:47,816 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:47,817 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2021-06-05 06:31:47,817 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=289, Invalid=2161, Unknown=0, NotChecked=0, Total=2450 [2021-06-05 06:31:47,817 INFO L87 Difference]: Start difference. First operand 1386 states and 2977 transitions. Second operand has 50 states, 50 states have (on average 1.72) internal successors, (86), 49 states have internal predecessors, (86), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:51,349 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:51,349 INFO L93 Difference]: Finished difference Result 2993 states and 6367 transitions. [2021-06-05 06:31:51,350 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2021-06-05 06:31:51,350 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 50 states have (on average 1.72) internal successors, (86), 49 states have internal predecessors, (86), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 50 [2021-06-05 06:31:51,350 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:51,354 INFO L225 Difference]: With dead ends: 2993 [2021-06-05 06:31:51,354 INFO L226 Difference]: Without dead ends: 2897 [2021-06-05 06:31:51,355 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 29 SyntacticMatches, 2 SemanticMatches, 88 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2594 ImplicationChecksByTransitivity, 2552.2ms TimeCoverageRelationStatistics Valid=812, Invalid=7198, Unknown=0, NotChecked=0, Total=8010 [2021-06-05 06:31:51,358 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2897 states. [2021-06-05 06:31:51,377 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2897 to 1478. [2021-06-05 06:31:51,379 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1478 states, 1477 states have (on average 2.159106296547055) internal successors, (3189), 1477 states have internal predecessors, (3189), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:51,382 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1478 states to 1478 states and 3189 transitions. [2021-06-05 06:31:51,382 INFO L78 Accepts]: Start accepts. Automaton has 1478 states and 3189 transitions. Word has length 50 [2021-06-05 06:31:51,382 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:51,382 INFO L482 AbstractCegarLoop]: Abstraction has 1478 states and 3189 transitions. [2021-06-05 06:31:51,382 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 50 states, 50 states have (on average 1.72) internal successors, (86), 49 states have internal predecessors, (86), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:51,382 INFO L276 IsEmpty]: Start isEmpty. Operand 1478 states and 3189 transitions. [2021-06-05 06:31:51,384 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2021-06-05 06:31:51,384 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:51,385 INFO L521 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:51,608 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable192,20 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:51,609 INFO L430 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:51,609 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:51,609 INFO L82 PathProgramCache]: Analyzing trace with hash -231269501, now seen corresponding path program 20 times [2021-06-05 06:31:51,609 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:51,609 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1517837679] [2021-06-05 06:31:51,609 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:51,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:31:52,168 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 0 proven. 61 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-06-05 06:31:52,168 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:31:52,168 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1517837679] [2021-06-05 06:31:52,168 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1517837679] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:52,168 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1970395919] [2021-06-05 06:31:52,168 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:31:52,199 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-06-05 06:31:52,200 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:31:52,200 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 47 conjunts are in the unsatisfiable core [2021-06-05 06:31:52,201 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:31:53,339 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:53,339 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 58 treesize of output 86 [2021-06-05 06:31:53,345 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:53,426 INFO L628 ElimStorePlain]: treesize reduction 75, result has 66.5 percent of original size [2021-06-05 06:31:53,455 INFO L550 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-06-05 06:31:53,455 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 6 variables, input treesize:76, output treesize:76 [2021-06-05 06:31:53,915 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,916 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,916 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,917 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:53,918 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,918 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,919 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,920 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,920 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,921 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:53,924 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:53,927 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:53,929 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 6 disjoint index pairs (out of 15 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 16 [2021-06-05 06:31:53,930 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:53,933 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,933 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,934 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,935 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:53,935 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,936 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,936 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,937 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,938 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:31:53,942 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:31:53,944 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 6 disjoint index pairs (out of 15 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 57 treesize of output 19 [2021-06-05 06:31:53,946 INFO L550 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2021-06-05 06:31:53,951 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:31:53,952 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-06-05 06:31:53,952 INFO L247 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:126, output treesize:5 [2021-06-05 06:31:53,960 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 1 proven. 61 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:31:53,961 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1970395919] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:31:53,961 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:31:53,961 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 26] total 47 [2021-06-05 06:31:53,961 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [485216997] [2021-06-05 06:31:53,961 INFO L462 AbstractCegarLoop]: Interpolant automaton has 48 states [2021-06-05 06:31:53,961 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:31:53,961 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2021-06-05 06:31:53,962 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=244, Invalid=2012, Unknown=0, NotChecked=0, Total=2256 [2021-06-05 06:31:53,962 INFO L87 Difference]: Start difference. First operand 1478 states and 3189 transitions. Second operand has 48 states, 48 states have (on average 1.8958333333333333) internal successors, (91), 47 states have internal predecessors, (91), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:59,289 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-06-05 06:31:59,289 INFO L93 Difference]: Finished difference Result 3235 states and 6875 transitions. [2021-06-05 06:31:59,289 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 82 states. [2021-06-05 06:31:59,290 INFO L78 Accepts]: Start accepts. Automaton has has 48 states, 48 states have (on average 1.8958333333333333) internal successors, (91), 47 states have internal predecessors, (91), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 50 [2021-06-05 06:31:59,290 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-06-05 06:31:59,293 INFO L225 Difference]: With dead ends: 3235 [2021-06-05 06:31:59,293 INFO L226 Difference]: Without dead ends: 3122 [2021-06-05 06:31:59,294 INFO L777 BasicCegarLoop]: 0 DeclaredPredicates, 144 GetRequests, 25 SyntacticMatches, 8 SemanticMatches, 111 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4889 ImplicationChecksByTransitivity, 4296.0ms TimeCoverageRelationStatistics Valid=1351, Invalid=11305, Unknown=0, NotChecked=0, Total=12656 [2021-06-05 06:31:59,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3122 states. [2021-06-05 06:31:59,315 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3122 to 1551. [2021-06-05 06:31:59,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1551 states, 1550 states have (on average 2.1580645161290324) internal successors, (3345), 1550 states have internal predecessors, (3345), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:59,320 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1551 states to 1551 states and 3345 transitions. [2021-06-05 06:31:59,320 INFO L78 Accepts]: Start accepts. Automaton has 1551 states and 3345 transitions. Word has length 50 [2021-06-05 06:31:59,320 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-06-05 06:31:59,320 INFO L482 AbstractCegarLoop]: Abstraction has 1551 states and 3345 transitions. [2021-06-05 06:31:59,320 INFO L483 AbstractCegarLoop]: Interpolant automaton has has 48 states, 48 states have (on average 1.8958333333333333) internal successors, (91), 47 states have internal predecessors, (91), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:31:59,320 INFO L276 IsEmpty]: Start isEmpty. Operand 1551 states and 3345 transitions. [2021-06-05 06:31:59,322 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2021-06-05 06:31:59,323 INFO L513 BasicCegarLoop]: Found error trace [2021-06-05 06:31:59,323 INFO L521 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-06-05 06:31:59,546 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable205 [2021-06-05 06:31:59,546 INFO L430 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-06-05 06:31:59,546 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-06-05 06:31:59,546 INFO L82 PathProgramCache]: Analyzing trace with hash 1024877813, now seen corresponding path program 21 times [2021-06-05 06:31:59,546 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-06-05 06:31:59,546 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1323576728] [2021-06-05 06:31:59,546 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-06-05 06:31:59,552 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-06-05 06:32:00,047 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 0 proven. 62 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:32:00,047 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-06-05 06:32:00,047 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1323576728] [2021-06-05 06:32:00,047 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1323576728] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:32:00,047 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1486399363] [2021-06-05 06:32:00,047 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:32:00,078 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2021-06-05 06:32:00,079 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-06-05 06:32:00,079 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 44 conjunts are in the unsatisfiable core [2021-06-05 06:32:00,080 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-06-05 06:32:02,306 WARN L205 SmtUtils]: Spent 311.00 ms on a formula simplification that was a NOOP. DAG size: 48 [2021-06-05 06:32:02,443 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:32:02,443 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 54 treesize of output 82 [2021-06-05 06:32:02,451 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:32:02,479 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:32:02,480 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 54 treesize of output 82 [2021-06-05 06:32:02,486 INFO L550 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2021-06-05 06:32:02,688 WARN L205 SmtUtils]: Spent 200.00 ms on a formula simplification. DAG size of input: 124 DAG size of output: 98 [2021-06-05 06:32:02,688 INFO L628 ElimStorePlain]: treesize reduction 149, result has 64.4 percent of original size [2021-06-05 06:32:02,751 INFO L550 ElimStorePlain]: Start of recursive call 1: 14 dim-0 vars, 1 dim-1 vars, End of recursive call: 8 dim-0 vars, and 2 xjuncts. [2021-06-05 06:32:02,751 INFO L247 ElimStorePlain]: Needed 3 recursive calls to eliminate 15 variables, input treesize:163, output treesize:133 [2021-06-05 06:32:12,628 WARN L205 SmtUtils]: Spent 7.04 s on a formula simplification that was a NOOP. DAG size: 63 [2021-06-05 06:32:43,383 WARN L205 SmtUtils]: Spent 10.86 s on a formula simplification. DAG size of input: 64 DAG size of output: 59 [2021-06-05 06:32:43,601 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:32:43,603 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:32:43,606 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:32:43,611 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:32:43,617 INFO L173 IndexEqualityManager]: detected equality via solver [2021-06-05 06:32:43,746 WARN L205 SmtUtils]: Spent 119.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 54 [2021-06-05 06:32:43,747 INFO L354 Elim1Store]: treesize reduction 16, result has 85.8 percent of original size [2021-06-05 06:32:43,747 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 7 select indices, 7 select index equivalence classes, 3 disjoint index pairs (out of 21 index pairs), introduced 6 new quantified variables, introduced 16 case distinctions, treesize of input 45 treesize of output 115 [2021-06-05 06:32:44,012 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-06-05 06:32:44,023 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:32:44,026 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:32:44,027 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-06-05 06:32:44,109 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-06-05 06:32:44,109 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 3 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 12 case distinctions, treesize of input 38 treesize of output 128 [2021-06-05 06:32:44,776 WARN L205 SmtUtils]: Spent 118.00 ms on a formula simplification. DAG size of input: 304 DAG size of output: 270 [2021-06-05 06:32:44,884 WARN L205 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 304 DAG size of output: 270 [2021-06-05 06:32:45,017 WARN L205 SmtUtils]: Spent 129.00 ms on a formula simplification. DAG size of input: 311 DAG size of output: 277 [2021-06-05 06:32:45,806 INFO L550 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 4 xjuncts. [2021-06-05 06:32:46,060 WARN L205 SmtUtils]: Spent 253.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 72 [2021-06-05 06:32:46,061 INFO L628 ElimStorePlain]: treesize reduction 656, result has 19.0 percent of original size [2021-06-05 06:32:46,087 INFO L550 ElimStorePlain]: Start of recursive call 1: 9 dim-0 vars, 1 dim-1 vars, End of recursive call: and 4 xjuncts. [2021-06-05 06:32:46,087 INFO L247 ElimStorePlain]: Needed 3 recursive calls to eliminate 10 variables, input treesize:133, output treesize:37 [2021-06-05 06:32:46,226 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 3 proven. 59 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-06-05 06:32:46,227 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1486399363] provided 0 perfect and 1 imperfect interpolant sequences [2021-06-05 06:32:46,227 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-06-05 06:32:46,227 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 27] total 50 [2021-06-05 06:32:46,227 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1745265293] [2021-06-05 06:32:46,227 INFO L462 AbstractCegarLoop]: Interpolant automaton has 51 states [2021-06-05 06:32:46,227 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-06-05 06:32:46,227 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2021-06-05 06:32:46,228 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=279, Invalid=2266, Unknown=5, NotChecked=0, Total=2550 [2021-06-05 06:32:46,229 INFO L87 Difference]: Start difference. First operand 1551 states and 3345 transitions. Second operand has 51 states, 51 states have (on average 1.8431372549019607) internal successors, (94), 50 states have internal predecessors, (94), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-06-05 06:33:03,420 WARN L205 SmtUtils]: Spent 199.00 ms on a formula simplification. DAG size of input: 133 DAG size of output: 40 [2021-06-05 06:33:11,809 WARN L205 SmtUtils]: Spent 1.58 s on a formula simplification. DAG size of input: 138 DAG size of output: 42 [2021-06-05 06:33:27,753 WARN L205 SmtUtils]: Spent 7.32 s on a formula simplification. DAG size of input: 107 DAG size of output: 68 [2021-06-05 06:33:47,396 WARN L205 SmtUtils]: Spent 8.51 s on a formula simplification. DAG size of input: 87 DAG size of output: 61 [2021-06-05 06:34:00,713 WARN L205 SmtUtils]: Spent 7.63 s on a formula simplification. DAG size of input: 85 DAG size of output: 57 [2021-06-05 06:34:08,610 WARN L205 SmtUtils]: Spent 2.42 s on a formula simplification. DAG size of input: 130 DAG size of output: 51 [2021-06-05 06:34:26,775 WARN L205 SmtUtils]: Spent 12.75 s on a formula simplification. DAG size of input: 122 DAG size of output: 70 [2021-06-05 06:34:30,959 WARN L205 SmtUtils]: Spent 2.33 s on a formula simplification. DAG size of input: 120 DAG size of output: 46 [2021-06-05 06:34:43,456 WARN L205 SmtUtils]: Spent 8.46 s on a formula simplification. DAG size of input: 83 DAG size of output: 57 [2021-06-05 06:34:55,467 WARN L205 SmtUtils]: Spent 283.00 ms on a formula simplification. DAG size of input: 124 DAG size of output: 54 [2021-06-05 06:35:15,779 WARN L205 SmtUtils]: Spent 14.51 s on a formula simplification. DAG size of input: 122 DAG size of output: 72 [2021-06-05 06:35:24,983 WARN L205 SmtUtils]: Spent 392.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 52 [2021-06-05 06:35:29,830 WARN L205 SmtUtils]: Spent 146.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 49 [2021-06-05 06:35:44,450 WARN L205 SmtUtils]: Spent 11.20 s on a formula simplification. DAG size of input: 89 DAG size of output: 50 [2021-06-05 06:36:07,175 WARN L205 SmtUtils]: Spent 14.30 s on a formula simplification. DAG size of input: 119 DAG size of output: 70 [2021-06-05 06:36:19,197 WARN L205 SmtUtils]: Spent 8.42 s on a formula simplification. DAG size of input: 90 DAG size of output: 64 [2021-06-05 06:36:27,007 WARN L205 SmtUtils]: Spent 3.29 s on a formula simplification. DAG size of input: 102 DAG size of output: 68 [2021-06-05 06:36:46,923 WARN L205 SmtUtils]: Spent 10.63 s on a formula simplification. DAG size of input: 121 DAG size of output: 48 [2021-06-05 06:36:56,367 WARN L205 SmtUtils]: Spent 2.63 s on a formula simplification. DAG size of input: 127 DAG size of output: 51 [2021-06-05 06:37:10,307 WARN L205 SmtUtils]: Spent 4.15 s on a formula simplification. DAG size of input: 123 DAG size of output: 69 [2021-06-05 06:37:21,552 WARN L205 SmtUtils]: Spent 2.78 s on a formula simplification. DAG size of input: 97 DAG size of output: 51 [2021-06-05 06:37:33,566 WARN L205 SmtUtils]: Spent 2.16 s on a formula simplification. DAG size of input: 137 DAG size of output: 52 [2021-06-05 06:37:43,291 WARN L205 SmtUtils]: Spent 229.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 55 [2021-06-05 06:38:05,133 WARN L205 SmtUtils]: Spent 12.90 s on a formula simplification. DAG size of input: 125 DAG size of output: 57 [2021-06-05 06:38:30,212 WARN L205 SmtUtils]: Spent 13.74 s on a formula simplification. DAG size of input: 106 DAG size of output: 60 [2021-06-05 06:38:36,601 WARN L205 SmtUtils]: Spent 5.46 s on a formula simplification. DAG size of input: 142 DAG size of output: 59 [2021-06-05 06:38:48,274 WARN L205 SmtUtils]: Spent 2.49 s on a formula simplification. DAG size of input: 126 DAG size of output: 51 [2021-06-05 06:39:09,089 WARN L205 SmtUtils]: Spent 12.46 s on a formula simplification. DAG size of input: 115 DAG size of output: 68 [2021-06-05 06:39:33,726 WARN L205 SmtUtils]: Spent 13.15 s on a formula simplification. DAG size of input: 130 DAG size of output: 69 [2021-06-05 06:39:36,896 WARN L205 SmtUtils]: Spent 645.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 64 [2021-06-05 06:39:49,457 WARN L205 SmtUtils]: Spent 6.68 s on a formula simplification. DAG size of input: 89 DAG size of output: 63 [2021-06-05 06:40:15,402 WARN L205 SmtUtils]: Spent 2.72 s on a formula simplification. DAG size of input: 136 DAG size of output: 52 [2021-06-05 06:40:45,393 WARN L205 SmtUtils]: Spent 13.14 s on a formula simplification. DAG size of input: 113 DAG size of output: 64 [2021-06-05 06:40:57,163 WARN L205 SmtUtils]: Spent 6.51 s on a formula simplification. DAG size of input: 88 DAG size of output: 60 [2021-06-05 06:41:04,152 WARN L205 SmtUtils]: Spent 675.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 59 [2021-06-05 06:41:15,196 WARN L205 SmtUtils]: Spent 6.14 s on a formula simplification. DAG size of input: 78 DAG size of output: 40 [2021-06-05 06:41:57,966 WARN L205 SmtUtils]: Spent 3.54 s on a formula simplification. DAG size of input: 141 DAG size of output: 59 [2021-06-05 06:42:17,729 WARN L205 SmtUtils]: Spent 12.45 s on a formula simplification. DAG size of input: 99 DAG size of output: 64 [2021-06-05 06:42:35,034 WARN L205 SmtUtils]: Spent 9.80 s on a formula simplification. DAG size of input: 86 DAG size of output: 60 [2021-06-05 06:42:48,057 WARN L205 SmtUtils]: Spent 7.67 s on a formula simplification. DAG size of input: 85 DAG size of output: 59 [2021-06-05 06:43:08,536 WARN L205 SmtUtils]: Spent 5.33 s on a formula simplification. DAG size of input: 116 DAG size of output: 64 [2021-06-05 06:43:31,158 WARN L205 SmtUtils]: Spent 12.91 s on a formula simplification. DAG size of input: 101 DAG size of output: 66 [2021-06-05 06:44:01,403 WARN L205 SmtUtils]: Spent 13.27 s on a formula simplification. DAG size of input: 113 DAG size of output: 71 [2021-06-05 06:44:35,722 WARN L205 SmtUtils]: Spent 7.27 s on a formula simplification. DAG size of input: 118 DAG size of output: 66 [2021-06-05 06:44:50,581 WARN L205 SmtUtils]: Spent 5.07 s on a formula simplification. DAG size of input: 93 DAG size of output: 67 [2021-06-05 06:45:06,557 WARN L205 SmtUtils]: Spent 6.60 s on a formula simplification. DAG size of input: 92 DAG size of output: 66 Received shutdown request... [2021-06-05 06:45:18,362 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 115 states. [2021-06-05 06:45:18,562 WARN L519 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable229,22 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-06-05 06:45:18,562 WARN L547 AbstractCegarLoop]: Verification canceled [2021-06-05 06:45:18,564 INFO L246 ceAbstractionStarter]: Analysis of concurrent program completed with 1 thread instances [2021-06-05 06:45:18,565 WARN L196 ceAbstractionStarter]: Timeout [2021-06-05 06:45:18,565 INFO L202 PluginConnector]: Adding new model inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 05.06 06:45:18 BasicIcfg [2021-06-05 06:45:18,565 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2021-06-05 06:45:18,566 INFO L168 Benchmark]: Toolchain (without parser) took 869614.17 ms. Allocated memory was 377.5 MB in the beginning and 608.2 MB in the end (delta: 230.7 MB). Free memory was 357.6 MB in the beginning and 431.8 MB in the end (delta: -74.2 MB). Peak memory consumption was 159.9 MB. Max. memory is 16.0 GB. [2021-06-05 06:45:18,566 INFO L168 Benchmark]: Boogie PL CUP Parser took 0.15 ms. Allocated memory is still 377.5 MB. Free memory was 358.8 MB in the beginning and 358.8 MB in the end (delta: 65.7 kB). There was no memory consumed. Max. memory is 16.0 GB. [2021-06-05 06:45:18,566 INFO L168 Benchmark]: Boogie Procedure Inliner took 25.21 ms. Allocated memory is still 377.5 MB. Free memory was 357.6 MB in the beginning and 356.1 MB in the end (delta: 1.5 MB). Peak memory consumption was 2.1 MB. Max. memory is 16.0 GB. [2021-06-05 06:45:18,566 INFO L168 Benchmark]: Boogie Preprocessor took 17.71 ms. Allocated memory is still 377.5 MB. Free memory was 356.1 MB in the beginning and 355.2 MB in the end (delta: 964.8 kB). Peak memory consumption was 2.1 MB. Max. memory is 16.0 GB. [2021-06-05 06:45:18,566 INFO L168 Benchmark]: RCFGBuilder took 305.42 ms. Allocated memory is still 377.5 MB. Free memory was 355.1 MB in the beginning and 342.3 MB in the end (delta: 12.8 MB). Peak memory consumption was 12.6 MB. Max. memory is 16.0 GB. [2021-06-05 06:45:18,566 INFO L168 Benchmark]: TraceAbstraction took 869247.86 ms. Allocated memory was 377.5 MB in the beginning and 608.2 MB in the end (delta: 230.7 MB). Free memory was 341.9 MB in the beginning and 431.8 MB in the end (delta: -89.9 MB). Peak memory consumption was 143.2 MB. Max. memory is 16.0 GB. [2021-06-05 06:45:18,566 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * Boogie PL CUP Parser took 0.15 ms. Allocated memory is still 377.5 MB. Free memory was 358.8 MB in the beginning and 358.8 MB in the end (delta: 65.7 kB). There was no memory consumed. Max. memory is 16.0 GB. * Boogie Procedure Inliner took 25.21 ms. Allocated memory is still 377.5 MB. Free memory was 357.6 MB in the beginning and 356.1 MB in the end (delta: 1.5 MB). Peak memory consumption was 2.1 MB. Max. memory is 16.0 GB. * Boogie Preprocessor took 17.71 ms. Allocated memory is still 377.5 MB. Free memory was 356.1 MB in the beginning and 355.2 MB in the end (delta: 964.8 kB). Peak memory consumption was 2.1 MB. Max. memory is 16.0 GB. * RCFGBuilder took 305.42 ms. Allocated memory is still 377.5 MB. Free memory was 355.1 MB in the beginning and 342.3 MB in the end (delta: 12.8 MB). Peak memory consumption was 12.6 MB. Max. memory is 16.0 GB. * TraceAbstraction took 869247.86 ms. Allocated memory was 377.5 MB in the beginning and 608.2 MB in the end (delta: 230.7 MB). Free memory was 341.9 MB in the beginning and 431.8 MB in the end (delta: -89.9 MB). Peak memory consumption was 143.2 MB. Max. memory is 16.0 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 57]: Timeout (TraceAbstraction) Unable to prove that petrification did provide enough thread instances (tool internal message, not intended for end users) Cancelled while BasicCegarLoop was constructing difference of abstraction (1551states) and FLOYD_HOARE automaton (currently 115 states, 51 states before enhancement),while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 153 known predicates. - TimeoutResultAtElement [Line: 57]: Timeout (TraceAbstraction) Unable to prove that petrification did provide enough thread instances (tool internal message, not intended for end users) Cancelled while BasicCegarLoop was constructing difference of abstraction (1551states) and FLOYD_HOARE automaton (currently 115 states, 51 states before enhancement),while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 153 known predicates. - TimeoutResultAtElement [Line: 62]: Timeout (TraceAbstraction) Unable to prove that assertion always holds Cancelled while BasicCegarLoop was constructing difference of abstraction (1551states) and FLOYD_HOARE automaton (currently 115 states, 51 states before enhancement),while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 153 known predicates. - StatisticsResult: Ultimate Automizer benchmark data with 1 thread instances CFG has 5 procedures, 41 locations, 3 error locations. Started 1 CEGAR loops. VerificationResult: TIMEOUT, OverallTime: 869135.4ms, OverallIterations: 23, TraceHistogramMax: 4, EmptinessCheckTime: 53.1ms, AutomataDifference: 797798.5ms, DeadEndRemovalTime: 0.0ms, HoareAnnotationTime: 0.0ms, InitialAbstractionConstructionTime: 19.2ms, PartialOrderReductionTime: 0.0ms, HoareTripleCheckerStatistics: 1085 SDtfs, 4976 SDslu, 11746 SDs, 0 SdLazy, 29186 SolverSat, 3233 SolverUnsat, 4 SolverUnknown, 0 SolverNotchecked, 79433.1ms Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1846 GetRequests, 588 SyntacticMatches, 37 SemanticMatches, 1220 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41096 ImplicationChecksByTransitivity, 761822.9ms Time, 0.0ms BasicInterpolantAutomatonTime, BiggestAbstraction: size=2028occurred in iteration=18, InterpolantAutomatonStates: 787, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0ms DumpTime, AutomataMinimizationStatistics: 502.2ms AutomataMinimizationTime, 22 MinimizatonAttempts, 20540 StatesRemovedByMinimization, 21 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 114.7ms SsaConstructionTime, 451.6ms SatisfiabilityAnalysisTime, 65028.6ms InterpolantComputationTime, 1672 NumberOfCodeBlocks, 1672 NumberOfCodeBlocksAsserted, 78 NumberOfCheckSat, 1628 ConstructedInterpolants, 268 QuantifiedInterpolants, 27388 SizeOfPredicates, 223 NumberOfNonLiveVariables, 1741 ConjunctsInSsa, 544 ConjunctsInUnsatCore, 44 InterpolantComputations, 2 PerfectInterpolantSequences, 260/1315 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown