java -Xss4m -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_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/id_build.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 13:06:01,135 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 13:06:01,137 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 13:06:01,148 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 13:06:01,148 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 13:06:01,149 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 13:06:01,150 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 13:06:01,152 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 13:06:01,154 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 13:06:01,155 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 13:06:01,155 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 13:06:01,156 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 13:06:01,156 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 13:06:01,158 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 13:06:01,158 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 13:06:01,159 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 13:06:01,163 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 13:06:01,165 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 13:06:01,167 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 13:06:01,168 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 13:06:01,169 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 13:06:01,171 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 13:06:01,172 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 13:06:01,172 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 13:06:01,173 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 13:06:01,174 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 13:06:01,174 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 13:06:01,175 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 13:06:01,176 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 13:06:01,176 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 13:06:01,177 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 13:06:01,178 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 13:06:01,178 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 13:06:01,179 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 13:06:01,179 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 13:06:01,180 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 13:06:01,202 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 13:06:01,202 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 13:06:01,203 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 13:06:01,203 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 13:06:01,205 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 13:06:01,206 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 13:06:01,206 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 13:06:01,206 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 13:06:01,206 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 13:06:01,206 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 13:06:01,207 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 13:06:01,207 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 13:06:01,207 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:06:01,207 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 13:06:01,207 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 13:06:01,207 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 13:06:01,208 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 13:06:01,208 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 13:06:01,208 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 13:06:01,208 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 13:06:01,208 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 13:06:01,214 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 13:06:01,214 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 13:06:01,273 INFO ]: Repository-Root is: /tmp [2018-06-25 13:06:01,295 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 13:06:01,302 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 13:06:01,303 INFO ]: Initializing SmtParser... [2018-06-25 13:06:01,304 INFO ]: SmtParser initialized [2018-06-25 13:06:01,304 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/id_build.c.smt2 [2018-06-25 13:06:01,305 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-25 13:06:01,402 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/id_build.c.smt2 unknown [2018-06-25 13:06:01,646 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/id_build.c.smt2 [2018-06-25 13:06:01,651 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 13:06:01,656 INFO ]: Walking toolchain with 4 elements. [2018-06-25 13:06:01,657 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 13:06:01,657 INFO ]: Initializing ChcToBoogie... [2018-06-25 13:06:01,657 INFO ]: ChcToBoogie initialized [2018-06-25 13:06:01,663 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:06:01" (1/1) ... [2018-06-25 13:06:01,722 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:06:01 Unit [2018-06-25 13:06:01,722 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 13:06:01,723 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 13:06:01,723 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 13:06:01,723 INFO ]: Boogie Preprocessor initialized [2018-06-25 13:06:01,744 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:06:01" (1/1) ... [2018-06-25 13:06:01,744 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:06:01" (1/1) ... [2018-06-25 13:06:01,764 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:06:01" (1/1) ... [2018-06-25 13:06:01,765 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:06:01" (1/1) ... [2018-06-25 13:06:01,768 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:06:01" (1/1) ... [2018-06-25 13:06:01,770 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:06:01" (1/1) ... [2018-06-25 13:06:01,771 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:06:01" (1/1) ... [2018-06-25 13:06:01,774 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 13:06:01,775 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 13:06:01,775 INFO ]: Initializing RCFGBuilder... [2018-06-25 13:06:01,775 INFO ]: RCFGBuilder initialized [2018-06-25 13:06:01,776 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:06:01" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:06:01,794 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 13:06:01,794 INFO ]: Found specification of procedure gotoProc [2018-06-25 13:06:01,794 INFO ]: Found implementation of procedure gotoProc [2018-06-25 13:06:01,794 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 13:06:01,794 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 13:06:01,794 INFO ]: Found implementation of procedure Ultimate.START [2018-06-25 13:06:01,978 INFO ]: Using library mode [2018-06-25 13:06:01,978 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:06:01 BoogieIcfgContainer [2018-06-25 13:06:01,978 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 13:06:01,980 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 13:06:01,981 INFO ]: Initializing TraceAbstraction... [2018-06-25 13:06:01,984 INFO ]: TraceAbstraction initialized [2018-06-25 13:06:01,984 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:06:01" (1/3) ... [2018-06-25 13:06:01,985 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@11e4b796 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 01:06:01, skipping insertion in model container [2018-06-25 13:06:01,985 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:06:01" (2/3) ... [2018-06-25 13:06:01,986 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@11e4b796 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 01:06:01, skipping insertion in model container [2018-06-25 13:06:01,986 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:06:01" (3/3) ... [2018-06-25 13:06:01,988 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 13:06:01,999 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 13:06:02,010 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 13:06:02,062 INFO ]: Using default assertion order modulation [2018-06-25 13:06:02,062 INFO ]: Interprodecural is true [2018-06-25 13:06:02,062 INFO ]: Hoare is false [2018-06-25 13:06:02,062 INFO ]: Compute interpolants for FPandBP [2018-06-25 13:06:02,062 INFO ]: Backedges is TWOTRACK [2018-06-25 13:06:02,062 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 13:06:02,062 INFO ]: Difference is false [2018-06-25 13:06:02,063 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 13:06:02,063 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 13:06:02,082 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 13:06:02,098 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 13:06:02,098 INFO ]: Found error trace [2018-06-25 13:06:02,101 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:06:02,101 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:06:02,106 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-25 13:06:02,109 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:06:02,109 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:06:02,163 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:02,163 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:06:02,163 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:02,204 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:02,317 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:02,321 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 13:06:02,321 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 13:06:02,323 INFO ]: Interpolant automaton has 3 states [2018-06-25 13:06:02,340 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 13:06:02,340 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:06:02,343 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 13:06:02,414 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:06:02,414 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 13:06:02,415 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 13:06:02,416 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 13:06:02,417 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:06:02,430 INFO ]: With dead ends: 9 [2018-06-25 13:06:02,430 INFO ]: Without dead ends: 9 [2018-06-25 13:06:02,440 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:06:02,456 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 13:06:02,473 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 13:06:02,475 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 13:06:02,475 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 13:06:02,476 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 13:06:02,477 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:06:02,477 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 13:06:02,477 INFO ]: Interpolant automaton has 3 states. [2018-06-25 13:06:02,477 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 13:06:02,477 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 13:06:02,477 INFO ]: Found error trace [2018-06-25 13:06:02,477 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:06:02,478 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:06:02,478 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-25 13:06:02,478 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:06:02,478 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:06:02,479 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:02,479 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:06:02,479 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:02,514 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:02,685 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:02,685 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:06:02,685 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-25 13:06:02,694 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:06:02,739 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:02,746 INFO ]: Computing forward predicates... [2018-06-25 13:06:03,054 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:03,078 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:06:03,079 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 13:06:03,079 INFO ]: Interpolant automaton has 5 states [2018-06-25 13:06:03,079 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 13:06:03,079 INFO ]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-25 13:06:03,080 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 13:06:03,102 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:06:03,102 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 13:06:03,102 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-25 13:06:03,102 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 13:06:03,102 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:06:03,102 INFO ]: With dead ends: 10 [2018-06-25 13:06:03,102 INFO ]: Without dead ends: 10 [2018-06-25 13:06:03,103 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-25 13:06:03,103 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 13:06:03,104 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 13:06:03,104 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 13:06:03,104 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 13:06:03,105 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 13:06:03,105 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:06:03,105 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 13:06:03,105 INFO ]: Interpolant automaton has 5 states. [2018-06-25 13:06:03,105 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 13:06:03,105 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 13:06:03,105 INFO ]: Found error trace [2018-06-25 13:06:03,105 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:06:03,105 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:06:03,105 INFO ]: Analyzing trace with hash -2043975570, now seen corresponding path program 2 times [2018-06-25 13:06:03,105 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:06:03,105 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:06:03,106 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:03,106 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:06:03,106 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:03,175 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:03,437 WARN ]: Spent 187.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-25 13:06:03,621 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:03,622 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:06:03,622 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-25 13:06:03,630 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 13:06:03,675 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 13:06:03,675 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:03,678 INFO ]: Computing forward predicates... [2018-06-25 13:06:03,842 WARN ]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-25 13:06:05,340 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:05,372 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:06:05,372 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-25 13:06:05,372 INFO ]: Interpolant automaton has 6 states [2018-06-25 13:06:05,372 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 13:06:05,372 INFO ]: CoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-25 13:06:05,373 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-25 13:06:05,696 WARN ]: Spent 221.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-25 13:06:05,715 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:06:05,715 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 13:06:05,715 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 13:06:05,715 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-25 13:06:05,715 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:06:05,716 INFO ]: With dead ends: 11 [2018-06-25 13:06:05,716 INFO ]: Without dead ends: 11 [2018-06-25 13:06:05,716 INFO ]: 0 DeclaredPredicates, 14 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2018-06-25 13:06:05,716 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 13:06:05,717 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 13:06:05,717 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 13:06:05,718 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 13:06:05,718 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 13:06:05,718 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:06:05,718 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 13:06:05,718 INFO ]: Interpolant automaton has 6 states. [2018-06-25 13:06:05,718 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 13:06:05,718 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 13:06:05,718 INFO ]: Found error trace [2018-06-25 13:06:05,718 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:06:05,718 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:06:05,719 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 3 times [2018-06-25 13:06:05,719 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:06:05,719 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:06:05,720 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:05,720 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:06:05,720 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:05,779 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:06,024 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:06,024 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:06:06,024 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-25 13:06:06,031 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 13:06:06,079 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 13:06:06,079 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:06,082 INFO ]: Computing forward predicates... [2018-06-25 13:06:07,861 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:07,894 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:06:07,915 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-25 13:06:07,915 INFO ]: Interpolant automaton has 7 states [2018-06-25 13:06:07,916 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 13:06:07,916 INFO ]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-06-25 13:06:07,916 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-25 13:06:08,107 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:06:08,107 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 13:06:08,107 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 13:06:08,107 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-25 13:06:08,108 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:06:08,108 INFO ]: With dead ends: 12 [2018-06-25 13:06:08,108 INFO ]: Without dead ends: 12 [2018-06-25 13:06:08,108 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2018-06-25 13:06:08,109 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 13:06:08,110 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 13:06:08,110 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 13:06:08,110 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 13:06:08,110 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 13:06:08,110 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:06:08,110 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 13:06:08,110 INFO ]: Interpolant automaton has 7 states. [2018-06-25 13:06:08,110 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 13:06:08,111 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 13:06:08,111 INFO ]: Found error trace [2018-06-25 13:06:08,111 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:06:08,111 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:06:08,111 INFO ]: Analyzing trace with hash -1433955954, now seen corresponding path program 4 times [2018-06-25 13:06:08,111 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:06:08,111 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:06:08,112 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:08,112 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:06:08,112 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:08,147 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:08,285 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:08,285 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:06:08,285 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-25 13:06:08,291 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 13:06:08,337 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 13:06:08,337 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:08,341 INFO ]: Computing forward predicates... [2018-06-25 13:06:08,858 WARN ]: Spent 284.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-25 13:06:13,365 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:13,399 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:06:13,401 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 8 [2018-06-25 13:06:13,401 INFO ]: Interpolant automaton has 8 states [2018-06-25 13:06:13,401 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-25 13:06:13,401 INFO ]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-06-25 13:06:13,401 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 8 states. [2018-06-25 13:06:14,015 WARN ]: Spent 532.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 12 [2018-06-25 13:06:14,284 WARN ]: Spent 145.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-25 13:06:14,354 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:06:14,354 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-25 13:06:14,354 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-25 13:06:14,354 INFO ]: Start accepts. Automaton has 8 states. Word has length 11 [2018-06-25 13:06:14,354 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:06:14,355 INFO ]: With dead ends: 13 [2018-06-25 13:06:14,355 INFO ]: Without dead ends: 13 [2018-06-25 13:06:14,355 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=58, Invalid=98, Unknown=0, NotChecked=0, Total=156 [2018-06-25 13:06:14,355 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-25 13:06:14,356 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-25 13:06:14,356 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-25 13:06:14,357 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-25 13:06:14,357 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-25 13:06:14,357 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:06:14,357 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-25 13:06:14,357 INFO ]: Interpolant automaton has 8 states. [2018-06-25 13:06:14,357 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-25 13:06:14,357 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-25 13:06:14,357 INFO ]: Found error trace [2018-06-25 13:06:14,357 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:06:14,357 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:06:14,357 INFO ]: Analyzing trace with hash -1502133097, now seen corresponding path program 5 times [2018-06-25 13:06:14,357 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:06:14,358 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:06:14,358 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:14,358 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:06:14,358 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:14,423 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:14,748 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 17 [2018-06-25 13:06:14,795 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:14,796 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:06:14,796 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-25 13:06:14,802 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 13:06:14,841 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-25 13:06:14,841 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:14,846 INFO ]: Computing forward predicates... [2018-06-25 13:06:19,064 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:19,084 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:06:19,101 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2018-06-25 13:06:19,101 INFO ]: Interpolant automaton has 9 states [2018-06-25 13:06:19,101 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-25 13:06:19,101 INFO ]: CoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2018-06-25 13:06:19,101 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 9 states. [2018-06-25 13:06:19,467 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:06:19,467 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-25 13:06:19,467 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-25 13:06:19,467 INFO ]: Start accepts. Automaton has 9 states. Word has length 12 [2018-06-25 13:06:19,467 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:06:19,467 INFO ]: With dead ends: 14 [2018-06-25 13:06:19,467 INFO ]: Without dead ends: 14 [2018-06-25 13:06:19,468 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 8 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=70, Invalid=140, Unknown=0, NotChecked=0, Total=210 [2018-06-25 13:06:19,468 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-25 13:06:19,469 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-25 13:06:19,469 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-25 13:06:19,470 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-25 13:06:19,470 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-25 13:06:19,470 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:06:19,470 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-25 13:06:19,470 INFO ]: Interpolant automaton has 9 states. [2018-06-25 13:06:19,470 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-25 13:06:19,470 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-25 13:06:19,470 INFO ]: Found error trace [2018-06-25 13:06:19,470 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:06:19,470 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:06:19,470 INFO ]: Analyzing trace with hash 679342766, now seen corresponding path program 6 times [2018-06-25 13:06:19,470 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:06:19,470 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:06:19,478 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:19,478 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:06:19,478 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:19,584 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:19,931 WARN ]: Spent 212.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-25 13:06:20,334 WARN ]: Spent 355.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-25 13:06:20,772 WARN ]: Spent 375.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-25 13:06:20,853 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:20,853 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:06:20,853 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-25 13:06:20,862 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 13:06:20,914 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-25 13:06:20,914 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:20,918 INFO ]: Computing forward predicates... [2018-06-25 13:06:23,053 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:23,084 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:06:23,085 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 10 [2018-06-25 13:06:23,085 INFO ]: Interpolant automaton has 10 states [2018-06-25 13:06:23,085 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-25 13:06:23,085 INFO ]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2018-06-25 13:06:23,085 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 10 states. [2018-06-25 13:06:23,440 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:06:23,440 INFO ]: Finished difference Result 15 states and 15 transitions. [2018-06-25 13:06:23,440 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-25 13:06:23,440 INFO ]: Start accepts. Automaton has 10 states. Word has length 13 [2018-06-25 13:06:23,440 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:06:23,441 INFO ]: With dead ends: 15 [2018-06-25 13:06:23,441 INFO ]: Without dead ends: 15 [2018-06-25 13:06:23,441 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 7 SyntacticMatches, 6 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 51 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=89, Invalid=183, Unknown=0, NotChecked=0, Total=272 [2018-06-25 13:06:23,441 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-25 13:06:23,443 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-25 13:06:23,443 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-25 13:06:23,443 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-06-25 13:06:23,444 INFO ]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 13 [2018-06-25 13:06:23,444 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:06:23,444 INFO ]: Abstraction has 15 states and 15 transitions. [2018-06-25 13:06:23,444 INFO ]: Interpolant automaton has 10 states. [2018-06-25 13:06:23,444 INFO ]: Start isEmpty. Operand 15 states and 15 transitions. [2018-06-25 13:06:23,444 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-25 13:06:23,444 INFO ]: Found error trace [2018-06-25 13:06:23,444 INFO ]: trace histogram [7, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:06:23,444 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:06:23,444 INFO ]: Analyzing trace with hash -414382217, now seen corresponding path program 7 times [2018-06-25 13:06:23,444 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:06:23,444 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:06:23,445 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:23,445 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:06:23,445 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:23,505 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:23,812 WARN ]: Spent 117.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-25 13:06:23,923 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:23,923 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:06:23,923 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-25 13:06:23,930 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:06:23,970 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:23,974 INFO ]: Computing forward predicates... [2018-06-25 13:06:31,551 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:31,571 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:06:31,571 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 12 [2018-06-25 13:06:31,571 INFO ]: Interpolant automaton has 12 states [2018-06-25 13:06:31,572 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-25 13:06:31,572 INFO ]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2018-06-25 13:06:31,572 INFO ]: Start difference. First operand 15 states and 15 transitions. Second operand 12 states. [2018-06-25 13:06:31,842 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 28 [2018-06-25 13:06:32,145 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:06:32,145 INFO ]: Finished difference Result 17 states and 17 transitions. [2018-06-25 13:06:32,145 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-25 13:06:32,145 INFO ]: Start accepts. Automaton has 12 states. Word has length 14 [2018-06-25 13:06:32,146 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:06:32,146 INFO ]: With dead ends: 17 [2018-06-25 13:06:32,146 INFO ]: Without dead ends: 17 [2018-06-25 13:06:32,146 INFO ]: 0 DeclaredPredicates, 32 GetRequests, 7 SyntacticMatches, 6 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 69 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=146, Invalid=274, Unknown=0, NotChecked=0, Total=420 [2018-06-25 13:06:32,146 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-25 13:06:32,148 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-25 13:06:32,148 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-25 13:06:32,148 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 17 transitions. [2018-06-25 13:06:32,148 INFO ]: Start accepts. Automaton has 17 states and 17 transitions. Word has length 14 [2018-06-25 13:06:32,148 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:06:32,148 INFO ]: Abstraction has 17 states and 17 transitions. [2018-06-25 13:06:32,148 INFO ]: Interpolant automaton has 12 states. [2018-06-25 13:06:32,148 INFO ]: Start isEmpty. Operand 17 states and 17 transitions. [2018-06-25 13:06:32,149 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-25 13:06:32,149 INFO ]: Found error trace [2018-06-25 13:06:32,149 INFO ]: trace histogram [9, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:06:32,149 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:06:32,149 INFO ]: Analyzing trace with hash 1237160535, now seen corresponding path program 8 times [2018-06-25 13:06:32,149 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:06:32,149 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:06:32,150 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:32,150 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:06:32,150 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:06:32,228 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:32,542 WARN ]: Spent 189.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-25 13:06:32,829 WARN ]: Spent 236.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-25 13:06:33,043 INFO ]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:06:33,043 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:06:33,043 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:06:33,052 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 13:06:33,107 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 13:06:33,107 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:06:33,110 INFO ]: Computing forward predicates... [2018-06-25 13:07:02,390 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:07:02,401 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-25 13:07:04,275 INFO ]: Timeout while computing interpolants [2018-06-25 13:07:04,475 WARN ]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:07:04,475 WARN ]: Verification canceled [2018-06-25 13:07:04,479 WARN ]: Timeout [2018-06-25 13:07:04,479 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 01:07:04 BoogieIcfgContainer [2018-06-25 13:07:04,479 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 13:07:04,480 INFO ]: Toolchain (without parser) took 62828.53 ms. Allocated memory was 307.2 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 260.6 MB in the beginning and 554.9 MB in the end (delta: -294.2 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 13:07:04,481 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 307.2 MB. Free memory is still 272.7 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 13:07:04,481 INFO ]: ChcToBoogie took 65.67 ms. Allocated memory is still 307.2 MB. Free memory was 260.6 MB in the beginning and 258.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:07:04,481 INFO ]: Boogie Preprocessor took 51.35 ms. Allocated memory is still 307.2 MB. Free memory was 258.6 MB in the beginning and 256.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:07:04,482 INFO ]: RCFGBuilder took 203.19 ms. Allocated memory is still 307.2 MB. Free memory was 256.6 MB in the beginning and 247.6 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:07:04,482 INFO ]: TraceAbstraction took 62499.69 ms. Allocated memory was 307.2 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 246.6 MB in the beginning and 554.9 MB in the end (delta: -308.2 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 13:07:04,485 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 307.2 MB. Free memory is still 272.7 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 65.67 ms. Allocated memory is still 307.2 MB. Free memory was 260.6 MB in the beginning and 258.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 51.35 ms. Allocated memory is still 307.2 MB. Free memory was 258.6 MB in the beginning and 256.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 203.19 ms. Allocated memory is still 307.2 MB. Free memory was 256.6 MB in the beginning and 247.6 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 62499.69 ms. Allocated memory was 307.2 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 246.6 MB in the beginning and 554.9 MB in the end (delta: -308.2 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 17 with TraceHistMax 9, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while XnfDer was eliminating 14811 quantified variables from 14 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 62.4s OverallTime, 9 OverallIterations, 9 TraceHistogramMax, 2.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 56 SDtfs, 21 SDslu, 184 SDs, 0 SdLazy, 70 SolverSat, 50 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 154 GetRequests, 52 SyntacticMatches, 26 SemanticMatches, 76 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 207 ImplicationChecksByTransitivity, 6.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=17occurred in iteration=8, 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, 8 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 25.8s InterpolantComputationTime, 161 NumberOfCodeBlocks, 161 NumberOfCodeBlocksAsserted, 24 NumberOfCheckSat, 146 ConstructedInterpolants, 0 QuantifiedInterpolants, 9481 SizeOfPredicates, 28 NumberOfNonLiveVariables, 1260 ConjunctsInSsa, 252 ConjunctsInUnsatCore, 15 InterpolantComputations, 1 PerfectInterpolantSequences, 0/168 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/id_build.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_13-07-04-495.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/id_build.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_13-07-04-495.csv Completed graceful shutdown