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_4_e2_968_e1_956.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 19:21:12,145 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 19:21:12,147 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 19:21:12,160 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 19:21:12,161 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 19:21:12,162 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 19:21:12,165 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 19:21:12,167 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 19:21:12,168 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 19:21:12,170 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 19:21:12,171 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 19:21:12,171 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 19:21:12,172 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 19:21:12,173 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 19:21:12,177 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 19:21:12,178 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 19:21:12,180 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 19:21:12,191 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 19:21:12,192 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 19:21:12,193 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 19:21:12,194 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 19:21:12,196 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 19:21:12,197 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 19:21:12,197 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 19:21:12,198 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 19:21:12,198 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 19:21:12,199 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 19:21:12,200 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 19:21:12,201 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 19:21:12,201 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 19:21:12,201 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 19:21:12,202 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 19:21:12,202 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 19:21:12,203 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 19:21:12,204 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 19:21:12,204 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:21:12,219 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 19:21:12,219 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 19:21:12,220 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 19:21:12,220 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 19:21:12,221 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 19:21:12,221 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 19:21:12,221 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 19:21:12,222 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 19:21:12,222 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 19:21:12,222 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 19:21:12,222 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 19:21:12,222 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 19:21:12,223 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 19:21:12,223 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 19:21:12,223 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 19:21:12,223 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 19:21:12,223 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 19:21:12,223 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 19:21:12,224 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 19:21:12,225 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 19:21:12,225 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 19:21:12,277 INFO ]: Repository-Root is: /tmp [2018-06-22 19:21:12,292 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 19:21:12,297 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 19:21:12,298 INFO ]: Initializing SmtParser... [2018-06-22 19:21:12,298 INFO ]: SmtParser initialized [2018-06-22 19:21:12,299 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_4_e2_968_e1_956.smt2 [2018-06-22 19:21:12,301 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:21:12,398 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_4_e2_968_e1_956.smt2 unknown [2018-06-22 19:21:12,804 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_4_e2_968_e1_956.smt2 [2018-06-22 19:21:12,809 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 19:21:12,820 INFO ]: Walking toolchain with 4 elements. [2018-06-22 19:21:12,821 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 19:21:12,821 INFO ]: Initializing ChcToBoogie... [2018-06-22 19:21:12,821 INFO ]: ChcToBoogie initialized [2018-06-22 19:21:12,829 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 07:21:12" (1/1) ... [2018-06-22 19:21:12,889 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:21:12 Unit [2018-06-22 19:21:12,889 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 19:21:12,889 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 19:21:12,889 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 19:21:12,889 INFO ]: Boogie Preprocessor initialized [2018-06-22 19:21:12,917 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:21:12" (1/1) ... [2018-06-22 19:21:12,917 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:21:12" (1/1) ... [2018-06-22 19:21:12,928 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:21:12" (1/1) ... [2018-06-22 19:21:12,929 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:21:12" (1/1) ... [2018-06-22 19:21:12,941 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:21:12" (1/1) ... [2018-06-22 19:21:12,942 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:21:12" (1/1) ... [2018-06-22 19:21:12,948 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:21:12" (1/1) ... [2018-06-22 19:21:12,952 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 19:21:12,953 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 19:21:12,953 INFO ]: Initializing RCFGBuilder... [2018-06-22 19:21:12,953 INFO ]: RCFGBuilder initialized [2018-06-22 19:21:12,954 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:21:12" (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) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 19:21:12,966 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 19:21:12,966 INFO ]: Found specification of procedure False [2018-06-22 19:21:12,966 INFO ]: Found implementation of procedure False [2018-06-22 19:21:12,966 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 19:21:12,966 INFO ]: Found specification of procedure state [2018-06-22 19:21:12,966 INFO ]: Found implementation of procedure state [2018-06-22 19:21:12,966 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 19:21:12,966 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 19:21:12,966 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 19:21:13,386 INFO ]: Using library mode [2018-06-22 19:21:13,391 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 07:21:13 BoogieIcfgContainer [2018-06-22 19:21:13,391 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 19:21:13,393 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 19:21:13,393 INFO ]: Initializing TraceAbstraction... [2018-06-22 19:21:13,400 INFO ]: TraceAbstraction initialized [2018-06-22 19:21:13,400 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 07:21:12" (1/3) ... [2018-06-22 19:21:13,401 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7d13e891 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 07:21:13, skipping insertion in model container [2018-06-22 19:21:13,401 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:21:12" (2/3) ... [2018-06-22 19:21:13,402 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7d13e891 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 07:21:13, skipping insertion in model container [2018-06-22 19:21:13,402 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 07:21:13" (3/3) ... [2018-06-22 19:21:13,404 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 19:21:13,413 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 19:21:13,421 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 19:21:13,460 INFO ]: Using default assertion order modulation [2018-06-22 19:21:13,460 INFO ]: Interprodecural is true [2018-06-22 19:21:13,460 INFO ]: Hoare is false [2018-06-22 19:21:13,460 INFO ]: Compute interpolants for FPandBP [2018-06-22 19:21:13,460 INFO ]: Backedges is TWOTRACK [2018-06-22 19:21:13,460 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 19:21:13,460 INFO ]: Difference is false [2018-06-22 19:21:13,460 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 19:21:13,461 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 19:21:13,475 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 19:21:13,495 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 19:21:13,496 INFO ]: Found error trace [2018-06-22 19:21:13,497 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:21:13,497 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:21:13,503 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 19:21:13,505 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:21:13,506 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:21:13,549 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:13,549 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:21:13,549 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:13,636 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:21:13,871 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:21:13,874 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 19:21:13,874 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 19:21:13,876 INFO ]: Interpolant automaton has 4 states [2018-06-22 19:21:13,886 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 19:21:13,887 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 19:21:13,888 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 19:21:14,016 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:21:14,016 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 19:21:14,016 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 19:21:14,018 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 19:21:14,018 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:21:14,028 INFO ]: With dead ends: 13 [2018-06-22 19:21:14,028 INFO ]: Without dead ends: 13 [2018-06-22 19:21:14,029 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 19:21:14,042 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 19:21:14,075 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 19:21:14,076 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 19:21:14,076 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 19:21:14,077 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 19:21:14,077 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:21:14,077 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 19:21:14,077 INFO ]: Interpolant automaton has 4 states. [2018-06-22 19:21:14,077 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 19:21:14,078 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 19:21:14,078 INFO ]: Found error trace [2018-06-22 19:21:14,078 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:21:14,079 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:21:14,079 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 19:21:14,079 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:21:14,079 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:21:14,079 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:14,079 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:21:14,079 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:14,180 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:21:14,658 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:21:14,658 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:21:14,658 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:21:14,664 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:21:14,782 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:21:14,792 INFO ]: Computing forward predicates... [2018-06-22 19:21:15,163 WARN ]: Spent 223.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 7 [2018-06-22 19:21:15,439 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:21:15,461 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:21:15,461 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 19:21:15,462 INFO ]: Interpolant automaton has 9 states [2018-06-22 19:21:15,462 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 19:21:15,462 INFO ]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-06-22 19:21:15,462 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 19:21:16,017 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:21:16,017 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 19:21:16,018 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 19:21:16,018 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 19:21:16,019 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:21:16,019 INFO ]: With dead ends: 15 [2018-06-22 19:21:16,019 INFO ]: Without dead ends: 15 [2018-06-22 19:21:16,020 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2018-06-22 19:21:16,020 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 19:21:16,022 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 19:21:16,022 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 19:21:16,025 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 19:21:16,025 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 19:21:16,025 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:21:16,025 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 19:21:16,025 INFO ]: Interpolant automaton has 9 states. [2018-06-22 19:21:16,025 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 19:21:16,026 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 19:21:16,026 INFO ]: Found error trace [2018-06-22 19:21:16,026 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:21:16,026 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:21:16,026 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 19:21:16,026 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:21:16,026 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:21:16,027 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:16,027 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:21:16,027 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:16,151 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:21:16,602 WARN ]: Spent 132.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 53 [2018-06-22 19:21:16,734 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:21:16,734 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:21:16,734 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:21:16,746 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 19:21:16,918 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 19:21:16,918 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:21:16,924 INFO ]: Computing forward predicates... [2018-06-22 19:21:17,335 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:21:17,354 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:21:17,354 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-22 19:21:17,355 INFO ]: Interpolant automaton has 13 states [2018-06-22 19:21:17,355 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 19:21:17,355 INFO ]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2018-06-22 19:21:17,355 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 13 states. [2018-06-22 19:21:17,533 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 72 [2018-06-22 19:21:17,751 WARN ]: Spent 159.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 78 [2018-06-22 19:21:17,920 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:21:17,920 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 19:21:17,922 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 19:21:17,922 INFO ]: Start accepts. Automaton has 13 states. Word has length 17 [2018-06-22 19:21:17,922 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:21:17,923 INFO ]: With dead ends: 17 [2018-06-22 19:21:17,923 INFO ]: Without dead ends: 17 [2018-06-22 19:21:17,923 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=60, Invalid=212, Unknown=0, NotChecked=0, Total=272 [2018-06-22 19:21:17,923 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 19:21:17,926 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 19:21:17,926 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 19:21:17,927 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 19:21:17,927 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 19:21:17,927 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:21:17,927 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 19:21:17,927 INFO ]: Interpolant automaton has 13 states. [2018-06-22 19:21:17,927 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 19:21:17,928 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 19:21:17,928 INFO ]: Found error trace [2018-06-22 19:21:17,928 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:21:17,928 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:21:17,928 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 19:21:17,928 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:21:17,928 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:21:17,929 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:17,929 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:21:17,929 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:18,044 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:21:18,367 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 32 [2018-06-22 19:21:18,651 WARN ]: Spent 174.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 28 [2018-06-22 19:21:18,755 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:21:18,755 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:21:18,755 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) [2018-06-22 19:21:18,772 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 19:21:18,906 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 19:21:18,906 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:21:18,917 INFO ]: Computing forward predicates... [2018-06-22 19:21:19,416 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:21:19,437 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:21:19,438 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2018-06-22 19:21:19,438 INFO ]: Interpolant automaton has 17 states [2018-06-22 19:21:19,438 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 19:21:19,438 INFO ]: CoverageRelationStatistics Valid=36, Invalid=236, Unknown=0, NotChecked=0, Total=272 [2018-06-22 19:21:19,438 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 17 states. [2018-06-22 19:21:19,741 WARN ]: Spent 246.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 77 [2018-06-22 19:21:20,056 WARN ]: Spent 231.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 96 [2018-06-22 19:21:20,277 WARN ]: Spent 193.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 80 [2018-06-22 19:21:20,446 WARN ]: Spent 137.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 70 [2018-06-22 19:21:20,508 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:21:20,508 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 19:21:20,509 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 19:21:20,509 INFO ]: Start accepts. Automaton has 17 states. Word has length 21 [2018-06-22 19:21:20,509 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:21:20,509 INFO ]: With dead ends: 19 [2018-06-22 19:21:20,509 INFO ]: Without dead ends: 19 [2018-06-22 19:21:20,510 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=90, Invalid=372, Unknown=0, NotChecked=0, Total=462 [2018-06-22 19:21:20,510 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 19:21:20,512 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 19:21:20,512 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 19:21:20,512 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 19:21:20,512 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 19:21:20,512 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:21:20,512 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 19:21:20,512 INFO ]: Interpolant automaton has 17 states. [2018-06-22 19:21:20,512 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 19:21:20,513 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 19:21:20,513 INFO ]: Found error trace [2018-06-22 19:21:20,513 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:21:20,513 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:21:20,513 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-22 19:21:20,513 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:21:20,513 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:21:20,514 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:20,514 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:21:20,514 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:20,677 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:21:21,188 WARN ]: Spent 120.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 19:21:22,388 WARN ]: Spent 1.12 s on a formula simplification. DAG size of input: 45 DAG size of output: 21 [2018-06-22 19:21:23,195 WARN ]: Spent 699.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 46 [2018-06-22 19:21:23,553 WARN ]: Spent 340.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 47 [2018-06-22 19:21:23,800 WARN ]: Spent 166.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 29 [2018-06-22 19:21:24,227 WARN ]: Spent 387.00 ms on a formula simplification. DAG size of input: 121 DAG size of output: 24 [2018-06-22 19:21:24,367 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 16 [2018-06-22 19:21:24,381 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:21:24,381 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:21:24,381 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 19:21:24,392 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 19:21:24,534 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 19:21:24,534 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:21:24,541 INFO ]: Computing forward predicates... [2018-06-22 19:21:24,973 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:21:24,994 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:21:24,994 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 20 [2018-06-22 19:21:24,994 INFO ]: Interpolant automaton has 20 states [2018-06-22 19:21:24,994 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 19:21:24,994 INFO ]: CoverageRelationStatistics Valid=44, Invalid=336, Unknown=0, NotChecked=0, Total=380 [2018-06-22 19:21:24,994 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 20 states. [2018-06-22 19:21:25,322 WARN ]: Spent 275.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 97 [2018-06-22 19:21:25,825 WARN ]: Spent 420.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 115 [2018-06-22 19:21:26,335 WARN ]: Spent 476.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 111 [2018-06-22 19:21:26,710 WARN ]: Spent 334.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 106 [2018-06-22 19:21:26,985 WARN ]: Spent 238.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 90 [2018-06-22 19:21:27,059 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:21:27,059 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 19:21:27,059 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 19:21:27,059 INFO ]: Start accepts. Automaton has 20 states. Word has length 25 [2018-06-22 19:21:27,060 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:21:27,060 INFO ]: With dead ends: 21 [2018-06-22 19:21:27,060 INFO ]: Without dead ends: 21 [2018-06-22 19:21:27,061 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=118, Invalid=532, Unknown=0, NotChecked=0, Total=650 [2018-06-22 19:21:27,061 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 19:21:27,063 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 19:21:27,063 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 19:21:27,064 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 19:21:27,064 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 19:21:27,064 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:21:27,064 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 19:21:27,064 INFO ]: Interpolant automaton has 20 states. [2018-06-22 19:21:27,064 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 19:21:27,065 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 19:21:27,065 INFO ]: Found error trace [2018-06-22 19:21:27,065 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:21:27,065 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:21:27,065 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-22 19:21:27,065 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:21:27,065 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:21:27,066 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:27,066 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:21:27,066 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:27,256 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:21:28,004 WARN ]: Spent 111.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 19:21:28,662 WARN ]: Spent 560.00 ms on a formula simplification. DAG size of input: 148 DAG size of output: 38 [2018-06-22 19:21:30,211 WARN ]: Spent 1.49 s on a formula simplification. DAG size of input: 248 DAG size of output: 51 [2018-06-22 19:21:30,983 WARN ]: Spent 663.00 ms on a formula simplification. DAG size of input: 216 DAG size of output: 44 [2018-06-22 19:21:31,424 WARN ]: Spent 278.00 ms on a formula simplification. DAG size of input: 138 DAG size of output: 44 [2018-06-22 19:21:31,782 WARN ]: Spent 292.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 41 [2018-06-22 19:21:32,597 WARN ]: Spent 727.00 ms on a formula simplification. DAG size of input: 297 DAG size of output: 22 [2018-06-22 19:21:34,081 WARN ]: Spent 1.32 s on a formula simplification. DAG size of input: 271 DAG size of output: 30 [2018-06-22 19:21:34,744 WARN ]: Spent 520.00 ms on a formula simplification. DAG size of input: 154 DAG size of output: 16 [2018-06-22 19:21:34,768 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:21:34,768 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:21:34,768 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:21:34,777 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 19:21:35,040 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 19:21:35,040 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:21:35,049 INFO ]: Computing forward predicates... [2018-06-22 19:21:35,452 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:21:35,472 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:21:35,473 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 24 [2018-06-22 19:21:35,473 INFO ]: Interpolant automaton has 24 states [2018-06-22 19:21:35,473 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 19:21:35,473 INFO ]: CoverageRelationStatistics Valid=53, Invalid=499, Unknown=0, NotChecked=0, Total=552 [2018-06-22 19:21:35,473 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 24 states. [2018-06-22 19:21:35,752 WARN ]: Spent 224.00 ms on a formula simplification. DAG size of input: 133 DAG size of output: 113 [2018-06-22 19:21:36,360 WARN ]: Spent 483.00 ms on a formula simplification. DAG size of input: 181 DAG size of output: 149 [2018-06-22 19:21:36,709 WARN ]: Spent 298.00 ms on a formula simplification. DAG size of input: 171 DAG size of output: 138 [2018-06-22 19:21:37,021 WARN ]: Spent 261.00 ms on a formula simplification. DAG size of input: 157 DAG size of output: 129 [2018-06-22 19:21:37,332 WARN ]: Spent 239.00 ms on a formula simplification. DAG size of input: 142 DAG size of output: 114 [2018-06-22 19:21:37,607 WARN ]: Spent 219.00 ms on a formula simplification. DAG size of input: 131 DAG size of output: 103 [2018-06-22 19:21:37,713 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:21:37,713 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 19:21:37,715 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 19:21:37,715 INFO ]: Start accepts. Automaton has 24 states. Word has length 29 [2018-06-22 19:21:37,715 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:21:37,715 INFO ]: With dead ends: 23 [2018-06-22 19:21:37,715 INFO ]: Without dead ends: 23 [2018-06-22 19:21:37,716 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 19 SyntacticMatches, 1 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 9.1s TimeCoverageRelationStatistics Valid=175, Invalid=755, Unknown=0, NotChecked=0, Total=930 [2018-06-22 19:21:37,716 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 19:21:37,722 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 19:21:37,722 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 19:21:37,723 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 19:21:37,723 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 19:21:37,723 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:21:37,724 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 19:21:37,724 INFO ]: Interpolant automaton has 24 states. [2018-06-22 19:21:37,724 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 19:21:37,724 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 19:21:37,724 INFO ]: Found error trace [2018-06-22 19:21:37,725 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:21:37,725 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:21:37,727 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-22 19:21:37,727 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:21:37,727 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:21:37,728 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:37,728 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:21:37,728 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:21:38,316 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:21:40,337 WARN ]: Spent 121.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 19:21:43,424 WARN ]: Spent 2.87 s on a formula simplification. DAG size of input: 712 DAG size of output: 33 [2018-06-22 19:21:48,214 WARN ]: Spent 4.59 s on a formula simplification. DAG size of input: 634 DAG size of output: 47 [2018-06-22 19:21:49,112 WARN ]: Spent 774.00 ms on a formula simplification. DAG size of input: 321 DAG size of output: 41 [2018-06-22 19:21:52,829 WARN ]: Spent 3.48 s on a formula simplification. DAG size of input: 458 DAG size of output: 29 [2018-06-22 19:21:54,562 WARN ]: Spent 1.61 s on a formula simplification. DAG size of input: 365 DAG size of output: 38 [2018-06-22 19:21:55,788 WARN ]: Spent 1.06 s on a formula simplification. DAG size of input: 358 DAG size of output: 30 [2018-06-22 19:21:59,089 WARN ]: Spent 3.03 s on a formula simplification. DAG size of input: 825 DAG size of output: 21 [2018-06-22 19:22:04,263 WARN ]: Spent 4.79 s on a formula simplification. DAG size of input: 1094 DAG size of output: 31 [2018-06-22 19:22:13,511 WARN ]: Spent 8.77 s on a formula simplification. DAG size of input: 1297 DAG size of output: 33 Received shutdown request... [2018-06-22 19:22:19,732 WARN ]: Removed 2 from assertion stack [2018-06-22 19:22:19,732 WARN ]: Verification canceled [2018-06-22 19:22:19,735 WARN ]: Timeout [2018-06-22 19:22:19,735 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 07:22:19 BoogieIcfgContainer [2018-06-22 19:22:19,735 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 19:22:19,736 INFO ]: Toolchain (without parser) took 66926.66 ms. Allocated memory was 309.9 MB in the beginning and 1.4 GB in the end (delta: 1.1 GB). Free memory was 251.3 MB in the beginning and 920.7 MB in the end (delta: -669.5 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 19:22:19,737 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 309.9 MB. Free memory is still 275.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 19:22:19,737 INFO ]: ChcToBoogie took 68.38 ms. Allocated memory is still 309.9 MB. Free memory was 251.3 MB in the beginning and 249.3 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:22:19,737 INFO ]: Boogie Preprocessor took 62.71 ms. Allocated memory is still 309.9 MB. Free memory was 249.3 MB in the beginning and 247.3 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:22:19,737 INFO ]: RCFGBuilder took 438.78 ms. Allocated memory is still 309.9 MB. Free memory was 247.3 MB in the beginning and 223.3 MB in the end (delta: 24.0 MB). Peak memory consumption was 24.0 MB. Max. memory is 3.6 GB. [2018-06-22 19:22:19,738 INFO ]: TraceAbstraction took 66342.06 ms. Allocated memory was 309.9 MB in the beginning and 1.4 GB in the end (delta: 1.1 GB). Free memory was 223.3 MB in the beginning and 920.7 MB in the end (delta: -697.5 MB). Peak memory consumption was 1.1 GB. Max. memory is 3.6 GB. [2018-06-22 19:22:19,740 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 309.9 MB. Free memory is still 275.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 68.38 ms. Allocated memory is still 309.9 MB. Free memory was 251.3 MB in the beginning and 249.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 62.71 ms. Allocated memory is still 309.9 MB. Free memory was 249.3 MB in the beginning and 247.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 438.78 ms. Allocated memory is still 309.9 MB. Free memory was 247.3 MB in the beginning and 223.3 MB in the end (delta: 24.0 MB). Peak memory consumption was 24.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 66342.06 ms. Allocated memory was 309.9 MB in the beginning and 1.4 GB in the end (delta: 1.1 GB). Free memory was 223.3 MB in the beginning and 920.7 MB in the end (delta: -697.5 MB). Peak memory consumption was 1.1 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 759. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 66.2s OverallTime, 7 OverallIterations, 7 TraceHistogramMax, 6.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 71 SDtfs, 143 SDslu, 460 SDs, 0 SdLazy, 383 SolverSat, 178 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 178 GetRequests, 77 SyntacticMatches, 2 SemanticMatches, 99 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 118 ImplicationChecksByTransitivity, 18.5s 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.3s SatisfiabilityAnalysisTime, 15.6s InterpolantComputationTime, 219 NumberOfCodeBlocks, 219 NumberOfCodeBlocksAsserted, 21 NumberOfCheckSat, 208 ConstructedInterpolants, 0 QuantifiedInterpolants, 55904 SizeOfPredicates, 143 NumberOfNonLiveVariables, 4435 ConjunctsInSsa, 188 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_4_e2_968_e1_956.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_19-22-19-748.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/metros_4_e2_968_e1_956.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_19-22-19-748.csv Completed graceful shutdown