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/vmt-chc-benchmarks/ctigar/down.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:01:27,693 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:01:27,695 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:01:27,707 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:01:27,707 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:01:27,708 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:01:27,709 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:01:27,713 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:01:27,714 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:01:27,716 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:01:27,717 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:01:27,717 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:01:27,718 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:01:27,719 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:01:27,719 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:01:27,723 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:01:27,725 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:01:27,727 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:01:27,728 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:01:27,729 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:01:27,730 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:01:27,732 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:01:27,733 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:01:27,733 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:01:27,734 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:01:27,734 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:01:27,735 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:01:27,736 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:01:27,737 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:01:27,737 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:01:27,738 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:01:27,738 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:01:27,738 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:01:27,739 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:01:27,740 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:01:27,740 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 15:01:27,753 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:01:27,753 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:01:27,753 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:01:27,753 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:01:27,754 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:01:27,755 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:01:27,755 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:01:27,755 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:01:27,755 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:01:27,755 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:01:27,756 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:01:27,756 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:01:27,756 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:01:27,756 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:01:27,756 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:01:27,757 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:01:27,757 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:01:27,757 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:01:27,757 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:01:27,758 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:01:27,759 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:01:27,814 INFO ]: Repository-Root is: /tmp [2018-06-22 15:01:27,829 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:01:27,834 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:01:27,836 INFO ]: Initializing SmtParser... [2018-06-22 15:01:27,836 INFO ]: SmtParser initialized [2018-06-22 15:01:27,837 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/down.c.smt2 [2018-06-22 15:01:27,838 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 15:01:27,925 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/down.c.smt2 unknown [2018-06-22 15:01:28,150 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/down.c.smt2 [2018-06-22 15:01:28,155 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:01:28,161 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:01:28,161 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:01:28,161 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:01:28,161 INFO ]: ChcToBoogie initialized [2018-06-22 15:01:28,165 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:01:28" (1/1) ... [2018-06-22 15:01:28,212 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:28 Unit [2018-06-22 15:01:28,212 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:01:28,215 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:01:28,215 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:01:28,215 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:01:28,237 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:28" (1/1) ... [2018-06-22 15:01:28,237 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:28" (1/1) ... [2018-06-22 15:01:28,245 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:28" (1/1) ... [2018-06-22 15:01:28,245 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:28" (1/1) ... [2018-06-22 15:01:28,259 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:28" (1/1) ... [2018-06-22 15:01:28,260 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:28" (1/1) ... [2018-06-22 15:01:28,261 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:28" (1/1) ... [2018-06-22 15:01:28,263 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:01:28,263 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:01:28,263 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:01:28,264 INFO ]: RCFGBuilder initialized [2018-06-22 15:01:28,264 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:28" (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) [2018-06-22 15:01:28,276 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:01:28,276 INFO ]: Found specification of procedure False [2018-06-22 15:01:28,276 INFO ]: Found implementation of procedure False [2018-06-22 15:01:28,276 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:01:28,276 INFO ]: Found specification of procedure state [2018-06-22 15:01:28,276 INFO ]: Found implementation of procedure state [2018-06-22 15:01:28,276 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:01:28,276 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:01:28,276 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:01:28,532 INFO ]: Using library mode [2018-06-22 15:01:28,532 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:01:28 BoogieIcfgContainer [2018-06-22 15:01:28,532 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:01:28,534 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:01:28,534 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:01:28,538 INFO ]: TraceAbstraction initialized [2018-06-22 15:01:28,538 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:01:28" (1/3) ... [2018-06-22 15:01:28,539 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@769ca9f6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:01:28, skipping insertion in model container [2018-06-22 15:01:28,539 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:28" (2/3) ... [2018-06-22 15:01:28,539 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@769ca9f6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:01:28, skipping insertion in model container [2018-06-22 15:01:28,539 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:01:28" (3/3) ... [2018-06-22 15:01:28,541 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:01:28,551 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:01:28,561 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:01:28,597 INFO ]: Using default assertion order modulation [2018-06-22 15:01:28,598 INFO ]: Interprodecural is true [2018-06-22 15:01:28,598 INFO ]: Hoare is false [2018-06-22 15:01:28,598 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:01:28,598 INFO ]: Backedges is TWOTRACK [2018-06-22 15:01:28,598 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:01:28,598 INFO ]: Difference is false [2018-06-22 15:01:28,598 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:01:28,598 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:01:28,612 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:01:28,624 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:01:28,624 INFO ]: Found error trace [2018-06-22 15:01:28,625 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:28,625 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:28,631 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 15:01:28,633 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:28,634 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:28,673 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:28,673 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:01:28,673 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:28,696 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:28,781 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:01:28,783 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:01:28,783 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:01:28,784 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:01:28,798 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:01:28,798 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:01:28,800 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:01:28,865 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:01:28,865 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:01:28,866 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:01:28,866 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:01:28,867 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:01:28,876 INFO ]: With dead ends: 13 [2018-06-22 15:01:28,876 INFO ]: Without dead ends: 13 [2018-06-22 15:01:28,877 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:01:28,890 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:01:28,920 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:01:28,921 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:01:28,922 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:01:28,923 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:01:28,924 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:01:28,924 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:01:28,924 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:01:28,924 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:01:28,925 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:01:28,925 INFO ]: Found error trace [2018-06-22 15:01:28,925 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:28,925 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:28,926 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 15:01:28,926 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:28,926 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:28,927 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:28,927 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:01:28,927 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:28,966 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:29,176 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:01:29,176 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:01:29,176 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 15:01:29,183 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:01:29,211 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:29,220 INFO ]: Computing forward predicates... [2018-06-22 15:01:29,671 WARN ]: Spent 154.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 15:01:29,882 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:01:29,914 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:01:29,915 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 15:01:29,915 INFO ]: Interpolant automaton has 9 states [2018-06-22 15:01:29,915 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 15:01:29,915 INFO ]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-22 15:01:29,916 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 15:01:30,147 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:01:30,147 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:01:30,147 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:01:30,147 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 15:01:30,148 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:01:30,148 INFO ]: With dead ends: 15 [2018-06-22 15:01:30,148 INFO ]: Without dead ends: 15 [2018-06-22 15:01:30,149 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:01:30,149 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:01:30,152 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:01:30,152 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:01:30,152 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:01:30,153 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:01:30,153 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:01:30,153 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:01:30,153 INFO ]: Interpolant automaton has 9 states. [2018-06-22 15:01:30,153 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:01:30,153 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:01:30,153 INFO ]: Found error trace [2018-06-22 15:01:30,153 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:30,154 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:30,154 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 15:01:30,154 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:30,154 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:30,155 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:30,155 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:01:30,155 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:30,206 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:30,436 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:01:30,436 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:01:30,436 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 15:01:30,447 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:01:30,485 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:01:30,485 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:30,510 INFO ]: Computing forward predicates... [2018-06-22 15:01:30,971 WARN ]: Spent 277.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 15:01:31,073 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:01:31,096 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:01:31,096 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:01:31,096 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:01:31,097 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:01:31,097 INFO ]: CoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:01:31,097 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:01:31,594 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:01:31,595 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:01:31,595 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:01:31,595 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:01:31,595 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:01:31,596 INFO ]: With dead ends: 17 [2018-06-22 15:01:31,596 INFO ]: Without dead ends: 17 [2018-06-22 15:01:31,597 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=53, Invalid=157, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:01:31,597 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:01:31,600 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:01:31,600 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:01:31,600 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:01:31,600 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:01:31,600 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:01:31,600 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:01:31,600 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:01:31,601 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:01:31,601 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:01:31,601 INFO ]: Found error trace [2018-06-22 15:01:31,601 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:31,601 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:31,602 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 15:01:31,602 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:31,602 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:31,602 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:31,602 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:01:31,602 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:31,633 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:32,008 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:01:32,008 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:01:32,008 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 15:01:32,014 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:01:32,055 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:01:32,055 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:32,058 INFO ]: Computing forward predicates... [2018-06-22 15:01:32,564 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:01:32,591 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:01:32,592 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 12 [2018-06-22 15:01:32,592 INFO ]: Interpolant automaton has 12 states [2018-06-22 15:01:32,592 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 15:01:32,592 INFO ]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:01:32,592 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 12 states. [2018-06-22 15:01:32,946 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:01:32,946 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:01:32,947 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:01:32,947 INFO ]: Start accepts. Automaton has 12 states. Word has length 21 [2018-06-22 15:01:32,947 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:01:32,948 INFO ]: With dead ends: 19 [2018-06-22 15:01:32,948 INFO ]: Without dead ends: 19 [2018-06-22 15:01:32,948 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 18 SyntacticMatches, 2 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=66, Invalid=174, Unknown=0, NotChecked=0, Total=240 [2018-06-22 15:01:32,948 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:01:32,951 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:01:32,951 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:01:32,952 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:01:32,952 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:01:32,952 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:01:32,952 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:01:32,952 INFO ]: Interpolant automaton has 12 states. [2018-06-22 15:01:32,952 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:01:32,953 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:01:32,953 INFO ]: Found error trace [2018-06-22 15:01:32,953 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:32,953 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:32,953 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 15:01:32,953 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:32,953 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:32,954 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:32,954 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:01:32,954 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:32,987 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:33,256 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:01:33,256 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:01:33,256 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 15:01:33,275 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:01:33,320 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:01:33,320 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:33,324 INFO ]: Computing forward predicates... [2018-06-22 15:01:33,705 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:01:33,727 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:01:33,727 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 16 [2018-06-22 15:01:33,727 INFO ]: Interpolant automaton has 16 states [2018-06-22 15:01:33,727 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 15:01:33,727 INFO ]: CoverageRelationStatistics Valid=39, Invalid=201, Unknown=0, NotChecked=0, Total=240 [2018-06-22 15:01:33,728 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 16 states. [2018-06-22 15:01:34,023 WARN ]: Spent 152.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 38 [2018-06-22 15:01:34,378 WARN ]: Spent 171.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 28 [2018-06-22 15:01:34,527 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:01:34,527 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:01:34,532 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:01:34,532 INFO ]: Start accepts. Automaton has 16 states. Word has length 25 [2018-06-22 15:01:34,532 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:01:34,533 INFO ]: With dead ends: 21 [2018-06-22 15:01:34,533 INFO ]: Without dead ends: 21 [2018-06-22 15:01:34,533 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 20 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 50 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=95, Invalid=367, Unknown=0, NotChecked=0, Total=462 [2018-06-22 15:01:34,534 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:01:34,536 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:01:34,536 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:01:34,537 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:01:34,537 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:01:34,537 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:01:34,537 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:01:34,537 INFO ]: Interpolant automaton has 16 states. [2018-06-22 15:01:34,537 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:01:34,538 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:01:34,538 INFO ]: Found error trace [2018-06-22 15:01:34,538 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:34,538 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:34,538 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 15:01:34,539 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:34,539 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:34,539 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:34,539 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:01:34,539 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:34,597 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:35,112 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:01:35,112 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:01:35,112 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 15:01:35,118 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:01:35,222 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:01:35,222 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:35,227 INFO ]: Computing forward predicates... [2018-06-22 15:01:42,695 WARN ]: Spent 6.45 s on a formula simplification. DAG size of input: 596 DAG size of output: 54 [2018-06-22 15:01:44,090 WARN ]: Spent 804.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 19 [2018-06-22 15:01:44,899 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:01:44,918 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:01:44,918 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 20 [2018-06-22 15:01:44,918 INFO ]: Interpolant automaton has 20 states [2018-06-22 15:01:44,919 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 15:01:44,919 INFO ]: CoverageRelationStatistics Valid=54, Invalid=326, Unknown=0, NotChecked=0, Total=380 [2018-06-22 15:01:44,919 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 20 states. [2018-06-22 15:01:45,480 WARN ]: Spent 517.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 84 [2018-06-22 15:01:45,645 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 20 [2018-06-22 15:01:45,929 WARN ]: Spent 251.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 38 [2018-06-22 15:01:46,655 WARN ]: Spent 423.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 44 [2018-06-22 15:01:46,884 WARN ]: Spent 205.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 33 [2018-06-22 15:01:47,039 WARN ]: Spent 125.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 23 [2018-06-22 15:01:47,493 WARN ]: Spent 426.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 74 [2018-06-22 15:01:47,559 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:01:47,559 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:01:47,562 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:01:47,562 INFO ]: Start accepts. Automaton has 20 states. Word has length 29 [2018-06-22 15:01:47,563 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:01:47,563 INFO ]: With dead ends: 25 [2018-06-22 15:01:47,563 INFO ]: Without dead ends: 25 [2018-06-22 15:01:47,564 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 22 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 84 ImplicationChecksByTransitivity, 11.3s TimeCoverageRelationStatistics Valid=153, Invalid=549, Unknown=0, NotChecked=0, Total=702 [2018-06-22 15:01:47,564 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:01:47,567 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:01:47,567 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:01:47,568 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:01:47,568 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 29 [2018-06-22 15:01:47,568 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:01:47,568 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:01:47,568 INFO ]: Interpolant automaton has 20 states. [2018-06-22 15:01:47,568 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:01:47,571 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:01:47,571 INFO ]: Found error trace [2018-06-22 15:01:47,571 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:47,571 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:47,571 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 6 times [2018-06-22 15:01:47,571 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:47,571 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:47,572 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:47,572 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:01:47,572 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:47,693 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:48,469 WARN ]: Spent 537.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-22 15:01:48,760 WARN ]: Spent 214.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 22 [2018-06-22 15:01:48,973 WARN ]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2018-06-22 15:01:49,431 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:01:49,431 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:01:49,431 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) [2018-06-22 15:01:49,448 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:01:49,506 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2018-06-22 15:01:49,506 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:49,512 INFO ]: Computing forward predicates... [2018-06-22 15:01:49,970 WARN ]: Spent 348.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 32 [2018-06-22 15:01:50,236 WARN ]: Spent 229.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 25 [2018-06-22 15:01:50,947 WARN ]: Spent 222.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 28 [2018-06-22 15:01:51,374 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:01:51,393 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:01:51,393 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 25 [2018-06-22 15:01:51,393 INFO ]: Interpolant automaton has 25 states [2018-06-22 15:01:51,393 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-22 15:01:51,394 INFO ]: CoverageRelationStatistics Valid=72, Invalid=528, Unknown=0, NotChecked=0, Total=600 [2018-06-22 15:01:51,394 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 25 states. [2018-06-22 15:01:52,021 WARN ]: Spent 586.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 67 [2018-06-22 15:01:52,314 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 36 [2018-06-22 15:01:52,477 WARN ]: Spent 134.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 31 [2018-06-22 15:01:52,659 WARN ]: Spent 154.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 30 [2018-06-22 15:01:52,827 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 25 [2018-06-22 15:01:53,134 WARN ]: Spent 251.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 41 [2018-06-22 15:01:53,483 WARN ]: Spent 281.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 51 [2018-06-22 15:01:53,518 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:01:53,518 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 15:01:53,519 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 15:01:53,519 INFO ]: Start accepts. Automaton has 25 states. Word has length 37 [2018-06-22 15:01:53,519 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:01:53,520 INFO ]: With dead ends: 27 [2018-06-22 15:01:53,520 INFO ]: Without dead ends: 27 [2018-06-22 15:01:53,520 INFO ]: 0 DeclaredPredicates, 62 GetRequests, 28 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 137 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=214, Invalid=842, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 15:01:53,520 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 15:01:53,526 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 15:01:53,526 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 15:01:53,527 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 15:01:53,527 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 15:01:53,527 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:01:53,527 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 15:01:53,527 INFO ]: Interpolant automaton has 25 states. [2018-06-22 15:01:53,527 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 15:01:53,528 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 15:01:53,528 INFO ]: Found error trace [2018-06-22 15:01:53,528 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:53,528 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:53,528 INFO ]: Analyzing trace with hash 1618126293, now seen corresponding path program 7 times [2018-06-22 15:01:53,528 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:53,528 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:53,529 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:53,529 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:01:53,529 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:53,598 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:53,807 WARN ]: Spent 104.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-22 15:01:54,591 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 15:01:54,591 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:01:54,591 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 15:01:54,598 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:01:54,642 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:54,648 INFO ]: Computing forward predicates... [2018-06-22 15:01:58,117 WARN ]: Spent 2.90 s on a formula simplification. DAG size of input: 550 DAG size of output: 47 [2018-06-22 15:01:58,855 WARN ]: Spent 383.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 39 [2018-06-22 15:02:00,859 WARN ]: Spent 1.72 s on a formula simplification. DAG size of input: 251 DAG size of output: 57 [2018-06-22 15:02:01,898 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 15:02:01,917 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:02:01,925 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 32 [2018-06-22 15:02:01,926 INFO ]: Interpolant automaton has 32 states [2018-06-22 15:02:01,926 INFO ]: Constructing interpolant automaton starting with 32 interpolants. [2018-06-22 15:02:01,926 INFO ]: CoverageRelationStatistics Valid=107, Invalid=885, Unknown=0, NotChecked=0, Total=992 [2018-06-22 15:02:01,926 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 32 states. [2018-06-22 15:02:03,016 WARN ]: Spent 1.00 s on a formula simplification. DAG size of input: 161 DAG size of output: 101 [2018-06-22 15:02:03,392 WARN ]: Spent 326.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 21 [2018-06-22 15:02:03,794 WARN ]: Spent 363.00 ms on a formula simplification. DAG size of input: 166 DAG size of output: 40 [2018-06-22 15:02:04,272 WARN ]: Spent 408.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 53 [2018-06-22 15:02:04,723 WARN ]: Spent 408.00 ms on a formula simplification. DAG size of input: 163 DAG size of output: 23 [2018-06-22 15:02:05,292 WARN ]: Spent 501.00 ms on a formula simplification. DAG size of input: 157 DAG size of output: 35 [2018-06-22 15:02:05,841 WARN ]: Spent 503.00 ms on a formula simplification. DAG size of input: 160 DAG size of output: 40 [2018-06-22 15:02:06,537 WARN ]: Spent 641.00 ms on a formula simplification. DAG size of input: 160 DAG size of output: 53 [2018-06-22 15:02:07,472 WARN ]: Spent 887.00 ms on a formula simplification. DAG size of input: 166 DAG size of output: 63 [2018-06-22 15:02:07,526 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:02:07,526 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 15:02:07,527 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 15:02:07,527 INFO ]: Start accepts. Automaton has 32 states. Word has length 41 [2018-06-22 15:02:07,527 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:02:07,528 INFO ]: With dead ends: 29 [2018-06-22 15:02:07,528 INFO ]: Without dead ends: 29 [2018-06-22 15:02:07,528 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 27 SyntacticMatches, 3 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 274 ImplicationChecksByTransitivity, 12.7s TimeCoverageRelationStatistics Valid=309, Invalid=1413, Unknown=0, NotChecked=0, Total=1722 [2018-06-22 15:02:07,529 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 15:02:07,532 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 15:02:07,532 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 15:02:07,533 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 15:02:07,533 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 15:02:07,533 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:02:07,533 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 15:02:07,533 INFO ]: Interpolant automaton has 32 states. [2018-06-22 15:02:07,533 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 15:02:07,534 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 15:02:07,534 INFO ]: Found error trace [2018-06-22 15:02:07,534 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:02:07,534 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:02:07,534 INFO ]: Analyzing trace with hash 996918775, now seen corresponding path program 8 times [2018-06-22 15:02:07,534 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:02:07,534 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:02:07,535 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:02:07,535 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:02:07,535 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:02:07,607 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:02:08,389 WARN ]: Spent 525.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 20 [2018-06-22 15:02:09,213 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 15:02:09,213 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:02:09,213 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 15:02:09,219 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:02:09,298 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:02:09,298 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:02:09,310 INFO ]: Computing forward predicates... [2018-06-22 15:02:09,484 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 19 [2018-06-22 15:02:09,707 WARN ]: Spent 190.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 35 [2018-06-22 15:02:09,885 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 32 [2018-06-22 15:02:10,058 WARN ]: Spent 132.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 25 [2018-06-22 15:02:13,131 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 15:02:13,150 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:02:13,150 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 41 [2018-06-22 15:02:13,150 INFO ]: Interpolant automaton has 41 states [2018-06-22 15:02:13,151 INFO ]: Constructing interpolant automaton starting with 41 interpolants. [2018-06-22 15:02:13,155 INFO ]: CoverageRelationStatistics Valid=138, Invalid=1502, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 15:02:13,155 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 41 states. [2018-06-22 15:02:13,594 WARN ]: Spent 364.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 73 [2018-06-22 15:02:13,811 WARN ]: Spent 132.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 32 [2018-06-22 15:02:14,104 WARN ]: Spent 250.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 39 [2018-06-22 15:02:14,417 WARN ]: Spent 224.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 40 [2018-06-22 15:02:14,644 WARN ]: Spent 183.00 ms on a formula simplification. DAG size of input: 118 DAG size of output: 47 [2018-06-22 15:02:14,909 WARN ]: Spent 225.00 ms on a formula simplification. DAG size of input: 102 DAG size of output: 41 [2018-06-22 15:02:15,202 WARN ]: Spent 249.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 51 [2018-06-22 15:02:15,637 WARN ]: Spent 375.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 47 [2018-06-22 15:02:16,019 WARN ]: Spent 318.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 54 [2018-06-22 15:02:16,374 WARN ]: Spent 304.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 53 [2018-06-22 15:02:16,414 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:02:16,414 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 15:02:16,414 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 15:02:16,414 INFO ]: Start accepts. Automaton has 41 states. Word has length 45 [2018-06-22 15:02:16,414 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:02:16,415 INFO ]: With dead ends: 31 [2018-06-22 15:02:16,415 INFO ]: Without dead ends: 31 [2018-06-22 15:02:16,416 INFO ]: 0 DeclaredPredicates, 76 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 418 ImplicationChecksByTransitivity, 6.3s TimeCoverageRelationStatistics Valid=376, Invalid=2174, Unknown=0, NotChecked=0, Total=2550 [2018-06-22 15:02:16,416 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 15:02:16,419 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 15:02:16,419 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 15:02:16,420 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 15:02:16,420 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 15:02:16,420 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:02:16,420 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 15:02:16,420 INFO ]: Interpolant automaton has 41 states. [2018-06-22 15:02:16,420 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 15:02:16,421 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 15:02:16,422 INFO ]: Found error trace [2018-06-22 15:02:16,422 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:02:16,422 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:02:16,422 INFO ]: Analyzing trace with hash -570306151, now seen corresponding path program 9 times [2018-06-22 15:02:16,422 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:02:16,422 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:02:16,422 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:02:16,422 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:02:16,422 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:02:16,493 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:02:16,862 WARN ]: Spent 120.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 34 [2018-06-22 15:02:17,641 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 15:02:17,641 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:02:17,641 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 15:02:17,647 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:02:17,723 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2018-06-22 15:02:17,723 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:02:17,739 INFO ]: Computing forward predicates... [2018-06-22 15:02:18,666 WARN ]: Spent 727.00 ms on a formula simplification. DAG size of input: 178 DAG size of output: 40 [2018-06-22 15:02:18,826 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 30 [2018-06-22 15:02:19,059 WARN ]: Spent 190.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 35 [2018-06-22 15:02:19,198 WARN ]: Spent 101.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 32 [2018-06-22 15:02:19,501 WARN ]: Spent 250.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 31 [2018-06-22 15:02:19,983 WARN ]: Spent 126.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 39 [2018-06-22 15:02:21,639 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 15:02:21,658 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:02:21,659 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 44 [2018-06-22 15:02:21,659 INFO ]: Interpolant automaton has 44 states [2018-06-22 15:02:21,659 INFO ]: Constructing interpolant automaton starting with 44 interpolants. [2018-06-22 15:02:21,660 INFO ]: CoverageRelationStatistics Valid=149, Invalid=1743, Unknown=0, NotChecked=0, Total=1892 [2018-06-22 15:02:21,660 INFO ]: Start difference. First operand 31 states and 32 transitions. Second operand 44 states. [2018-06-22 15:02:22,372 WARN ]: Spent 640.00 ms on a formula simplification. DAG size of input: 144 DAG size of output: 79 [2018-06-22 15:02:22,659 WARN ]: Spent 233.00 ms on a formula simplification. DAG size of input: 142 DAG size of output: 36 [2018-06-22 15:02:23,038 WARN ]: Spent 333.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 43 [2018-06-22 15:02:23,484 WARN ]: Spent 381.00 ms on a formula simplification. DAG size of input: 150 DAG size of output: 43 [2018-06-22 15:02:23,887 WARN ]: Spent 354.00 ms on a formula simplification. DAG size of input: 150 DAG size of output: 51 [2018-06-22 15:02:24,249 WARN ]: Spent 314.00 ms on a formula simplification. DAG size of input: 150 DAG size of output: 44 [2018-06-22 15:02:24,752 WARN ]: Spent 442.00 ms on a formula simplification. DAG size of input: 151 DAG size of output: 51 [2018-06-22 15:02:25,230 WARN ]: Spent 426.00 ms on a formula simplification. DAG size of input: 151 DAG size of output: 48 [2018-06-22 15:02:25,769 WARN ]: Spent 485.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 53 [2018-06-22 15:02:26,294 WARN ]: Spent 470.00 ms on a formula simplification. DAG size of input: 147 DAG size of output: 45 [2018-06-22 15:02:26,958 WARN ]: Spent 613.00 ms on a formula simplification. DAG size of input: 148 DAG size of output: 60 [2018-06-22 15:02:27,003 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:02:27,003 INFO ]: Finished difference Result 33 states and 34 transitions. [2018-06-22 15:02:27,004 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 15:02:27,004 INFO ]: Start accepts. Automaton has 44 states. Word has length 49 [2018-06-22 15:02:27,004 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:02:27,004 INFO ]: With dead ends: 33 [2018-06-22 15:02:27,004 INFO ]: Without dead ends: 33 [2018-06-22 15:02:27,005 INFO ]: 0 DeclaredPredicates, 83 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 490 ImplicationChecksByTransitivity, 8.9s TimeCoverageRelationStatistics Valid=440, Invalid=2530, Unknown=0, NotChecked=0, Total=2970 [2018-06-22 15:02:27,005 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-22 15:02:27,009 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 33. [2018-06-22 15:02:27,009 INFO ]: Start removeUnreachable. Operand 33 states. [2018-06-22 15:02:27,010 INFO ]: Finished removeUnreachable. Reduced from 33 states to 33 states and 34 transitions. [2018-06-22 15:02:27,010 INFO ]: Start accepts. Automaton has 33 states and 34 transitions. Word has length 49 [2018-06-22 15:02:27,010 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:02:27,010 INFO ]: Abstraction has 33 states and 34 transitions. [2018-06-22 15:02:27,010 INFO ]: Interpolant automaton has 44 states. [2018-06-22 15:02:27,010 INFO ]: Start isEmpty. Operand 33 states and 34 transitions. [2018-06-22 15:02:27,011 INFO ]: Finished isEmpty. Found accepting run of length 54 [2018-06-22 15:02:27,011 INFO ]: Found error trace [2018-06-22 15:02:27,011 INFO ]: trace histogram [12, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:02:27,011 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:02:27,011 INFO ]: Analyzing trace with hash 1955719355, now seen corresponding path program 10 times [2018-06-22 15:02:27,011 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:02:27,011 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:02:27,012 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:02:27,012 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:02:27,012 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:02:27,121 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:02:27,501 WARN ]: Spent 143.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-06-22 15:02:28,357 INFO ]: Checked inductivity of 253 backedges. 0 proven. 187 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-06-22 15:02:28,357 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:02:28,357 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 15:02:28,364 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:02:28,422 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:02:28,422 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:02:28,429 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 15:02:28,876 WARN ]: Removed 5 from assertion stack [2018-06-22 15:02:28,876 INFO ]: Timeout while computing interpolants [2018-06-22 15:02:29,076 WARN ]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:02:29,076 WARN ]: Verification canceled [2018-06-22 15:02:29,080 WARN ]: Timeout [2018-06-22 15:02:29,080 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:02:29 BoogieIcfgContainer [2018-06-22 15:02:29,080 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:02:29,080 INFO ]: Toolchain (without parser) took 60925.23 ms. Allocated memory was 304.1 MB in the beginning and 793.2 MB in the end (delta: 489.2 MB). Free memory was 256.5 MB in the beginning and 731.0 MB in the end (delta: -474.6 MB). Peak memory consumption was 575.7 MB. Max. memory is 3.6 GB. [2018-06-22 15:02:29,081 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 304.1 MB. Free memory is still 266.6 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:02:29,081 INFO ]: ChcToBoogie took 51.31 ms. Allocated memory is still 304.1 MB. Free memory is still 254.5 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:02:29,081 INFO ]: Boogie Preprocessor took 48.16 ms. Allocated memory is still 304.1 MB. Free memory was 254.5 MB in the beginning and 252.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 15:02:29,081 INFO ]: RCFGBuilder took 268.98 ms. Allocated memory is still 304.1 MB. Free memory was 252.5 MB in the beginning and 244.5 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:02:29,082 INFO ]: TraceAbstraction took 60545.88 ms. Allocated memory was 304.1 MB in the beginning and 793.2 MB in the end (delta: 489.2 MB). Free memory was 242.5 MB in the beginning and 731.0 MB in the end (delta: -488.5 MB). Peak memory consumption was 561.8 MB. Max. memory is 3.6 GB. [2018-06-22 15:02:29,084 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.06 ms. Allocated memory is still 304.1 MB. Free memory is still 266.6 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 51.31 ms. Allocated memory is still 304.1 MB. Free memory is still 254.5 MB. There was no memory consumed. Max. memory is 3.6 GB. * Boogie Preprocessor took 48.16 ms. Allocated memory is still 304.1 MB. Free memory was 254.5 MB in the beginning and 252.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 268.98 ms. Allocated memory is still 304.1 MB. Free memory was 252.5 MB in the beginning and 244.5 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 60545.88 ms. Allocated memory was 304.1 MB in the beginning and 793.2 MB in the end (delta: 489.2 MB). Free memory was 242.5 MB in the beginning and 731.0 MB in the end (delta: -488.5 MB). Peak memory consumption was 561.8 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 analyzing trace of length 54 with TraceHistMax 12, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 71. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 60.4s OverallTime, 11 OverallIterations, 12 TraceHistogramMax, 20.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 137 SDtfs, 687 SDslu, 1015 SDs, 0 SdLazy, 906 SolverSat, 808 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 469 GetRequests, 200 SyntacticMatches, 12 SemanticMatches, 257 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1515 ImplicationChecksByTransitivity, 48.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=33occurred in iteration=10, 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: 0.0s AutomataMinimizationTime, 10 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.9s SatisfiabilityAnalysisTime, 35.8s InterpolantComputationTime, 563 NumberOfCodeBlocks, 563 NumberOfCodeBlocksAsserted, 46 NumberOfCheckSat, 544 ConstructedInterpolants, 0 QuantifiedInterpolants, 1019828 SizeOfPredicates, 564 NumberOfNonLiveVariables, 1954 ConjunctsInSsa, 475 ConjunctsInUnsatCore, 19 InterpolantComputations, 1 PerfectInterpolantSequences, 398/1494 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/down.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-02-29-095.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/down.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-02-29-095.csv Completed graceful shutdown