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/cars.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 14:52:44,651 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 14:52:44,653 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 14:52:44,667 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 14:52:44,667 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 14:52:44,668 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 14:52:44,669 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 14:52:44,673 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 14:52:44,675 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 14:52:44,676 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 14:52:44,677 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 14:52:44,677 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 14:52:44,678 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 14:52:44,679 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 14:52:44,682 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 14:52:44,683 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 14:52:44,684 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 14:52:44,694 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 14:52:44,695 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 14:52:44,696 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 14:52:44,697 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 14:52:44,703 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 14:52:44,703 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 14:52:44,703 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 14:52:44,704 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 14:52:44,705 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 14:52:44,706 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 14:52:44,706 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 14:52:44,707 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 14:52:44,707 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 14:52:44,708 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 14:52:44,708 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 14:52:44,709 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 14:52:44,709 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 14:52:44,710 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 14:52:44,710 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 14:52:44,733 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 14:52:44,733 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 14:52:44,734 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 14:52:44,734 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 14:52:44,735 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 14:52:44,735 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 14:52:44,735 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 14:52:44,735 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 14:52:44,735 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 14:52:44,737 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 14:52:44,737 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 14:52:44,737 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 14:52:44,737 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 14:52:44,737 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 14:52:44,738 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 14:52:44,738 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 14:52:44,738 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 14:52:44,738 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 14:52:44,738 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 14:52:44,740 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 14:52:44,740 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 14:52:44,794 INFO ]: Repository-Root is: /tmp [2018-06-22 14:52:44,812 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 14:52:44,819 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 14:52:44,820 INFO ]: Initializing SmtParser... [2018-06-22 14:52:44,821 INFO ]: SmtParser initialized [2018-06-22 14:52:44,821 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/cars.c.smt2 [2018-06-22 14:52:44,823 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 14:52:44,919 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/cars.c.smt2 unknown [2018-06-22 14:52:45,377 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/cars.c.smt2 [2018-06-22 14:52:45,382 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 14:52:45,391 INFO ]: Walking toolchain with 4 elements. [2018-06-22 14:52:45,391 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 14:52:45,391 INFO ]: Initializing ChcToBoogie... [2018-06-22 14:52:45,391 INFO ]: ChcToBoogie initialized [2018-06-22 14:52:45,395 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:52:45" (1/1) ... [2018-06-22 14:52:45,444 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:52:45 Unit [2018-06-22 14:52:45,445 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 14:52:45,445 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 14:52:45,445 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 14:52:45,445 INFO ]: Boogie Preprocessor initialized [2018-06-22 14:52:45,467 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:52:45" (1/1) ... [2018-06-22 14:52:45,467 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:52:45" (1/1) ... [2018-06-22 14:52:45,488 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:52:45" (1/1) ... [2018-06-22 14:52:45,488 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:52:45" (1/1) ... [2018-06-22 14:52:45,506 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:52:45" (1/1) ... [2018-06-22 14:52:45,507 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:52:45" (1/1) ... [2018-06-22 14:52:45,509 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:52:45" (1/1) ... [2018-06-22 14:52:45,515 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 14:52:45,515 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 14:52:45,515 INFO ]: Initializing RCFGBuilder... [2018-06-22 14:52:45,515 INFO ]: RCFGBuilder initialized [2018-06-22 14:52:45,516 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:52:45" (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 14:52:45,531 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 14:52:45,531 INFO ]: Found specification of procedure False [2018-06-22 14:52:45,531 INFO ]: Found implementation of procedure False [2018-06-22 14:52:45,531 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 14:52:45,531 INFO ]: Found specification of procedure state [2018-06-22 14:52:45,531 INFO ]: Found implementation of procedure state [2018-06-22 14:52:45,531 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 14:52:45,531 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 14:52:45,531 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 14:52:45,898 INFO ]: Using library mode [2018-06-22 14:52:45,899 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:52:45 BoogieIcfgContainer [2018-06-22 14:52:45,899 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 14:52:45,902 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 14:52:45,902 INFO ]: Initializing TraceAbstraction... [2018-06-22 14:52:45,905 INFO ]: TraceAbstraction initialized [2018-06-22 14:52:45,906 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:52:45" (1/3) ... [2018-06-22 14:52:45,909 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@66b857ca and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 02:52:45, skipping insertion in model container [2018-06-22 14:52:45,909 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:52:45" (2/3) ... [2018-06-22 14:52:45,909 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@66b857ca and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 02:52:45, skipping insertion in model container [2018-06-22 14:52:45,909 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:52:45" (3/3) ... [2018-06-22 14:52:45,911 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 14:52:45,921 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 14:52:45,930 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 14:52:45,972 INFO ]: Using default assertion order modulation [2018-06-22 14:52:45,972 INFO ]: Interprodecural is true [2018-06-22 14:52:45,972 INFO ]: Hoare is false [2018-06-22 14:52:45,972 INFO ]: Compute interpolants for FPandBP [2018-06-22 14:52:45,972 INFO ]: Backedges is TWOTRACK [2018-06-22 14:52:45,972 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 14:52:45,972 INFO ]: Difference is false [2018-06-22 14:52:45,972 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 14:52:45,972 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 14:52:45,985 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 14:52:45,994 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 14:52:45,995 INFO ]: Found error trace [2018-06-22 14:52:45,995 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:52:45,996 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:52:46,001 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 14:52:46,003 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:52:46,003 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:52:46,040 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:46,040 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:52:46,040 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:46,079 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:46,270 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 14:52:46,273 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 14:52:46,273 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 14:52:46,275 INFO ]: Interpolant automaton has 4 states [2018-06-22 14:52:46,290 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 14:52:46,290 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 14:52:46,293 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 14:52:46,393 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:52:46,393 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 14:52:46,393 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 14:52:46,394 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 14:52:46,395 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:52:46,404 INFO ]: With dead ends: 13 [2018-06-22 14:52:46,404 INFO ]: Without dead ends: 13 [2018-06-22 14:52:46,406 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 14:52:46,420 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 14:52:46,439 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 14:52:46,440 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 14:52:46,441 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 14:52:46,442 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 14:52:46,442 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:52:46,442 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 14:52:46,442 INFO ]: Interpolant automaton has 4 states. [2018-06-22 14:52:46,442 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 14:52:46,443 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 14:52:46,443 INFO ]: Found error trace [2018-06-22 14:52:46,443 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:52:46,443 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:52:46,444 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 14:52:46,444 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:52:46,444 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:52:46,444 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:46,444 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:52:46,444 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:46,545 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:47,048 WARN ]: Spent 306.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-22 14:52:47,281 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 14:52:47,281 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:52:47,281 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 14:52:47,289 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:52:47,357 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:47,367 INFO ]: Computing forward predicates... [2018-06-22 14:52:47,981 WARN ]: Spent 472.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 15 [2018-06-22 14:52:48,396 WARN ]: Spent 163.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2018-06-22 14:52:48,525 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 14:52:48,545 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:52:48,545 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 14:52:48,546 INFO ]: Interpolant automaton has 9 states [2018-06-22 14:52:48,546 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 14:52:48,546 INFO ]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-06-22 14:52:48,546 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 14:52:48,912 WARN ]: Spent 357.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-06-22 14:52:49,169 WARN ]: Spent 198.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 24 [2018-06-22 14:52:49,244 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:52:49,244 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 14:52:49,245 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 14:52:49,245 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 14:52:49,245 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:52:49,245 INFO ]: With dead ends: 15 [2018-06-22 14:52:49,245 INFO ]: Without dead ends: 15 [2018-06-22 14:52:49,246 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-06-22 14:52:49,246 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 14:52:49,248 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 14:52:49,248 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 14:52:49,248 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 14:52:49,248 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 14:52:49,248 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:52:49,248 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 14:52:49,248 INFO ]: Interpolant automaton has 9 states. [2018-06-22 14:52:49,248 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 14:52:49,250 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 14:52:49,250 INFO ]: Found error trace [2018-06-22 14:52:49,250 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:52:49,250 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:52:49,250 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 14:52:49,250 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:52:49,250 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:52:49,251 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:49,251 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:52:49,251 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:49,324 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:49,537 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 14:52:49,537 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:52:49,537 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 14:52:49,547 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 14:52:49,636 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 14:52:49,636 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:49,655 INFO ]: Computing forward predicates... [2018-06-22 14:52:49,979 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 14:52:50,001 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:52:50,001 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 14:52:50,001 INFO ]: Interpolant automaton has 11 states [2018-06-22 14:52:50,002 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 14:52:50,002 INFO ]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2018-06-22 14:52:50,002 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 14:52:50,298 WARN ]: Spent 102.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 23 [2018-06-22 14:52:50,376 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:52:50,376 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 14:52:50,377 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 14:52:50,377 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 14:52:50,377 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:52:50,377 INFO ]: With dead ends: 17 [2018-06-22 14:52:50,377 INFO ]: Without dead ends: 17 [2018-06-22 14:52:50,378 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2018-06-22 14:52:50,378 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 14:52:50,381 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 14:52:50,381 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 14:52:50,382 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 14:52:50,382 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 14:52:50,382 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:52:50,382 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 14:52:50,382 INFO ]: Interpolant automaton has 11 states. [2018-06-22 14:52:50,382 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 14:52:50,383 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 14:52:50,383 INFO ]: Found error trace [2018-06-22 14:52:50,383 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:52:50,383 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:52:50,383 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 14:52:50,383 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:52:50,383 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:52:50,384 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:50,384 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:52:50,384 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:50,459 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:51,003 WARN ]: Spent 268.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-22 14:52:51,465 WARN ]: Spent 381.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2018-06-22 14:52:51,558 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 14:52:51,558 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:52:51,558 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 14:52:51,573 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 14:52:51,666 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 14:52:51,666 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:51,672 INFO ]: Computing forward predicates... [2018-06-22 14:52:51,886 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 14:52:51,905 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:52:51,905 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 13 [2018-06-22 14:52:51,905 INFO ]: Interpolant automaton has 13 states [2018-06-22 14:52:51,905 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 14:52:51,906 INFO ]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2018-06-22 14:52:51,906 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 13 states. [2018-06-22 14:52:52,096 WARN ]: Spent 148.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 32 [2018-06-22 14:52:52,327 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:52:52,327 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 14:52:52,328 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 14:52:52,328 INFO ]: Start accepts. Automaton has 13 states. Word has length 21 [2018-06-22 14:52:52,328 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:52:52,329 INFO ]: With dead ends: 19 [2018-06-22 14:52:52,329 INFO ]: Without dead ends: 19 [2018-06-22 14:52:52,329 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=70, Invalid=236, Unknown=0, NotChecked=0, Total=306 [2018-06-22 14:52:52,329 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 14:52:52,331 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 14:52:52,331 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 14:52:52,332 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 14:52:52,332 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 14:52:52,332 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:52:52,332 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 14:52:52,332 INFO ]: Interpolant automaton has 13 states. [2018-06-22 14:52:52,332 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 14:52:52,333 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 14:52:52,333 INFO ]: Found error trace [2018-06-22 14:52:52,333 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:52:52,333 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:52:52,333 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-22 14:52:52,333 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:52:52,333 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:52:52,334 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:52,334 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:52:52,334 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:52,413 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:52,997 WARN ]: Spent 266.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-22 14:52:53,197 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 14:52:53,197 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:52:53,197 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 14:52:53,203 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 14:52:53,289 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 14:52:53,289 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:53,294 INFO ]: Computing forward predicates... [2018-06-22 14:52:53,478 WARN ]: Spent 126.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 13 [2018-06-22 14:52:54,139 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 14:52:54,161 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:52:54,161 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 15 [2018-06-22 14:52:54,161 INFO ]: Interpolant automaton has 15 states [2018-06-22 14:52:54,161 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 14:52:54,162 INFO ]: CoverageRelationStatistics Valid=40, Invalid=170, Unknown=0, NotChecked=0, Total=210 [2018-06-22 14:52:54,162 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 15 states. [2018-06-22 14:52:54,353 WARN ]: Spent 143.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 36 [2018-06-22 14:52:54,762 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:52:54,762 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 14:52:54,769 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 14:52:54,769 INFO ]: Start accepts. Automaton has 15 states. Word has length 25 [2018-06-22 14:52:54,769 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:52:54,770 INFO ]: With dead ends: 21 [2018-06-22 14:52:54,770 INFO ]: Without dead ends: 21 [2018-06-22 14:52:54,770 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=91, Invalid=329, Unknown=0, NotChecked=0, Total=420 [2018-06-22 14:52:54,770 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 14:52:54,773 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 14:52:54,773 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 14:52:54,774 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 14:52:54,774 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 14:52:54,774 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:52:54,774 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 14:52:54,774 INFO ]: Interpolant automaton has 15 states. [2018-06-22 14:52:54,774 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 14:52:54,775 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 14:52:54,775 INFO ]: Found error trace [2018-06-22 14:52:54,775 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:52:54,775 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:52:54,776 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-22 14:52:54,776 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:52:54,776 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:52:54,779 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:54,779 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:52:54,779 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:54,886 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:55,737 WARN ]: Spent 598.00 ms on a formula simplification that was a NOOP. DAG size: 20 [2018-06-22 14:52:55,995 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 14:52:55,995 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:52:55,995 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 14:52:56,001 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 14:52:56,110 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 14:52:56,110 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:56,118 INFO ]: Computing forward predicates... [2018-06-22 14:52:56,373 WARN ]: Spent 159.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 29 [2018-06-22 14:52:56,863 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 14:52:56,896 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:52:56,910 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 17 [2018-06-22 14:52:56,911 INFO ]: Interpolant automaton has 17 states [2018-06-22 14:52:56,911 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 14:52:56,911 INFO ]: CoverageRelationStatistics Valid=50, Invalid=222, Unknown=0, NotChecked=0, Total=272 [2018-06-22 14:52:56,911 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 17 states. [2018-06-22 14:52:57,501 WARN ]: Spent 298.00 ms on a formula simplification that was a NOOP. DAG size: 41 [2018-06-22 14:52:57,824 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 25 [2018-06-22 14:52:57,987 WARN ]: Spent 102.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 27 [2018-06-22 14:52:58,189 WARN ]: Spent 185.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 32 [2018-06-22 14:52:58,348 WARN ]: Spent 134.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 34 [2018-06-22 14:52:58,375 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:52:58,375 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 14:52:58,376 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 14:52:58,376 INFO ]: Start accepts. Automaton has 17 states. Word has length 29 [2018-06-22 14:52:58,376 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:52:58,377 INFO ]: With dead ends: 23 [2018-06-22 14:52:58,377 INFO ]: Without dead ends: 23 [2018-06-22 14:52:58,377 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=113, Invalid=393, Unknown=0, NotChecked=0, Total=506 [2018-06-22 14:52:58,377 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 14:52:58,381 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 14:52:58,381 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 14:52:58,381 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 14:52:58,381 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 14:52:58,382 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:52:58,382 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 14:52:58,382 INFO ]: Interpolant automaton has 17 states. [2018-06-22 14:52:58,382 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 14:52:58,383 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 14:52:58,383 INFO ]: Found error trace [2018-06-22 14:52:58,383 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:52:58,383 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:52:58,383 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-22 14:52:58,383 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:52:58,383 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:52:58,384 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:58,384 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:52:58,384 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:58,509 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:58,981 WARN ]: Spent 131.00 ms on a formula simplification that was a NOOP. DAG size: 33 [2018-06-22 14:52:59,461 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 14:52:59,461 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:52:59,461 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 14:52:59,468 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 14:52:59,609 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 14:52:59,609 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:59,618 INFO ]: Computing forward predicates... [2018-06-22 14:53:01,447 WARN ]: Spent 1.38 s on a formula simplification. DAG size of input: 77 DAG size of output: 36 [2018-06-22 14:53:02,121 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 14:53:02,153 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:53:02,153 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 19 [2018-06-22 14:53:02,153 INFO ]: Interpolant automaton has 19 states [2018-06-22 14:53:02,153 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 14:53:02,153 INFO ]: CoverageRelationStatistics Valid=52, Invalid=290, Unknown=0, NotChecked=0, Total=342 [2018-06-22 14:53:02,154 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 19 states. [2018-06-22 14:53:02,512 WARN ]: Spent 275.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 57 [2018-06-22 14:53:03,047 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 28 [2018-06-22 14:53:03,195 WARN ]: Spent 125.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 32 [2018-06-22 14:53:03,422 WARN ]: Spent 199.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 41 [2018-06-22 14:53:03,674 WARN ]: Spent 227.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 39 [2018-06-22 14:53:03,712 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:53:03,712 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 14:53:03,713 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 14:53:03,713 INFO ]: Start accepts. Automaton has 19 states. Word has length 33 [2018-06-22 14:53:03,713 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:53:03,714 INFO ]: With dead ends: 25 [2018-06-22 14:53:03,714 INFO ]: Without dead ends: 25 [2018-06-22 14:53:03,714 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 29 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 80 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=137, Invalid=565, Unknown=0, NotChecked=0, Total=702 [2018-06-22 14:53:03,714 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 14:53:03,717 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 14:53:03,717 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 14:53:03,718 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 14:53:03,718 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 14:53:03,719 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:53:03,719 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 14:53:03,719 INFO ]: Interpolant automaton has 19 states. [2018-06-22 14:53:03,719 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 14:53:03,720 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 14:53:03,720 INFO ]: Found error trace [2018-06-22 14:53:03,720 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:53:03,720 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:53:03,720 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 7 times [2018-06-22 14:53:03,720 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:53:03,720 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:53:03,721 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:53:03,721 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:53:03,721 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:53:03,856 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:53:04,369 WARN ]: Spent 152.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 37 [2018-06-22 14:53:04,804 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 14:53:04,804 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:53:04,805 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 14:53:04,811 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:53:04,947 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:53:04,956 INFO ]: Computing forward predicates... [2018-06-22 14:53:05,637 WARN ]: Spent 490.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 34 [2018-06-22 14:53:06,102 WARN ]: Spent 243.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 38 [2018-06-22 14:53:06,543 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 31 [2018-06-22 14:53:07,034 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 14:53:07,054 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:53:07,054 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 24 [2018-06-22 14:53:07,054 INFO ]: Interpolant automaton has 24 states [2018-06-22 14:53:07,055 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 14:53:07,055 INFO ]: CoverageRelationStatistics Valid=68, Invalid=484, Unknown=0, NotChecked=0, Total=552 [2018-06-22 14:53:07,055 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 24 states. [2018-06-22 14:53:07,772 WARN ]: Spent 623.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 67 [2018-06-22 14:53:07,986 WARN ]: Spent 170.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 31 [2018-06-22 14:53:08,190 WARN ]: Spent 175.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 31 [2018-06-22 14:53:08,339 WARN ]: Spent 116.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 27 [2018-06-22 14:53:08,610 WARN ]: Spent 216.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 33 [2018-06-22 14:53:09,071 WARN ]: Spent 393.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 42 [2018-06-22 14:53:09,421 WARN ]: Spent 318.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 46 [2018-06-22 14:53:09,756 WARN ]: Spent 305.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 44 [2018-06-22 14:53:09,792 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:53:09,792 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 14:53:09,793 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 14:53:09,793 INFO ]: Start accepts. Automaton has 24 states. Word has length 37 [2018-06-22 14:53:09,793 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:53:09,794 INFO ]: With dead ends: 27 [2018-06-22 14:53:09,794 INFO ]: Without dead ends: 27 [2018-06-22 14:53:09,794 INFO ]: 0 DeclaredPredicates, 63 GetRequests, 30 SyntacticMatches, 2 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 136 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=190, Invalid=866, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 14:53:09,794 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 14:53:09,798 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 14:53:09,798 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 14:53:09,799 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 14:53:09,799 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 14:53:09,799 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:53:09,799 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 14:53:09,799 INFO ]: Interpolant automaton has 24 states. [2018-06-22 14:53:09,799 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 14:53:09,800 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 14:53:09,800 INFO ]: Found error trace [2018-06-22 14:53:09,800 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:53:09,800 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:53:09,800 INFO ]: Analyzing trace with hash -544278078, now seen corresponding path program 8 times [2018-06-22 14:53:09,800 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:53:09,800 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:53:09,801 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:53:09,801 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:53:09,801 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:53:09,924 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:53:10,487 WARN ]: Spent 234.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 23 [2018-06-22 14:53:10,718 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 36 [2018-06-22 14:53:10,884 WARN ]: Spent 157.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 39 [2018-06-22 14:53:11,300 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 14:53:11,300 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:53:11,300 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 14:53:11,305 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 14:53:11,515 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 14:53:11,515 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:53:11,525 INFO ]: Computing forward predicates... [2018-06-22 14:53:11,813 WARN ]: Spent 187.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 35 [2018-06-22 14:53:12,188 WARN ]: Spent 323.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 36 [2018-06-22 14:53:12,475 WARN ]: Spent 232.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 38 [2018-06-22 14:53:13,210 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 14:53:13,231 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:53:13,275 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 27 [2018-06-22 14:53:13,275 INFO ]: Interpolant automaton has 27 states [2018-06-22 14:53:13,276 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-22 14:53:13,276 INFO ]: CoverageRelationStatistics Valid=77, Invalid=625, Unknown=0, NotChecked=0, Total=702 [2018-06-22 14:53:13,276 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 27 states. [2018-06-22 14:53:14,251 WARN ]: Spent 871.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 67 [2018-06-22 14:53:14,513 WARN ]: Spent 202.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 28 [2018-06-22 14:53:14,754 WARN ]: Spent 210.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 27 [2018-06-22 14:53:14,992 WARN ]: Spent 203.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 28 [2018-06-22 14:53:15,276 WARN ]: Spent 251.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 33 [2018-06-22 14:53:15,682 WARN ]: Spent 370.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 49 [2018-06-22 14:53:16,098 WARN ]: Spent 311.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 40 [2018-06-22 14:53:16,483 WARN ]: Spent 350.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 44 [2018-06-22 14:53:16,913 WARN ]: Spent 394.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 39 [2018-06-22 14:53:16,954 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:53:16,954 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 14:53:16,954 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 14:53:16,954 INFO ]: Start accepts. Automaton has 27 states. Word has length 41 [2018-06-22 14:53:16,954 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:53:16,955 INFO ]: With dead ends: 29 [2018-06-22 14:53:16,955 INFO ]: Without dead ends: 29 [2018-06-22 14:53:16,955 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 32 SyntacticMatches, 3 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 180 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=232, Invalid=1100, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 14:53:16,955 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 14:53:16,959 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 14:53:16,959 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 14:53:16,960 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 14:53:16,960 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 14:53:16,960 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:53:16,960 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 14:53:16,960 INFO ]: Interpolant automaton has 27 states. [2018-06-22 14:53:16,960 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 14:53:16,961 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 14:53:16,961 INFO ]: Found error trace [2018-06-22 14:53:16,961 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:53:16,961 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:53:16,961 INFO ]: Analyzing trace with hash 1442343014, now seen corresponding path program 9 times [2018-06-22 14:53:16,961 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:53:16,961 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:53:16,962 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:53:16,962 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:53:16,962 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:53:17,106 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:53:17,572 WARN ]: Spent 251.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 3 [2018-06-22 14:53:18,984 WARN ]: Spent 1.36 s on a formula simplification. DAG size of input: 27 DAG size of output: 27 [2018-06-22 14:53:19,121 WARN ]: Spent 131.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 34 [2018-06-22 14:53:19,389 WARN ]: Spent 259.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 37 [2018-06-22 14:53:19,658 WARN ]: Spent 256.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 38 [2018-06-22 14:53:19,898 WARN ]: Spent 222.00 ms on a formula simplification. DAG size of input: 66 DAG size of output: 35 [2018-06-22 14:53:20,524 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 14:53:20,524 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:53:20,524 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 14:53:20,531 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 14:53:20,738 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 14:53:20,738 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:53:20,749 INFO ]: Computing forward predicates... [2018-06-22 14:53:21,147 WARN ]: Spent 232.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 30 [2018-06-22 14:53:22,628 WARN ]: Spent 1.21 s on a formula simplification. DAG size of input: 109 DAG size of output: 57 [2018-06-22 14:53:23,184 WARN ]: Spent 471.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 41 [2018-06-22 14:53:23,614 WARN ]: Spent 233.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 38 [2018-06-22 14:53:24,490 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 14:53:24,512 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:53:24,512 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 28 [2018-06-22 14:53:24,512 INFO ]: Interpolant automaton has 28 states [2018-06-22 14:53:24,512 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-22 14:53:24,513 INFO ]: CoverageRelationStatistics Valid=71, Invalid=685, Unknown=0, NotChecked=0, Total=756 [2018-06-22 14:53:24,513 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 28 states. [2018-06-22 14:53:25,878 WARN ]: Spent 1.29 s on a formula simplification. DAG size of input: 115 DAG size of output: 86 [2018-06-22 14:53:26,381 WARN ]: Spent 439.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 32 [2018-06-22 14:53:26,881 WARN ]: Spent 461.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 35 [2018-06-22 14:53:27,241 WARN ]: Spent 312.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 34 [2018-06-22 14:53:27,612 WARN ]: Spent 330.00 ms on a formula simplification. DAG size of input: 119 DAG size of output: 41 [2018-06-22 14:53:28,445 WARN ]: Spent 788.00 ms on a formula simplification. DAG size of input: 119 DAG size of output: 56 [2018-06-22 14:53:29,129 WARN ]: Spent 641.00 ms on a formula simplification. DAG size of input: 121 DAG size of output: 58 [2018-06-22 14:53:30,129 WARN ]: Spent 954.00 ms on a formula simplification. DAG size of input: 119 DAG size of output: 63 [2018-06-22 14:53:31,210 WARN ]: Spent 1.02 s on a formula simplification. DAG size of input: 117 DAG size of output: 69 [2018-06-22 14:53:31,886 WARN ]: Spent 633.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 46 [2018-06-22 14:53:31,927 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:53:31,927 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 14:53:31,927 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 14:53:31,927 INFO ]: Start accepts. Automaton has 28 states. Word has length 45 [2018-06-22 14:53:31,928 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:53:31,928 INFO ]: With dead ends: 31 [2018-06-22 14:53:31,928 INFO ]: Without dead ends: 31 [2018-06-22 14:53:31,929 INFO ]: 0 DeclaredPredicates, 77 GetRequests, 35 SyntacticMatches, 5 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 151 ImplicationChecksByTransitivity, 13.1s TimeCoverageRelationStatistics Valid=252, Invalid=1230, Unknown=0, NotChecked=0, Total=1482 [2018-06-22 14:53:31,929 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 14:53:31,933 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 14:53:31,933 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 14:53:31,934 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 14:53:31,934 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 14:53:31,934 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:53:31,934 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 14:53:31,934 INFO ]: Interpolant automaton has 28 states. [2018-06-22 14:53:31,934 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 14:53:31,935 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 14:53:31,935 INFO ]: Found error trace [2018-06-22 14:53:31,935 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:53:31,935 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:53:31,935 INFO ]: Analyzing trace with hash 352352522, now seen corresponding path program 10 times [2018-06-22 14:53:31,935 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:53:31,935 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:53:31,936 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:53:31,936 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:53:31,936 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:53:32,058 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:53:32,556 WARN ]: Spent 172.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 19 [2018-06-22 14:53:33,588 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 14:53:33,588 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:53:33,588 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 14:53:33,594 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 14:53:33,794 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 14:53:33,794 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:53:33,806 INFO ]: Computing forward predicates... [2018-06-22 14:53:34,235 WARN ]: Spent 282.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 35 [2018-06-22 14:53:34,479 WARN ]: Spent 187.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 36 [2018-06-22 14:53:35,127 WARN ]: Spent 545.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 45 [2018-06-22 14:53:35,420 WARN ]: Spent 234.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 38 [2018-06-22 14:53:35,565 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 31 [2018-06-22 14:53:36,185 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 14:53:36,205 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:53:36,205 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 31 [2018-06-22 14:53:36,206 INFO ]: Interpolant automaton has 31 states [2018-06-22 14:53:36,206 INFO ]: Constructing interpolant automaton starting with 31 interpolants. [2018-06-22 14:53:36,207 INFO ]: CoverageRelationStatistics Valid=88, Invalid=842, Unknown=0, NotChecked=0, Total=930 [2018-06-22 14:53:36,207 INFO ]: Start difference. First operand 31 states and 32 transitions. Second operand 31 states. [2018-06-22 14:53:37,405 WARN ]: Spent 1.12 s on a formula simplification. DAG size of input: 111 DAG size of output: 82 [2018-06-22 14:53:37,880 WARN ]: Spent 374.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 43 [2018-06-22 14:53:38,250 WARN ]: Spent 329.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 28 [2018-06-22 14:53:38,532 WARN ]: Spent 241.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 44 [2018-06-22 14:53:38,910 WARN ]: Spent 336.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 33 [2018-06-22 14:53:39,652 WARN ]: Spent 697.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 54 [2018-06-22 14:53:40,233 WARN ]: Spent 536.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 59 [2018-06-22 14:53:40,915 WARN ]: Spent 639.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 59 [2018-06-22 14:53:41,556 WARN ]: Spent 593.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 43 [2018-06-22 14:53:42,158 WARN ]: Spent 560.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 42 [2018-06-22 14:53:42,874 WARN ]: Spent 673.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 56 [2018-06-22 14:53:42,919 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:53:42,920 INFO ]: Finished difference Result 33 states and 34 transitions. [2018-06-22 14:53:42,920 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 14:53:42,920 INFO ]: Start accepts. Automaton has 31 states. Word has length 49 [2018-06-22 14:53:42,920 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:53:42,921 INFO ]: With dead ends: 33 [2018-06-22 14:53:42,921 INFO ]: Without dead ends: 33 [2018-06-22 14:53:42,921 INFO ]: 0 DeclaredPredicates, 84 GetRequests, 38 SyntacticMatches, 5 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 252 ImplicationChecksByTransitivity, 9.5s TimeCoverageRelationStatistics Valid=309, Invalid=1497, Unknown=0, NotChecked=0, Total=1806 [2018-06-22 14:53:42,921 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-22 14:53:42,925 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 33. [2018-06-22 14:53:42,925 INFO ]: Start removeUnreachable. Operand 33 states. [2018-06-22 14:53:42,925 INFO ]: Finished removeUnreachable. Reduced from 33 states to 33 states and 34 transitions. [2018-06-22 14:53:42,925 INFO ]: Start accepts. Automaton has 33 states and 34 transitions. Word has length 49 [2018-06-22 14:53:42,926 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:53:42,926 INFO ]: Abstraction has 33 states and 34 transitions. [2018-06-22 14:53:42,926 INFO ]: Interpolant automaton has 31 states. [2018-06-22 14:53:42,926 INFO ]: Start isEmpty. Operand 33 states and 34 transitions. [2018-06-22 14:53:42,926 INFO ]: Finished isEmpty. Found accepting run of length 54 [2018-06-22 14:53:42,926 INFO ]: Found error trace [2018-06-22 14:53:42,927 INFO ]: trace histogram [12, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:53:42,927 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:53:42,927 INFO ]: Analyzing trace with hash 53554094, now seen corresponding path program 11 times [2018-06-22 14:53:42,927 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:53:42,927 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:53:42,927 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:53:42,927 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:53:42,927 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:53:43,048 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:53:43,745 WARN ]: Spent 108.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 37 [2018-06-22 14:53:44,370 INFO ]: Checked inductivity of 253 backedges. 0 proven. 187 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-06-22 14:53:44,370 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:53:44,370 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:53:44,376 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 Received shutdown request... [2018-06-22 14:53:44,661 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2018-06-22 14:53:44,661 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:53:44,673 INFO ]: Computing forward predicates... [2018-06-22 14:53:44,674 INFO ]: Timeout while computing interpolants [2018-06-22 14:53:44,874 WARN ]: Destroyed unattended storables created during the last iteration: 13 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:53:44,875 WARN ]: Verification canceled [2018-06-22 14:53:44,878 WARN ]: Timeout [2018-06-22 14:53:44,878 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 02:53:44 BoogieIcfgContainer [2018-06-22 14:53:44,878 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 14:53:44,879 INFO ]: Toolchain (without parser) took 59496.39 ms. Allocated memory was 304.6 MB in the beginning and 979.9 MB in the end (delta: 675.3 MB). Free memory was 240.1 MB in the beginning and 380.8 MB in the end (delta: -140.7 MB). Peak memory consumption was 534.6 MB. Max. memory is 3.6 GB. [2018-06-22 14:53:44,879 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 304.6 MB. Free memory is still 270.1 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 14:53:44,880 INFO ]: ChcToBoogie took 53.55 ms. Allocated memory is still 304.6 MB. Free memory was 240.1 MB in the beginning and 237.1 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:53:44,880 INFO ]: Boogie Preprocessor took 69.40 ms. Allocated memory is still 304.6 MB. Free memory was 237.1 MB in the beginning and 236.1 MB in the end (delta: 996.2 kB). Peak memory consumption was 996.2 kB. Max. memory is 3.6 GB. [2018-06-22 14:53:44,880 INFO ]: RCFGBuilder took 383.63 ms. Allocated memory is still 304.6 MB. Free memory was 235.1 MB in the beginning and 216.1 MB in the end (delta: 19.0 MB). Peak memory consumption was 19.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:53:44,880 INFO ]: TraceAbstraction took 58975.77 ms. Allocated memory was 304.6 MB in the beginning and 979.9 MB in the end (delta: 675.3 MB). Free memory was 216.1 MB in the beginning and 380.8 MB in the end (delta: -164.6 MB). Peak memory consumption was 510.7 MB. Max. memory is 3.6 GB. [2018-06-22 14:53:44,883 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 304.6 MB. Free memory is still 270.1 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 53.55 ms. Allocated memory is still 304.6 MB. Free memory was 240.1 MB in the beginning and 237.1 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 69.40 ms. Allocated memory is still 304.6 MB. Free memory was 237.1 MB in the beginning and 236.1 MB in the end (delta: 996.2 kB). Peak memory consumption was 996.2 kB. Max. memory is 3.6 GB. * RCFGBuilder took 383.63 ms. Allocated memory is still 304.6 MB. Free memory was 235.1 MB in the beginning and 216.1 MB in the end (delta: 19.0 MB). Peak memory consumption was 19.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 58975.77 ms. Allocated memory was 304.6 MB in the beginning and 979.9 MB in the end (delta: 675.3 MB). Free memory was 216.1 MB in the beginning and 380.8 MB in the end (delta: -164.6 MB). Peak memory consumption was 510.7 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 XnfDer was eliminating 1 quantified variables from 1 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 58.9s OverallTime, 12 OverallIterations, 12 TraceHistogramMax, 25.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 166 SDtfs, 553 SDslu, 1178 SDs, 0 SdLazy, 1104 SolverSat, 673 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 528 GetRequests, 261 SyntacticMatches, 17 SemanticMatches, 250 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 951 ImplicationChecksByTransitivity, 44.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=33occurred in iteration=11, 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, 11 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 2.2s SatisfiabilityAnalysisTime, 28.0s InterpolantComputationTime, 629 NumberOfCodeBlocks, 629 NumberOfCodeBlocksAsserted, 48 NumberOfCheckSat, 608 ConstructedInterpolants, 0 QuantifiedInterpolants, 777264 SizeOfPredicates, 1216 NumberOfNonLiveVariables, 6625 ConjunctsInSsa, 639 ConjunctsInUnsatCore, 21 InterpolantComputations, 1 PerfectInterpolantSequences, 440/1650 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/cars.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_14-53-44-891.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cars.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_14-53-44-891.csv Completed graceful shutdown