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/lifnatprime.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:11:26,062 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:11:26,064 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:11:26,077 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:11:26,077 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:11:26,079 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:11:26,080 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:11:26,082 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:11:26,083 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:11:26,084 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:11:26,085 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:11:26,085 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:11:26,086 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:11:26,089 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:11:26,090 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:11:26,091 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:11:26,103 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:11:26,107 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:11:26,108 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:11:26,109 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:11:26,110 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:11:26,112 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:11:26,113 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:11:26,113 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:11:26,114 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:11:26,114 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:11:26,119 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:11:26,119 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:11:26,120 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:11:26,121 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:11:26,121 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:11:26,124 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:11:26,125 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:11:26,125 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:11:26,126 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:11:26,126 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:11:26,146 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:11:26,146 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:11:26,147 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:11:26,147 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:11:26,148 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:11:26,149 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:11:26,149 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:11:26,149 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:11:26,149 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:11:26,149 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:11:26,150 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:11:26,150 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:11:26,150 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:11:26,150 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:11:26,150 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:11:26,151 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:11:26,151 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:11:26,151 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:11:26,151 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:11:26,153 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:11:26,153 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:11:26,201 INFO ]: Repository-Root is: /tmp [2018-06-22 15:11:26,216 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:11:26,222 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:11:26,223 INFO ]: Initializing SmtParser... [2018-06-22 15:11:26,223 INFO ]: SmtParser initialized [2018-06-22 15:11:26,224 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/lifnatprime.c.smt2 [2018-06-22 15:11:26,225 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:11:26,305 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/lifnatprime.c.smt2 unknown [2018-06-22 15:11:26,767 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/lifnatprime.c.smt2 [2018-06-22 15:11:26,771 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:11:26,778 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:11:26,779 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:11:26,779 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:11:26,779 INFO ]: ChcToBoogie initialized [2018-06-22 15:11:26,782 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:11:26" (1/1) ... [2018-06-22 15:11:26,834 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:11:26 Unit [2018-06-22 15:11:26,834 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:11:26,835 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:11:26,835 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:11:26,835 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:11:26,857 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:11:26" (1/1) ... [2018-06-22 15:11:26,857 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:11:26" (1/1) ... [2018-06-22 15:11:26,879 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:11:26" (1/1) ... [2018-06-22 15:11:26,880 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:11:26" (1/1) ... [2018-06-22 15:11:26,906 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:11:26" (1/1) ... [2018-06-22 15:11:26,907 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:11:26" (1/1) ... [2018-06-22 15:11:26,911 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:11:26" (1/1) ... [2018-06-22 15:11:26,923 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:11:26,924 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:11:26,924 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:11:26,924 INFO ]: RCFGBuilder initialized [2018-06-22 15:11:26,924 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:11:26" (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:11:26,948 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:11:26,948 INFO ]: Found specification of procedure False [2018-06-22 15:11:26,948 INFO ]: Found implementation of procedure False [2018-06-22 15:11:26,948 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:11:26,949 INFO ]: Found specification of procedure state [2018-06-22 15:11:26,949 INFO ]: Found implementation of procedure state [2018-06-22 15:11:26,949 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:11:26,949 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:11:26,949 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:11:27,386 INFO ]: Using library mode [2018-06-22 15:11:27,387 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:11:27 BoogieIcfgContainer [2018-06-22 15:11:27,387 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:11:27,389 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:11:27,389 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:11:27,392 INFO ]: TraceAbstraction initialized [2018-06-22 15:11:27,392 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:11:26" (1/3) ... [2018-06-22 15:11:27,393 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3ae177e5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:11:27, skipping insertion in model container [2018-06-22 15:11:27,393 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:11:26" (2/3) ... [2018-06-22 15:11:27,393 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3ae177e5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:11:27, skipping insertion in model container [2018-06-22 15:11:27,393 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:11:27" (3/3) ... [2018-06-22 15:11:27,395 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:11:27,404 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:11:27,415 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:11:27,465 INFO ]: Using default assertion order modulation [2018-06-22 15:11:27,466 INFO ]: Interprodecural is true [2018-06-22 15:11:27,466 INFO ]: Hoare is false [2018-06-22 15:11:27,466 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:11:27,466 INFO ]: Backedges is TWOTRACK [2018-06-22 15:11:27,466 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:11:27,466 INFO ]: Difference is false [2018-06-22 15:11:27,466 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:11:27,466 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:11:27,484 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:11:27,502 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:11:27,502 INFO ]: Found error trace [2018-06-22 15:11:27,503 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:11:27,503 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:11:27,509 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 15:11:27,511 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:11:27,511 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:11:27,559 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:27,559 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:11:27,559 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:27,602 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:27,799 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:11:27,802 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:11:27,803 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:11:27,804 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:11:27,821 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:11:27,821 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:11:27,823 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:11:27,946 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:11:27,946 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:11:27,947 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:11:27,948 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:11:27,949 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:11:27,963 INFO ]: With dead ends: 13 [2018-06-22 15:11:27,963 INFO ]: Without dead ends: 13 [2018-06-22 15:11:27,967 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:11:28,001 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:11:28,040 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:11:28,042 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:11:28,042 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:11:28,043 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:11:28,043 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:11:28,043 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:11:28,043 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:11:28,043 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:11:28,045 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:11:28,045 INFO ]: Found error trace [2018-06-22 15:11:28,045 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:11:28,045 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:11:28,045 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 15:11:28,045 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:11:28,045 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:11:28,046 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:28,046 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:11:28,046 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:28,197 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:28,755 WARN ]: Spent 320.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 16 [2018-06-22 15:11:28,848 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:11:28,848 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:11:28,848 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:11:28,857 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:11:28,930 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:28,943 INFO ]: Computing forward predicates... [2018-06-22 15:11:29,255 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 9 [2018-06-22 15:11:29,757 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:11:29,780 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:11:29,780 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 15:11:29,780 INFO ]: Interpolant automaton has 9 states [2018-06-22 15:11:29,781 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 15:11:29,781 INFO ]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-06-22 15:11:29,781 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 15:11:29,969 WARN ]: Spent 178.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-22 15:11:30,192 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:11:30,193 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:11:30,193 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:11:30,193 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 15:11:30,193 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:11:30,194 INFO ]: With dead ends: 15 [2018-06-22 15:11:30,194 INFO ]: Without dead ends: 15 [2018-06-22 15:11:30,195 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:11:30,195 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:11:30,198 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:11:30,198 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:11:30,198 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:11:30,199 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:11:30,199 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:11:30,199 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:11:30,199 INFO ]: Interpolant automaton has 9 states. [2018-06-22 15:11:30,199 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:11:30,199 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:11:30,199 INFO ]: Found error trace [2018-06-22 15:11:30,199 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:11:30,199 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:11:30,200 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 15:11:30,200 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:11:30,200 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:11:30,201 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:30,201 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:11:30,201 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:30,303 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:30,582 WARN ]: Spent 108.00 ms on a formula simplification. DAG size of input: 4 DAG size of output: 1 [2018-06-22 15:11:31,550 WARN ]: Spent 922.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 16 [2018-06-22 15:11:31,733 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:11:31,733 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:11:31,733 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:11:31,740 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:11:31,837 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:11:31,837 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:31,843 INFO ]: Computing forward predicates... [2018-06-22 15:11:32,147 WARN ]: Spent 151.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 22 [2018-06-22 15:11:32,270 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:11:32,303 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:11:32,303 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:11:32,304 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:11:32,304 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:11:32,304 INFO ]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:11:32,304 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:11:32,459 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 33 [2018-06-22 15:11:32,706 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 28 [2018-06-22 15:11:32,727 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:11:32,727 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:11:32,727 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:11:32,727 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:11:32,727 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:11:32,728 INFO ]: With dead ends: 17 [2018-06-22 15:11:32,728 INFO ]: Without dead ends: 17 [2018-06-22 15:11:32,728 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2018-06-22 15:11:32,728 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:11:32,731 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:11:32,731 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:11:32,732 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:11:32,732 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:11:32,732 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:11:32,732 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:11:32,732 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:11:32,732 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:11:32,732 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:11:32,732 INFO ]: Found error trace [2018-06-22 15:11:32,733 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:11:32,733 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:11:32,733 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 15:11:32,733 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:11:32,733 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:11:32,734 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:32,734 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:11:32,734 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:32,836 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:33,155 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 4 DAG size of output: 1 [2018-06-22 15:11:33,424 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:11:33,425 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:11:33,425 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:11:33,437 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:11:33,572 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:11:33,572 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:33,577 INFO ]: Computing forward predicates... [2018-06-22 15:11:34,036 WARN ]: Spent 227.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 7 [2018-06-22 15:11:34,215 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 18 [2018-06-22 15:11:34,458 WARN ]: Spent 209.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 28 [2018-06-22 15:11:34,617 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:11:34,637 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:11:34,637 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2018-06-22 15:11:34,637 INFO ]: Interpolant automaton has 15 states [2018-06-22 15:11:34,637 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 15:11:34,637 INFO ]: CoverageRelationStatistics Valid=42, Invalid=168, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:11:34,638 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 15 states. [2018-06-22 15:11:34,810 WARN ]: Spent 150.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 40 [2018-06-22 15:11:35,003 WARN ]: Spent 171.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 22 [2018-06-22 15:11:35,122 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 32 [2018-06-22 15:11:35,317 WARN ]: Spent 170.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 36 [2018-06-22 15:11:35,340 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:11:35,340 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:11:35,341 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:11:35,341 INFO ]: Start accepts. Automaton has 15 states. Word has length 21 [2018-06-22 15:11:35,341 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:11:35,342 INFO ]: With dead ends: 19 [2018-06-22 15:11:35,342 INFO ]: Without dead ends: 19 [2018-06-22 15:11:35,342 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 16 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=82, Invalid=260, Unknown=0, NotChecked=0, Total=342 [2018-06-22 15:11:35,342 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:11:35,344 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:11:35,344 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:11:35,345 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:11:35,345 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:11:35,345 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:11:35,345 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:11:35,345 INFO ]: Interpolant automaton has 15 states. [2018-06-22 15:11:35,345 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:11:35,346 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:11:35,346 INFO ]: Found error trace [2018-06-22 15:11:35,346 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:11:35,346 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:11:35,346 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-22 15:11:35,346 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:11:35,346 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:11:35,347 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:35,347 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:11:35,347 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:35,441 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:35,978 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:11:35,978 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:11:35,978 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:11:35,986 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:11:36,119 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:11:36,119 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:36,128 INFO ]: Computing forward predicates... [2018-06-22 15:11:36,551 WARN ]: Spent 312.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 28 [2018-06-22 15:11:36,762 WARN ]: Spent 132.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 28 [2018-06-22 15:11:37,200 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:11:37,221 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:11:37,227 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 16 [2018-06-22 15:11:37,227 INFO ]: Interpolant automaton has 16 states [2018-06-22 15:11:37,227 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 15:11:37,227 INFO ]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2018-06-22 15:11:37,227 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 16 states. [2018-06-22 15:11:37,739 WARN ]: Spent 468.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 40 [2018-06-22 15:11:37,923 WARN ]: Spent 153.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 29 [2018-06-22 15:11:38,104 WARN ]: Spent 165.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 31 [2018-06-22 15:11:38,491 WARN ]: Spent 370.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 33 [2018-06-22 15:11:38,849 WARN ]: Spent 340.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 38 [2018-06-22 15:11:38,877 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:11:38,877 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:11:38,883 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:11:38,883 INFO ]: Start accepts. Automaton has 16 states. Word has length 25 [2018-06-22 15:11:38,883 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:11:38,884 INFO ]: With dead ends: 21 [2018-06-22 15:11:38,884 INFO ]: Without dead ends: 21 [2018-06-22 15:11:38,884 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 19 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=96, Invalid=324, Unknown=0, NotChecked=0, Total=420 [2018-06-22 15:11:38,884 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:11:38,887 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:11:38,887 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:11:38,888 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:11:38,888 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:11:38,888 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:11:38,888 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:11:38,888 INFO ]: Interpolant automaton has 16 states. [2018-06-22 15:11:38,888 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:11:38,889 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:11:38,889 INFO ]: Found error trace [2018-06-22 15:11:38,889 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:11:38,889 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:11:38,889 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-22 15:11:38,889 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:11:38,889 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:11:38,890 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:38,890 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:11:38,890 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:39,004 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:39,276 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 4 DAG size of output: 1 [2018-06-22 15:11:39,514 WARN ]: Spent 188.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-06-22 15:11:39,795 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:11:39,796 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:11:39,796 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:11:39,803 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:11:39,958 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:11:39,958 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:39,965 INFO ]: Computing forward predicates... [2018-06-22 15:11:40,436 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 29 [2018-06-22 15:11:42,513 WARN ]: Spent 564.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-22 15:11:43,374 WARN ]: Spent 353.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-22 15:11:43,395 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:11:43,429 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:11:43,429 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 19 [2018-06-22 15:11:43,429 INFO ]: Interpolant automaton has 19 states [2018-06-22 15:11:43,429 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 15:11:43,429 INFO ]: CoverageRelationStatistics Valid=54, Invalid=288, Unknown=0, NotChecked=0, Total=342 [2018-06-22 15:11:43,430 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 19 states. [2018-06-22 15:11:43,955 WARN ]: Spent 301.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 44 [2018-06-22 15:11:44,099 WARN ]: Spent 114.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 27 [2018-06-22 15:11:44,300 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 30 [2018-06-22 15:11:44,547 WARN ]: Spent 226.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 35 [2018-06-22 15:11:44,837 WARN ]: Spent 223.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 33 [2018-06-22 15:11:45,093 WARN ]: Spent 228.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 40 [2018-06-22 15:11:45,120 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:11:45,120 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:11:45,129 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:11:45,129 INFO ]: Start accepts. Automaton has 19 states. Word has length 29 [2018-06-22 15:11:45,129 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:11:45,130 INFO ]: With dead ends: 23 [2018-06-22 15:11:45,130 INFO ]: Without dead ends: 23 [2018-06-22 15:11:45,130 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 21 SyntacticMatches, 4 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 95 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=127, Invalid=473, Unknown=0, NotChecked=0, Total=600 [2018-06-22 15:11:45,130 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:11:45,133 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:11:45,133 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:11:45,134 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:11:45,134 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:11:45,134 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:11:45,134 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:11:45,134 INFO ]: Interpolant automaton has 19 states. [2018-06-22 15:11:45,134 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:11:45,135 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:11:45,135 INFO ]: Found error trace [2018-06-22 15:11:45,135 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:11:45,135 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:11:45,135 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-22 15:11:45,136 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:11:45,136 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:11:45,136 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:45,136 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:11:45,136 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:45,253 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:45,531 WARN ]: Spent 109.00 ms on a formula simplification. DAG size of input: 4 DAG size of output: 1 [2018-06-22 15:11:45,679 WARN ]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-06-22 15:11:46,076 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:11:46,076 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:11:46,076 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 15:11:46,084 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:11:46,285 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:11:46,286 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:46,299 INFO ]: Computing forward predicates... [2018-06-22 15:11:46,987 WARN ]: Spent 334.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 25 [2018-06-22 15:11:48,493 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:11:48,523 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:11:48,523 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 19 [2018-06-22 15:11:48,524 INFO ]: Interpolant automaton has 19 states [2018-06-22 15:11:48,524 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 15:11:48,524 INFO ]: CoverageRelationStatistics Valid=51, Invalid=291, Unknown=0, NotChecked=0, Total=342 [2018-06-22 15:11:48,524 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 19 states. [2018-06-22 15:11:48,945 WARN ]: Spent 353.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 42 [2018-06-22 15:11:49,225 WARN ]: Spent 139.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 29 [2018-06-22 15:11:49,445 WARN ]: Spent 200.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 33 [2018-06-22 15:11:49,636 WARN ]: Spent 171.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 33 [2018-06-22 15:11:49,774 WARN ]: Spent 116.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 32 [2018-06-22 15:11:50,026 WARN ]: Spent 231.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 33 [2018-06-22 15:11:50,134 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:11:50,134 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:11:50,135 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:11:50,135 INFO ]: Start accepts. Automaton has 19 states. Word has length 33 [2018-06-22 15:11:50,136 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:11:50,136 INFO ]: With dead ends: 25 [2018-06-22 15:11:50,136 INFO ]: Without dead ends: 25 [2018-06-22 15:11:50,137 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 25 SyntacticMatches, 6 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 96 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=134, Invalid=516, Unknown=0, NotChecked=0, Total=650 [2018-06-22 15:11:50,137 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:11:50,140 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:11:50,140 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:11:50,141 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:11:50,141 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:11:50,141 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:11:50,141 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:11:50,141 INFO ]: Interpolant automaton has 19 states. [2018-06-22 15:11:50,141 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:11:50,142 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:11:50,142 INFO ]: Found error trace [2018-06-22 15:11:50,142 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:11:50,142 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:11:50,142 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 7 times [2018-06-22 15:11:50,142 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:11:50,142 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:11:50,143 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:50,143 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:11:50,143 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:50,281 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:50,575 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 4 DAG size of output: 1 [2018-06-22 15:11:50,951 WARN ]: Spent 320.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 15 [2018-06-22 15:11:51,441 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:11:51,442 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:11:51,442 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:11:51,448 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:11:51,651 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:51,664 INFO ]: Computing forward predicates... [2018-06-22 15:11:52,434 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:11:52,454 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:11:52,454 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 21 [2018-06-22 15:11:52,455 INFO ]: Interpolant automaton has 21 states [2018-06-22 15:11:52,455 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 15:11:52,455 INFO ]: CoverageRelationStatistics Valid=60, Invalid=360, Unknown=0, NotChecked=0, Total=420 [2018-06-22 15:11:52,455 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 21 states. [2018-06-22 15:11:52,718 WARN ]: Spent 232.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 43 [2018-06-22 15:11:52,867 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 24 [2018-06-22 15:11:53,047 WARN ]: Spent 160.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 30 [2018-06-22 15:11:53,274 WARN ]: Spent 183.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 34 [2018-06-22 15:11:53,470 WARN ]: Spent 175.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 34 [2018-06-22 15:11:53,610 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 33 [2018-06-22 15:11:53,819 WARN ]: Spent 156.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 30 [2018-06-22 15:11:54,162 WARN ]: Spent 319.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 37 [2018-06-22 15:11:54,236 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:11:54,236 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 15:11:54,236 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 15:11:54,236 INFO ]: Start accepts. Automaton has 21 states. Word has length 37 [2018-06-22 15:11:54,236 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:11:54,237 INFO ]: With dead ends: 27 [2018-06-22 15:11:54,237 INFO ]: Without dead ends: 27 [2018-06-22 15:11:54,237 INFO ]: 0 DeclaredPredicates, 62 GetRequests, 27 SyntacticMatches, 8 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 125 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=167, Invalid=645, Unknown=0, NotChecked=0, Total=812 [2018-06-22 15:11:54,237 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 15:11:54,241 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 15:11:54,241 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 15:11:54,241 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 15:11:54,241 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 15:11:54,242 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:11:54,242 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 15:11:54,242 INFO ]: Interpolant automaton has 21 states. [2018-06-22 15:11:54,242 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 15:11:54,243 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 15:11:54,243 INFO ]: Found error trace [2018-06-22 15:11:54,243 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:11:54,243 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:11:54,243 INFO ]: Analyzing trace with hash -544278078, now seen corresponding path program 8 times [2018-06-22 15:11:54,243 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:11:54,243 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:11:54,243 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:54,243 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:11:54,244 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:54,367 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:55,273 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:11:55,273 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:11:55,273 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:11:55,279 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:11:55,493 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:11:55,493 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:55,505 INFO ]: Computing forward predicates... [2018-06-22 15:12:03,028 WARN ]: Spent 6.90 s on a formula simplification. DAG size of input: 737 DAG size of output: 63 [2018-06-22 15:12:05,855 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:12:05,875 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:12:05,875 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 23 [2018-06-22 15:12:05,879 INFO ]: Interpolant automaton has 23 states [2018-06-22 15:12:05,879 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 15:12:05,880 INFO ]: CoverageRelationStatistics Valid=60, Invalid=446, Unknown=0, NotChecked=0, Total=506 [2018-06-22 15:12:05,881 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 23 states. [2018-06-22 15:12:06,495 WARN ]: Spent 501.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 83 [2018-06-22 15:12:06,862 WARN ]: Spent 282.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 63 [2018-06-22 15:12:07,382 WARN ]: Spent 488.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 67 [2018-06-22 15:12:07,912 WARN ]: Spent 496.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 70 [2018-06-22 15:12:08,481 WARN ]: Spent 535.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 71 [2018-06-22 15:12:08,855 WARN ]: Spent 341.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 70 [2018-06-22 15:12:09,375 WARN ]: Spent 487.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 67 [2018-06-22 15:12:09,756 WARN ]: Spent 347.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 69 [2018-06-22 15:12:10,301 WARN ]: Spent 511.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 72 [2018-06-22 15:12:10,339 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:12:10,339 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 15:12:10,340 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 15:12:10,340 INFO ]: Start accepts. Automaton has 23 states. Word has length 41 [2018-06-22 15:12:10,340 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:12:10,340 INFO ]: With dead ends: 29 [2018-06-22 15:12:10,340 INFO ]: Without dead ends: 29 [2018-06-22 15:12:10,341 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 30 SyntacticMatches, 9 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 147 ImplicationChecksByTransitivity, 12.7s TimeCoverageRelationStatistics Valid=187, Invalid=869, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 15:12:10,341 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 15:12:10,345 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 15:12:10,345 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 15:12:10,346 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 15:12:10,346 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 15:12:10,346 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:12:10,346 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 15:12:10,346 INFO ]: Interpolant automaton has 23 states. [2018-06-22 15:12:10,346 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 15:12:10,347 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 15:12:10,347 INFO ]: Found error trace [2018-06-22 15:12:10,347 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:10,347 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:10,347 INFO ]: Analyzing trace with hash 1442343014, now seen corresponding path program 9 times [2018-06-22 15:12:10,348 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:10,348 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:10,349 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:10,349 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:12:10,349 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:10,527 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:10,900 WARN ]: Spent 124.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 6 [2018-06-22 15:12:11,771 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:12:11,771 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:12:11,771 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:12:11,777 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:12:12,066 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 15:12:12,066 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:12,079 INFO ]: Computing forward predicates... [2018-06-22 15:12:12,522 WARN ]: Spent 331.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 47 [2018-06-22 15:12:12,795 WARN ]: Spent 222.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 36 [2018-06-22 15:12:12,978 WARN ]: Spent 139.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 33 [2018-06-22 15:12:13,144 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 37 [2018-06-22 15:12:13,383 WARN ]: Spent 143.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 35 [2018-06-22 15:12:13,569 WARN ]: Spent 141.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 35 [2018-06-22 15:12:13,749 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 28 [2018-06-22 15:12:15,340 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:12:15,361 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:12:15,361 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 38 [2018-06-22 15:12:15,361 INFO ]: Interpolant automaton has 38 states [2018-06-22 15:12:15,361 INFO ]: Constructing interpolant automaton starting with 38 interpolants. [2018-06-22 15:12:15,362 INFO ]: CoverageRelationStatistics Valid=117, Invalid=1289, Unknown=0, NotChecked=0, Total=1406 [2018-06-22 15:12:15,362 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 38 states. [2018-06-22 15:12:16,279 WARN ]: Spent 818.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 86 [2018-06-22 15:12:16,646 WARN ]: Spent 281.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 41 [2018-06-22 15:12:17,058 WARN ]: Spent 370.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 58 [2018-06-22 15:12:17,500 WARN ]: Spent 386.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 57 [2018-06-22 15:12:17,959 WARN ]: Spent 408.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 59 [2018-06-22 15:12:18,405 WARN ]: Spent 385.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 59 [2018-06-22 15:12:18,900 WARN ]: Spent 449.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 61 [2018-06-22 15:12:19,372 WARN ]: Spent 410.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 62 [2018-06-22 15:12:19,820 WARN ]: Spent 398.00 ms on a formula simplification. DAG size of input: 115 DAG size of output: 59 [2018-06-22 15:12:20,390 WARN ]: Spent 519.00 ms on a formula simplification. DAG size of input: 115 DAG size of output: 69 [2018-06-22 15:12:20,444 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:12:20,444 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 15:12:20,444 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 15:12:20,444 INFO ]: Start accepts. Automaton has 38 states. Word has length 45 [2018-06-22 15:12:20,445 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:12:20,445 INFO ]: With dead ends: 31 [2018-06-22 15:12:20,445 INFO ]: Without dead ends: 31 [2018-06-22 15:12:20,446 INFO ]: 0 DeclaredPredicates, 77 GetRequests, 28 SyntacticMatches, 2 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 371 ImplicationChecksByTransitivity, 7.8s TimeCoverageRelationStatistics Valid=336, Invalid=2016, Unknown=0, NotChecked=0, Total=2352 [2018-06-22 15:12:20,446 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 15:12:20,450 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 15:12:20,450 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 15:12:20,450 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 15:12:20,451 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 15:12:20,451 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:12:20,451 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 15:12:20,451 INFO ]: Interpolant automaton has 38 states. [2018-06-22 15:12:20,451 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 15:12:20,452 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 15:12:20,452 INFO ]: Found error trace [2018-06-22 15:12:20,452 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:20,452 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:20,452 INFO ]: Analyzing trace with hash 352352522, now seen corresponding path program 10 times [2018-06-22 15:12:20,452 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:20,452 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:20,453 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:20,453 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:12:20,453 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:21,007 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:21,591 WARN ]: Spent 299.00 ms on a formula simplification. DAG size of input: 6 DAG size of output: 5 [2018-06-22 15:12:21,796 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 24 [2018-06-22 15:12:23,068 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:12:23,068 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:12:23,068 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:12:23,075 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:12:23,323 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:12:23,323 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:23,335 INFO ]: Computing forward predicates... [2018-06-22 15:12:24,701 WARN ]: Spent 857.00 ms on a formula simplification. DAG size of input: 136 DAG size of output: 53 [2018-06-22 15:12:25,259 WARN ]: Spent 292.00 ms on a formula simplification. DAG size of input: 66 DAG size of output: 54 Received shutdown request... [2018-06-22 15:12:25,945 WARN ]: Removed 2 from assertion stack [2018-06-22 15:12:25,945 INFO ]: Timeout while computing interpolants [2018-06-22 15:12:26,146 WARN ]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:12:26,146 WARN ]: Verification canceled [2018-06-22 15:12:26,149 WARN ]: Timeout [2018-06-22 15:12:26,149 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:12:26 BoogieIcfgContainer [2018-06-22 15:12:26,150 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:12:26,150 INFO ]: Toolchain (without parser) took 59378.46 ms. Allocated memory was 306.7 MB in the beginning and 1.0 GB in the end (delta: 741.9 MB). Free memory was 235.2 MB in the beginning and 462.9 MB in the end (delta: -227.7 MB). Peak memory consumption was 514.1 MB. Max. memory is 3.6 GB. [2018-06-22 15:12:26,151 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 306.7 MB. Free memory is still 272.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:12:26,151 INFO ]: ChcToBoogie took 55.64 ms. Allocated memory is still 306.7 MB. Free memory was 235.2 MB in the beginning and 232.2 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:12:26,151 INFO ]: Boogie Preprocessor took 88.28 ms. Allocated memory is still 306.7 MB. Free memory was 232.2 MB in the beginning and 230.2 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:12:26,152 INFO ]: RCFGBuilder took 463.42 ms. Allocated memory is still 306.7 MB. Free memory was 230.2 MB in the beginning and 206.4 MB in the end (delta: 23.8 MB). Peak memory consumption was 23.8 MB. Max. memory is 3.6 GB. [2018-06-22 15:12:26,152 INFO ]: TraceAbstraction took 58760.93 ms. Allocated memory was 306.7 MB in the beginning and 1.0 GB in the end (delta: 741.9 MB). Free memory was 206.4 MB in the beginning and 462.9 MB in the end (delta: -256.6 MB). Peak memory consumption was 485.3 MB. Max. memory is 3.6 GB. [2018-06-22 15:12:26,154 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 306.7 MB. Free memory is still 272.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 55.64 ms. Allocated memory is still 306.7 MB. Free memory was 235.2 MB in the beginning and 232.2 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 88.28 ms. Allocated memory is still 306.7 MB. Free memory was 232.2 MB in the beginning and 230.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 463.42 ms. Allocated memory is still 306.7 MB. Free memory was 230.2 MB in the beginning and 206.4 MB in the end (delta: 23.8 MB). Peak memory consumption was 23.8 MB. Max. memory is 3.6 GB. * TraceAbstraction took 58760.93 ms. Allocated memory was 306.7 MB in the beginning and 1.0 GB in the end (delta: 741.9 MB). Free memory was 206.4 MB in the beginning and 462.9 MB in the end (delta: -256.6 MB). Peak memory consumption was 485.3 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 50 with TraceHistMax 11, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 149. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 58.6s OverallTime, 11 OverallIterations, 11 TraceHistogramMax, 17.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 140 SDtfs, 401 SDslu, 1015 SDs, 0 SdLazy, 923 SolverSat, 497 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 439 GetRequests, 193 SyntacticMatches, 34 SemanticMatches, 212 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 977 ImplicationChecksByTransitivity, 38.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=31occurred 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.1s SsaConstructionTime, 2.4s SatisfiabilityAnalysisTime, 31.7s InterpolantComputationTime, 531 NumberOfCodeBlocks, 531 NumberOfCodeBlocksAsserted, 44 NumberOfCheckSat, 512 ConstructedInterpolants, 0 QuantifiedInterpolants, 471124 SizeOfPredicates, 1028 NumberOfNonLiveVariables, 6939 ConjunctsInSsa, 545 ConjunctsInUnsatCore, 19 InterpolantComputations, 1 PerfectInterpolantSequences, 330/1230 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/lifnatprime.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-12-26-163.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lifnatprime.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-12-26-163.csv Completed graceful shutdown