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/lustre/metros_5.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 19:28:19,219 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 19:28:19,221 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 19:28:19,235 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 19:28:19,236 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 19:28:19,236 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 19:28:19,240 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 19:28:19,242 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 19:28:19,243 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 19:28:19,245 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 19:28:19,246 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 19:28:19,246 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 19:28:19,247 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 19:28:19,248 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 19:28:19,248 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 19:28:19,253 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 19:28:19,254 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 19:28:19,263 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 19:28:19,265 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 19:28:19,266 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 19:28:19,267 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 19:28:19,276 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 19:28:19,277 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 19:28:19,277 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 19:28:19,278 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 19:28:19,278 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 19:28:19,279 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 19:28:19,280 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 19:28:19,281 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 19:28:19,281 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 19:28:19,281 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 19:28:19,282 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 19:28:19,282 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 19:28:19,289 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 19:28:19,289 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 19:28:19,290 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 19:28:19,307 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 19:28:19,308 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 19:28:19,308 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 19:28:19,308 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 19:28:19,309 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 19:28:19,309 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 19:28:19,309 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 19:28:19,310 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 19:28:19,312 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 19:28:19,313 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 19:28:19,313 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 19:28:19,313 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 19:28:19,313 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 19:28:19,313 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 19:28:19,313 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 19:28:19,314 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 19:28:19,314 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 19:28:19,314 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 19:28:19,314 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 19:28:19,316 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 19:28:19,317 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 19:28:19,372 INFO ]: Repository-Root is: /tmp [2018-06-22 19:28:19,385 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 19:28:19,389 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 19:28:19,391 INFO ]: Initializing SmtParser... [2018-06-22 19:28:19,391 INFO ]: SmtParser initialized [2018-06-22 19:28:19,392 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_5.smt2 [2018-06-22 19:28:19,393 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 19:28:19,484 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_5.smt2 unknown [2018-06-22 19:28:19,952 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_5.smt2 [2018-06-22 19:28:19,956 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 19:28:19,967 INFO ]: Walking toolchain with 4 elements. [2018-06-22 19:28:19,968 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 19:28:19,968 INFO ]: Initializing ChcToBoogie... [2018-06-22 19:28:19,968 INFO ]: ChcToBoogie initialized [2018-06-22 19:28:19,978 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 07:28:19" (1/1) ... [2018-06-22 19:28:20,067 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:28:20 Unit [2018-06-22 19:28:20,067 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 19:28:20,068 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 19:28:20,068 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 19:28:20,068 INFO ]: Boogie Preprocessor initialized [2018-06-22 19:28:20,090 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:28:20" (1/1) ... [2018-06-22 19:28:20,090 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:28:20" (1/1) ... [2018-06-22 19:28:20,111 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:28:20" (1/1) ... [2018-06-22 19:28:20,112 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:28:20" (1/1) ... [2018-06-22 19:28:20,117 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:28:20" (1/1) ... [2018-06-22 19:28:20,118 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:28:20" (1/1) ... [2018-06-22 19:28:20,129 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:28:20" (1/1) ... [2018-06-22 19:28:20,133 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 19:28:20,133 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 19:28:20,133 INFO ]: Initializing RCFGBuilder... [2018-06-22 19:28:20,133 INFO ]: RCFGBuilder initialized [2018-06-22 19:28:20,134 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:28:20" (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 19:28:20,164 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 19:28:20,164 INFO ]: Found specification of procedure False [2018-06-22 19:28:20,164 INFO ]: Found implementation of procedure False [2018-06-22 19:28:20,164 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 19:28:20,164 INFO ]: Found specification of procedure state [2018-06-22 19:28:20,164 INFO ]: Found implementation of procedure state [2018-06-22 19:28:20,164 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 19:28:20,164 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 19:28:20,164 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 19:28:20,561 INFO ]: Using library mode [2018-06-22 19:28:20,562 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 07:28:20 BoogieIcfgContainer [2018-06-22 19:28:20,562 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 19:28:20,563 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 19:28:20,563 INFO ]: Initializing TraceAbstraction... [2018-06-22 19:28:20,569 INFO ]: TraceAbstraction initialized [2018-06-22 19:28:20,569 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 07:28:19" (1/3) ... [2018-06-22 19:28:20,570 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1647cc51 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 07:28:20, skipping insertion in model container [2018-06-22 19:28:20,570 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:28:20" (2/3) ... [2018-06-22 19:28:20,570 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1647cc51 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 07:28:20, skipping insertion in model container [2018-06-22 19:28:20,570 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 07:28:20" (3/3) ... [2018-06-22 19:28:20,573 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 19:28:20,583 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 19:28:20,593 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 19:28:20,638 INFO ]: Using default assertion order modulation [2018-06-22 19:28:20,639 INFO ]: Interprodecural is true [2018-06-22 19:28:20,639 INFO ]: Hoare is false [2018-06-22 19:28:20,639 INFO ]: Compute interpolants for FPandBP [2018-06-22 19:28:20,639 INFO ]: Backedges is TWOTRACK [2018-06-22 19:28:20,639 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 19:28:20,639 INFO ]: Difference is false [2018-06-22 19:28:20,639 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 19:28:20,639 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 19:28:20,652 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 19:28:20,668 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 19:28:20,668 INFO ]: Found error trace [2018-06-22 19:28:20,669 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:28:20,669 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:28:20,675 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 19:28:20,677 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:28:20,678 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:28:20,728 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:28:20,728 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:28:20,728 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:28:20,832 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:28:20,999 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 19:28:21,001 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 19:28:21,001 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 19:28:21,002 INFO ]: Interpolant automaton has 4 states [2018-06-22 19:28:21,013 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 19:28:21,013 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 19:28:21,015 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 19:28:21,156 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:28:21,156 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 19:28:21,157 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 19:28:21,158 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 19:28:21,158 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:28:21,187 INFO ]: With dead ends: 13 [2018-06-22 19:28:21,187 INFO ]: Without dead ends: 13 [2018-06-22 19:28:21,189 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 19:28:21,214 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 19:28:21,238 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 19:28:21,239 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 19:28:21,240 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 19:28:21,241 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 19:28:21,241 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:28:21,241 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 19:28:21,241 INFO ]: Interpolant automaton has 4 states. [2018-06-22 19:28:21,242 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 19:28:21,243 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 19:28:21,243 INFO ]: Found error trace [2018-06-22 19:28:21,243 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:28:21,243 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:28:21,243 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 19:28:21,243 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:28:21,243 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:28:21,244 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:28:21,244 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:28:21,244 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:28:21,363 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:28:21,803 WARN ]: Spent 143.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-22 19:28:21,995 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 19:28:21,995 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:28:21,995 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 19:28:22,002 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:28:22,158 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:28:22,169 INFO ]: Computing forward predicates... [2018-06-22 19:28:22,643 WARN ]: Spent 292.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-22 19:28:22,821 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 19:28:22,856 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:28:22,856 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 19:28:22,856 INFO ]: Interpolant automaton has 9 states [2018-06-22 19:28:22,857 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 19:28:22,857 INFO ]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-06-22 19:28:22,857 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 19:28:23,232 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:28:23,232 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 19:28:23,232 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 19:28:23,232 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 19:28:23,233 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:28:23,233 INFO ]: With dead ends: 15 [2018-06-22 19:28:23,233 INFO ]: Without dead ends: 15 [2018-06-22 19:28:23,234 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2018-06-22 19:28:23,234 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 19:28:23,237 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 19:28:23,237 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 19:28:23,237 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 19:28:23,237 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 19:28:23,237 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:28:23,238 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 19:28:23,238 INFO ]: Interpolant automaton has 9 states. [2018-06-22 19:28:23,238 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 19:28:23,238 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 19:28:23,238 INFO ]: Found error trace [2018-06-22 19:28:23,238 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:28:23,238 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:28:23,238 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 19:28:23,238 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:28:23,238 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:28:23,239 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:28:23,239 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:28:23,239 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:28:23,333 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:28:23,687 WARN ]: Spent 128.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-22 19:28:23,796 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 19:28:23,796 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:28:23,796 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 19:28:23,816 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 19:28:23,962 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 19:28:23,962 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:28:23,969 INFO ]: Computing forward predicates... [2018-06-22 19:28:24,256 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 19:28:24,281 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:28:24,281 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-22 19:28:24,281 INFO ]: Interpolant automaton has 13 states [2018-06-22 19:28:24,282 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 19:28:24,282 INFO ]: CoverageRelationStatistics Valid=26, Invalid=130, Unknown=0, NotChecked=0, Total=156 [2018-06-22 19:28:24,282 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 13 states. [2018-06-22 19:28:24,718 WARN ]: Spent 174.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 73 [2018-06-22 19:28:24,919 WARN ]: Spent 153.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 48 [2018-06-22 19:28:24,960 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:28:24,960 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 19:28:24,962 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 19:28:24,962 INFO ]: Start accepts. Automaton has 13 states. Word has length 17 [2018-06-22 19:28:24,962 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:28:24,963 INFO ]: With dead ends: 17 [2018-06-22 19:28:24,963 INFO ]: Without dead ends: 17 [2018-06-22 19:28:24,963 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=59, Invalid=213, Unknown=0, NotChecked=0, Total=272 [2018-06-22 19:28:24,963 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 19:28:24,966 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 19:28:24,966 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 19:28:24,967 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 19:28:24,967 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 19:28:24,967 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:28:24,967 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 19:28:24,967 INFO ]: Interpolant automaton has 13 states. [2018-06-22 19:28:24,967 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 19:28:24,968 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 19:28:24,968 INFO ]: Found error trace [2018-06-22 19:28:24,968 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:28:24,968 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:28:24,968 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 19:28:24,968 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:28:24,968 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:28:24,969 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:28:24,969 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:28:24,969 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:28:25,099 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:28:25,580 WARN ]: Spent 190.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 26 [2018-06-22 19:28:25,920 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 19:28:25,920 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:28:25,920 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 19:28:25,938 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 19:28:26,113 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 19:28:26,113 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:28:26,121 INFO ]: Computing forward predicates... [2018-06-22 19:28:26,544 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 19:28:26,569 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:28:26,569 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2018-06-22 19:28:26,570 INFO ]: Interpolant automaton has 17 states [2018-06-22 19:28:26,570 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 19:28:26,570 INFO ]: CoverageRelationStatistics Valid=34, Invalid=238, Unknown=0, NotChecked=0, Total=272 [2018-06-22 19:28:26,570 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 17 states. [2018-06-22 19:28:26,808 WARN ]: Spent 184.00 ms on a formula simplification that was a NOOP. DAG size: 104 [2018-06-22 19:28:27,392 WARN ]: Spent 405.00 ms on a formula simplification. DAG size of input: 144 DAG size of output: 132 [2018-06-22 19:28:27,702 WARN ]: Spent 252.00 ms on a formula simplification. DAG size of input: 127 DAG size of output: 120 [2018-06-22 19:28:27,970 WARN ]: Spent 225.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 91 [2018-06-22 19:28:28,069 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:28:28,069 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 19:28:28,071 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 19:28:28,071 INFO ]: Start accepts. Automaton has 17 states. Word has length 21 [2018-06-22 19:28:28,071 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:28:28,071 INFO ]: With dead ends: 19 [2018-06-22 19:28:28,071 INFO ]: Without dead ends: 19 [2018-06-22 19:28:28,072 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=89, Invalid=373, Unknown=0, NotChecked=0, Total=462 [2018-06-22 19:28:28,072 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 19:28:28,075 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 19:28:28,075 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 19:28:28,076 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 19:28:28,076 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 19:28:28,076 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:28:28,076 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 19:28:28,076 INFO ]: Interpolant automaton has 17 states. [2018-06-22 19:28:28,076 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 19:28:28,078 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 19:28:28,078 INFO ]: Found error trace [2018-06-22 19:28:28,078 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:28:28,078 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:28:28,078 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-22 19:28:28,078 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:28:28,078 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:28:28,079 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:28:28,079 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:28:28,079 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:28:28,266 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:28:28,838 WARN ]: Spent 136.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-22 19:28:29,159 WARN ]: Spent 283.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 31 [2018-06-22 19:28:29,741 WARN ]: Spent 472.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 35 [2018-06-22 19:28:30,081 WARN ]: Spent 317.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 31 [2018-06-22 19:28:30,480 WARN ]: Spent 301.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 27 [2018-06-22 19:28:31,027 WARN ]: Spent 496.00 ms on a formula simplification. DAG size of input: 138 DAG size of output: 37 [2018-06-22 19:28:31,168 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 19:28:31,168 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:28:31,168 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) [2018-06-22 19:28:31,185 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 19:28:31,365 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 19:28:31,365 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:28:31,379 INFO ]: Computing forward predicates... [2018-06-22 19:28:31,547 WARN ]: Spent 100.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-22 19:28:32,016 INFO ]: Checked inductivity of 36 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-06-22 19:28:32,037 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:28:32,037 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 20 [2018-06-22 19:28:32,038 INFO ]: Interpolant automaton has 20 states [2018-06-22 19:28:32,038 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 19:28:32,038 INFO ]: CoverageRelationStatistics Valid=43, Invalid=337, Unknown=0, NotChecked=0, Total=380 [2018-06-22 19:28:32,038 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 20 states. [2018-06-22 19:28:32,302 WARN ]: Spent 210.00 ms on a formula simplification that was a NOOP. DAG size: 109 [2018-06-22 19:28:32,884 WARN ]: Spent 464.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 116 [2018-06-22 19:28:33,649 WARN ]: Spent 687.00 ms on a formula simplification. DAG size of input: 172 DAG size of output: 132 [2018-06-22 19:28:34,305 WARN ]: Spent 597.00 ms on a formula simplification. DAG size of input: 160 DAG size of output: 148 [2018-06-22 19:28:34,634 WARN ]: Spent 279.00 ms on a formula simplification. DAG size of input: 102 DAG size of output: 96 [2018-06-22 19:28:34,699 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:28:34,699 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 19:28:34,700 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 19:28:34,700 INFO ]: Start accepts. Automaton has 20 states. Word has length 25 [2018-06-22 19:28:34,700 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:28:34,701 INFO ]: With dead ends: 21 [2018-06-22 19:28:34,701 INFO ]: Without dead ends: 21 [2018-06-22 19:28:34,701 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 5.4s TimeCoverageRelationStatistics Valid=128, Invalid=522, Unknown=0, NotChecked=0, Total=650 [2018-06-22 19:28:34,701 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 19:28:34,703 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 19:28:34,703 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 19:28:34,703 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 19:28:34,703 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 19:28:34,704 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:28:34,704 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 19:28:34,704 INFO ]: Interpolant automaton has 20 states. [2018-06-22 19:28:34,705 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 19:28:34,706 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 19:28:34,706 INFO ]: Found error trace [2018-06-22 19:28:34,706 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:28:34,707 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:28:34,707 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-22 19:28:34,707 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:28:34,707 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:28:34,707 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:28:34,707 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:28:34,707 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:28:35,016 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:28:36,019 WARN ]: Spent 143.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-22 19:28:38,726 WARN ]: Spent 2.57 s on a formula simplification. DAG size of input: 288 DAG size of output: 37 [2018-06-22 19:28:41,163 WARN ]: Spent 2.35 s on a formula simplification. DAG size of input: 356 DAG size of output: 34 [2018-06-22 19:28:42,328 WARN ]: Spent 1.05 s on a formula simplification. DAG size of input: 222 DAG size of output: 33 [2018-06-22 19:28:43,267 WARN ]: Spent 846.00 ms on a formula simplification. DAG size of input: 377 DAG size of output: 35 [2018-06-22 19:28:44,876 WARN ]: Spent 1.38 s on a formula simplification. DAG size of input: 375 DAG size of output: 32 [2018-06-22 19:28:46,510 WARN ]: Spent 1.49 s on a formula simplification. DAG size of input: 390 DAG size of output: 39 [2018-06-22 19:28:50,069 WARN ]: Spent 3.33 s on a formula simplification. DAG size of input: 472 DAG size of output: 49 [2018-06-22 19:28:51,221 WARN ]: Spent 1.05 s on a formula simplification. DAG size of input: 186 DAG size of output: 60 [2018-06-22 19:28:51,246 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 19:28:51,246 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:28:51,246 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 19:28:51,253 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 19:28:51,541 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 19:28:51,541 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:28:51,557 INFO ]: Computing forward predicates... [2018-06-22 19:28:52,465 WARN ]: Spent 290.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 49 [2018-06-22 19:28:52,505 INFO ]: Checked inductivity of 55 backedges. 0 proven. 39 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2018-06-22 19:28:52,527 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:28:52,527 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 24 [2018-06-22 19:28:52,527 INFO ]: Interpolant automaton has 24 states [2018-06-22 19:28:52,527 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 19:28:52,527 INFO ]: CoverageRelationStatistics Valid=52, Invalid=500, Unknown=0, NotChecked=0, Total=552 [2018-06-22 19:28:52,528 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 24 states. [2018-06-22 19:28:53,080 WARN ]: Spent 481.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 143 [2018-06-22 19:28:53,411 WARN ]: Spent 162.00 ms on a formula simplification that was a NOOP. DAG size: 83 [2018-06-22 19:28:55,279 WARN ]: Spent 1.79 s on a formula simplification. DAG size of input: 260 DAG size of output: 201 [2018-06-22 19:28:57,613 WARN ]: Spent 2.16 s on a formula simplification. DAG size of input: 289 DAG size of output: 237 [2018-06-22 19:28:59,939 WARN ]: Spent 2.24 s on a formula simplification. DAG size of input: 292 DAG size of output: 250 [2018-06-22 19:29:01,038 WARN ]: Spent 962.00 ms on a formula simplification. DAG size of input: 232 DAG size of output: 214 [2018-06-22 19:29:01,594 WARN ]: Spent 456.00 ms on a formula simplification. DAG size of input: 142 DAG size of output: 130 [2018-06-22 19:29:01,690 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:29:01,690 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 19:29:01,691 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 19:29:01,691 INFO ]: Start accepts. Automaton has 24 states. Word has length 29 [2018-06-22 19:29:01,691 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:29:01,692 INFO ]: With dead ends: 23 [2018-06-22 19:29:01,692 INFO ]: Without dead ends: 23 [2018-06-22 19:29:01,693 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 24.4s TimeCoverageRelationStatistics Valid=171, Invalid=759, Unknown=0, NotChecked=0, Total=930 [2018-06-22 19:29:01,693 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 19:29:01,697 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 19:29:01,697 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 19:29:01,698 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 19:29:01,698 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 19:29:01,698 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:29:01,698 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 19:29:01,698 INFO ]: Interpolant automaton has 24 states. [2018-06-22 19:29:01,698 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 19:29:01,699 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 19:29:01,699 INFO ]: Found error trace [2018-06-22 19:29:01,699 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:29:01,699 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:29:01,699 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-22 19:29:01,699 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:29:01,699 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:29:01,700 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:29:01,700 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:29:01,700 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:29:02,274 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:29:11,360 WARN ]: Spent 4.76 s on a formula simplification. DAG size of input: 697 DAG size of output: 12 Received shutdown request... [2018-06-22 19:29:25,675 WARN ]: Removed 2 from assertion stack [2018-06-22 19:29:25,675 WARN ]: Verification canceled [2018-06-22 19:29:25,679 WARN ]: Timeout [2018-06-22 19:29:25,679 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 07:29:25 BoogieIcfgContainer [2018-06-22 19:29:25,679 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 19:29:25,680 INFO ]: Toolchain (without parser) took 65723.66 ms. Allocated memory was 307.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 249.1 MB in the beginning and 840.8 MB in the end (delta: -591.6 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 19:29:25,680 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 307.8 MB. Free memory is still 273.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 19:29:25,681 INFO ]: ChcToBoogie took 99.59 ms. Allocated memory is still 307.8 MB. Free memory was 249.1 MB in the beginning and 247.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 19:29:25,681 INFO ]: Boogie Preprocessor took 65.04 ms. Allocated memory is still 307.8 MB. Free memory was 247.1 MB in the beginning and 245.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 19:29:25,681 INFO ]: RCFGBuilder took 428.72 ms. Allocated memory is still 307.8 MB. Free memory was 245.2 MB in the beginning and 222.0 MB in the end (delta: 23.1 MB). Peak memory consumption was 23.1 MB. Max. memory is 3.6 GB. [2018-06-22 19:29:25,682 INFO ]: TraceAbstraction took 65115.76 ms. Allocated memory was 307.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 221.0 MB in the beginning and 840.8 MB in the end (delta: -619.7 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 19:29:25,683 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.8 MB. Free memory is still 273.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 99.59 ms. Allocated memory is still 307.8 MB. Free memory was 249.1 MB in the beginning and 247.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 65.04 ms. Allocated memory is still 307.8 MB. Free memory was 247.1 MB in the beginning and 245.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 428.72 ms. Allocated memory is still 307.8 MB. Free memory was 245.2 MB in the beginning and 222.0 MB in the end (delta: 23.1 MB). Peak memory consumption was 23.1 MB. Max. memory is 3.6 GB. * TraceAbstraction took 65115.76 ms. Allocated memory was 307.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 221.0 MB in the beginning and 840.8 MB in the end (delta: -619.7 MB). Peak memory consumption was 1.2 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 34 with TraceHistMax 7, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 798. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 65.0s OverallTime, 7 OverallIterations, 7 TraceHistogramMax, 14.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 69 SDtfs, 140 SDslu, 442 SDs, 0 SdLazy, 358 SolverSat, 182 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 179 GetRequests, 79 SyntacticMatches, 0 SemanticMatches, 100 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 118 ImplicationChecksByTransitivity, 34.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=23occurred in iteration=6, 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, 6 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 1.5s SatisfiabilityAnalysisTime, 24.2s InterpolantComputationTime, 219 NumberOfCodeBlocks, 219 NumberOfCodeBlocksAsserted, 21 NumberOfCheckSat, 208 ConstructedInterpolants, 0 QuantifiedInterpolants, 136928 SizeOfPredicates, 141 NumberOfNonLiveVariables, 4435 ConjunctsInSsa, 296 ConjunctsInUnsatCore, 11 InterpolantComputations, 1 PerfectInterpolantSequences, 72/250 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_5.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_19-29-25-692.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/metros_5.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_19-29-25-692.csv Completed graceful shutdown