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/nest-if8.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:22:51,026 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:22:51,029 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:22:51,041 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:22:51,041 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:22:51,042 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:22:51,045 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:22:51,047 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:22:51,049 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:22:51,050 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:22:51,051 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:22:51,052 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:22:51,052 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:22:51,053 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:22:51,054 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:22:51,055 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:22:51,057 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:22:51,058 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:22:51,060 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:22:51,061 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:22:51,062 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:22:51,064 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:22:51,064 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:22:51,064 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:22:51,065 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:22:51,066 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:22:51,066 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:22:51,067 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:22:51,068 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:22:51,068 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:22:51,069 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:22:51,069 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:22:51,070 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:22:51,070 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:22:51,071 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:22:51,071 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:22:51,090 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:22:51,090 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:22:51,090 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:22:51,090 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:22:51,091 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:22:51,091 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:22:51,092 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:22:51,092 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:22:51,092 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:22:51,092 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:22:51,094 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:22:51,095 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:22:51,095 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:22:51,095 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:22:51,095 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:22:51,095 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:22:51,096 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:22:51,096 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:22:51,096 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:22:51,097 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:22:51,098 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:22:51,149 INFO ]: Repository-Root is: /tmp [2018-06-22 15:22:51,165 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:22:51,169 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:22:51,170 INFO ]: Initializing SmtParser... [2018-06-22 15:22:51,171 INFO ]: SmtParser initialized [2018-06-22 15:22:51,172 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/nest-if8.c.smt2 [2018-06-22 15:22:51,173 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:22:51,253 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nest-if8.c.smt2 unknown [2018-06-22 15:22:51,592 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nest-if8.c.smt2 [2018-06-22 15:22:51,598 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:22:51,603 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:22:51,604 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:22:51,604 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:22:51,604 INFO ]: ChcToBoogie initialized [2018-06-22 15:22:51,607 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:22:51" (1/1) ... [2018-06-22 15:22:51,654 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:22:51 Unit [2018-06-22 15:22:51,654 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:22:51,655 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:22:51,655 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:22:51,655 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:22:51,676 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:22:51" (1/1) ... [2018-06-22 15:22:51,676 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:22:51" (1/1) ... [2018-06-22 15:22:51,695 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:22:51" (1/1) ... [2018-06-22 15:22:51,695 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:22:51" (1/1) ... [2018-06-22 15:22:51,700 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:22:51" (1/1) ... [2018-06-22 15:22:51,702 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:22:51" (1/1) ... [2018-06-22 15:22:51,711 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:22:51" (1/1) ... [2018-06-22 15:22:51,714 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:22:51,715 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:22:51,724 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:22:51,724 INFO ]: RCFGBuilder initialized [2018-06-22 15:22:51,726 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:22:51" (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:22:51,749 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:22:51,749 INFO ]: Found specification of procedure False [2018-06-22 15:22:51,749 INFO ]: Found implementation of procedure False [2018-06-22 15:22:51,749 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:22:51,749 INFO ]: Found specification of procedure state [2018-06-22 15:22:51,749 INFO ]: Found implementation of procedure state [2018-06-22 15:22:51,749 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:22:51,749 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:22:51,749 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:22:52,058 INFO ]: Using library mode [2018-06-22 15:22:52,059 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:22:52 BoogieIcfgContainer [2018-06-22 15:22:52,059 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:22:52,061 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:22:52,061 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:22:52,068 INFO ]: TraceAbstraction initialized [2018-06-22 15:22:52,068 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:22:51" (1/3) ... [2018-06-22 15:22:52,069 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b414c4e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:22:52, skipping insertion in model container [2018-06-22 15:22:52,069 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:22:51" (2/3) ... [2018-06-22 15:22:52,070 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b414c4e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:22:52, skipping insertion in model container [2018-06-22 15:22:52,070 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:22:52" (3/3) ... [2018-06-22 15:22:52,072 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:22:52,082 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:22:52,093 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:22:52,137 INFO ]: Using default assertion order modulation [2018-06-22 15:22:52,137 INFO ]: Interprodecural is true [2018-06-22 15:22:52,137 INFO ]: Hoare is false [2018-06-22 15:22:52,137 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:22:52,137 INFO ]: Backedges is TWOTRACK [2018-06-22 15:22:52,137 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:22:52,137 INFO ]: Difference is false [2018-06-22 15:22:52,137 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:22:52,137 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:22:52,150 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:22:52,160 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:22:52,160 INFO ]: Found error trace [2018-06-22 15:22:52,161 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:22:52,161 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:22:52,165 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 15:22:52,166 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:22:52,166 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:22:52,197 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:22:52,197 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:22:52,197 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:22:52,229 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:22:52,422 WARN ]: Spent 115.00 ms on a formula simplification that was a NOOP. DAG size: 4 [2018-06-22 15:22:52,514 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:22:52,516 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:22:52,516 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:22:52,518 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:22:52,528 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:22:52,528 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:22:52,530 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:22:52,597 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:22:52,597 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:22:52,597 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:22:52,598 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:22:52,599 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:22:52,607 INFO ]: With dead ends: 13 [2018-06-22 15:22:52,607 INFO ]: Without dead ends: 13 [2018-06-22 15:22:52,608 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:22:52,622 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:22:52,639 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:22:52,640 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:22:52,641 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:22:52,642 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:22:52,642 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:22:52,642 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:22:52,642 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:22:52,643 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:22:52,644 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:22:52,644 INFO ]: Found error trace [2018-06-22 15:22:52,644 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:22:52,644 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:22:52,644 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 15:22:52,644 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:22:52,644 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:22:52,645 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:22:52,645 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:22:52,645 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:22:52,701 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:22:52,977 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:22:52,977 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:22:52,977 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:22:52,985 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:22:53,030 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:22:53,039 INFO ]: Computing forward predicates... [2018-06-22 15:22:53,547 WARN ]: Spent 158.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 15:22:53,707 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:22:53,727 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:22:53,728 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 15:22:53,728 INFO ]: Interpolant automaton has 9 states [2018-06-22 15:22:53,728 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 15:22:53,728 INFO ]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-06-22 15:22:53,728 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 15:22:53,973 WARN ]: Spent 175.00 ms on a formula simplification. DAG size of input: 7 DAG size of output: 6 [2018-06-22 15:22:54,212 WARN ]: Spent 181.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 12 [2018-06-22 15:22:54,355 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:22:54,355 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:22:54,356 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:22:54,356 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 15:22:54,356 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:22:54,356 INFO ]: With dead ends: 15 [2018-06-22 15:22:54,356 INFO ]: Without dead ends: 15 [2018-06-22 15:22:54,357 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:22:54,357 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:22:54,360 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:22:54,360 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:22:54,360 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:22:54,360 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:22:54,361 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:22:54,361 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:22:54,361 INFO ]: Interpolant automaton has 9 states. [2018-06-22 15:22:54,361 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:22:54,361 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:22:54,361 INFO ]: Found error trace [2018-06-22 15:22:54,361 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:22:54,361 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:22:54,361 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 15:22:54,362 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:22:54,362 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:22:54,362 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:22:54,362 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:22:54,362 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:22:54,418 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:22:54,936 WARN ]: Spent 310.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-22 15:22:55,228 WARN ]: Spent 287.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 16 [2018-06-22 15:22:55,319 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:22:55,319 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:22:55,344 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:22:55,350 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:22:55,392 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:22:55,392 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:22:55,396 INFO ]: Computing forward predicates... [2018-06-22 15:22:55,879 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:22:55,898 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:22:55,898 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:22:55,899 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:22:55,899 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:22:55,899 INFO ]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:22:55,899 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:22:56,270 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:22:56,270 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:22:56,270 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:22:56,270 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:22:56,270 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:22:56,271 INFO ]: With dead ends: 17 [2018-06-22 15:22:56,271 INFO ]: Without dead ends: 17 [2018-06-22 15:22:56,271 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:22:56,271 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:22:56,274 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:22:56,274 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:22:56,275 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:22:56,275 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:22:56,275 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:22:56,275 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:22:56,275 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:22:56,275 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:22:56,276 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:22:56,276 INFO ]: Found error trace [2018-06-22 15:22:56,276 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:22:56,276 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:22:56,276 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 15:22:56,276 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:22:56,276 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:22:56,277 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:22:56,277 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:22:56,277 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:22:56,322 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:22:56,654 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:22:56,654 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:22:56,654 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:22:56,670 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:22:56,715 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:22:56,715 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:22:56,719 INFO ]: Computing forward predicates... [2018-06-22 15:22:58,119 WARN ]: Spent 1.02 s on a formula simplification. DAG size of input: 109 DAG size of output: 33 [2018-06-22 15:22:58,420 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:22:58,440 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:22:58,440 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2018-06-22 15:22:58,440 INFO ]: Interpolant automaton has 15 states [2018-06-22 15:22:58,440 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 15:22:58,440 INFO ]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:22:58,441 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 15 states. [2018-06-22 15:22:58,723 WARN ]: Spent 198.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 46 [2018-06-22 15:22:59,023 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 25 [2018-06-22 15:22:59,307 WARN ]: Spent 266.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 34 [2018-06-22 15:22:59,340 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:22:59,340 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:22:59,340 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:22:59,340 INFO ]: Start accepts. Automaton has 15 states. Word has length 21 [2018-06-22 15:22:59,340 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:22:59,341 INFO ]: With dead ends: 19 [2018-06-22 15:22:59,341 INFO ]: Without dead ends: 19 [2018-06-22 15:22:59,341 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 16 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=77, Invalid=303, Unknown=0, NotChecked=0, Total=380 [2018-06-22 15:22:59,341 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:22:59,344 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:22:59,344 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:22:59,345 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:22:59,345 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:22:59,345 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:22:59,345 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:22:59,345 INFO ]: Interpolant automaton has 15 states. [2018-06-22 15:22:59,345 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:22:59,346 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:22:59,346 INFO ]: Found error trace [2018-06-22 15:22:59,346 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:22:59,346 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:22:59,346 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-22 15:22:59,346 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:22:59,346 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:22:59,347 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:22:59,347 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:22:59,347 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:22:59,399 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:22:59,934 WARN ]: Spent 199.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 22 [2018-06-22 15:23:00,169 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:23:00,169 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:23:00,169 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:23:00,175 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:23:00,215 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:23:00,215 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:23:00,219 INFO ]: Computing forward predicates... [2018-06-22 15:23:00,867 WARN ]: Spent 557.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 35 [2018-06-22 15:23:03,212 WARN ]: Spent 1.94 s on a formula simplification. DAG size of input: 26 DAG size of output: 22 [2018-06-22 15:23:03,570 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:23:03,589 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:23:03,589 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 16 [2018-06-22 15:23:03,589 INFO ]: Interpolant automaton has 16 states [2018-06-22 15:23:03,589 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 15:23:03,590 INFO ]: CoverageRelationStatistics Valid=40, Invalid=200, Unknown=0, NotChecked=0, Total=240 [2018-06-22 15:23:03,590 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 16 states. [2018-06-22 15:23:04,097 WARN ]: Spent 470.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 60 [2018-06-22 15:23:04,648 WARN ]: Spent 309.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 48 [2018-06-22 15:23:04,784 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 35 [2018-06-22 15:23:04,813 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:23:04,813 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:23:04,813 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:23:04,813 INFO ]: Start accepts. Automaton has 16 states. Word has length 25 [2018-06-22 15:23:04,813 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:23:04,814 INFO ]: With dead ends: 21 [2018-06-22 15:23:04,814 INFO ]: Without dead ends: 21 [2018-06-22 15:23:04,814 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 19 SyntacticMatches, 3 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=97, Invalid=365, Unknown=0, NotChecked=0, Total=462 [2018-06-22 15:23:04,814 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:23:04,817 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:23:04,817 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:23:04,817 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:23:04,818 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:23:04,818 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:23:04,818 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:23:04,818 INFO ]: Interpolant automaton has 16 states. [2018-06-22 15:23:04,818 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:23:04,819 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:23:04,819 INFO ]: Found error trace [2018-06-22 15:23:04,819 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:23:04,819 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:23:04,819 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-22 15:23:04,819 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:23:04,819 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:23:04,820 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:23:04,820 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:23:04,820 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:23:04,914 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:23:05,738 WARN ]: Spent 648.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 11 [2018-06-22 15:23:06,047 WARN ]: Spent 236.00 ms on a formula simplification that was a NOOP. DAG size: 27 [2018-06-22 15:23:06,294 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:23:06,294 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:23:06,294 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:23:06,301 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:23:06,363 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:23:06,363 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:23:06,367 INFO ]: Computing forward predicates... [2018-06-22 15:23:06,702 WARN ]: Spent 244.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 21 [2018-06-22 15:23:06,849 WARN ]: Spent 112.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 32 [2018-06-22 15:23:07,071 WARN ]: Spent 102.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 22 [2018-06-22 15:23:07,383 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:23:07,408 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:23:07,409 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 19 [2018-06-22 15:23:07,409 INFO ]: Interpolant automaton has 19 states [2018-06-22 15:23:07,409 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 15:23:07,409 INFO ]: CoverageRelationStatistics Valid=42, Invalid=300, Unknown=0, NotChecked=0, Total=342 [2018-06-22 15:23:07,409 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 19 states. [2018-06-22 15:23:07,814 WARN ]: Spent 327.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 48 [2018-06-22 15:23:08,048 WARN ]: Spent 187.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 36 [2018-06-22 15:23:08,215 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 30 [2018-06-22 15:23:08,456 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 41 [2018-06-22 15:23:08,670 WARN ]: Spent 145.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 38 [2018-06-22 15:23:08,959 WARN ]: Spent 265.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 37 [2018-06-22 15:23:09,029 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:23:09,029 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:23:09,029 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:23:09,029 INFO ]: Start accepts. Automaton has 19 states. Word has length 29 [2018-06-22 15:23:09,030 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:23:09,030 INFO ]: With dead ends: 23 [2018-06-22 15:23:09,030 INFO ]: Without dead ends: 23 [2018-06-22 15:23:09,031 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 22 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=122, Invalid=528, Unknown=0, NotChecked=0, Total=650 [2018-06-22 15:23:09,031 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:23:09,036 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:23:09,036 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:23:09,037 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:23:09,037 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:23:09,037 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:23:09,037 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:23:09,037 INFO ]: Interpolant automaton has 19 states. [2018-06-22 15:23:09,037 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:23:09,037 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:23:09,038 INFO ]: Found error trace [2018-06-22 15:23:09,038 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:23:09,040 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:23:09,040 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-22 15:23:09,040 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:23:09,040 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:23:09,041 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:23:09,041 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:23:09,041 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:23:09,147 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:23:09,784 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:23:09,784 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:23:09,784 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:23:09,790 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:23:09,889 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:23:09,889 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:23:09,895 INFO ]: Computing forward predicates... [2018-06-22 15:23:10,762 WARN ]: Spent 599.00 ms on a formula simplification. DAG size of input: 130 DAG size of output: 38 [2018-06-22 15:23:11,072 WARN ]: Spent 196.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 32 [2018-06-22 15:23:11,250 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 23 [2018-06-22 15:23:11,819 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:23:11,848 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:23:11,848 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 22 [2018-06-22 15:23:11,848 INFO ]: Interpolant automaton has 22 states [2018-06-22 15:23:11,848 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-22 15:23:11,848 INFO ]: CoverageRelationStatistics Valid=50, Invalid=412, Unknown=0, NotChecked=0, Total=462 [2018-06-22 15:23:11,849 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 22 states. [2018-06-22 15:23:12,348 WARN ]: Spent 413.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 62 [2018-06-22 15:23:12,563 WARN ]: Spent 173.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 33 [2018-06-22 15:23:12,761 WARN ]: Spent 174.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 26 [2018-06-22 15:23:13,021 WARN ]: Spent 234.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 34 [2018-06-22 15:23:13,274 WARN ]: Spent 224.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 37 [2018-06-22 15:23:13,490 WARN ]: Spent 187.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 33 [2018-06-22 15:23:13,797 WARN ]: Spent 279.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 44 [2018-06-22 15:23:13,828 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:23:13,828 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:23:13,829 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:23:13,830 INFO ]: Start accepts. Automaton has 22 states. Word has length 33 [2018-06-22 15:23:13,830 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:23:13,830 INFO ]: With dead ends: 25 [2018-06-22 15:23:13,830 INFO ]: Without dead ends: 25 [2018-06-22 15:23:13,831 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 25 SyntacticMatches, 3 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=156, Invalid=714, Unknown=0, NotChecked=0, Total=870 [2018-06-22 15:23:13,831 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:23:13,834 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:23:13,834 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:23:13,835 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:23:13,835 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:23:13,835 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:23:13,835 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:23:13,835 INFO ]: Interpolant automaton has 22 states. [2018-06-22 15:23:13,835 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:23:13,836 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:23:13,836 INFO ]: Found error trace [2018-06-22 15:23:13,836 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:23:13,836 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:23:13,836 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 7 times [2018-06-22 15:23:13,836 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:23:13,836 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:23:13,837 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:23:13,837 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:23:13,837 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:23:13,973 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:23:14,341 WARN ]: Spent 134.00 ms on a formula simplification that was a NOOP. DAG size: 35 [2018-06-22 15:23:14,582 WARN ]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 41 [2018-06-22 15:23:14,840 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 32 [2018-06-22 15:23:15,184 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:23:15,185 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:23:15,185 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:23:15,191 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:23:15,287 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:23:15,301 INFO ]: Computing forward predicates... [2018-06-22 15:23:16,997 WARN ]: Spent 1.26 s on a formula simplification. DAG size of input: 108 DAG size of output: 95 [2018-06-22 15:23:17,357 WARN ]: Spent 292.00 ms on a formula simplification. DAG size of input: 66 DAG size of output: 46 [2018-06-22 15:23:17,606 WARN ]: Spent 161.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 41 [2018-06-22 15:23:17,782 WARN ]: Spent 133.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 43 [2018-06-22 15:23:18,889 WARN ]: Spent 896.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 49 [2018-06-22 15:23:19,114 WARN ]: Spent 174.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 31 Received shutdown request... [2018-06-22 15:23:56,680 INFO ]: Timeout while computing interpolants [2018-06-22 15:23:56,881 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:23:56,881 WARN ]: Verification canceled [2018-06-22 15:23:56,884 WARN ]: Timeout [2018-06-22 15:23:56,884 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:23:56 BoogieIcfgContainer [2018-06-22 15:23:56,885 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:23:56,885 INFO ]: Toolchain (without parser) took 65287.15 ms. Allocated memory was 308.8 MB in the beginning and 890.8 MB in the end (delta: 582.0 MB). Free memory was 259.2 MB in the beginning and 280.2 MB in the end (delta: -21.0 MB). Peak memory consumption was 669.5 MB. Max. memory is 3.6 GB. [2018-06-22 15:23:56,886 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:23:56,886 INFO ]: ChcToBoogie took 50.63 ms. Allocated memory is still 308.8 MB. Free memory was 259.2 MB in the beginning and 257.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:23:56,890 INFO ]: Boogie Preprocessor took 59.39 ms. Allocated memory is still 308.8 MB. Free memory was 257.2 MB in the beginning and 255.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:23:56,890 INFO ]: RCFGBuilder took 344.66 ms. Allocated memory is still 308.8 MB. Free memory was 255.2 MB in the beginning and 245.2 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:23:56,891 INFO ]: TraceAbstraction took 64823.79 ms. Allocated memory was 308.8 MB in the beginning and 890.8 MB in the end (delta: 582.0 MB). Free memory was 243.2 MB in the beginning and 280.2 MB in the end (delta: -36.9 MB). Peak memory consumption was 653.6 MB. Max. memory is 3.6 GB. [2018-06-22 15:23:56,893 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 50.63 ms. Allocated memory is still 308.8 MB. Free memory was 259.2 MB in the beginning and 257.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 59.39 ms. Allocated memory is still 308.8 MB. Free memory was 257.2 MB in the beginning and 255.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 344.66 ms. Allocated memory is still 308.8 MB. Free memory was 255.2 MB in the beginning and 245.2 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 64823.79 ms. Allocated memory was 308.8 MB in the beginning and 890.8 MB in the end (delta: 582.0 MB). Free memory was 243.2 MB in the beginning and 280.2 MB in the end (delta: -36.9 MB). Peak memory consumption was 653.6 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 38 with TraceHistMax 8, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 8 quantified variables from 7 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 64.7s OverallTime, 8 OverallIterations, 8 TraceHistogramMax, 6.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 88 SDtfs, 173 SDslu, 503 SDs, 0 SdLazy, 417 SolverSat, 215 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 235 GetRequests, 109 SyntacticMatches, 11 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 196 ImplicationChecksByTransitivity, 17.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=25occurred in iteration=7, 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, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 13.7s InterpolantComputationTime, 285 NumberOfCodeBlocks, 285 NumberOfCodeBlocksAsserted, 28 NumberOfCheckSat, 272 ConstructedInterpolants, 0 QuantifiedInterpolants, 211224 SizeOfPredicates, 360 NumberOfNonLiveVariables, 1353 ConjunctsInSsa, 221 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 112/406 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/nest-if8.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-23-56-902.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/nest-if8.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-23-56-902.csv Completed graceful shutdown