java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/up-nd.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:46:07,505 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:46:07,508 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:46:08,182 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:46:08,230 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:46:08,231 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:46:08,232 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:46:08,235 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:46:08,236 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:46:08,237 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:46:08,238 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:46:08,239 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:46:08,240 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:46:08,241 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:46:08,242 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:46:08,244 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:46:08,246 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:46:08,248 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:46:08,249 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:46:08,250 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:46:08,251 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:46:08,253 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:46:08,254 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:46:08,254 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:46:08,255 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:46:08,256 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:46:08,256 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:46:08,257 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:46:08,258 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:46:08,258 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:46:08,259 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:46:08,260 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:46:08,260 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:46:08,261 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:46:08,262 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:46:08,262 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 15:46:08,275 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:46:08,276 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:46:08,276 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:46:08,276 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:46:08,277 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:46:08,277 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:46:08,278 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:46:08,278 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:46:08,278 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:46:08,278 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:46:08,279 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:46:08,279 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:46:08,279 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:46:08,279 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:46:08,279 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:46:08,280 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:46:08,280 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:46:08,280 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:46:08,280 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:46:08,281 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:46:08,282 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:46:08,322 INFO ]: Repository-Root is: /tmp [2018-06-22 15:46:08,337 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:46:08,340 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:46:08,345 INFO ]: Initializing SmtParser... [2018-06-22 15:46:08,345 INFO ]: SmtParser initialized [2018-06-22 15:46:08,346 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/up-nd.c.smt2 [2018-06-22 15:46:08,347 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 15:46:08,436 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/up-nd.c.smt2 unknown [2018-06-22 15:46:08,691 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/up-nd.c.smt2 [2018-06-22 15:46:08,705 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:46:08,710 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:46:08,711 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:46:08,711 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:46:08,711 INFO ]: ChcToBoogie initialized [2018-06-22 15:46:08,718 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:46:08" (1/1) ... [2018-06-22 15:46:08,765 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:46:08 Unit [2018-06-22 15:46:08,768 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:46:08,769 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:46:08,769 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:46:08,769 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:46:08,789 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:46:08" (1/1) ... [2018-06-22 15:46:08,789 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:46:08" (1/1) ... [2018-06-22 15:46:08,796 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:46:08" (1/1) ... [2018-06-22 15:46:08,796 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:46:08" (1/1) ... [2018-06-22 15:46:08,800 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:46:08" (1/1) ... [2018-06-22 15:46:08,801 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:46:08" (1/1) ... [2018-06-22 15:46:08,803 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:46:08" (1/1) ... [2018-06-22 15:46:08,805 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:46:08,805 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:46:08,805 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:46:08,805 INFO ]: RCFGBuilder initialized [2018-06-22 15:46:08,806 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:46:08" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 15:46:08,824 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:46:08,824 INFO ]: Found specification of procedure False [2018-06-22 15:46:08,824 INFO ]: Found implementation of procedure False [2018-06-22 15:46:08,824 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:46:08,824 INFO ]: Found specification of procedure state [2018-06-22 15:46:08,824 INFO ]: Found implementation of procedure state [2018-06-22 15:46:08,824 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:46:08,824 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:46:08,824 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:46:09,069 INFO ]: Using library mode [2018-06-22 15:46:09,069 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:46:09 BoogieIcfgContainer [2018-06-22 15:46:09,069 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:46:09,071 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:46:09,071 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:46:09,078 INFO ]: TraceAbstraction initialized [2018-06-22 15:46:09,078 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:46:08" (1/3) ... [2018-06-22 15:46:09,078 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@312d8c26 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:46:09, skipping insertion in model container [2018-06-22 15:46:09,078 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:46:08" (2/3) ... [2018-06-22 15:46:09,079 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@312d8c26 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:46:09, skipping insertion in model container [2018-06-22 15:46:09,079 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:46:09" (3/3) ... [2018-06-22 15:46:09,080 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:46:09,091 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:46:09,101 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:46:09,137 INFO ]: Using default assertion order modulation [2018-06-22 15:46:09,138 INFO ]: Interprodecural is true [2018-06-22 15:46:09,138 INFO ]: Hoare is false [2018-06-22 15:46:09,138 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:46:09,138 INFO ]: Backedges is TWOTRACK [2018-06-22 15:46:09,138 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:46:09,138 INFO ]: Difference is false [2018-06-22 15:46:09,138 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:46:09,138 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:46:09,155 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:46:09,165 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:46:09,165 INFO ]: Found error trace [2018-06-22 15:46:09,166 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:46:09,166 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:46:09,169 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 15:46:09,171 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:46:09,171 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:46:09,204 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:09,204 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:46:09,204 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:09,234 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:09,338 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:46:09,340 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:46:09,340 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:46:09,342 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:46:09,376 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:46:09,376 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:46:09,379 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:46:09,485 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:46:09,485 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:46:09,486 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:46:09,487 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:46:09,487 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:46:09,496 INFO ]: With dead ends: 13 [2018-06-22 15:46:09,501 INFO ]: Without dead ends: 13 [2018-06-22 15:46:09,502 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 15:46:09,515 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:46:09,544 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:46:09,545 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:46:09,546 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:46:09,548 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:46:09,549 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:46:09,549 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:46:09,549 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:46:09,549 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:46:09,550 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:46:09,550 INFO ]: Found error trace [2018-06-22 15:46:09,550 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:46:09,550 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:46:09,550 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 15:46:09,550 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:46:09,550 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:46:09,551 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:09,551 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:46:09,551 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:09,612 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:09,791 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:46:09,791 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:46:09,791 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:46:09,799 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:46:09,835 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:09,845 INFO ]: Computing forward predicates... [2018-06-22 15:46:10,298 WARN ]: Spent 159.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 15:46:10,410 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:46:10,448 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:46:10,448 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 15:46:10,449 INFO ]: Interpolant automaton has 9 states [2018-06-22 15:46:10,449 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 15:46:10,449 INFO ]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-06-22 15:46:10,449 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 15:46:10,807 WARN ]: Spent 138.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 15:46:11,137 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:46:11,137 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:46:11,138 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:46:11,139 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 15:46:11,139 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:46:11,139 INFO ]: With dead ends: 15 [2018-06-22 15:46:11,139 INFO ]: Without dead ends: 15 [2018-06-22 15:46:11,140 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:46:11,140 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:46:11,144 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:46:11,144 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:46:11,144 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:46:11,145 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:46:11,145 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:46:11,145 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:46:11,145 INFO ]: Interpolant automaton has 9 states. [2018-06-22 15:46:11,145 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:46:11,145 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:46:11,145 INFO ]: Found error trace [2018-06-22 15:46:11,145 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:46:11,146 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:46:11,148 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 15:46:11,148 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:46:11,148 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:46:11,149 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:11,149 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:46:11,149 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:11,240 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:11,627 WARN ]: Spent 173.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 15:46:11,707 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:46:11,707 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:46:11,707 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:46:11,716 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:46:11,776 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:46:11,776 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:11,780 INFO ]: Computing forward predicates... [2018-06-22 15:46:12,278 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:46:12,300 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:46:12,300 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:46:12,300 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:46:12,300 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:46:12,301 INFO ]: CoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:46:12,301 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:46:12,525 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:46:12,525 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:46:12,525 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:46:12,525 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:46:12,525 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:46:12,526 INFO ]: With dead ends: 17 [2018-06-22 15:46:12,526 INFO ]: Without dead ends: 17 [2018-06-22 15:46:12,526 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2018-06-22 15:46:12,526 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:46:12,529 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:46:12,529 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:46:12,530 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:46:12,530 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:46:12,530 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:46:12,530 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:46:12,530 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:46:12,530 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:46:12,531 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:46:12,531 INFO ]: Found error trace [2018-06-22 15:46:12,531 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:46:12,531 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:46:12,531 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 15:46:12,531 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:46:12,531 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:46:12,532 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:12,532 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:46:12,532 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:12,564 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:12,966 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:46:12,966 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:46:12,966 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:46:12,974 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:46:13,022 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:46:13,023 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:13,026 INFO ]: Computing forward predicates... [2018-06-22 15:46:13,447 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:46:13,477 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:46:13,525 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 13 [2018-06-22 15:46:13,526 INFO ]: Interpolant automaton has 13 states [2018-06-22 15:46:13,526 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 15:46:13,526 INFO ]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2018-06-22 15:46:13,526 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 13 states. [2018-06-22 15:46:13,871 WARN ]: Spent 212.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 32 [2018-06-22 15:46:14,145 WARN ]: Spent 124.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 22 [2018-06-22 15:46:14,181 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:46:14,181 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:46:14,182 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:46:14,182 INFO ]: Start accepts. Automaton has 13 states. Word has length 21 [2018-06-22 15:46:14,182 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:46:14,182 INFO ]: With dead ends: 19 [2018-06-22 15:46:14,182 INFO ]: Without dead ends: 19 [2018-06-22 15:46:14,183 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 18 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=69, Invalid=237, Unknown=0, NotChecked=0, Total=306 [2018-06-22 15:46:14,183 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:46:14,186 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:46:14,186 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:46:14,186 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:46:14,186 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:46:14,187 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:46:14,187 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:46:14,187 INFO ]: Interpolant automaton has 13 states. [2018-06-22 15:46:14,187 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:46:14,187 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:46:14,187 INFO ]: Found error trace [2018-06-22 15:46:14,189 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:46:14,189 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:46:14,190 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-22 15:46:14,190 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:46:14,190 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:46:14,190 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:14,190 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:46:14,190 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:14,236 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:14,661 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:46:14,661 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:46:14,661 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:46:14,669 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:46:14,720 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:46:14,720 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:14,724 INFO ]: Computing forward predicates... [2018-06-22 15:46:14,976 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 21 [2018-06-22 15:46:15,323 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:46:15,345 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:46:15,345 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 16 [2018-06-22 15:46:15,345 INFO ]: Interpolant automaton has 16 states [2018-06-22 15:46:15,345 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 15:46:15,346 INFO ]: CoverageRelationStatistics Valid=37, Invalid=203, Unknown=0, NotChecked=0, Total=240 [2018-06-22 15:46:15,346 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 16 states. [2018-06-22 15:46:15,797 WARN ]: Spent 420.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 46 [2018-06-22 15:46:16,075 WARN ]: Spent 167.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 27 [2018-06-22 15:46:16,314 WARN ]: Spent 217.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 30 [2018-06-22 15:46:16,491 WARN ]: Spent 131.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 27 [2018-06-22 15:46:16,527 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:46:16,527 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:46:16,530 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:46:16,530 INFO ]: Start accepts. Automaton has 16 states. Word has length 25 [2018-06-22 15:46:16,530 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:46:16,531 INFO ]: With dead ends: 21 [2018-06-22 15:46:16,531 INFO ]: Without dead ends: 21 [2018-06-22 15:46:16,531 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 20 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=93, Invalid=369, Unknown=0, NotChecked=0, Total=462 [2018-06-22 15:46:16,531 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:46:16,534 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:46:16,534 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:46:16,535 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:46:16,535 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:46:16,535 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:46:16,535 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:46:16,535 INFO ]: Interpolant automaton has 16 states. [2018-06-22 15:46:16,535 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:46:16,536 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:46:16,536 INFO ]: Found error trace [2018-06-22 15:46:16,536 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:46:16,536 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:46:16,537 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-22 15:46:16,537 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:46:16,537 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:46:16,537 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:16,537 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:46:16,537 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:16,580 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:16,970 WARN ]: Spent 111.00 ms on a formula simplification that was a NOOP. DAG size: 20 [2018-06-22 15:46:17,091 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:46:17,091 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:46:17,091 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:46:17,097 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:46:17,144 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:46:17,144 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:17,149 INFO ]: Computing forward predicates... [2018-06-22 15:46:17,617 WARN ]: Spent 307.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 34 [2018-06-22 15:46:17,944 WARN ]: Spent 159.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 30 [2018-06-22 15:46:18,538 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:46:18,560 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:46:18,564 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 23 [2018-06-22 15:46:18,565 INFO ]: Interpolant automaton has 23 states [2018-06-22 15:46:18,565 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 15:46:18,565 INFO ]: CoverageRelationStatistics Valid=69, Invalid=437, Unknown=0, NotChecked=0, Total=506 [2018-06-22 15:46:18,565 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 23 states. [2018-06-22 15:46:19,117 WARN ]: Spent 510.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 66 [2018-06-22 15:46:19,446 WARN ]: Spent 181.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 42 [2018-06-22 15:46:19,950 WARN ]: Spent 478.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 52 [2018-06-22 15:46:20,180 WARN ]: Spent 202.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 39 [2018-06-22 15:46:20,556 WARN ]: Spent 350.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 59 [2018-06-22 15:46:20,703 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:46:20,703 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:46:20,704 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:46:20,704 INFO ]: Start accepts. Automaton has 23 states. Word has length 29 [2018-06-22 15:46:20,704 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:46:20,705 INFO ]: With dead ends: 23 [2018-06-22 15:46:20,705 INFO ]: Without dead ends: 23 [2018-06-22 15:46:20,705 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 81 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=166, Invalid=704, Unknown=0, NotChecked=0, Total=870 [2018-06-22 15:46:20,705 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:46:20,708 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:46:20,708 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:46:20,709 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:46:20,709 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:46:20,709 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:46:20,709 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:46:20,709 INFO ]: Interpolant automaton has 23 states. [2018-06-22 15:46:20,709 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:46:20,710 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:46:20,710 INFO ]: Found error trace [2018-06-22 15:46:20,710 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:46:20,710 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:46:20,710 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-22 15:46:20,710 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:46:20,710 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:46:20,711 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:20,711 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:46:20,711 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:20,805 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:21,630 WARN ]: Spent 542.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-22 15:46:22,282 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:46:22,283 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:46:22,283 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:46:22,296 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:46:22,384 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:46:22,384 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:22,389 INFO ]: Computing forward predicates... [2018-06-22 15:46:25,123 WARN ]: Spent 2.29 s on a formula simplification. DAG size of input: 53 DAG size of output: 16 [2018-06-22 15:46:26,409 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:46:26,442 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:46:26,442 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 25 [2018-06-22 15:46:26,443 INFO ]: Interpolant automaton has 25 states [2018-06-22 15:46:26,443 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-22 15:46:26,443 INFO ]: CoverageRelationStatistics Valid=76, Invalid=524, Unknown=0, NotChecked=0, Total=600 [2018-06-22 15:46:26,443 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 25 states. [2018-06-22 15:46:27,152 WARN ]: Spent 632.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 75 [2018-06-22 15:46:27,387 WARN ]: Spent 179.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 30 [2018-06-22 15:46:27,631 WARN ]: Spent 206.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 50 [2018-06-22 15:46:27,949 WARN ]: Spent 280.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 48 [2018-06-22 15:46:28,203 WARN ]: Spent 226.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 31 [2018-06-22 15:46:28,476 WARN ]: Spent 170.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 43 [2018-06-22 15:46:28,890 WARN ]: Spent 370.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 65 [2018-06-22 15:46:28,926 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:46:28,926 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:46:28,926 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:46:28,926 INFO ]: Start accepts. Automaton has 25 states. Word has length 33 [2018-06-22 15:46:28,926 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:46:28,927 INFO ]: With dead ends: 25 [2018-06-22 15:46:28,927 INFO ]: Without dead ends: 25 [2018-06-22 15:46:28,928 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 23 SyntacticMatches, 2 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 98 ImplicationChecksByTransitivity, 6.9s TimeCoverageRelationStatistics Valid=197, Invalid=859, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 15:46:28,928 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:46:28,930 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:46:28,931 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:46:28,931 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:46:28,931 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:46:28,931 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:46:28,931 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:46:28,931 INFO ]: Interpolant automaton has 25 states. [2018-06-22 15:46:28,931 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:46:28,932 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:46:28,932 INFO ]: Found error trace [2018-06-22 15:46:28,932 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:46:28,932 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:46:28,932 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 7 times [2018-06-22 15:46:28,932 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:46:28,932 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:46:28,933 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:28,933 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:46:28,933 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:46:29,014 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:29,815 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:46:29,815 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:46:29,815 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:46:29,822 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:46:29,891 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:46:29,907 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 15:47:18,746 WARN ]: Removed 2 from assertion stack [2018-06-22 15:47:18,746 INFO ]: Timeout while computing interpolants [2018-06-22 15:47:18,946 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:47:18,946 WARN ]: Verification canceled [2018-06-22 15:47:18,950 WARN ]: Timeout [2018-06-22 15:47:18,950 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:47:18 BoogieIcfgContainer [2018-06-22 15:47:18,950 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:47:18,950 INFO ]: Toolchain (without parser) took 70245.25 ms. Allocated memory was 303.0 MB in the beginning and 909.6 MB in the end (delta: 606.6 MB). Free memory was 255.4 MB in the beginning and 624.4 MB in the end (delta: -369.0 MB). Peak memory consumption was 692.4 MB. Max. memory is 3.6 GB. [2018-06-22 15:47:18,951 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 303.0 MB. Free memory is still 267.5 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:47:18,951 INFO ]: ChcToBoogie took 57.30 ms. Allocated memory is still 303.0 MB. Free memory was 255.4 MB in the beginning and 253.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:47:18,952 INFO ]: Boogie Preprocessor took 36.12 ms. Allocated memory is still 303.0 MB. Free memory was 253.4 MB in the beginning and 251.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:47:18,952 INFO ]: RCFGBuilder took 264.12 ms. Allocated memory is still 303.0 MB. Free memory was 251.5 MB in the beginning and 241.5 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:47:18,953 INFO ]: TraceAbstraction took 69878.83 ms. Allocated memory was 303.0 MB in the beginning and 909.6 MB in the end (delta: 606.6 MB). Free memory was 241.5 MB in the beginning and 624.4 MB in the end (delta: -382.9 MB). Peak memory consumption was 678.4 MB. Max. memory is 3.6 GB. [2018-06-22 15:47:18,956 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 303.0 MB. Free memory is still 267.5 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 57.30 ms. Allocated memory is still 303.0 MB. Free memory was 255.4 MB in the beginning and 253.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 36.12 ms. Allocated memory is still 303.0 MB. Free memory was 253.4 MB in the beginning and 251.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 264.12 ms. Allocated memory is still 303.0 MB. Free memory was 251.5 MB in the beginning and 241.5 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 69878.83 ms. Allocated memory was 303.0 MB in the beginning and 909.6 MB in the end (delta: 606.6 MB). Free memory was 241.5 MB in the beginning and 624.4 MB in the end (delta: -382.9 MB). Peak memory consumption was 678.4 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 38 with TraceHistMax 8, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 3008. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 69.8s OverallTime, 8 OverallIterations, 8 TraceHistogramMax, 7.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 89 SDtfs, 184 SDslu, 486 SDs, 0 SdLazy, 408 SolverSat, 241 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 234 GetRequests, 110 SyntacticMatches, 5 SemanticMatches, 119 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 260 ImplicationChecksByTransitivity, 14.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=25occurred in iteration=7, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 11.0s InterpolantComputationTime, 285 NumberOfCodeBlocks, 285 NumberOfCodeBlocksAsserted, 28 NumberOfCheckSat, 272 ConstructedInterpolants, 0 QuantifiedInterpolants, 87512 SizeOfPredicates, 328 NumberOfNonLiveVariables, 1104 ConjunctsInSsa, 199 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 112/406 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/up-nd.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-47-18-968.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/up-nd.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-47-18-968.csv Completed graceful shutdown