java -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/chccomp2018/chcToBoogie_automizer.epf -i /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_4_e1_821_e5_911.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-55b8104 [2018-06-18 16:14:35,946 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-18 16:14:35,948 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-18 16:14:35,962 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-18 16:14:35,962 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-18 16:14:35,963 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-18 16:14:35,965 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-18 16:14:35,966 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-18 16:14:35,968 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-18 16:14:35,968 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-18 16:14:35,971 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-18 16:14:35,972 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-18 16:14:35,972 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-18 16:14:35,973 INFO L177 SettingsManager]: ChcToBoogie provides no preferences, ignoring... [2018-06-18 16:14:35,975 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-18 16:14:35,976 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-18 16:14:35,977 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-18 16:14:35,979 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-18 16:14:35,990 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-18 16:14:35,991 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-18 16:14:35,992 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-18 16:14:35,995 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-18 16:14:35,995 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-18 16:14:35,995 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-18 16:14:35,996 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-18 16:14:35,997 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-18 16:14:35,998 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-18 16:14:35,998 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-18 16:14:36,005 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-18 16:14:36,005 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-18 16:14:36,006 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-18 16:14:36,006 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-18 16:14:36,006 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-18 16:14:36,007 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-18 16:14:36,008 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-18 16:14:36,008 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chccomp2018/chcToBoogie_automizer.epf [2018-06-18 16:14:36,020 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-18 16:14:36,021 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-18 16:14:36,021 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-18 16:14:36,021 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-18 16:14:36,023 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-18 16:14:36,023 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-18 16:14:36,023 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-18 16:14:36,023 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-18 16:14:36,023 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-18 16:14:36,024 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-18 16:14:36,024 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-18 16:14:36,024 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-18 16:14:36,024 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-18 16:14:36,024 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-18 16:14:36,025 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-18 16:14:36,025 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-18 16:14:36,025 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-18 16:14:36,026 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-18 16:14:36,027 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-18 16:14:36,074 INFO ]: Repository-Root is: /tmp [2018-06-18 16:14:36,090 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-18 16:14:36,095 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-18 16:14:36,097 INFO ]: Initializing SmtParser... [2018-06-18 16:14:36,098 INFO ]: SmtParser initialized [2018-06-18 16:14:36,098 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_4_e1_821_e5_911.smt2 [2018-06-18 16:14:36,100 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-18 16:14:36,189 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_4_e1_821_e5_911.smt2 unknown [2018-06-18 16:14:36,614 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_4_e1_821_e5_911.smt2 [2018-06-18 16:14:36,622 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-18 16:14:36,628 INFO ]: Walking toolchain with 4 elements. [2018-06-18 16:14:36,628 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-18 16:14:36,628 INFO ]: Initializing ChcToBoogie... [2018-06-18 16:14:36,628 INFO ]: ChcToBoogie initialized [2018-06-18 16:14:36,635 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 04:14:36" (1/1) ... [2018-06-18 16:14:36,706 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 04:14:36 Unit [2018-06-18 16:14:36,706 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-18 16:14:36,706 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-18 16:14:36,706 INFO ]: Initializing Boogie Preprocessor... [2018-06-18 16:14:36,706 INFO ]: Boogie Preprocessor initialized [2018-06-18 16:14:36,728 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 04:14:36" (1/1) ... [2018-06-18 16:14:36,728 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 04:14:36" (1/1) ... [2018-06-18 16:14:36,744 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 04:14:36" (1/1) ... [2018-06-18 16:14:36,744 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 04:14:36" (1/1) ... [2018-06-18 16:14:36,761 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 04:14:36" (1/1) ... [2018-06-18 16:14:36,762 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 04:14:36" (1/1) ... [2018-06-18 16:14:36,773 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 04:14:36" (1/1) ... [2018-06-18 16:14:36,776 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-18 16:14:36,776 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-18 16:14:36,776 INFO ]: Initializing RCFGBuilder... [2018-06-18 16:14:36,776 INFO ]: RCFGBuilder initialized [2018-06-18 16:14:36,777 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 04:14:36" (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-18 16:14:36,799 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-18 16:14:36,799 INFO ]: Found specification of procedure False [2018-06-18 16:14:36,799 INFO ]: Found implementation of procedure False [2018-06-18 16:14:36,799 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-18 16:14:36,799 INFO ]: Found specification of procedure state [2018-06-18 16:14:36,799 INFO ]: Found implementation of procedure state [2018-06-18 16:14:36,799 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-18 16:14:36,799 INFO ]: Found specification of procedure Ultimate.START [2018-06-18 16:14:36,799 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-18 16:14:37,229 INFO ]: Using library mode [2018-06-18 16:14:37,230 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 04:14:37 BoogieIcfgContainer [2018-06-18 16:14:37,230 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-18 16:14:37,231 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-18 16:14:37,231 INFO ]: Initializing TraceAbstraction... [2018-06-18 16:14:37,237 INFO ]: TraceAbstraction initialized [2018-06-18 16:14:37,237 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 04:14:36" (1/3) ... [2018-06-18 16:14:37,238 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@432d9686 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 18.06 04:14:37, skipping insertion in model container [2018-06-18 16:14:37,238 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 04:14:36" (2/3) ... [2018-06-18 16:14:37,238 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@432d9686 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.06 04:14:37, skipping insertion in model container [2018-06-18 16:14:37,238 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 04:14:37" (3/3) ... [2018-06-18 16:14:37,240 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-18 16:14:37,251 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-18 16:14:37,262 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-18 16:14:37,308 INFO ]: Using default assertion order modulation [2018-06-18 16:14:37,308 INFO ]: Interprodecural is true [2018-06-18 16:14:37,308 INFO ]: Hoare is false [2018-06-18 16:14:37,308 INFO ]: Compute interpolants for FPandBP [2018-06-18 16:14:37,308 INFO ]: Backedges is TWOTRACK [2018-06-18 16:14:37,308 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-18 16:14:37,308 INFO ]: Difference is false [2018-06-18 16:14:37,308 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-18 16:14:37,308 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-18 16:14:37,322 INFO ]: Start isEmpty. Operand 13 states. [2018-06-18 16:14:37,333 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-18 16:14:37,334 INFO ]: Found error trace [2018-06-18 16:14:37,336 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 16:14:37,336 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 16:14:37,341 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-18 16:14:37,343 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 16:14:37,344 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 16:14:37,380 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:37,380 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 16:14:37,380 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:37,513 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:14:37,522 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 16:14:37,750 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-18 16:14:37,753 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-18 16:14:37,753 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-18 16:14:37,755 INFO ]: Interpolant automaton has 4 states [2018-06-18 16:14:37,772 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-18 16:14:37,772 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 16:14:37,775 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-18 16:14:37,920 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 16:14:37,920 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-18 16:14:37,922 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-18 16:14:37,923 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-18 16:14:37,923 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 16:14:37,935 INFO ]: With dead ends: 13 [2018-06-18 16:14:37,935 INFO ]: Without dead ends: 13 [2018-06-18 16:14:37,936 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-18 16:14:37,950 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-18 16:14:37,975 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-18 16:14:37,976 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-18 16:14:37,977 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-18 16:14:37,978 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-18 16:14:37,978 INFO ]: Finished accepts. word is rejected. [2018-06-18 16:14:37,978 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-18 16:14:37,978 INFO ]: Interpolant automaton has 4 states. [2018-06-18 16:14:37,978 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-18 16:14:37,979 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-18 16:14:37,979 INFO ]: Found error trace [2018-06-18 16:14:37,979 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 16:14:37,979 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 16:14:37,980 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-18 16:14:37,980 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 16:14:37,980 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 16:14:37,980 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:37,980 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 16:14:37,980 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:38,086 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:14:38,087 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 16:14:38,450 WARN ]: Spent 124.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-18 16:14:38,537 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 16:14:38,537 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 16:14:38,537 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-18 16:14:38,545 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 16:14:38,684 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:14:38,695 INFO ]: Computing forward predicates... [2018-06-18 16:14:39,066 WARN ]: Spent 210.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 7 [2018-06-18 16:14:39,194 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 16:14:39,214 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 16:14:39,215 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-18 16:14:39,215 INFO ]: Interpolant automaton has 9 states [2018-06-18 16:14:39,215 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-18 16:14:39,215 INFO ]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-06-18 16:14:39,216 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-18 16:14:39,756 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 16:14:39,756 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-18 16:14:39,757 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-18 16:14:39,757 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-18 16:14:39,757 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 16:14:39,758 INFO ]: With dead ends: 15 [2018-06-18 16:14:39,758 INFO ]: Without dead ends: 15 [2018-06-18 16:14:39,759 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2018-06-18 16:14:39,759 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-18 16:14:39,761 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-18 16:14:39,761 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-18 16:14:39,762 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-18 16:14:39,763 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-18 16:14:39,764 INFO ]: Finished accepts. word is rejected. [2018-06-18 16:14:39,764 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-18 16:14:39,764 INFO ]: Interpolant automaton has 9 states. [2018-06-18 16:14:39,764 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-18 16:14:39,764 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-18 16:14:39,764 INFO ]: Found error trace [2018-06-18 16:14:39,764 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 16:14:39,764 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 16:14:39,764 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-18 16:14:39,765 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 16:14:39,765 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 16:14:39,765 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:39,765 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 16:14:39,765 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:39,897 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:14:39,898 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 16:14:40,368 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 16:14:40,368 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 16:14:40,368 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) [2018-06-18 16:14:40,385 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 16:14:40,541 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-18 16:14:40,541 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:14:40,547 INFO ]: Computing forward predicates... [2018-06-18 16:14:40,966 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 16:14:40,993 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 16:14:40,993 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-18 16:14:40,994 INFO ]: Interpolant automaton has 13 states [2018-06-18 16:14:40,994 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-18 16:14:40,994 INFO ]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2018-06-18 16:14:40,994 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 13 states. [2018-06-18 16:14:41,429 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 16:14:41,429 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-18 16:14:41,431 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-18 16:14:41,431 INFO ]: Start accepts. Automaton has 13 states. Word has length 17 [2018-06-18 16:14:41,431 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 16:14:41,431 INFO ]: With dead ends: 17 [2018-06-18 16:14:41,431 INFO ]: Without dead ends: 17 [2018-06-18 16:14:41,432 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=66, Invalid=206, Unknown=0, NotChecked=0, Total=272 [2018-06-18 16:14:41,432 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-18 16:14:41,435 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-18 16:14:41,435 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-18 16:14:41,436 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-18 16:14:41,436 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-18 16:14:41,436 INFO ]: Finished accepts. word is rejected. [2018-06-18 16:14:41,436 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-18 16:14:41,436 INFO ]: Interpolant automaton has 13 states. [2018-06-18 16:14:41,436 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-18 16:14:41,437 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-18 16:14:41,437 INFO ]: Found error trace [2018-06-18 16:14:41,437 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 16:14:41,437 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 16:14:41,437 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-18 16:14:41,437 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 16:14:41,437 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 16:14:41,438 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:41,438 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 16:14:41,438 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:41,593 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:14:41,594 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 16:14:42,068 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 16:14:42,068 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 16:14:42,068 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-18 16:14:42,075 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-18 16:14:42,278 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-18 16:14:42,278 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:14:42,286 INFO ]: Computing forward predicates... [2018-06-18 16:14:42,725 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 16:14:42,758 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 16:14:42,759 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2018-06-18 16:14:42,759 INFO ]: Interpolant automaton has 17 states [2018-06-18 16:14:42,759 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-18 16:14:42,760 INFO ]: CoverageRelationStatistics Valid=38, Invalid=234, Unknown=0, NotChecked=0, Total=272 [2018-06-18 16:14:42,760 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 17 states. [2018-06-18 16:14:43,270 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 16:14:43,270 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-18 16:14:43,270 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-18 16:14:43,270 INFO ]: Start accepts. Automaton has 17 states. Word has length 21 [2018-06-18 16:14:43,270 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 16:14:43,271 INFO ]: With dead ends: 19 [2018-06-18 16:14:43,271 INFO ]: Without dead ends: 19 [2018-06-18 16:14:43,271 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=98, Invalid=364, Unknown=0, NotChecked=0, Total=462 [2018-06-18 16:14:43,271 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-18 16:14:43,275 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-18 16:14:43,275 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-18 16:14:43,275 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-18 16:14:43,276 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-18 16:14:43,276 INFO ]: Finished accepts. word is rejected. [2018-06-18 16:14:43,276 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-18 16:14:43,276 INFO ]: Interpolant automaton has 17 states. [2018-06-18 16:14:43,276 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-18 16:14:43,276 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-18 16:14:43,276 INFO ]: Found error trace [2018-06-18 16:14:43,276 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 16:14:43,277 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 16:14:43,277 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-18 16:14:43,277 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 16:14:43,277 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 16:14:43,277 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:43,278 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 16:14:43,278 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:43,427 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:14:43,428 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 16:14:43,880 WARN ]: Spent 115.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-18 16:14:44,093 WARN ]: Spent 137.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 24 [2018-06-18 16:14:44,458 WARN ]: Spent 251.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 27 [2018-06-18 16:14:44,587 WARN ]: Spent 117.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 27 [2018-06-18 16:14:44,917 WARN ]: Spent 171.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 25 [2018-06-18 16:14:44,988 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-18 16:14:44,988 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 16:14:44,988 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-18 16:14:44,994 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-18 16:14:45,166 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-18 16:14:45,166 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:14:45,173 INFO ]: Computing forward predicates... [2018-06-18 16:14:45,826 INFO ]: Checked inductivity of 36 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-06-18 16:14:45,848 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 16:14:45,848 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 20 [2018-06-18 16:14:45,848 INFO ]: Interpolant automaton has 20 states [2018-06-18 16:14:45,848 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-18 16:14:45,848 INFO ]: CoverageRelationStatistics Valid=46, Invalid=334, Unknown=0, NotChecked=0, Total=380 [2018-06-18 16:14:45,848 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 20 states. [2018-06-18 16:14:46,021 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 59 [2018-06-18 16:14:46,407 WARN ]: Spent 288.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 69 [2018-06-18 16:14:46,622 WARN ]: Spent 179.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 69 [2018-06-18 16:14:46,764 WARN ]: Spent 110.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 58 [2018-06-18 16:14:46,920 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 16:14:46,920 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-18 16:14:46,921 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-18 16:14:46,921 INFO ]: Start accepts. Automaton has 20 states. Word has length 25 [2018-06-18 16:14:46,921 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 16:14:46,922 INFO ]: With dead ends: 21 [2018-06-18 16:14:46,922 INFO ]: Without dead ends: 21 [2018-06-18 16:14:46,922 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=132, Invalid=518, Unknown=0, NotChecked=0, Total=650 [2018-06-18 16:14:46,922 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-18 16:14:46,925 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-18 16:14:46,925 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-18 16:14:46,926 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-18 16:14:46,926 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-18 16:14:46,926 INFO ]: Finished accepts. word is rejected. [2018-06-18 16:14:46,926 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-18 16:14:46,926 INFO ]: Interpolant automaton has 20 states. [2018-06-18 16:14:46,926 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-18 16:14:46,927 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-18 16:14:46,927 INFO ]: Found error trace [2018-06-18 16:14:46,927 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 16:14:46,927 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 16:14:46,927 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-18 16:14:46,927 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 16:14:46,927 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 16:14:46,928 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:46,928 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 16:14:46,928 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:47,212 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:14:47,213 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 16:14:47,930 WARN ]: Spent 120.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-18 16:14:48,742 WARN ]: Spent 737.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 24 [2018-06-18 16:14:49,922 WARN ]: Spent 1.06 s on a formula simplification. DAG size of input: 157 DAG size of output: 28 [2018-06-18 16:14:50,513 WARN ]: Spent 340.00 ms on a formula simplification. DAG size of input: 227 DAG size of output: 22 [2018-06-18 16:14:50,876 WARN ]: Spent 271.00 ms on a formula simplification. DAG size of input: 225 DAG size of output: 21 [2018-06-18 16:14:51,559 WARN ]: Spent 589.00 ms on a formula simplification. DAG size of input: 284 DAG size of output: 24 [2018-06-18 16:14:52,044 WARN ]: Spent 298.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 21 [2018-06-18 16:14:52,119 INFO ]: Checked inductivity of 55 backedges. 0 proven. 39 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2018-06-18 16:14:52,119 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 16:14:52,119 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-18 16:14:52,127 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-18 16:14:52,372 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-18 16:14:52,372 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:14:52,384 INFO ]: Computing forward predicates... [2018-06-18 16:14:52,778 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-18 16:14:52,799 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 16:14:52,799 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14] total 24 [2018-06-18 16:14:52,800 INFO ]: Interpolant automaton has 24 states [2018-06-18 16:14:52,800 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-18 16:14:52,800 INFO ]: CoverageRelationStatistics Valid=54, Invalid=498, Unknown=0, NotChecked=0, Total=552 [2018-06-18 16:14:52,800 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 24 states. [2018-06-18 16:14:53,135 WARN ]: Spent 263.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 84 [2018-06-18 16:14:53,391 WARN ]: Spent 191.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 95 [2018-06-18 16:14:53,766 WARN ]: Spent 223.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 94 [2018-06-18 16:14:54,064 WARN ]: Spent 172.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 92 [2018-06-18 16:14:54,250 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 85 [2018-06-18 16:14:54,419 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 74 [2018-06-18 16:14:54,466 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 16:14:54,466 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-18 16:14:54,467 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-18 16:14:54,467 INFO ]: Start accepts. Automaton has 24 states. Word has length 29 [2018-06-18 16:14:54,467 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 16:14:54,467 INFO ]: With dead ends: 23 [2018-06-18 16:14:54,467 INFO ]: Without dead ends: 23 [2018-06-18 16:14:54,468 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 19 SyntacticMatches, 1 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=176, Invalid=754, Unknown=0, NotChecked=0, Total=930 [2018-06-18 16:14:54,468 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-18 16:14:54,472 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-18 16:14:54,472 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-18 16:14:54,473 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-18 16:14:54,473 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-18 16:14:54,473 INFO ]: Finished accepts. word is rejected. [2018-06-18 16:14:54,473 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-18 16:14:54,473 INFO ]: Interpolant automaton has 24 states. [2018-06-18 16:14:54,473 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-18 16:14:54,476 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-18 16:14:54,476 INFO ]: Found error trace [2018-06-18 16:14:54,476 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 16:14:54,476 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 16:14:54,476 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-18 16:14:54,476 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 16:14:54,476 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 16:14:54,477 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:54,477 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 16:14:54,477 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:14:54,962 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:14:54,963 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 16:14:56,950 WARN ]: Spent 116.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-18 16:14:59,981 WARN ]: Spent 2.79 s on a formula simplification. DAG size of input: 685 DAG size of output: 26 [2018-06-18 16:15:03,472 WARN ]: Spent 3.19 s on a formula simplification. DAG size of input: 412 DAG size of output: 21 [2018-06-18 16:15:08,502 WARN ]: Spent 4.84 s on a formula simplification. DAG size of input: 558 DAG size of output: 28 [2018-06-18 16:15:10,825 WARN ]: Spent 1.82 s on a formula simplification. DAG size of input: 453 DAG size of output: 33 [2018-06-18 16:15:12,605 WARN ]: Spent 1.60 s on a formula simplification. DAG size of input: 448 DAG size of output: 23 [2018-06-18 16:15:16,866 WARN ]: Spent 3.87 s on a formula simplification. DAG size of input: 1153 DAG size of output: 27 [2018-06-18 16:15:24,640 WARN ]: Spent 7.22 s on a formula simplification. DAG size of input: 1438 DAG size of output: 28 [2018-06-18 16:15:28,794 WARN ]: Spent 3.65 s on a formula simplification. DAG size of input: 1135 DAG size of output: 20 [2018-06-18 16:15:34,402 WARN ]: Spent 5.21 s on a formula simplification. DAG size of input: 680 DAG size of output: 19 [2018-06-18 16:15:34,418 INFO ]: Checked inductivity of 78 backedges. 2 proven. 54 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2018-06-18 16:15:34,418 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 16:15:34,418 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-18 16:15:34,424 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-18 16:15:34,717 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-18 16:15:34,717 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:15:34,728 INFO ]: Computing forward predicates... [2018-06-18 16:15:35,260 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-18 16:15:35,294 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 16:15:35,294 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 16] total 28 [2018-06-18 16:15:35,295 INFO ]: Interpolant automaton has 28 states [2018-06-18 16:15:35,295 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-18 16:15:35,295 INFO ]: CoverageRelationStatistics Valid=79, Invalid=677, Unknown=0, NotChecked=0, Total=756 [2018-06-18 16:15:35,295 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 28 states. [2018-06-18 16:15:35,526 WARN ]: Spent 133.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 77 [2018-06-18 16:15:35,733 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 86 [2018-06-18 16:15:35,935 WARN ]: Spent 170.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 87 [2018-06-18 16:15:36,149 WARN ]: Spent 181.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 94 [2018-06-18 16:15:36,354 WARN ]: Spent 166.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 87 [2018-06-18 16:15:36,547 WARN ]: Spent 146.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 80 [2018-06-18 16:15:36,719 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 72 [2018-06-18 16:15:36,765 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 16:15:36,766 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-18 16:15:36,766 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-18 16:15:36,766 INFO ]: Start accepts. Automaton has 28 states. Word has length 33 [2018-06-18 16:15:36,767 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 16:15:36,767 INFO ]: With dead ends: 25 [2018-06-18 16:15:36,767 INFO ]: Without dead ends: 25 [2018-06-18 16:15:36,768 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 21 SyntacticMatches, 1 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 38.0s TimeCoverageRelationStatistics Valid=246, Invalid=1014, Unknown=0, NotChecked=0, Total=1260 [2018-06-18 16:15:36,768 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-18 16:15:36,772 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-18 16:15:36,772 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-18 16:15:36,774 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-18 16:15:36,774 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-18 16:15:36,775 INFO ]: Finished accepts. word is rejected. [2018-06-18 16:15:36,775 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-18 16:15:36,775 INFO ]: Interpolant automaton has 28 states. [2018-06-18 16:15:36,775 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-18 16:15:36,776 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-18 16:15:36,776 INFO ]: Found error trace [2018-06-18 16:15:36,776 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 16:15:36,776 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 16:15:36,776 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-18 16:15:36,776 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 16:15:36,776 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 16:15:36,777 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:15:36,779 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 16:15:36,779 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 16:15:37,758 INFO ]: Conjunction of SSA is unsat [2018-06-18 16:15:37,760 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. Received shutdown request... [2018-06-18 16:15:41,049 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,064 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,065 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,066 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,066 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,090 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,114 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,185 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,234 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,345 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,405 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,463 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,521 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,576 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,615 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,660 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,682 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,693 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,694 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,694 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,694 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,694 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,695 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 16:15:41,701 WARN ]: Verification canceled [2018-06-18 16:15:41,706 WARN ]: Timeout [2018-06-18 16:15:41,707 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.06 04:15:41 BoogieIcfgContainer [2018-06-18 16:15:41,707 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-18 16:15:41,708 INFO ]: Toolchain (without parser) took 65085.65 ms. Allocated memory was 307.2 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 249.6 MB in the beginning and 790.9 MB in the end (delta: -541.3 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-18 16:15:41,709 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 307.2 MB. Free memory is still 272.7 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-18 16:15:41,709 INFO ]: ChcToBoogie took 77.92 ms. Allocated memory is still 307.2 MB. Free memory was 248.6 MB in the beginning and 245.6 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-18 16:15:41,710 INFO ]: Boogie Preprocessor took 69.37 ms. Allocated memory is still 307.2 MB. Free memory was 245.6 MB in the beginning and 243.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-18 16:15:41,710 INFO ]: RCFGBuilder took 453.40 ms. Allocated memory is still 307.2 MB. Free memory was 243.6 MB in the beginning and 220.6 MB in the end (delta: 23.1 MB). Peak memory consumption was 23.1 MB. Max. memory is 3.6 GB. [2018-06-18 16:15:41,710 INFO ]: TraceAbstraction took 64476.02 ms. Allocated memory was 307.2 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 219.6 MB in the beginning and 790.9 MB in the end (delta: -571.4 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-18 16:15:41,714 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 307.2 MB. Free memory is still 272.7 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 77.92 ms. Allocated memory is still 307.2 MB. Free memory was 248.6 MB in the beginning and 245.6 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.37 ms. Allocated memory is still 307.2 MB. Free memory was 245.6 MB in the beginning and 243.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 453.40 ms. Allocated memory is still 307.2 MB. Free memory was 243.6 MB in the beginning and 220.6 MB in the end (delta: 23.1 MB). Peak memory consumption was 23.1 MB. Max. memory is 3.6 GB. * TraceAbstraction took 64476.02 ms. Allocated memory was 307.2 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 219.6 MB in the beginning and 790.9 MB in the end (delta: -571.4 MB). Peak memory consumption was 1.3 GB. 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 InterpolatingTraceCheckCraig was constructing Craig interpolants, while NestedInterpolantsBuilder was constructing predicates for 36 interpolants. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 64.4s OverallTime, 8 OverallIterations, 8 TraceHistogramMax, 5.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 76 SDtfs, 201 SDslu, 554 SDs, 0 SdLazy, 429 SolverSat, 262 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 234 GetRequests, 98 SyntacticMatches, 3 SemanticMatches, 133 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 272 ImplicationChecksByTransitivity, 49.3s 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.3s SsaConstructionTime, 2.3s SatisfiabilityAnalysisTime, 50.5s InterpolantComputationTime, 285 NumberOfCodeBlocks, 285 NumberOfCodeBlocksAsserted, 29 NumberOfCheckSat, 272 ConstructedInterpolants, 0 QuantifiedInterpolants, 70588 SizeOfPredicates, 204 NumberOfNonLiveVariables, 6039 ConjunctsInSsa, 270 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 117/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/metros_4_e1_821_e5_911.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-18_16-15-41-724.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/metros_4_e1_821_e5_911.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-18_16-15-41-724.csv Completed graceful shutdown