java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/llreve-bench/smt2/rec__triangular.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 12:18:42,622 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 12:18:42,624 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 12:18:42,636 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 12:18:42,636 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 12:18:42,637 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 12:18:42,638 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 12:18:42,639 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 12:18:42,641 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 12:18:42,642 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 12:18:42,643 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 12:18:42,643 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 12:18:42,644 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 12:18:42,645 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 12:18:42,646 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 12:18:42,646 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 12:18:42,652 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 12:18:42,660 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 12:18:42,662 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 12:18:42,663 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 12:18:42,664 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 12:18:42,666 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 12:18:42,667 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 12:18:42,667 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 12:18:42,668 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 12:18:42,677 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 12:18:42,678 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 12:18:42,679 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 12:18:42,680 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 12:18:42,680 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 12:18:42,681 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 12:18:42,681 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 12:18:42,682 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 12:18:42,682 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 12:18:42,683 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 12:18:42,683 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 12:18:42,709 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 12:18:42,709 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 12:18:42,710 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 12:18:42,710 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 12:18:42,712 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 12:18:42,712 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 12:18:42,712 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 12:18:42,713 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 12:18:42,713 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 12:18:42,713 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 12:18:42,713 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 12:18:42,713 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 12:18:42,713 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 12:18:42,714 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 12:18:42,714 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 12:18:42,714 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 12:18:42,714 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 12:18:42,714 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 12:18:42,715 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 12:18:42,716 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 12:18:42,717 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 12:18:42,771 INFO ]: Repository-Root is: /tmp [2018-06-22 12:18:42,786 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 12:18:42,789 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 12:18:42,791 INFO ]: Initializing SmtParser... [2018-06-22 12:18:42,791 INFO ]: SmtParser initialized [2018-06-22 12:18:42,792 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/llreve-bench/smt2/rec__triangular.smt2 [2018-06-22 12:18:42,793 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 12:18:42,864 INFO ]: Executing SMT file /storage/chc-comp/llreve-bench/smt2/rec__triangular.smt2 unknown de.uni_freiburg.informatik.ultimate.plugins.generator.treeautomizer.parsing.HornClauseParserScript$1@1d849b9d [2018-06-22 12:18:43,098 INFO ]: Succesfully executed SMT file /storage/chc-comp/llreve-bench/smt2/rec__triangular.smt2 [2018-06-22 12:18:43,103 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 12:18:43,109 INFO ]: Walking toolchain with 4 elements. [2018-06-22 12:18:43,109 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 12:18:43,109 INFO ]: Initializing ChcToBoogie... [2018-06-22 12:18:43,110 INFO ]: ChcToBoogie initialized [2018-06-22 12:18:43,112 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 12:18:43" (1/1) ... [2018-06-22 12:18:43,159 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:18:43 Unit [2018-06-22 12:18:43,159 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 12:18:43,160 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 12:18:43,160 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 12:18:43,160 INFO ]: Boogie Preprocessor initialized [2018-06-22 12:18:43,181 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:18:43" (1/1) ... [2018-06-22 12:18:43,181 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:18:43" (1/1) ... [2018-06-22 12:18:43,189 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:18:43" (1/1) ... [2018-06-22 12:18:43,189 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:18:43" (1/1) ... [2018-06-22 12:18:43,193 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:18:43" (1/1) ... [2018-06-22 12:18:43,196 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:18:43" (1/1) ... [2018-06-22 12:18:43,197 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:18:43" (1/1) ... [2018-06-22 12:18:43,200 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 12:18:43,201 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 12:18:43,201 INFO ]: Initializing RCFGBuilder... [2018-06-22 12:18:43,201 INFO ]: RCFGBuilder initialized [2018-06-22 12:18:43,202 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:18:43" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 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 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 12:18:43,217 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 12:18:43,217 INFO ]: Found specification of procedure False [2018-06-22 12:18:43,217 INFO ]: Found implementation of procedure False [2018-06-22 12:18:43,217 INFO ]: Specification and implementation of procedure INV_REC_g^g given in one single declaration [2018-06-22 12:18:43,217 INFO ]: Found specification of procedure INV_REC_g^g [2018-06-22 12:18:43,217 INFO ]: Found implementation of procedure INV_REC_g^g [2018-06-22 12:18:43,217 INFO ]: Specification and implementation of procedure INV_REC_g__1 given in one single declaration [2018-06-22 12:18:43,217 INFO ]: Found specification of procedure INV_REC_g__1 [2018-06-22 12:18:43,217 INFO ]: Found implementation of procedure INV_REC_g__1 [2018-06-22 12:18:43,217 INFO ]: Specification and implementation of procedure INV_REC_g__1_PRE given in one single declaration [2018-06-22 12:18:43,217 INFO ]: Found specification of procedure INV_REC_g__1_PRE [2018-06-22 12:18:43,217 INFO ]: Found implementation of procedure INV_REC_g__1_PRE [2018-06-22 12:18:43,217 INFO ]: Specification and implementation of procedure INV_REC_g__2 given in one single declaration [2018-06-22 12:18:43,217 INFO ]: Found specification of procedure INV_REC_g__2 [2018-06-22 12:18:43,217 INFO ]: Found implementation of procedure INV_REC_g__2 [2018-06-22 12:18:43,217 INFO ]: Specification and implementation of procedure INV_REC_g__2_PRE given in one single declaration [2018-06-22 12:18:43,217 INFO ]: Found specification of procedure INV_REC_g__2_PRE [2018-06-22 12:18:43,217 INFO ]: Found implementation of procedure INV_REC_g__2_PRE [2018-06-22 12:18:43,217 INFO ]: Specification and implementation of procedure INV_REC_g^g_PRE given in one single declaration [2018-06-22 12:18:43,217 INFO ]: Found specification of procedure INV_REC_g^g_PRE [2018-06-22 12:18:43,217 INFO ]: Found implementation of procedure INV_REC_g^g_PRE [2018-06-22 12:18:43,218 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 12:18:43,218 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 12:18:43,218 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 12:18:43,561 INFO ]: Using library mode [2018-06-22 12:18:43,562 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 12:18:43 BoogieIcfgContainer [2018-06-22 12:18:43,562 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 12:18:43,563 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 12:18:43,563 INFO ]: Initializing TraceAbstraction... [2018-06-22 12:18:43,566 INFO ]: TraceAbstraction initialized [2018-06-22 12:18:43,566 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 12:18:43" (1/3) ... [2018-06-22 12:18:43,567 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c01deb7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 12:18:43, skipping insertion in model container [2018-06-22 12:18:43,567 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:18:43" (2/3) ... [2018-06-22 12:18:43,568 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c01deb7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 12:18:43, skipping insertion in model container [2018-06-22 12:18:43,568 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 12:18:43" (3/3) ... [2018-06-22 12:18:43,569 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 12:18:43,578 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 12:18:43,587 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 12:18:43,636 INFO ]: Using default assertion order modulation [2018-06-22 12:18:43,636 INFO ]: Interprodecural is true [2018-06-22 12:18:43,636 INFO ]: Hoare is false [2018-06-22 12:18:43,636 INFO ]: Compute interpolants for FPandBP [2018-06-22 12:18:43,636 INFO ]: Backedges is TWOTRACK [2018-06-22 12:18:43,636 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 12:18:43,637 INFO ]: Difference is false [2018-06-22 12:18:43,637 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 12:18:43,637 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 12:18:43,657 INFO ]: Start isEmpty. Operand 45 states. [2018-06-22 12:18:43,681 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 12:18:43,681 INFO ]: Found error trace [2018-06-22 12:18:43,682 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:18:43,682 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:18:43,690 INFO ]: Analyzing trace with hash 591892167, now seen corresponding path program 1 times [2018-06-22 12:18:43,691 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:18:43,691 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:18:43,727 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:43,727 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:18:43,727 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:43,761 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:43,881 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 12:18:43,882 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 12:18:43,882 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-06-22 12:18:43,884 INFO ]: Interpolant automaton has 6 states [2018-06-22 12:18:43,893 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 12:18:43,894 INFO ]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-06-22 12:18:43,895 INFO ]: Start difference. First operand 45 states. Second operand 6 states. [2018-06-22 12:18:44,347 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:18:44,347 INFO ]: Finished difference Result 49 states and 75 transitions. [2018-06-22 12:18:44,348 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 12:18:44,349 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-22 12:18:44,349 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:18:44,359 INFO ]: With dead ends: 49 [2018-06-22 12:18:44,359 INFO ]: Without dead ends: 49 [2018-06-22 12:18:44,365 INFO ]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2018-06-22 12:18:44,378 INFO ]: Start minimizeSevpa. Operand 49 states. [2018-06-22 12:18:44,414 INFO ]: Finished minimizeSevpa. Reduced states from 49 to 45. [2018-06-22 12:18:44,418 INFO ]: Start removeUnreachable. Operand 45 states. [2018-06-22 12:18:44,421 INFO ]: Finished removeUnreachable. Reduced from 45 states to 45 states and 65 transitions. [2018-06-22 12:18:44,424 INFO ]: Start accepts. Automaton has 45 states and 65 transitions. Word has length 13 [2018-06-22 12:18:44,425 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:18:44,425 INFO ]: Abstraction has 45 states and 65 transitions. [2018-06-22 12:18:44,425 INFO ]: Interpolant automaton has 6 states. [2018-06-22 12:18:44,425 INFO ]: Start isEmpty. Operand 45 states and 65 transitions. [2018-06-22 12:18:44,429 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 12:18:44,429 INFO ]: Found error trace [2018-06-22 12:18:44,429 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:18:44,429 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:18:44,429 INFO ]: Analyzing trace with hash 393697710, now seen corresponding path program 1 times [2018-06-22 12:18:44,429 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:18:44,429 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:18:44,430 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:44,430 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:18:44,430 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:44,450 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:44,542 INFO ]: Checked inductivity of 6 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 12:18:44,542 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:18:44,542 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:18:44,552 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:18:44,571 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:44,578 INFO ]: Computing forward predicates... [2018-06-22 12:18:44,938 INFO ]: Checked inductivity of 6 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 12:18:44,959 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 12:18:44,960 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 8 [2018-06-22 12:18:44,960 INFO ]: Interpolant automaton has 8 states [2018-06-22 12:18:44,960 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 12:18:44,960 INFO ]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2018-06-22 12:18:44,961 INFO ]: Start difference. First operand 45 states and 65 transitions. Second operand 8 states. [2018-06-22 12:18:45,563 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:18:45,563 INFO ]: Finished difference Result 67 states and 109 transitions. [2018-06-22 12:18:45,563 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 12:18:45,564 INFO ]: Start accepts. Automaton has 8 states. Word has length 21 [2018-06-22 12:18:45,564 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:18:45,567 INFO ]: With dead ends: 67 [2018-06-22 12:18:45,567 INFO ]: Without dead ends: 62 [2018-06-22 12:18:45,567 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 19 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-06-22 12:18:45,568 INFO ]: Start minimizeSevpa. Operand 62 states. [2018-06-22 12:18:45,580 INFO ]: Finished minimizeSevpa. Reduced states from 62 to 56. [2018-06-22 12:18:45,580 INFO ]: Start removeUnreachable. Operand 56 states. [2018-06-22 12:18:45,582 INFO ]: Finished removeUnreachable. Reduced from 56 states to 56 states and 88 transitions. [2018-06-22 12:18:45,582 INFO ]: Start accepts. Automaton has 56 states and 88 transitions. Word has length 21 [2018-06-22 12:18:45,582 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:18:45,582 INFO ]: Abstraction has 56 states and 88 transitions. [2018-06-22 12:18:45,582 INFO ]: Interpolant automaton has 8 states. [2018-06-22 12:18:45,582 INFO ]: Start isEmpty. Operand 56 states and 88 transitions. [2018-06-22 12:18:45,585 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 12:18:45,585 INFO ]: Found error trace [2018-06-22 12:18:45,585 INFO ]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:18:45,585 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:18:45,585 INFO ]: Analyzing trace with hash 81341968, now seen corresponding path program 1 times [2018-06-22 12:18:45,585 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:18:45,585 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:18:45,586 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:45,586 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:18:45,586 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:45,601 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:45,889 INFO ]: Checked inductivity of 12 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 12:18:45,889 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:18:45,889 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:18:45,901 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:18:45,927 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:45,930 INFO ]: Computing forward predicates... [2018-06-22 12:18:46,035 INFO ]: Checked inductivity of 12 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 12:18:46,059 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:18:46,059 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 12:18:46,059 INFO ]: Interpolant automaton has 8 states [2018-06-22 12:18:46,060 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 12:18:46,060 INFO ]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-06-22 12:18:46,060 INFO ]: Start difference. First operand 56 states and 88 transitions. Second operand 8 states. [2018-06-22 12:18:46,315 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:18:46,316 INFO ]: Finished difference Result 70 states and 103 transitions. [2018-06-22 12:18:46,316 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 12:18:46,316 INFO ]: Start accepts. Automaton has 8 states. Word has length 25 [2018-06-22 12:18:46,316 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:18:46,319 INFO ]: With dead ends: 70 [2018-06-22 12:18:46,319 INFO ]: Without dead ends: 60 [2018-06-22 12:18:46,320 INFO ]: 0 DeclaredPredicates, 33 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=36, Invalid=74, Unknown=0, NotChecked=0, Total=110 [2018-06-22 12:18:46,320 INFO ]: Start minimizeSevpa. Operand 60 states. [2018-06-22 12:18:46,331 INFO ]: Finished minimizeSevpa. Reduced states from 60 to 56. [2018-06-22 12:18:46,331 INFO ]: Start removeUnreachable. Operand 56 states. [2018-06-22 12:18:46,333 INFO ]: Finished removeUnreachable. Reduced from 56 states to 56 states and 82 transitions. [2018-06-22 12:18:46,333 INFO ]: Start accepts. Automaton has 56 states and 82 transitions. Word has length 25 [2018-06-22 12:18:46,333 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:18:46,333 INFO ]: Abstraction has 56 states and 82 transitions. [2018-06-22 12:18:46,333 INFO ]: Interpolant automaton has 8 states. [2018-06-22 12:18:46,333 INFO ]: Start isEmpty. Operand 56 states and 82 transitions. [2018-06-22 12:18:46,335 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 12:18:46,335 INFO ]: Found error trace [2018-06-22 12:18:46,335 INFO ]: trace histogram [7, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:18:46,336 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:18:46,336 INFO ]: Analyzing trace with hash 2069384290, now seen corresponding path program 2 times [2018-06-22 12:18:46,336 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:18:46,336 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:18:46,337 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:46,337 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:18:46,337 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:46,366 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:46,499 INFO ]: Checked inductivity of 90 backedges. 23 proven. 17 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2018-06-22 12:18:46,499 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:18:46,499 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:18:46,513 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 12:18:46,562 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 12:18:46,562 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:46,566 INFO ]: Computing forward predicates... [2018-06-22 12:18:46,742 INFO ]: Checked inductivity of 90 backedges. 23 proven. 17 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2018-06-22 12:18:46,775 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:18:46,776 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10] total 14 [2018-06-22 12:18:46,776 INFO ]: Interpolant automaton has 14 states [2018-06-22 12:18:46,776 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 12:18:46,776 INFO ]: CoverageRelationStatistics Valid=28, Invalid=154, Unknown=0, NotChecked=0, Total=182 [2018-06-22 12:18:46,776 INFO ]: Start difference. First operand 56 states and 82 transitions. Second operand 14 states. [2018-06-22 12:18:47,703 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:18:47,703 INFO ]: Finished difference Result 104 states and 174 transitions. [2018-06-22 12:18:47,703 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-06-22 12:18:47,703 INFO ]: Start accepts. Automaton has 14 states. Word has length 49 [2018-06-22 12:18:47,703 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:18:47,705 INFO ]: With dead ends: 104 [2018-06-22 12:18:47,705 INFO ]: Without dead ends: 84 [2018-06-22 12:18:47,706 INFO ]: 0 DeclaredPredicates, 76 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=129, Invalid=423, Unknown=0, NotChecked=0, Total=552 [2018-06-22 12:18:47,706 INFO ]: Start minimizeSevpa. Operand 84 states. [2018-06-22 12:18:47,721 INFO ]: Finished minimizeSevpa. Reduced states from 84 to 65. [2018-06-22 12:18:47,721 INFO ]: Start removeUnreachable. Operand 65 states. [2018-06-22 12:18:47,723 INFO ]: Finished removeUnreachable. Reduced from 65 states to 65 states and 102 transitions. [2018-06-22 12:18:47,723 INFO ]: Start accepts. Automaton has 65 states and 102 transitions. Word has length 49 [2018-06-22 12:18:47,724 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:18:47,724 INFO ]: Abstraction has 65 states and 102 transitions. [2018-06-22 12:18:47,724 INFO ]: Interpolant automaton has 14 states. [2018-06-22 12:18:47,724 INFO ]: Start isEmpty. Operand 65 states and 102 transitions. [2018-06-22 12:18:47,726 INFO ]: Finished isEmpty. Found accepting run of length 54 [2018-06-22 12:18:47,726 INFO ]: Found error trace [2018-06-22 12:18:47,726 INFO ]: trace histogram [8, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:18:47,726 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:18:47,727 INFO ]: Analyzing trace with hash -416655420, now seen corresponding path program 3 times [2018-06-22 12:18:47,727 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:18:47,727 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:18:47,727 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:47,727 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 12:18:47,727 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:47,753 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:47,987 INFO ]: Checked inductivity of 114 backedges. 33 proven. 12 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2018-06-22 12:18:47,987 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:18:47,987 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:18:47,994 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 12:18:48,067 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 12:18:48,067 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:48,071 INFO ]: Computing forward predicates... [2018-06-22 12:18:48,290 INFO ]: Checked inductivity of 114 backedges. 29 proven. 16 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2018-06-22 12:18:48,309 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:18:48,309 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 20 [2018-06-22 12:18:48,310 INFO ]: Interpolant automaton has 20 states [2018-06-22 12:18:48,310 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 12:18:48,310 INFO ]: CoverageRelationStatistics Valid=47, Invalid=333, Unknown=0, NotChecked=0, Total=380 [2018-06-22 12:18:48,310 INFO ]: Start difference. First operand 65 states and 102 transitions. Second operand 20 states. [2018-06-22 12:18:49,389 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:18:49,389 INFO ]: Finished difference Result 114 states and 189 transitions. [2018-06-22 12:18:49,390 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-06-22 12:18:49,390 INFO ]: Start accepts. Automaton has 20 states. Word has length 53 [2018-06-22 12:18:49,390 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:18:49,392 INFO ]: With dead ends: 114 [2018-06-22 12:18:49,392 INFO ]: Without dead ends: 97 [2018-06-22 12:18:49,393 INFO ]: 0 DeclaredPredicates, 82 GetRequests, 50 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 157 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=165, Invalid=957, Unknown=0, NotChecked=0, Total=1122 [2018-06-22 12:18:49,393 INFO ]: Start minimizeSevpa. Operand 97 states. [2018-06-22 12:18:49,406 INFO ]: Finished minimizeSevpa. Reduced states from 97 to 81. [2018-06-22 12:18:49,406 INFO ]: Start removeUnreachable. Operand 81 states. [2018-06-22 12:18:49,407 INFO ]: Finished removeUnreachable. Reduced from 81 states to 81 states and 132 transitions. [2018-06-22 12:18:49,408 INFO ]: Start accepts. Automaton has 81 states and 132 transitions. Word has length 53 [2018-06-22 12:18:49,408 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:18:49,408 INFO ]: Abstraction has 81 states and 132 transitions. [2018-06-22 12:18:49,408 INFO ]: Interpolant automaton has 20 states. [2018-06-22 12:18:49,408 INFO ]: Start isEmpty. Operand 81 states and 132 transitions. [2018-06-22 12:18:49,411 INFO ]: Finished isEmpty. Found accepting run of length 66 [2018-06-22 12:18:49,411 INFO ]: Found error trace [2018-06-22 12:18:49,411 INFO ]: trace histogram [11, 7, 7, 7, 4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:18:49,411 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:18:49,411 INFO ]: Analyzing trace with hash -152984086, now seen corresponding path program 4 times [2018-06-22 12:18:49,411 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:18:49,411 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:18:49,412 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:49,412 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 12:18:49,412 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:49,437 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:49,539 INFO ]: Checked inductivity of 210 backedges. 11 proven. 50 refuted. 0 times theorem prover too weak. 149 trivial. 0 not checked. [2018-06-22 12:18:49,539 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:18:49,539 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:18:49,545 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 12:18:49,576 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 12:18:49,576 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:49,580 INFO ]: Computing forward predicates... [2018-06-22 12:18:49,651 INFO ]: Checked inductivity of 210 backedges. 6 proven. 48 refuted. 0 times theorem prover too weak. 156 trivial. 0 not checked. [2018-06-22 12:18:49,671 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:18:49,671 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 11 [2018-06-22 12:18:49,671 INFO ]: Interpolant automaton has 11 states [2018-06-22 12:18:49,671 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 12:18:49,671 INFO ]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2018-06-22 12:18:49,672 INFO ]: Start difference. First operand 81 states and 132 transitions. Second operand 11 states. [2018-06-22 12:18:49,968 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:18:49,968 INFO ]: Finished difference Result 137 states and 216 transitions. [2018-06-22 12:18:49,968 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 12:18:49,968 INFO ]: Start accepts. Automaton has 11 states. Word has length 65 [2018-06-22 12:18:49,969 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:18:49,971 INFO ]: With dead ends: 137 [2018-06-22 12:18:49,971 INFO ]: Without dead ends: 121 [2018-06-22 12:18:49,971 INFO ]: 0 DeclaredPredicates, 83 GetRequests, 66 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=67, Invalid=239, Unknown=0, NotChecked=0, Total=306 [2018-06-22 12:18:49,971 INFO ]: Start minimizeSevpa. Operand 121 states. [2018-06-22 12:18:49,987 INFO ]: Finished minimizeSevpa. Reduced states from 121 to 97. [2018-06-22 12:18:49,987 INFO ]: Start removeUnreachable. Operand 97 states. [2018-06-22 12:18:49,989 INFO ]: Finished removeUnreachable. Reduced from 97 states to 97 states and 156 transitions. [2018-06-22 12:18:49,989 INFO ]: Start accepts. Automaton has 97 states and 156 transitions. Word has length 65 [2018-06-22 12:18:49,989 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:18:49,989 INFO ]: Abstraction has 97 states and 156 transitions. [2018-06-22 12:18:49,989 INFO ]: Interpolant automaton has 11 states. [2018-06-22 12:18:49,989 INFO ]: Start isEmpty. Operand 97 states and 156 transitions. [2018-06-22 12:18:49,994 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 12:18:49,994 INFO ]: Found error trace [2018-06-22 12:18:49,994 INFO ]: trace histogram [5, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:18:49,994 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:18:49,994 INFO ]: Analyzing trace with hash 1627921124, now seen corresponding path program 1 times [2018-06-22 12:18:49,994 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:18:49,994 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:18:49,995 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:49,995 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 12:18:49,995 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:50,017 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:50,085 INFO ]: Checked inductivity of 34 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2018-06-22 12:18:50,085 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:18:50,085 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:18:50,094 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:18:50,110 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:50,112 INFO ]: Computing forward predicates... [2018-06-22 12:18:50,147 INFO ]: Checked inductivity of 34 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2018-06-22 12:18:50,179 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:18:50,179 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-06-22 12:18:50,179 INFO ]: Interpolant automaton has 8 states [2018-06-22 12:18:50,179 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 12:18:50,180 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-22 12:18:50,180 INFO ]: Start difference. First operand 97 states and 156 transitions. Second operand 8 states. [2018-06-22 12:18:50,227 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:18:50,227 INFO ]: Finished difference Result 135 states and 207 transitions. [2018-06-22 12:18:50,227 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 12:18:50,227 INFO ]: Start accepts. Automaton has 8 states. Word has length 41 [2018-06-22 12:18:50,227 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:18:50,228 INFO ]: With dead ends: 135 [2018-06-22 12:18:50,228 INFO ]: Without dead ends: 61 [2018-06-22 12:18:50,228 INFO ]: 0 DeclaredPredicates, 46 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-22 12:18:50,228 INFO ]: Start minimizeSevpa. Operand 61 states. [2018-06-22 12:18:50,237 INFO ]: Finished minimizeSevpa. Reduced states from 61 to 61. [2018-06-22 12:18:50,237 INFO ]: Start removeUnreachable. Operand 61 states. [2018-06-22 12:18:50,238 INFO ]: Finished removeUnreachable. Reduced from 61 states to 61 states and 82 transitions. [2018-06-22 12:18:50,238 INFO ]: Start accepts. Automaton has 61 states and 82 transitions. Word has length 41 [2018-06-22 12:18:50,239 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:18:50,239 INFO ]: Abstraction has 61 states and 82 transitions. [2018-06-22 12:18:50,239 INFO ]: Interpolant automaton has 8 states. [2018-06-22 12:18:50,239 INFO ]: Start isEmpty. Operand 61 states and 82 transitions. [2018-06-22 12:18:50,240 INFO ]: Finished isEmpty. Found accepting run of length 70 [2018-06-22 12:18:50,240 INFO ]: Found error trace [2018-06-22 12:18:50,240 INFO ]: trace histogram [12, 8, 8, 8, 4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:18:50,241 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:18:50,241 INFO ]: Analyzing trace with hash -1958900404, now seen corresponding path program 5 times [2018-06-22 12:18:50,241 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:18:50,241 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:18:50,241 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:50,241 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:18:50,241 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:50,262 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:50,385 INFO ]: Checked inductivity of 250 backedges. 11 proven. 79 refuted. 0 times theorem prover too weak. 160 trivial. 0 not checked. [2018-06-22 12:18:50,386 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:18:50,386 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:18:50,392 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 12:18:50,503 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2018-06-22 12:18:50,503 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:50,508 INFO ]: Computing forward predicates... [2018-06-22 12:18:50,839 INFO ]: Checked inductivity of 250 backedges. 11 proven. 128 refuted. 0 times theorem prover too weak. 111 trivial. 0 not checked. [2018-06-22 12:18:50,859 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:18:50,859 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 15] total 24 [2018-06-22 12:18:50,860 INFO ]: Interpolant automaton has 24 states [2018-06-22 12:18:50,860 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 12:18:50,860 INFO ]: CoverageRelationStatistics Valid=51, Invalid=501, Unknown=0, NotChecked=0, Total=552 [2018-06-22 12:18:50,860 INFO ]: Start difference. First operand 61 states and 82 transitions. Second operand 24 states. [2018-06-22 12:18:52,025 WARN ]: Spent 214.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 30 [2018-06-22 12:18:52,707 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:18:52,707 INFO ]: Finished difference Result 157 states and 234 transitions. [2018-06-22 12:18:52,708 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-06-22 12:18:52,708 INFO ]: Start accepts. Automaton has 24 states. Word has length 69 [2018-06-22 12:18:52,708 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:18:52,710 INFO ]: With dead ends: 157 [2018-06-22 12:18:52,710 INFO ]: Without dead ends: 148 [2018-06-22 12:18:52,711 INFO ]: 0 DeclaredPredicates, 105 GetRequests, 57 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 404 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=342, Invalid=2108, Unknown=0, NotChecked=0, Total=2450 [2018-06-22 12:18:52,711 INFO ]: Start minimizeSevpa. Operand 148 states. [2018-06-22 12:18:52,732 INFO ]: Finished minimizeSevpa. Reduced states from 148 to 110. [2018-06-22 12:18:52,732 INFO ]: Start removeUnreachable. Operand 110 states. [2018-06-22 12:18:52,734 INFO ]: Finished removeUnreachable. Reduced from 110 states to 110 states and 163 transitions. [2018-06-22 12:18:52,734 INFO ]: Start accepts. Automaton has 110 states and 163 transitions. Word has length 69 [2018-06-22 12:18:52,734 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:18:52,734 INFO ]: Abstraction has 110 states and 163 transitions. [2018-06-22 12:18:52,734 INFO ]: Interpolant automaton has 24 states. [2018-06-22 12:18:52,735 INFO ]: Start isEmpty. Operand 110 states and 163 transitions. [2018-06-22 12:18:52,736 INFO ]: Finished isEmpty. Found accepting run of length 86 [2018-06-22 12:18:52,736 INFO ]: Found error trace [2018-06-22 12:18:52,736 INFO ]: trace histogram [16, 12, 12, 12, 4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:18:52,736 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:18:52,737 INFO ]: Analyzing trace with hash -1591574956, now seen corresponding path program 6 times [2018-06-22 12:18:52,737 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:18:52,737 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:18:52,737 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:52,737 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 12:18:52,737 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:52,758 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:52,913 INFO ]: Checked inductivity of 450 backedges. 51 proven. 104 refuted. 0 times theorem prover too weak. 295 trivial. 0 not checked. [2018-06-22 12:18:52,913 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:18:52,913 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:18:52,941 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 12:18:52,990 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2018-06-22 12:18:52,990 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:52,996 INFO ]: Computing forward predicates... [2018-06-22 12:18:53,413 INFO ]: Checked inductivity of 450 backedges. 123 proven. 12 refuted. 0 times theorem prover too weak. 315 trivial. 0 not checked. [2018-06-22 12:18:53,433 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:18:53,434 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 22 [2018-06-22 12:18:53,434 INFO ]: Interpolant automaton has 22 states [2018-06-22 12:18:53,434 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-22 12:18:53,434 INFO ]: CoverageRelationStatistics Valid=42, Invalid=420, Unknown=0, NotChecked=0, Total=462 [2018-06-22 12:18:53,434 INFO ]: Start difference. First operand 110 states and 163 transitions. Second operand 22 states. [2018-06-22 12:18:54,612 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:18:54,612 INFO ]: Finished difference Result 309 states and 512 transitions. [2018-06-22 12:18:54,614 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-06-22 12:18:54,614 INFO ]: Start accepts. Automaton has 22 states. Word has length 85 [2018-06-22 12:18:54,614 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:18:54,617 INFO ]: With dead ends: 309 [2018-06-22 12:18:54,617 INFO ]: Without dead ends: 272 [2018-06-22 12:18:54,617 INFO ]: 0 DeclaredPredicates, 134 GetRequests, 85 SyntacticMatches, 3 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 309 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=275, Invalid=1981, Unknown=0, NotChecked=0, Total=2256 [2018-06-22 12:18:54,617 INFO ]: Start minimizeSevpa. Operand 272 states. [2018-06-22 12:18:54,658 INFO ]: Finished minimizeSevpa. Reduced states from 272 to 198. [2018-06-22 12:18:54,658 INFO ]: Start removeUnreachable. Operand 198 states. [2018-06-22 12:18:54,668 INFO ]: Finished removeUnreachable. Reduced from 198 states to 198 states and 322 transitions. [2018-06-22 12:18:54,668 INFO ]: Start accepts. Automaton has 198 states and 322 transitions. Word has length 85 [2018-06-22 12:18:54,668 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:18:54,668 INFO ]: Abstraction has 198 states and 322 transitions. [2018-06-22 12:18:54,668 INFO ]: Interpolant automaton has 22 states. [2018-06-22 12:18:54,668 INFO ]: Start isEmpty. Operand 198 states and 322 transitions. [2018-06-22 12:18:54,671 INFO ]: Finished isEmpty. Found accepting run of length 122 [2018-06-22 12:18:54,671 INFO ]: Found error trace [2018-06-22 12:18:54,671 INFO ]: trace histogram [24, 19, 19, 19, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:18:54,671 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:18:54,671 INFO ]: Analyzing trace with hash 550896169, now seen corresponding path program 7 times [2018-06-22 12:18:54,671 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:18:54,671 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:18:54,672 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:54,672 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 12:18:54,672 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:18:54,718 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:54,971 INFO ]: Checked inductivity of 1041 backedges. 196 proven. 203 refuted. 0 times theorem prover too weak. 642 trivial. 0 not checked. [2018-06-22 12:18:54,972 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:18:54,972 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:18:54,979 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:18:55,032 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:18:55,036 INFO ]: Computing forward predicates... [2018-06-22 12:18:55,670 INFO ]: Checked inductivity of 1041 backedges. 64 proven. 323 refuted. 0 times theorem prover too weak. 654 trivial. 0 not checked. [2018-06-22 12:18:55,689 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:18:55,689 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 15] total 24 [2018-06-22 12:18:55,690 INFO ]: Interpolant automaton has 24 states [2018-06-22 12:18:55,690 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 12:18:55,690 INFO ]: CoverageRelationStatistics Valid=62, Invalid=489, Unknown=1, NotChecked=0, Total=552 [2018-06-22 12:18:55,690 INFO ]: Start difference. First operand 198 states and 322 transitions. Second operand 24 states. [2018-06-22 12:18:57,831 WARN ]: Spent 302.00 ms on a formula simplification that was a NOOP. DAG size: 31 [2018-06-22 12:18:58,169 WARN ]: Spent 283.00 ms on a formula simplification that was a NOOP. DAG size: 32 [2018-06-22 12:18:59,005 WARN ]: Spent 276.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 10 [2018-06-22 12:19:01,955 WARN ]: Spent 279.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 10 [2018-06-22 12:19:04,741 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:19:04,741 INFO ]: Finished difference Result 925 states and 1981 transitions. [2018-06-22 12:19:04,742 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-06-22 12:19:04,742 INFO ]: Start accepts. Automaton has 24 states. Word has length 121 [2018-06-22 12:19:04,743 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:19:04,755 INFO ]: With dead ends: 925 [2018-06-22 12:19:04,755 INFO ]: Without dead ends: 872 [2018-06-22 12:19:04,756 INFO ]: 0 DeclaredPredicates, 167 GetRequests, 112 SyntacticMatches, 8 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 367 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=376, Invalid=1971, Unknown=5, NotChecked=0, Total=2352 [2018-06-22 12:19:04,757 INFO ]: Start minimizeSevpa. Operand 872 states. [2018-06-22 12:19:04,864 INFO ]: Finished minimizeSevpa. Reduced states from 872 to 712. [2018-06-22 12:19:04,864 INFO ]: Start removeUnreachable. Operand 712 states. [2018-06-22 12:19:04,877 INFO ]: Finished removeUnreachable. Reduced from 712 states to 712 states and 1535 transitions. [2018-06-22 12:19:04,877 INFO ]: Start accepts. Automaton has 712 states and 1535 transitions. Word has length 121 [2018-06-22 12:19:04,877 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:19:04,877 INFO ]: Abstraction has 712 states and 1535 transitions. [2018-06-22 12:19:04,877 INFO ]: Interpolant automaton has 24 states. [2018-06-22 12:19:04,877 INFO ]: Start isEmpty. Operand 712 states and 1535 transitions. [2018-06-22 12:19:04,886 INFO ]: Finished isEmpty. Found accepting run of length 162 [2018-06-22 12:19:04,886 INFO ]: Found error trace [2018-06-22 12:19:04,886 INFO ]: trace histogram [34, 29, 29, 29, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:19:04,886 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:19:04,886 INFO ]: Analyzing trace with hash -1028429699, now seen corresponding path program 8 times [2018-06-22 12:19:04,886 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:19:04,886 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:19:04,887 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:04,887 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:19:04,887 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:04,937 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:05,900 INFO ]: Checked inductivity of 2131 backedges. 82 proven. 362 refuted. 0 times theorem prover too weak. 1687 trivial. 0 not checked. [2018-06-22 12:19:05,901 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:19:05,901 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:19:05,906 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 12:19:05,972 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 12:19:05,972 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:05,977 INFO ]: Computing forward predicates... [2018-06-22 12:19:06,140 INFO ]: Checked inductivity of 2131 backedges. 8 proven. 419 refuted. 0 times theorem prover too weak. 1704 trivial. 0 not checked. [2018-06-22 12:19:06,161 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:19:06,161 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 12] total 20 [2018-06-22 12:19:06,161 INFO ]: Interpolant automaton has 20 states [2018-06-22 12:19:06,161 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 12:19:06,161 INFO ]: CoverageRelationStatistics Valid=44, Invalid=336, Unknown=0, NotChecked=0, Total=380 [2018-06-22 12:19:06,161 INFO ]: Start difference. First operand 712 states and 1535 transitions. Second operand 20 states. [2018-06-22 12:19:06,816 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:19:06,816 INFO ]: Finished difference Result 1805 states and 4564 transitions. [2018-06-22 12:19:06,818 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-22 12:19:06,818 INFO ]: Start accepts. Automaton has 20 states. Word has length 161 [2018-06-22 12:19:06,819 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:19:06,855 INFO ]: With dead ends: 1805 [2018-06-22 12:19:06,855 INFO ]: Without dead ends: 1786 [2018-06-22 12:19:06,855 INFO ]: 0 DeclaredPredicates, 188 GetRequests, 155 SyntacticMatches, 3 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 83 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=151, Invalid=841, Unknown=0, NotChecked=0, Total=992 [2018-06-22 12:19:06,857 INFO ]: Start minimizeSevpa. Operand 1786 states. [2018-06-22 12:19:07,051 INFO ]: Finished minimizeSevpa. Reduced states from 1786 to 1464. [2018-06-22 12:19:07,051 INFO ]: Start removeUnreachable. Operand 1464 states. [2018-06-22 12:19:07,070 INFO ]: Finished removeUnreachable. Reduced from 1464 states to 1464 states and 3588 transitions. [2018-06-22 12:19:07,070 INFO ]: Start accepts. Automaton has 1464 states and 3588 transitions. Word has length 161 [2018-06-22 12:19:07,070 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:19:07,070 INFO ]: Abstraction has 1464 states and 3588 transitions. [2018-06-22 12:19:07,070 INFO ]: Interpolant automaton has 20 states. [2018-06-22 12:19:07,070 INFO ]: Start isEmpty. Operand 1464 states and 3588 transitions. [2018-06-22 12:19:07,078 INFO ]: Finished isEmpty. Found accepting run of length 114 [2018-06-22 12:19:07,078 INFO ]: Found error trace [2018-06-22 12:19:07,079 INFO ]: trace histogram [22, 17, 17, 17, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:19:07,079 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:19:07,079 INFO ]: Analyzing trace with hash 1278967397, now seen corresponding path program 9 times [2018-06-22 12:19:07,079 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:19:07,079 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:19:07,080 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:07,080 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 12:19:07,080 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:07,105 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:07,794 INFO ]: Checked inductivity of 871 backedges. 152 proven. 25 refuted. 0 times theorem prover too weak. 694 trivial. 0 not checked. [2018-06-22 12:19:07,794 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:19:07,794 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:19:07,808 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 12:19:07,844 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2018-06-22 12:19:07,844 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:07,847 INFO ]: Computing forward predicates... [2018-06-22 12:19:08,023 INFO ]: Checked inductivity of 871 backedges. 150 proven. 27 refuted. 0 times theorem prover too weak. 694 trivial. 0 not checked. [2018-06-22 12:19:08,042 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:19:08,042 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 23 [2018-06-22 12:19:08,043 INFO ]: Interpolant automaton has 23 states [2018-06-22 12:19:08,043 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 12:19:08,043 INFO ]: CoverageRelationStatistics Valid=59, Invalid=447, Unknown=0, NotChecked=0, Total=506 [2018-06-22 12:19:08,043 INFO ]: Start difference. First operand 1464 states and 3588 transitions. Second operand 23 states. [2018-06-22 12:19:09,843 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:19:09,843 INFO ]: Finished difference Result 2630 states and 7643 transitions. [2018-06-22 12:19:09,843 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-06-22 12:19:09,843 INFO ]: Start accepts. Automaton has 23 states. Word has length 113 [2018-06-22 12:19:09,846 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:19:09,864 INFO ]: With dead ends: 2630 [2018-06-22 12:19:09,864 INFO ]: Without dead ends: 1362 [2018-06-22 12:19:09,865 INFO ]: 0 DeclaredPredicates, 144 GetRequests, 110 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 167 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=186, Invalid=1074, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 12:19:09,866 INFO ]: Start minimizeSevpa. Operand 1362 states. [2018-06-22 12:19:09,981 INFO ]: Finished minimizeSevpa. Reduced states from 1362 to 1306. [2018-06-22 12:19:09,982 INFO ]: Start removeUnreachable. Operand 1306 states. [2018-06-22 12:19:09,995 INFO ]: Finished removeUnreachable. Reduced from 1306 states to 1306 states and 3016 transitions. [2018-06-22 12:19:09,995 INFO ]: Start accepts. Automaton has 1306 states and 3016 transitions. Word has length 113 [2018-06-22 12:19:09,995 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:19:09,995 INFO ]: Abstraction has 1306 states and 3016 transitions. [2018-06-22 12:19:09,995 INFO ]: Interpolant automaton has 23 states. [2018-06-22 12:19:09,996 INFO ]: Start isEmpty. Operand 1306 states and 3016 transitions. [2018-06-22 12:19:10,006 INFO ]: Finished isEmpty. Found accepting run of length 170 [2018-06-22 12:19:10,006 INFO ]: Found error trace [2018-06-22 12:19:10,006 INFO ]: trace histogram [36, 31, 31, 31, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:19:10,006 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:19:10,006 INFO ]: Analyzing trace with hash 1198051137, now seen corresponding path program 10 times [2018-06-22 12:19:10,006 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:19:10,006 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:19:10,013 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:10,013 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 12:19:10,013 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:10,044 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:11,005 INFO ]: Checked inductivity of 2397 backedges. 369 proven. 352 refuted. 0 times theorem prover too weak. 1676 trivial. 0 not checked. [2018-06-22 12:19:11,005 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:19:11,006 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:19:11,011 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 12:19:11,078 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 12:19:11,078 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:11,082 INFO ]: Computing forward predicates... [2018-06-22 12:19:11,329 INFO ]: Checked inductivity of 2397 backedges. 8 proven. 684 refuted. 0 times theorem prover too weak. 1705 trivial. 0 not checked. [2018-06-22 12:19:11,349 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:19:11,349 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 14] total 23 [2018-06-22 12:19:11,349 INFO ]: Interpolant automaton has 23 states [2018-06-22 12:19:11,349 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 12:19:11,350 INFO ]: CoverageRelationStatistics Valid=50, Invalid=456, Unknown=0, NotChecked=0, Total=506 [2018-06-22 12:19:11,350 INFO ]: Start difference. First operand 1306 states and 3016 transitions. Second operand 23 states. [2018-06-22 12:19:12,551 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:19:12,551 INFO ]: Finished difference Result 3728 states and 9764 transitions. [2018-06-22 12:19:12,554 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-06-22 12:19:12,554 INFO ]: Start accepts. Automaton has 23 states. Word has length 169 [2018-06-22 12:19:12,554 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:19:12,611 INFO ]: With dead ends: 3728 [2018-06-22 12:19:12,611 INFO ]: Without dead ends: 3668 [2018-06-22 12:19:12,611 INFO ]: 0 DeclaredPredicates, 206 GetRequests, 161 SyntacticMatches, 8 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=214, Invalid=1268, Unknown=0, NotChecked=0, Total=1482 [2018-06-22 12:19:12,614 INFO ]: Start minimizeSevpa. Operand 3668 states. [2018-06-22 12:19:12,953 INFO ]: Finished minimizeSevpa. Reduced states from 3668 to 3112. [2018-06-22 12:19:12,953 INFO ]: Start removeUnreachable. Operand 3112 states. [2018-06-22 12:19:12,979 INFO ]: Finished removeUnreachable. Reduced from 3112 states to 3112 states and 8042 transitions. [2018-06-22 12:19:12,979 INFO ]: Start accepts. Automaton has 3112 states and 8042 transitions. Word has length 169 [2018-06-22 12:19:12,979 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:19:12,979 INFO ]: Abstraction has 3112 states and 8042 transitions. [2018-06-22 12:19:12,979 INFO ]: Interpolant automaton has 23 states. [2018-06-22 12:19:12,979 INFO ]: Start isEmpty. Operand 3112 states and 8042 transitions. [2018-06-22 12:19:12,995 INFO ]: Finished isEmpty. Found accepting run of length 118 [2018-06-22 12:19:12,995 INFO ]: Found error trace [2018-06-22 12:19:12,995 INFO ]: trace histogram [23, 18, 18, 18, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:19:12,995 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:19:12,996 INFO ]: Analyzing trace with hash -1502375865, now seen corresponding path program 11 times [2018-06-22 12:19:12,996 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:19:12,996 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:19:12,996 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:12,996 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 12:19:12,996 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:13,014 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:15,171 INFO ]: Checked inductivity of 954 backedges. 146 proven. 312 refuted. 0 times theorem prover too weak. 496 trivial. 0 not checked. [2018-06-22 12:19:15,171 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:19:15,171 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:19:15,177 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 12:19:15,229 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2018-06-22 12:19:15,229 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:15,241 INFO ]: Computing forward predicates... [2018-06-22 12:19:15,806 INFO ]: Checked inductivity of 954 backedges. 127 proven. 372 refuted. 0 times theorem prover too weak. 455 trivial. 0 not checked. [2018-06-22 12:19:15,825 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:19:15,825 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 20] total 33 [2018-06-22 12:19:15,825 INFO ]: Interpolant automaton has 33 states [2018-06-22 12:19:15,825 INFO ]: Constructing interpolant automaton starting with 33 interpolants. [2018-06-22 12:19:15,826 INFO ]: CoverageRelationStatistics Valid=92, Invalid=964, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 12:19:15,826 INFO ]: Start difference. First operand 3112 states and 8042 transitions. Second operand 33 states. [2018-06-22 12:19:18,224 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:19:18,224 INFO ]: Finished difference Result 2961 states and 6352 transitions. [2018-06-22 12:19:18,227 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2018-06-22 12:19:18,227 INFO ]: Start accepts. Automaton has 33 states. Word has length 117 [2018-06-22 12:19:18,227 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:19:18,263 INFO ]: With dead ends: 2961 [2018-06-22 12:19:18,264 INFO ]: Without dead ends: 2810 [2018-06-22 12:19:18,265 INFO ]: 0 DeclaredPredicates, 179 GetRequests, 110 SyntacticMatches, 6 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 654 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=574, Invalid=3586, Unknown=0, NotChecked=0, Total=4160 [2018-06-22 12:19:18,266 INFO ]: Start minimizeSevpa. Operand 2810 states. [2018-06-22 12:19:18,487 INFO ]: Finished minimizeSevpa. Reduced states from 2810 to 1931. [2018-06-22 12:19:18,488 INFO ]: Start removeUnreachable. Operand 1931 states. [2018-06-22 12:19:18,499 INFO ]: Finished removeUnreachable. Reduced from 1931 states to 1931 states and 3828 transitions. [2018-06-22 12:19:18,499 INFO ]: Start accepts. Automaton has 1931 states and 3828 transitions. Word has length 117 [2018-06-22 12:19:18,500 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:19:18,500 INFO ]: Abstraction has 1931 states and 3828 transitions. [2018-06-22 12:19:18,500 INFO ]: Interpolant automaton has 33 states. [2018-06-22 12:19:18,500 INFO ]: Start isEmpty. Operand 1931 states and 3828 transitions. [2018-06-22 12:19:18,508 INFO ]: Finished isEmpty. Found accepting run of length 106 [2018-06-22 12:19:18,508 INFO ]: Found error trace [2018-06-22 12:19:18,508 INFO ]: trace histogram [20, 15, 15, 15, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:19:18,508 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:19:18,508 INFO ]: Analyzing trace with hash -523197023, now seen corresponding path program 12 times [2018-06-22 12:19:18,508 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:19:18,508 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:19:18,508 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:18,508 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 12:19:18,508 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:18,524 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:19,304 INFO ]: Checked inductivity of 717 backedges. 114 proven. 132 refuted. 0 times theorem prover too weak. 471 trivial. 0 not checked. [2018-06-22 12:19:19,304 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:19:19,304 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:19:19,311 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 12:19:19,354 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 12:19:19,354 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:19,358 INFO ]: Computing forward predicates... [2018-06-22 12:19:21,242 INFO ]: Checked inductivity of 717 backedges. 257 proven. 169 refuted. 0 times theorem prover too weak. 291 trivial. 0 not checked. [2018-06-22 12:19:21,262 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:19:21,262 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 23] total 37 [2018-06-22 12:19:21,263 INFO ]: Interpolant automaton has 37 states [2018-06-22 12:19:21,263 INFO ]: Constructing interpolant automaton starting with 37 interpolants. [2018-06-22 12:19:21,263 INFO ]: CoverageRelationStatistics Valid=92, Invalid=1238, Unknown=2, NotChecked=0, Total=1332 [2018-06-22 12:19:21,263 INFO ]: Start difference. First operand 1931 states and 3828 transitions. Second operand 37 states. [2018-06-22 12:19:21,959 WARN ]: Spent 256.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2018-06-22 12:19:22,481 WARN ]: Spent 281.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2018-06-22 12:19:24,729 WARN ]: Spent 537.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 22 [2018-06-22 12:19:29,497 WARN ]: Spent 143.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 19 [2018-06-22 12:19:31,245 WARN ]: Spent 611.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 23 [2018-06-22 12:19:32,130 WARN ]: Spent 173.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 19 [2018-06-22 12:19:34,071 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:19:34,071 INFO ]: Finished difference Result 2230 states and 3573 transitions. [2018-06-22 12:19:34,101 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-06-22 12:19:34,101 INFO ]: Start accepts. Automaton has 37 states. Word has length 105 [2018-06-22 12:19:34,101 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:19:34,111 INFO ]: With dead ends: 2230 [2018-06-22 12:19:34,111 INFO ]: Without dead ends: 967 [2018-06-22 12:19:34,112 INFO ]: 0 DeclaredPredicates, 158 GetRequests, 92 SyntacticMatches, 0 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 619 ImplicationChecksByTransitivity, 10.2s TimeCoverageRelationStatistics Valid=544, Invalid=3996, Unknown=16, NotChecked=0, Total=4556 [2018-06-22 12:19:34,113 INFO ]: Start minimizeSevpa. Operand 967 states. [2018-06-22 12:19:34,164 INFO ]: Finished minimizeSevpa. Reduced states from 967 to 731. [2018-06-22 12:19:34,164 INFO ]: Start removeUnreachable. Operand 731 states. [2018-06-22 12:19:34,172 INFO ]: Finished removeUnreachable. Reduced from 731 states to 731 states and 1213 transitions. [2018-06-22 12:19:34,173 INFO ]: Start accepts. Automaton has 731 states and 1213 transitions. Word has length 105 [2018-06-22 12:19:34,173 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:19:34,173 INFO ]: Abstraction has 731 states and 1213 transitions. [2018-06-22 12:19:34,173 INFO ]: Interpolant automaton has 37 states. [2018-06-22 12:19:34,173 INFO ]: Start isEmpty. Operand 731 states and 1213 transitions. [2018-06-22 12:19:34,175 INFO ]: Finished isEmpty. Found accepting run of length 82 [2018-06-22 12:19:34,175 INFO ]: Found error trace [2018-06-22 12:19:34,175 INFO ]: trace histogram [14, 9, 9, 9, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:19:34,175 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:19:34,175 INFO ]: Analyzing trace with hash -342258475, now seen corresponding path program 13 times [2018-06-22 12:19:34,175 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:19:34,175 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:19:34,175 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:34,175 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 12:19:34,175 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:34,187 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:34,936 INFO ]: Checked inductivity of 351 backedges. 106 proven. 33 refuted. 0 times theorem prover too weak. 212 trivial. 0 not checked. [2018-06-22 12:19:34,936 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:19:34,936 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:19:34,941 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:19:34,970 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:34,973 INFO ]: Computing forward predicates... [2018-06-22 12:19:35,146 INFO ]: Checked inductivity of 351 backedges. 106 proven. 32 refuted. 0 times theorem prover too weak. 213 trivial. 0 not checked. [2018-06-22 12:19:35,165 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:19:35,165 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 23 [2018-06-22 12:19:35,165 INFO ]: Interpolant automaton has 23 states [2018-06-22 12:19:35,166 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 12:19:35,166 INFO ]: CoverageRelationStatistics Valid=51, Invalid=455, Unknown=0, NotChecked=0, Total=506 [2018-06-22 12:19:35,166 INFO ]: Start difference. First operand 731 states and 1213 transitions. Second operand 23 states. [2018-06-22 12:19:35,723 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:19:35,723 INFO ]: Finished difference Result 785 states and 1265 transitions. [2018-06-22 12:19:35,724 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-06-22 12:19:35,724 INFO ]: Start accepts. Automaton has 23 states. Word has length 81 [2018-06-22 12:19:35,724 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:19:35,730 INFO ]: With dead ends: 785 [2018-06-22 12:19:35,730 INFO ]: Without dead ends: 775 [2018-06-22 12:19:35,731 INFO ]: 0 DeclaredPredicates, 114 GetRequests, 74 SyntacticMatches, 3 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 203 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=208, Invalid=1274, Unknown=0, NotChecked=0, Total=1482 [2018-06-22 12:19:35,732 INFO ]: Start minimizeSevpa. Operand 775 states. [2018-06-22 12:19:35,767 INFO ]: Finished minimizeSevpa. Reduced states from 775 to 733. [2018-06-22 12:19:35,767 INFO ]: Start removeUnreachable. Operand 733 states. [2018-06-22 12:19:35,771 INFO ]: Finished removeUnreachable. Reduced from 733 states to 733 states and 1213 transitions. [2018-06-22 12:19:35,771 INFO ]: Start accepts. Automaton has 733 states and 1213 transitions. Word has length 81 [2018-06-22 12:19:35,771 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:19:35,771 INFO ]: Abstraction has 733 states and 1213 transitions. [2018-06-22 12:19:35,771 INFO ]: Interpolant automaton has 23 states. [2018-06-22 12:19:35,771 INFO ]: Start isEmpty. Operand 733 states and 1213 transitions. [2018-06-22 12:19:35,774 INFO ]: Finished isEmpty. Found accepting run of length 90 [2018-06-22 12:19:35,774 INFO ]: Found error trace [2018-06-22 12:19:35,774 INFO ]: trace histogram [16, 11, 11, 11, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:19:35,774 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:19:35,774 INFO ]: Analyzing trace with hash -999228775, now seen corresponding path program 14 times [2018-06-22 12:19:35,774 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:19:35,774 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:19:35,774 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:35,775 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:19:35,775 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:35,787 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:36,268 INFO ]: Checked inductivity of 457 backedges. 42 proven. 121 refuted. 0 times theorem prover too weak. 294 trivial. 0 not checked. [2018-06-22 12:19:36,268 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:19:36,268 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:19:36,292 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 12:19:36,357 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 12:19:36,357 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:36,361 INFO ]: Computing forward predicates... [2018-06-22 12:19:36,725 INFO ]: Checked inductivity of 457 backedges. 43 proven. 115 refuted. 0 times theorem prover too weak. 299 trivial. 0 not checked. [2018-06-22 12:19:36,744 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:19:36,744 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12] total 18 [2018-06-22 12:19:36,744 INFO ]: Interpolant automaton has 18 states [2018-06-22 12:19:36,744 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-22 12:19:36,744 INFO ]: CoverageRelationStatistics Valid=45, Invalid=261, Unknown=0, NotChecked=0, Total=306 [2018-06-22 12:19:36,744 INFO ]: Start difference. First operand 733 states and 1213 transitions. Second operand 18 states. [2018-06-22 12:19:37,600 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:19:37,600 INFO ]: Finished difference Result 783 states and 1261 transitions. [2018-06-22 12:19:37,600 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-06-22 12:19:37,600 INFO ]: Start accepts. Automaton has 18 states. Word has length 89 [2018-06-22 12:19:37,600 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:19:37,603 INFO ]: With dead ends: 783 [2018-06-22 12:19:37,603 INFO ]: Without dead ends: 330 [2018-06-22 12:19:37,604 INFO ]: 0 DeclaredPredicates, 117 GetRequests, 83 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 131 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=179, Invalid=877, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 12:19:37,604 INFO ]: Start minimizeSevpa. Operand 330 states. [2018-06-22 12:19:37,617 INFO ]: Finished minimizeSevpa. Reduced states from 330 to 308. [2018-06-22 12:19:37,617 INFO ]: Start removeUnreachable. Operand 308 states. [2018-06-22 12:19:37,619 INFO ]: Finished removeUnreachable. Reduced from 308 states to 308 states and 484 transitions. [2018-06-22 12:19:37,619 INFO ]: Start accepts. Automaton has 308 states and 484 transitions. Word has length 89 [2018-06-22 12:19:37,619 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:19:37,619 INFO ]: Abstraction has 308 states and 484 transitions. [2018-06-22 12:19:37,619 INFO ]: Interpolant automaton has 18 states. [2018-06-22 12:19:37,619 INFO ]: Start isEmpty. Operand 308 states and 484 transitions. [2018-06-22 12:19:37,620 INFO ]: Finished isEmpty. Found accepting run of length 90 [2018-06-22 12:19:37,620 INFO ]: Found error trace [2018-06-22 12:19:37,620 INFO ]: trace histogram [16, 11, 11, 11, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:19:37,621 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:19:37,621 INFO ]: Analyzing trace with hash -1013617383, now seen corresponding path program 15 times [2018-06-22 12:19:37,621 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:19:37,621 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:19:37,621 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:37,621 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 12:19:37,621 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:19:37,635 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:37,876 INFO ]: Checked inductivity of 457 backedges. 152 proven. 58 refuted. 0 times theorem prover too weak. 247 trivial. 0 not checked. [2018-06-22 12:19:37,876 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:19:37,876 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:19:37,881 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 12:19:37,933 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2018-06-22 12:19:37,933 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:19:37,936 INFO ]: Computing forward predicates... [2018-06-22 12:19:39,873 INFO ]: Checked inductivity of 457 backedges. 156 proven. 117 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2018-06-22 12:19:39,892 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:19:39,892 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 22] total 39 [2018-06-22 12:19:39,892 INFO ]: Interpolant automaton has 39 states [2018-06-22 12:19:39,893 INFO ]: Constructing interpolant automaton starting with 39 interpolants. [2018-06-22 12:19:39,893 INFO ]: CoverageRelationStatistics Valid=96, Invalid=1386, Unknown=0, NotChecked=0, Total=1482 [2018-06-22 12:19:39,893 INFO ]: Start difference. First operand 308 states and 484 transitions. Second operand 39 states. Received shutdown request... [2018-06-22 12:19:41,744 WARN ]: Removed 4 from assertion stack [2018-06-22 12:19:41,744 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-06-22 12:19:41,744 WARN ]: Verification canceled [2018-06-22 12:19:41,747 WARN ]: Timeout [2018-06-22 12:19:41,748 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 12:19:41 BoogieIcfgContainer [2018-06-22 12:19:41,748 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 12:19:41,748 INFO ]: Toolchain (without parser) took 58645.27 ms. Allocated memory was 304.1 MB in the beginning and 660.6 MB in the end (delta: 356.5 MB). Free memory was 258.5 MB in the beginning and 357.9 MB in the end (delta: -99.4 MB). Peak memory consumption was 257.1 MB. Max. memory is 3.6 GB. [2018-06-22 12:19:41,749 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 304.1 MB. Free memory is still 268.6 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 12:19:41,749 INFO ]: ChcToBoogie took 50.04 ms. Allocated memory is still 304.1 MB. Free memory was 258.5 MB in the beginning and 256.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 12:19:41,749 INFO ]: Boogie Preprocessor took 40.52 ms. Allocated memory is still 304.1 MB. Free memory was 256.5 MB in the beginning and 254.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 12:19:41,750 INFO ]: RCFGBuilder took 360.97 ms. Allocated memory is still 304.1 MB. Free memory was 254.5 MB in the beginning and 244.5 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. [2018-06-22 12:19:41,750 INFO ]: TraceAbstraction took 58184.41 ms. Allocated memory was 304.1 MB in the beginning and 660.6 MB in the end (delta: 356.5 MB). Free memory was 242.5 MB in the beginning and 357.9 MB in the end (delta: -115.4 MB). Peak memory consumption was 241.2 MB. Max. memory is 3.6 GB. [2018-06-22 12:19:41,753 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 304.1 MB. Free memory is still 268.6 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 50.04 ms. Allocated memory is still 304.1 MB. Free memory was 258.5 MB in the beginning and 256.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 40.52 ms. Allocated memory is still 304.1 MB. Free memory was 256.5 MB in the beginning and 254.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 360.97 ms. Allocated memory is still 304.1 MB. Free memory was 254.5 MB in the beginning and 244.5 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 58184.41 ms. Allocated memory was 304.1 MB in the beginning and 660.6 MB in the end (delta: 356.5 MB). Free memory was 242.5 MB in the beginning and 357.9 MB in the end (delta: -115.4 MB). Peak memory consumption was 241.2 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was constructing difference of abstraction (308states) and interpolant automaton (currently 31 states, 39 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 24. - StatisticsResult: Ultimate Automizer benchmark data CFG has 8 procedures, 45 locations, 1 error locations. TIMEOUT Result, 58.1s OverallTime, 18 OverallIterations, 36 TraceHistogramMax, 38.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 773 SDtfs, 603 SDslu, 6436 SDs, 0 SdLazy, 12038 SolverSat, 2081 SolverUnsat, 17 SolverUnknown, 0 SolverNotchecked, 19.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 2003 GetRequests, 1363 SyntacticMatches, 38 SemanticMatches, 601 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3892 ImplicationChecksByTransitivity, 31.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=3112occurred in iteration=13, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 1.3s AutomataMinimizationTime, 17 MinimizatonAttempts, 2458 StatesRemovedByMinimization, 16 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 1.0s SatisfiabilityAnalysisTime, 16.3s InterpolantComputationTime, 2919 NumberOfCodeBlocks, 2831 NumberOfCodeBlocksAsserted, 79 NumberOfCheckSat, 2884 ConstructedInterpolants, 71 QuantifiedInterpolants, 762352 SizeOfPredicates, 185 NumberOfNonLiveVariables, 5682 ConjunctsInSsa, 506 ConjunctsInUnsatCore, 35 InterpolantComputations, 2 PerfectInterpolantSequences, 16735/21084 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/rec__triangular.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_12-19-41-847.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/rec__triangular.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_12-19-41-847.csv Completed graceful shutdown