java -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chccomp2018/chcToBoogie_automizer.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/up-nd.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-55b8104 [2018-06-18 13:49:07,334 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-18 13:49:07,337 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-18 13:49:07,352 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-18 13:49:07,353 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-18 13:49:07,353 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-18 13:49:07,355 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-18 13:49:07,356 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-18 13:49:07,358 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-18 13:49:07,359 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-18 13:49:07,359 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-18 13:49:07,360 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-18 13:49:07,361 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-18 13:49:07,364 INFO L177 SettingsManager]: ChcToBoogie provides no preferences, ignoring... [2018-06-18 13:49:07,365 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-18 13:49:07,366 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-18 13:49:07,367 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-18 13:49:07,369 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-18 13:49:07,371 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-18 13:49:07,373 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-18 13:49:07,375 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-18 13:49:07,377 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-18 13:49:07,377 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-18 13:49:07,377 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-18 13:49:07,378 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-18 13:49:07,379 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-18 13:49:07,380 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-18 13:49:07,381 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-18 13:49:07,382 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-18 13:49:07,382 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-18 13:49:07,383 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-18 13:49:07,383 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-18 13:49:07,384 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-18 13:49:07,384 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-18 13:49:07,385 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-18 13:49:07,385 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chccomp2018/chcToBoogie_automizer.epf [2018-06-18 13:49:07,398 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-18 13:49:07,399 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-18 13:49:07,399 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-18 13:49:07,399 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-18 13:49:07,401 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-18 13:49:07,401 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-18 13:49:07,401 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-18 13:49:07,402 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-18 13:49:07,402 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-18 13:49:07,402 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-18 13:49:07,402 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-18 13:49:07,402 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-18 13:49:07,403 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-18 13:49:07,403 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-18 13:49:07,403 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-18 13:49:07,403 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-18 13:49:07,404 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-18 13:49:07,405 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-18 13:49:07,405 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-18 13:49:07,456 INFO ]: Repository-Root is: /tmp [2018-06-18 13:49:07,476 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-18 13:49:07,480 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-18 13:49:07,481 INFO ]: Initializing SmtParser... [2018-06-18 13:49:07,481 INFO ]: SmtParser initialized [2018-06-18 13:49:07,482 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/up-nd.c.smt2 [2018-06-18 13:49:07,483 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-18 13:49:07,573 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/up-nd.c.smt2 unknown [2018-06-18 13:49:07,907 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/up-nd.c.smt2 [2018-06-18 13:49:07,913 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-18 13:49:07,919 INFO ]: Walking toolchain with 4 elements. [2018-06-18 13:49:07,919 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-18 13:49:07,919 INFO ]: Initializing ChcToBoogie... [2018-06-18 13:49:07,919 INFO ]: ChcToBoogie initialized [2018-06-18 13:49:07,930 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 01:49:07" (1/1) ... [2018-06-18 13:49:08,017 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:49:08 Unit [2018-06-18 13:49:08,018 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-18 13:49:08,019 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-18 13:49:08,019 INFO ]: Initializing Boogie Preprocessor... [2018-06-18 13:49:08,019 INFO ]: Boogie Preprocessor initialized [2018-06-18 13:49:08,040 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:49:08" (1/1) ... [2018-06-18 13:49:08,041 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:49:08" (1/1) ... [2018-06-18 13:49:08,058 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:49:08" (1/1) ... [2018-06-18 13:49:08,058 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:49:08" (1/1) ... [2018-06-18 13:49:08,070 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:49:08" (1/1) ... [2018-06-18 13:49:08,071 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:49:08" (1/1) ... [2018-06-18 13:49:08,073 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:49:08" (1/1) ... [2018-06-18 13:49:08,075 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-18 13:49:08,075 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-18 13:49:08,076 INFO ]: Initializing RCFGBuilder... [2018-06-18 13:49:08,076 INFO ]: RCFGBuilder initialized [2018-06-18 13:49:08,076 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:49: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-18 13:49:08,099 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-18 13:49:08,099 INFO ]: Found specification of procedure False [2018-06-18 13:49:08,099 INFO ]: Found implementation of procedure False [2018-06-18 13:49:08,099 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-18 13:49:08,099 INFO ]: Found specification of procedure state [2018-06-18 13:49:08,099 INFO ]: Found implementation of procedure state [2018-06-18 13:49:08,099 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-18 13:49:08,099 INFO ]: Found specification of procedure Ultimate.START [2018-06-18 13:49:08,099 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-18 13:49:08,319 INFO ]: Using library mode [2018-06-18 13:49:08,319 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 01:49:08 BoogieIcfgContainer [2018-06-18 13:49:08,320 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-18 13:49:08,324 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-18 13:49:08,324 INFO ]: Initializing TraceAbstraction... [2018-06-18 13:49:08,332 INFO ]: TraceAbstraction initialized [2018-06-18 13:49:08,333 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 01:49:07" (1/3) ... [2018-06-18 13:49:08,334 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4f5efc5d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 18.06 01:49:08, skipping insertion in model container [2018-06-18 13:49:08,334 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:49:08" (2/3) ... [2018-06-18 13:49:08,334 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4f5efc5d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.06 01:49:08, skipping insertion in model container [2018-06-18 13:49:08,334 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 01:49:08" (3/3) ... [2018-06-18 13:49:08,336 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-18 13:49:08,345 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-18 13:49:08,353 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-18 13:49:08,398 INFO ]: Using default assertion order modulation [2018-06-18 13:49:08,398 INFO ]: Interprodecural is true [2018-06-18 13:49:08,398 INFO ]: Hoare is false [2018-06-18 13:49:08,398 INFO ]: Compute interpolants for FPandBP [2018-06-18 13:49:08,398 INFO ]: Backedges is TWOTRACK [2018-06-18 13:49:08,398 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-18 13:49:08,398 INFO ]: Difference is false [2018-06-18 13:49:08,398 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-18 13:49:08,398 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-18 13:49:08,413 INFO ]: Start isEmpty. Operand 13 states. [2018-06-18 13:49:08,427 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-18 13:49:08,427 INFO ]: Found error trace [2018-06-18 13:49:08,428 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:49:08,428 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:49:08,431 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-18 13:49:08,433 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:49:08,433 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:49:08,475 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:08,476 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:49:08,476 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:08,511 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:08,521 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:49:08,683 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-18 13:49:08,686 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-18 13:49:08,686 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-18 13:49:08,689 INFO ]: Interpolant automaton has 4 states [2018-06-18 13:49:08,714 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-18 13:49:08,715 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 13:49:08,717 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-18 13:49:08,838 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:49:08,838 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-18 13:49:08,839 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-18 13:49:08,840 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-18 13:49:08,840 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:49:08,850 INFO ]: With dead ends: 13 [2018-06-18 13:49:08,851 INFO ]: Without dead ends: 13 [2018-06-18 13:49:08,852 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 13:49:08,871 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-18 13:49:08,900 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-18 13:49:08,902 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-18 13:49:08,902 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-18 13:49:08,903 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-18 13:49:08,903 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:49:08,903 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-18 13:49:08,903 INFO ]: Interpolant automaton has 4 states. [2018-06-18 13:49:08,904 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-18 13:49:08,905 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-18 13:49:08,905 INFO ]: Found error trace [2018-06-18 13:49:08,905 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:49:08,905 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:49:08,906 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-18 13:49:08,906 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:49:08,906 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:49:08,907 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:08,907 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:49:08,907 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:08,972 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:08,973 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:49:09,269 WARN ]: Spent 138.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-18 13:49:09,338 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 13:49:09,338 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:49:09,338 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 13:49:09,355 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:49:09,418 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:09,437 INFO ]: Computing forward predicates... [2018-06-18 13:49:09,739 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 13:49:09,761 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:49:09,761 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-18 13:49:09,762 INFO ]: Interpolant automaton has 6 states [2018-06-18 13:49:09,762 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-18 13:49:09,762 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-18 13:49:09,762 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 6 states. [2018-06-18 13:49:09,907 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:49:09,908 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-18 13:49:09,909 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-18 13:49:09,909 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-18 13:49:09,909 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:49:09,909 INFO ]: With dead ends: 15 [2018-06-18 13:49:09,909 INFO ]: Without dead ends: 15 [2018-06-18 13:49:09,910 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-18 13:49:09,910 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-18 13:49:09,914 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-18 13:49:09,915 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-18 13:49:09,915 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-18 13:49:09,915 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-18 13:49:09,915 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:49:09,915 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-18 13:49:09,915 INFO ]: Interpolant automaton has 6 states. [2018-06-18 13:49:09,915 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-18 13:49:09,916 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-18 13:49:09,916 INFO ]: Found error trace [2018-06-18 13:49:09,916 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:49:09,916 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:49:09,916 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-18 13:49:09,916 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:49:09,916 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:49:09,919 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:09,919 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:49:09,919 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:09,980 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:09,981 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:49:10,263 WARN ]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-18 13:49:10,505 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 13:49:10,505 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:49:10,505 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-18 13:49:10,514 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-18 13:49:10,568 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-18 13:49:10,568 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:10,579 INFO ]: Computing forward predicates... [2018-06-18 13:49:10,975 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 13:49:10,997 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:49:10,997 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-18 13:49:10,997 INFO ]: Interpolant automaton has 11 states [2018-06-18 13:49:10,997 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-18 13:49:10,997 INFO ]: CoverageRelationStatistics Valid=34, Invalid=76, Unknown=0, NotChecked=0, Total=110 [2018-06-18 13:49:10,998 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-18 13:49:11,722 WARN ]: Spent 596.00 ms on a formula simplification that was a NOOP. DAG size: 20 [2018-06-18 13:49:12,135 WARN ]: Spent 108.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 18 [2018-06-18 13:49:12,174 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:49:12,174 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-18 13:49:12,175 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-18 13:49:12,175 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-18 13:49:12,175 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:49:12,176 INFO ]: With dead ends: 17 [2018-06-18 13:49:12,176 INFO ]: Without dead ends: 17 [2018-06-18 13:49:12,176 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=49, Invalid=107, Unknown=0, NotChecked=0, Total=156 [2018-06-18 13:49:12,176 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-18 13:49:12,179 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-18 13:49:12,179 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-18 13:49:12,180 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-18 13:49:12,180 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-18 13:49:12,180 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:49:12,180 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-18 13:49:12,180 INFO ]: Interpolant automaton has 11 states. [2018-06-18 13:49:12,180 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-18 13:49:12,181 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-18 13:49:12,181 INFO ]: Found error trace [2018-06-18 13:49:12,181 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:49:12,181 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:49:12,181 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-18 13:49:12,181 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:49:12,181 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:49:12,182 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:12,182 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:49:12,182 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:12,217 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:12,218 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:49:12,626 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 13:49:12,626 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:49:12,626 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 13:49:12,643 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-18 13:49:12,724 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-18 13:49:12,724 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:12,729 INFO ]: Computing forward predicates... [2018-06-18 13:49:13,159 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 13:49:13,181 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:49:13,181 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 13 [2018-06-18 13:49:13,182 INFO ]: Interpolant automaton has 13 states [2018-06-18 13:49:13,182 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-18 13:49:13,182 INFO ]: CoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2018-06-18 13:49:13,182 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 13 states. [2018-06-18 13:49:13,820 WARN ]: Spent 583.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 29 [2018-06-18 13:49:14,077 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:49:14,077 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-18 13:49:14,078 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-18 13:49:14,078 INFO ]: Start accepts. Automaton has 13 states. Word has length 21 [2018-06-18 13:49:14,078 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:49:14,079 INFO ]: With dead ends: 19 [2018-06-18 13:49:14,079 INFO ]: Without dead ends: 19 [2018-06-18 13:49:14,079 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 18 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=74, Invalid=198, Unknown=0, NotChecked=0, Total=272 [2018-06-18 13:49:14,079 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-18 13:49:14,083 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-18 13:49:14,084 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-18 13:49:14,084 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-18 13:49:14,084 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-18 13:49:14,084 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:49:14,084 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-18 13:49:14,085 INFO ]: Interpolant automaton has 13 states. [2018-06-18 13:49:14,085 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-18 13:49:14,085 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-18 13:49:14,085 INFO ]: Found error trace [2018-06-18 13:49:14,085 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:49:14,085 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:49:14,086 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-18 13:49:14,086 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:49:14,086 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:49:14,086 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:14,086 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:49:14,086 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:14,143 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:14,143 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:49:14,717 WARN ]: Spent 121.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-18 13:49:14,823 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-18 13:49:14,823 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:49:14,823 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 13:49:14,830 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-18 13:49:14,865 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-18 13:49:14,865 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:14,869 INFO ]: Computing forward predicates... [2018-06-18 13:49:15,091 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 21 [2018-06-18 13:49:15,397 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-18 13:49:15,418 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:49:15,418 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 16 [2018-06-18 13:49:15,419 INFO ]: Interpolant automaton has 16 states [2018-06-18 13:49:15,419 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-18 13:49:15,419 INFO ]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2018-06-18 13:49:15,419 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 16 states. [2018-06-18 13:49:15,779 WARN ]: Spent 219.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 43 [2018-06-18 13:49:16,073 WARN ]: Spent 200.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 27 [2018-06-18 13:49:16,321 WARN ]: Spent 229.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 36 [2018-06-18 13:49:16,601 WARN ]: Spent 239.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 30 [2018-06-18 13:49:16,628 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:49:16,628 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-18 13:49:16,633 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-18 13:49:16,633 INFO ]: Start accepts. Automaton has 16 states. Word has length 25 [2018-06-18 13:49:16,634 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:49:16,634 INFO ]: With dead ends: 21 [2018-06-18 13:49:16,634 INFO ]: Without dead ends: 21 [2018-06-18 13:49:16,635 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 20 SyntacticMatches, 2 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=94, Invalid=326, Unknown=0, NotChecked=0, Total=420 [2018-06-18 13:49:16,635 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-18 13:49:16,638 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-18 13:49:16,638 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-18 13:49:16,639 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-18 13:49:16,639 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-18 13:49:16,639 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:49:16,639 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-18 13:49:16,639 INFO ]: Interpolant automaton has 16 states. [2018-06-18 13:49:16,639 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-18 13:49:16,640 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-18 13:49:16,640 INFO ]: Found error trace [2018-06-18 13:49:16,640 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:49:16,640 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:49:16,640 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-18 13:49:16,640 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:49:16,640 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:49:16,641 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:16,641 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:49:16,641 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:16,749 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:16,750 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:49:17,632 WARN ]: Spent 487.00 ms on a formula simplification that was a NOOP. DAG size: 33 [2018-06-18 13:49:17,788 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 24 [2018-06-18 13:49:17,947 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-18 13:49:17,947 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:49:17,947 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 13:49:17,955 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-18 13:49:18,018 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-18 13:49:18,018 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:18,025 INFO ]: Computing forward predicates... [2018-06-18 13:49:18,666 WARN ]: Spent 258.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 17 [2018-06-18 13:49:18,893 WARN ]: Spent 197.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 38 [2018-06-18 13:49:19,130 WARN ]: Spent 196.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 30 [2018-06-18 13:49:21,090 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-18 13:49:21,114 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:49:21,114 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 22 [2018-06-18 13:49:21,114 INFO ]: Interpolant automaton has 22 states [2018-06-18 13:49:21,114 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-18 13:49:21,115 INFO ]: CoverageRelationStatistics Valid=73, Invalid=389, Unknown=0, NotChecked=0, Total=462 [2018-06-18 13:49:21,115 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 22 states. [2018-06-18 13:49:21,756 WARN ]: Spent 596.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 67 [2018-06-18 13:49:21,930 WARN ]: Spent 110.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 22 [2018-06-18 13:49:22,165 WARN ]: Spent 211.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 37 [2018-06-18 13:49:22,560 WARN ]: Spent 364.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 50 [2018-06-18 13:49:23,091 WARN ]: Spent 496.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 45 [2018-06-18 13:49:23,421 WARN ]: Spent 303.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 60 [2018-06-18 13:49:23,508 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:49:23,508 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-18 13:49:23,509 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-18 13:49:23,509 INFO ]: Start accepts. Automaton has 22 states. Word has length 29 [2018-06-18 13:49:23,509 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:49:23,509 INFO ]: With dead ends: 23 [2018-06-18 13:49:23,509 INFO ]: Without dead ends: 23 [2018-06-18 13:49:23,510 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 21 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 95 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=166, Invalid=590, Unknown=0, NotChecked=0, Total=756 [2018-06-18 13:49:23,510 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-18 13:49:23,512 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-18 13:49:23,512 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-18 13:49:23,513 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-18 13:49:23,513 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-18 13:49:23,513 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:49:23,513 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-18 13:49:23,513 INFO ]: Interpolant automaton has 22 states. [2018-06-18 13:49:23,513 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-18 13:49:23,514 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-18 13:49:23,514 INFO ]: Found error trace [2018-06-18 13:49:23,514 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:49:23,514 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:49:23,514 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-18 13:49:23,514 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:49:23,514 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:49:23,515 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:23,515 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:49:23,515 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:23,600 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:23,601 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:49:24,239 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-18 13:49:24,239 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:49:24,239 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) [2018-06-18 13:49:24,254 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 13:49:24,316 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-18 13:49:24,316 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:24,322 INFO ]: Computing forward predicates... [2018-06-18 13:49:24,854 WARN ]: Spent 288.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 16 [2018-06-18 13:49:25,017 WARN ]: Spent 101.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 30 [2018-06-18 13:49:25,878 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-18 13:49:25,909 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:49:25,909 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 24 [2018-06-18 13:49:25,910 INFO ]: Interpolant automaton has 24 states [2018-06-18 13:49:25,910 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-18 13:49:25,910 INFO ]: CoverageRelationStatistics Valid=85, Invalid=467, Unknown=0, NotChecked=0, Total=552 [2018-06-18 13:49:25,910 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 24 states. [2018-06-18 13:49:26,512 WARN ]: Spent 421.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 63 [2018-06-18 13:49:26,666 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 30 [2018-06-18 13:49:26,840 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 45 [2018-06-18 13:49:27,049 WARN ]: Spent 184.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 43 [2018-06-18 13:49:27,257 WARN ]: Spent 181.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 33 [2018-06-18 13:49:27,505 WARN ]: Spent 222.00 ms on a formula simplification. DAG size of input: 66 DAG size of output: 35 [2018-06-18 13:49:27,849 WARN ]: Spent 235.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 60 [2018-06-18 13:49:27,878 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:49:27,878 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-18 13:49:27,878 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-18 13:49:27,878 INFO ]: Start accepts. Automaton has 24 states. Word has length 33 [2018-06-18 13:49:27,878 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:49:27,879 INFO ]: With dead ends: 25 [2018-06-18 13:49:27,879 INFO ]: Without dead ends: 25 [2018-06-18 13:49:27,880 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 24 SyntacticMatches, 2 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 115 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=196, Invalid=734, Unknown=0, NotChecked=0, Total=930 [2018-06-18 13:49:27,880 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-18 13:49:27,883 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-18 13:49:27,883 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-18 13:49:27,884 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-18 13:49:27,884 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-18 13:49:27,884 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:49:27,884 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-18 13:49:27,884 INFO ]: Interpolant automaton has 24 states. [2018-06-18 13:49:27,884 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-18 13:49:27,885 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-18 13:49:27,885 INFO ]: Found error trace [2018-06-18 13:49:27,885 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:49:27,885 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:49:27,885 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-18 13:49:27,885 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:49:27,885 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:49:27,886 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:27,886 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:49:27,886 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:49:27,944 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:27,945 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:49:28,758 WARN ]: Spent 626.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-18 13:49:29,418 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-18 13:49:29,418 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:49:29,418 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-18 13:49:29,434 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:49:29,505 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:49:29,513 INFO ]: Computing forward predicates... [2018-06-18 13:49:47,504 WARN ]: Spent 16.84 s on a formula simplification. DAG size of input: 662 DAG size of output: 79 Received shutdown request... [2018-06-18 13:50:18,468 WARN ]: Removed 8 from assertion stack [2018-06-18 13:50:18,469 INFO ]: Timeout while computing interpolants [2018-06-18 13:50:18,670 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 13:50:18,670 WARN ]: Verification canceled [2018-06-18 13:50:18,680 WARN ]: Timeout [2018-06-18 13:50:18,683 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.06 01:50:18 BoogieIcfgContainer [2018-06-18 13:50:18,683 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-18 13:50:18,684 INFO ]: Toolchain (without parser) took 70771.16 ms. Allocated memory was 308.3 MB in the beginning and 645.9 MB in the end (delta: 337.6 MB). Free memory was 260.7 MB in the beginning and 546.5 MB in the end (delta: -285.8 MB). Peak memory consumption was 397.6 MB. Max. memory is 3.6 GB. [2018-06-18 13:50:18,685 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.3 MB. Free memory is still 273.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-18 13:50:18,685 INFO ]: ChcToBoogie took 99.45 ms. Allocated memory is still 308.3 MB. Free memory was 260.7 MB in the beginning and 257.7 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:50:18,686 INFO ]: Boogie Preprocessor took 56.18 ms. Allocated memory is still 308.3 MB. Free memory was 257.7 MB in the beginning and 255.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:50:18,686 INFO ]: RCFGBuilder took 244.16 ms. Allocated memory is still 308.3 MB. Free memory was 255.6 MB in the beginning and 245.6 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:50:18,687 INFO ]: TraceAbstraction took 70359.72 ms. Allocated memory was 308.3 MB in the beginning and 645.9 MB in the end (delta: 337.6 MB). Free memory was 245.6 MB in the beginning and 546.5 MB in the end (delta: -300.8 MB). Peak memory consumption was 382.6 MB. Max. memory is 3.6 GB. [2018-06-18 13:50:18,695 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 308.3 MB. Free memory is still 273.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 99.45 ms. Allocated memory is still 308.3 MB. Free memory was 260.7 MB in the beginning and 257.7 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 56.18 ms. Allocated memory is still 308.3 MB. Free memory was 257.7 MB in the beginning and 255.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 244.16 ms. Allocated memory is still 308.3 MB. Free memory was 255.6 MB in the beginning and 245.6 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 70359.72 ms. Allocated memory was 308.3 MB in the beginning and 645.9 MB in the end (delta: 337.6 MB). Free memory was 245.6 MB in the beginning and 546.5 MB in the end (delta: -300.8 MB). Peak memory consumption was 382.6 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 38 with TraceHistMax 8, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 1722. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 70.2s OverallTime, 8 OverallIterations, 8 TraceHistogramMax, 7.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 87 SDtfs, 183 SDslu, 385 SDs, 0 SdLazy, 330 SolverSat, 218 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 226 GetRequests, 114 SyntacticMatches, 6 SemanticMatches, 106 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 279 ImplicationChecksByTransitivity, 13.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=25occurred in iteration=7, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 10.3s InterpolantComputationTime, 285 NumberOfCodeBlocks, 285 NumberOfCodeBlocksAsserted, 28 NumberOfCheckSat, 272 ConstructedInterpolants, 0 QuantifiedInterpolants, 93348 SizeOfPredicates, 328 NumberOfNonLiveVariables, 1104 ConjunctsInSsa, 200 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_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-18_13-50-18-717.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/up-nd.c.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-18_13-50-18-717.csv Completed graceful shutdown