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/ex2.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 13:00:01,214 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 13:00:01,217 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 13:00:01,230 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 13:00:01,230 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 13:00:01,233 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 13:00:01,235 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 13:00:01,237 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 13:00:01,238 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 13:00:01,240 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 13:00:01,241 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 13:00:01,241 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 13:00:01,242 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 13:00:01,243 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 13:00:01,243 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 13:00:01,247 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 13:00:01,248 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 13:00:01,258 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 13:00:01,259 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 13:00:01,260 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 13:00:01,261 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 13:00:01,268 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 13:00:01,268 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 13:00:01,269 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 13:00:01,270 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 13:00:01,270 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 13:00:01,271 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 13:00:01,272 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 13:00:01,274 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 13:00:01,274 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 13:00:01,275 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 13:00:01,276 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 13:00:01,276 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 13:00:01,276 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 13:00:01,280 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 13:00:01,280 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:00:01,301 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 13:00:01,301 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 13:00:01,304 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 13:00:01,304 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 13:00:01,305 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 13:00:01,306 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 13:00:01,306 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 13:00:01,306 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 13:00:01,306 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 13:00:01,306 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 13:00:01,307 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 13:00:01,307 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 13:00:01,307 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:00:01,307 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 13:00:01,307 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 13:00:01,307 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 13:00:01,310 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 13:00:01,310 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 13:00:01,310 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 13:00:01,311 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 13:00:01,311 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 13:00:01,312 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 13:00:01,312 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 13:00:01,353 INFO ]: Repository-Root is: /tmp [2018-06-25 13:00:01,372 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 13:00:01,376 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 13:00:01,378 INFO ]: Initializing SmtParser... [2018-06-25 13:00:01,378 INFO ]: SmtParser initialized [2018-06-25 13:00:01,379 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/ex2.c.smt2 [2018-06-25 13:00:01,380 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:00:01,467 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/ex2.c.smt2 unknown [2018-06-25 13:00:01,783 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/ex2.c.smt2 [2018-06-25 13:00:01,790 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 13:00:01,795 INFO ]: Walking toolchain with 4 elements. [2018-06-25 13:00:01,796 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 13:00:01,796 INFO ]: Initializing ChcToBoogie... [2018-06-25 13:00:01,796 INFO ]: ChcToBoogie initialized [2018-06-25 13:00:01,799 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:00:01" (1/1) ... [2018-06-25 13:00:01,866 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:00:01 Unit [2018-06-25 13:00:01,866 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 13:00:01,867 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 13:00:01,867 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 13:00:01,867 INFO ]: Boogie Preprocessor initialized [2018-06-25 13:00:01,888 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:00:01" (1/1) ... [2018-06-25 13:00:01,888 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:00:01" (1/1) ... [2018-06-25 13:00:01,897 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:00:01" (1/1) ... [2018-06-25 13:00:01,897 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:00:01" (1/1) ... [2018-06-25 13:00:01,915 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:00:01" (1/1) ... [2018-06-25 13:00:01,916 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:00:01" (1/1) ... [2018-06-25 13:00:01,927 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:00:01" (1/1) ... [2018-06-25 13:00:01,930 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 13:00:01,930 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 13:00:01,930 INFO ]: Initializing RCFGBuilder... [2018-06-25 13:00:01,930 INFO ]: RCFGBuilder initialized [2018-06-25 13:00:01,931 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:00: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) [2018-06-25 13:00:01,964 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 13:00:01,964 INFO ]: Found specification of procedure gotoProc [2018-06-25 13:00:01,964 INFO ]: Found implementation of procedure gotoProc [2018-06-25 13:00:01,964 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 13:00:01,964 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 13:00:01,964 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-25 13:00:02,250 INFO ]: Using library mode [2018-06-25 13:00:02,250 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:00:02 BoogieIcfgContainer [2018-06-25 13:00:02,250 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 13:00:02,259 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 13:00:02,259 INFO ]: Initializing TraceAbstraction... [2018-06-25 13:00:02,262 INFO ]: TraceAbstraction initialized [2018-06-25 13:00:02,263 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:00:01" (1/3) ... [2018-06-25 13:00:02,263 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4bdb50 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 01:00:02, skipping insertion in model container [2018-06-25 13:00:02,263 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:00:01" (2/3) ... [2018-06-25 13:00:02,264 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4bdb50 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 01:00:02, skipping insertion in model container [2018-06-25 13:00:02,264 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:00:02" (3/3) ... [2018-06-25 13:00:02,265 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 13:00:02,286 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 13:00:02,294 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 13:00:02,355 INFO ]: Using default assertion order modulation [2018-06-25 13:00:02,356 INFO ]: Interprodecural is true [2018-06-25 13:00:02,356 INFO ]: Hoare is false [2018-06-25 13:00:02,356 INFO ]: Compute interpolants for FPandBP [2018-06-25 13:00:02,356 INFO ]: Backedges is TWOTRACK [2018-06-25 13:00:02,356 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 13:00:02,356 INFO ]: Difference is false [2018-06-25 13:00:02,356 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 13:00:02,356 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 13:00:02,373 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 13:00:02,384 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 13:00:02,384 INFO ]: Found error trace [2018-06-25 13:00:02,385 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:00:02,385 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:00:02,392 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-25 13:00:02,394 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:00:02,394 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:00:02,433 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:00:02,433 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:00:02,433 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:00:02,476 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:00:02,579 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:00:02,581 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 13:00:02,582 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 13:00:02,583 INFO ]: Interpolant automaton has 3 states [2018-06-25 13:00:02,599 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 13:00:02,599 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:00:02,602 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 13:00:02,664 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:00:02,664 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 13:00:02,665 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 13:00:02,666 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 13:00:02,666 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:00:02,674 INFO ]: With dead ends: 9 [2018-06-25 13:00:02,674 INFO ]: Without dead ends: 9 [2018-06-25 13:00:02,676 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:00:02,689 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 13:00:02,717 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 13:00:02,718 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 13:00:02,718 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 13:00:02,719 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 13:00:02,719 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:00:02,719 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 13:00:02,719 INFO ]: Interpolant automaton has 3 states. [2018-06-25 13:00:02,719 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 13:00:02,719 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 13:00:02,719 INFO ]: Found error trace [2018-06-25 13:00:02,719 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:00:02,720 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:00:02,720 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-25 13:00:02,720 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:00:02,720 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:00:02,721 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:00:02,721 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:00:02,721 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:00:02,763 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:00:02,928 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:00:02,928 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:00:02,928 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:00:02,935 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:00:02,989 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:00:02,998 INFO ]: Computing forward predicates... [2018-06-25 13:00:03,362 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:00:03,396 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:00:03,396 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 13:00:03,397 INFO ]: Interpolant automaton has 5 states [2018-06-25 13:00:03,397 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 13:00:03,397 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-25 13:00:03,397 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 13:00:03,633 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:00:03,633 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 13:00:03,634 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 13:00:03,634 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 13:00:03,634 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:00:03,634 INFO ]: With dead ends: 11 [2018-06-25 13:00:03,634 INFO ]: Without dead ends: 11 [2018-06-25 13:00:03,635 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-25 13:00:03,635 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 13:00:03,636 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 13:00:03,636 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 13:00:03,637 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 13:00:03,637 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-25 13:00:03,637 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:00:03,637 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 13:00:03,637 INFO ]: Interpolant automaton has 5 states. [2018-06-25 13:00:03,637 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 13:00:03,637 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 13:00:03,637 INFO ]: Found error trace [2018-06-25 13:00:03,637 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:00:03,637 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:00:03,637 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 2 times [2018-06-25 13:00:03,638 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:00:03,638 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:00:03,640 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:00:03,640 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:00:03,640 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:00:03,759 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:00:04,072 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:00:04,072 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:00:04,072 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) [2018-06-25 13:00:04,089 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:00:04,197 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 13:00:04,197 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:00:04,201 INFO ]: Computing forward predicates... [2018-06-25 13:00:06,034 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:08,459 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:00:08,480 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:00:08,480 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-25 13:00:08,480 INFO ]: Interpolant automaton has 7 states [2018-06-25 13:00:08,480 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 13:00:08,481 INFO ]: CoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-06-25 13:00:08,481 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-25 13:00:08,784 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:00:08,784 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 13:00:08,784 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 13:00:08,784 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-25 13:00:08,784 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:00:08,784 INFO ]: With dead ends: 12 [2018-06-25 13:00:08,784 INFO ]: Without dead ends: 12 [2018-06-25 13:00:08,785 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=48, Invalid=62, Unknown=0, NotChecked=0, Total=110 [2018-06-25 13:00:08,785 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 13:00:08,786 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 13:00:08,786 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 13:00:08,787 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 13:00:08,787 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 13:00:08,787 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:00:08,787 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 13:00:08,787 INFO ]: Interpolant automaton has 7 states. [2018-06-25 13:00:08,787 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 13:00:08,787 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 13:00:08,787 INFO ]: Found error trace [2018-06-25 13:00:08,787 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:00:08,788 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:00:08,788 INFO ]: Analyzing trace with hash -1433955954, now seen corresponding path program 3 times [2018-06-25 13:00:08,788 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:00:08,788 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:00:08,788 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:00:08,788 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:00:08,788 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:00:08,846 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:00:09,131 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:00:09,131 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:00:09,131 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:00:09,137 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 13:00:09,191 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 13:00:09,191 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:00:09,195 INFO ]: Computing forward predicates... [2018-06-25 13:00:11,777 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:00:11,804 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:11,857 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:00:11,906 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:11,920 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:00:11,947 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:00:11,995 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 13:00:12,691 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:00:12,729 WARN ]: expecting exponential blowup for input size 10 [2018-06-25 13:00:13,325 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:13,332 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:13,337 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:13,372 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:13,378 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:13,384 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:13,393 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:13,461 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:00:13,519 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:13,565 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:13,571 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:13,577 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:00:13,597 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:00:13,622 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:00:13,628 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:00:13,649 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:00:13,671 WARN ]: expecting exponential blowup for input size 8 Received shutdown request... [2018-06-25 13:01:13,500 INFO ]: Timeout while computing interpolants [2018-06-25 13:01:13,701 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:01:13,701 WARN ]: Verification canceled [2018-06-25 13:01:13,704 WARN ]: Timeout [2018-06-25 13:01:13,704 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 01:01:13 BoogieIcfgContainer [2018-06-25 13:01:13,704 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 13:01:13,705 INFO ]: Toolchain (without parser) took 71914.92 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 258.7 MB in the beginning and 615.5 MB in the end (delta: -356.8 MB). Peak memory consumption was 858.5 MB. Max. memory is 3.6 GB. [2018-06-25 13:01:13,707 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 309.3 MB. Free memory is still 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 13:01:13,708 INFO ]: ChcToBoogie took 71.13 ms. Allocated memory is still 309.3 MB. Free memory was 258.7 MB in the beginning and 255.7 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:01:13,708 INFO ]: Boogie Preprocessor took 62.47 ms. Allocated memory is still 309.3 MB. Free memory was 255.7 MB in the beginning and 254.7 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-25 13:01:13,709 INFO ]: RCFGBuilder took 320.49 ms. Allocated memory is still 309.3 MB. Free memory was 254.7 MB in the beginning and 241.7 MB in the end (delta: 13.1 MB). Peak memory consumption was 13.1 MB. Max. memory is 3.6 GB. [2018-06-25 13:01:13,709 INFO ]: TraceAbstraction took 71445.14 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 241.7 MB in the beginning and 615.5 MB in the end (delta: -373.8 MB). Peak memory consumption was 841.5 MB. Max. memory is 3.6 GB. [2018-06-25 13:01:13,713 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 309.3 MB. Free memory is still 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 71.13 ms. Allocated memory is still 309.3 MB. Free memory was 258.7 MB in the beginning and 255.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 62.47 ms. Allocated memory is still 309.3 MB. Free memory was 255.7 MB in the beginning and 254.7 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 320.49 ms. Allocated memory is still 309.3 MB. Free memory was 254.7 MB in the beginning and 241.7 MB in the end (delta: 13.1 MB). Peak memory consumption was 13.1 MB. Max. memory is 3.6 GB. * TraceAbstraction took 71445.14 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 241.7 MB in the beginning and 615.5 MB in the end (delta: -373.8 MB). Peak memory consumption was 841.5 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 12 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 8 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 71.3s OverallTime, 4 OverallIterations, 4 TraceHistogramMax, 0.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 21 SDtfs, 3 SDslu, 42 SDs, 0 SdLazy, 18 SolverSat, 8 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 34 GetRequests, 16 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=12occurred in iteration=3, 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, 3 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 5.2s InterpolantComputationTime, 43 NumberOfCodeBlocks, 43 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 38 ConstructedInterpolants, 0 QuantifiedInterpolants, 1060 SizeOfPredicates, 12 NumberOfNonLiveVariables, 358 ConjunctsInSsa, 48 ConjunctsInUnsatCore, 5 InterpolantComputations, 1 PerfectInterpolantSequences, 0/14 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/ex2.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_13-01-13-733.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/ex2.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_13-01-13-733.csv Completed graceful shutdown