java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/seq3.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:31:38,242 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:31:38,245 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:31:38,257 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:31:38,257 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:31:38,259 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:31:38,260 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:31:38,264 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:31:38,266 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:31:38,268 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:31:38,268 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:31:38,269 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:31:38,269 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:31:38,271 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:31:38,274 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:31:38,275 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:31:38,289 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:31:38,291 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:31:38,292 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:31:38,293 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:31:38,294 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:31:38,296 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:31:38,296 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:31:38,296 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:31:38,297 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:31:38,298 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:31:38,299 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:31:38,299 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:31:38,300 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:31:38,301 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:31:38,304 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:31:38,305 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:31:38,305 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:31:38,306 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:31:38,306 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:31:38,307 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 15:31:38,328 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:31:38,328 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:31:38,330 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:31:38,330 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:31:38,331 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:31:38,332 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:31:38,332 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:31:38,332 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:31:38,332 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:31:38,332 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:31:38,333 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:31:38,333 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:31:38,333 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:31:38,333 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:31:38,333 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:31:38,334 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:31:38,336 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:31:38,337 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:31:38,337 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:31:38,338 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:31:38,339 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:31:38,388 INFO ]: Repository-Root is: /tmp [2018-06-22 15:31:38,404 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:31:38,408 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:31:38,410 INFO ]: Initializing SmtParser... [2018-06-22 15:31:38,410 INFO ]: SmtParser initialized [2018-06-22 15:31:38,411 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/seq3.c.smt2 [2018-06-22 15:31:38,412 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 15:31:38,503 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/seq3.c.smt2 unknown [2018-06-22 15:31:38,830 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/seq3.c.smt2 [2018-06-22 15:31:38,834 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:31:38,842 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:31:38,842 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:31:38,842 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:31:38,843 INFO ]: ChcToBoogie initialized [2018-06-22 15:31:38,846 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:31:38" (1/1) ... [2018-06-22 15:31:38,891 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:31:38 Unit [2018-06-22 15:31:38,891 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:31:38,892 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:31:38,892 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:31:38,892 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:31:38,914 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:31:38" (1/1) ... [2018-06-22 15:31:38,914 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:31:38" (1/1) ... [2018-06-22 15:31:38,924 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:31:38" (1/1) ... [2018-06-22 15:31:38,925 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:31:38" (1/1) ... [2018-06-22 15:31:38,936 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:31:38" (1/1) ... [2018-06-22 15:31:38,938 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:31:38" (1/1) ... [2018-06-22 15:31:38,944 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:31:38" (1/1) ... [2018-06-22 15:31:38,946 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:31:38,946 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:31:38,947 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:31:38,947 INFO ]: RCFGBuilder initialized [2018-06-22 15:31:38,947 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:31:38" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 15:31:38,959 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:31:38,959 INFO ]: Found specification of procedure False [2018-06-22 15:31:38,959 INFO ]: Found implementation of procedure False [2018-06-22 15:31:38,959 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:31:38,959 INFO ]: Found specification of procedure state [2018-06-22 15:31:38,959 INFO ]: Found implementation of procedure state [2018-06-22 15:31:38,959 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:31:38,959 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:31:38,959 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:31:39,209 INFO ]: Using library mode [2018-06-22 15:31:39,210 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:31:39 BoogieIcfgContainer [2018-06-22 15:31:39,210 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:31:39,211 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:31:39,211 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:31:39,214 INFO ]: TraceAbstraction initialized [2018-06-22 15:31:39,214 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:31:38" (1/3) ... [2018-06-22 15:31:39,215 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@29f86fb4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:31:39, skipping insertion in model container [2018-06-22 15:31:39,215 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:31:38" (2/3) ... [2018-06-22 15:31:39,215 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@29f86fb4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:31:39, skipping insertion in model container [2018-06-22 15:31:39,215 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:31:39" (3/3) ... [2018-06-22 15:31:39,217 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:31:39,226 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:31:39,237 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:31:39,280 INFO ]: Using default assertion order modulation [2018-06-22 15:31:39,280 INFO ]: Interprodecural is true [2018-06-22 15:31:39,280 INFO ]: Hoare is false [2018-06-22 15:31:39,281 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:31:39,281 INFO ]: Backedges is TWOTRACK [2018-06-22 15:31:39,281 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:31:39,281 INFO ]: Difference is false [2018-06-22 15:31:39,281 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:31:39,281 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:31:39,293 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:31:39,302 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:31:39,302 INFO ]: Found error trace [2018-06-22 15:31:39,303 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:31:39,303 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:31:39,308 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 15:31:39,309 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:31:39,309 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:31:39,341 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:31:39,341 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:31:39,341 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:31:39,366 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:31:39,422 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:31:39,425 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:31:39,426 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:31:39,427 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:31:39,438 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:31:39,439 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:31:39,440 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:31:39,535 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:31:39,535 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:31:39,536 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:31:39,537 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:31:39,537 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:31:39,549 INFO ]: With dead ends: 13 [2018-06-22 15:31:39,549 INFO ]: Without dead ends: 13 [2018-06-22 15:31:39,551 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:31:39,563 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:31:39,581 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:31:39,582 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:31:39,583 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:31:39,584 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:31:39,584 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:31:39,584 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:31:39,584 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:31:39,584 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:31:39,585 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:31:39,585 INFO ]: Found error trace [2018-06-22 15:31:39,585 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:31:39,585 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:31:39,586 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 15:31:39,586 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:31:39,586 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:31:39,587 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:31:39,587 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:31:39,587 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:31:39,648 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:31:39,903 WARN ]: Spent 176.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 15:31:39,990 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:31:39,990 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:31:39,990 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:31:39,998 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:31:40,052 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:31:40,060 INFO ]: Computing forward predicates... [2018-06-22 15:31:40,655 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:31:40,677 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:31:40,677 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 15:31:40,678 INFO ]: Interpolant automaton has 9 states [2018-06-22 15:31:40,678 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 15:31:40,678 INFO ]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-22 15:31:40,678 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 15:31:41,147 WARN ]: Spent 295.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 15:31:41,265 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:31:41,265 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:31:41,265 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:31:41,265 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 15:31:41,266 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:31:41,266 INFO ]: With dead ends: 15 [2018-06-22 15:31:41,266 INFO ]: Without dead ends: 15 [2018-06-22 15:31:41,268 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:31:41,268 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:31:41,270 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:31:41,270 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:31:41,271 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:31:41,271 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:31:41,271 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:31:41,271 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:31:41,271 INFO ]: Interpolant automaton has 9 states. [2018-06-22 15:31:41,271 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:31:41,272 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:31:41,272 INFO ]: Found error trace [2018-06-22 15:31:41,272 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:31:41,272 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:31:41,272 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 15:31:41,272 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:31:41,272 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:31:41,273 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:31:41,273 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:31:41,273 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:31:41,325 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:31:41,597 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:31:41,597 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:31:41,597 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:31:41,612 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:31:41,671 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:31:41,671 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:31:41,675 INFO ]: Computing forward predicates... [2018-06-22 15:31:42,398 WARN ]: Spent 198.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-22 15:31:42,420 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:31:42,463 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:31:42,463 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:31:42,463 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:31:42,463 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:31:42,464 INFO ]: CoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:31:42,464 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:31:42,804 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:31:42,804 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:31:42,804 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:31:42,804 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:31:42,805 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:31:42,805 INFO ]: With dead ends: 17 [2018-06-22 15:31:42,805 INFO ]: Without dead ends: 17 [2018-06-22 15:31:42,806 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=53, Invalid=157, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:31:42,806 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:31:42,809 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:31:42,810 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:31:42,810 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:31:42,810 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:31:42,810 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:31:42,810 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:31:42,810 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:31:42,810 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:31:42,811 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:31:42,811 INFO ]: Found error trace [2018-06-22 15:31:42,811 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:31:42,811 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:31:42,811 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 15:31:42,811 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:31:42,811 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:31:42,812 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:31:42,812 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:31:42,812 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:31:42,858 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:31:43,153 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:31:43,153 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:31:43,153 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 15:31:43,169 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:31:43,229 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:31:43,229 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:31:43,234 INFO ]: Computing forward predicates... [2018-06-22 15:31:46,284 WARN ]: Spent 2.53 s on a formula simplification. DAG size of input: 330 DAG size of output: 60 [2018-06-22 15:31:49,089 WARN ]: Spent 349.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 15:31:49,107 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:31:49,137 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:31:49,137 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 13 [2018-06-22 15:31:49,138 INFO ]: Interpolant automaton has 13 states [2018-06-22 15:31:49,138 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 15:31:49,138 INFO ]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2018-06-22 15:31:49,138 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 13 states. [2018-06-22 15:31:50,028 WARN ]: Spent 601.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 59 [2018-06-22 15:31:50,392 WARN ]: Spent 342.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 54 [2018-06-22 15:31:50,719 WARN ]: Spent 304.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 59 [2018-06-22 15:31:51,048 WARN ]: Spent 313.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 55 [2018-06-22 15:31:51,072 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:31:51,072 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:31:51,073 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:31:51,073 INFO ]: Start accepts. Automaton has 13 states. Word has length 21 [2018-06-22 15:31:51,073 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:31:51,073 INFO ]: With dead ends: 19 [2018-06-22 15:31:51,073 INFO ]: Without dead ends: 19 [2018-06-22 15:31:51,074 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 18 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2018-06-22 15:31:51,074 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:31:51,076 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:31:51,076 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:31:51,076 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:31:51,076 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:31:51,076 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:31:51,076 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:31:51,076 INFO ]: Interpolant automaton has 13 states. [2018-06-22 15:31:51,076 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:31:51,077 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:31:51,077 INFO ]: Found error trace [2018-06-22 15:31:51,077 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:31:51,077 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:31:51,077 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 15:31:51,077 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:31:51,077 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:31:51,078 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:31:51,078 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:31:51,078 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:31:51,135 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:31:51,807 WARN ]: Spent 467.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-22 15:31:52,256 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:31:52,256 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:31:52,256 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:31:52,262 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:31:52,310 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:31:52,310 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:31:52,314 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 15:32:49,243 WARN ]: Removed 2 from assertion stack [2018-06-22 15:32:49,244 INFO ]: Timeout while computing interpolants [2018-06-22 15:32:49,444 WARN ]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:32:49,444 WARN ]: Verification canceled [2018-06-22 15:32:49,447 WARN ]: Timeout [2018-06-22 15:32:49,448 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:32:49 BoogieIcfgContainer [2018-06-22 15:32:49,448 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:32:49,448 INFO ]: Toolchain (without parser) took 70613.84 ms. Allocated memory was 309.3 MB in the beginning and 965.2 MB in the end (delta: 655.9 MB). Free memory was 259.8 MB in the beginning and 397.4 MB in the end (delta: -137.7 MB). Peak memory consumption was 791.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:32:49,449 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 309.3 MB. Free memory is still 273.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:32:49,449 INFO ]: ChcToBoogie took 48.86 ms. Allocated memory is still 309.3 MB. Free memory is still 257.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:32:49,450 INFO ]: Boogie Preprocessor took 54.45 ms. Allocated memory is still 309.3 MB. Free memory was 257.8 MB in the beginning and 255.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:32:49,450 INFO ]: RCFGBuilder took 263.48 ms. Allocated memory is still 309.3 MB. Free memory was 255.8 MB in the beginning and 243.8 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:32:49,451 INFO ]: TraceAbstraction took 70236.52 ms. Allocated memory was 309.3 MB in the beginning and 965.2 MB in the end (delta: 655.9 MB). Free memory was 243.8 MB in the beginning and 397.4 MB in the end (delta: -153.6 MB). Peak memory consumption was 775.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:32:49,453 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 309.3 MB. Free memory is still 273.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 48.86 ms. Allocated memory is still 309.3 MB. Free memory is still 257.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * Boogie Preprocessor took 54.45 ms. Allocated memory is still 309.3 MB. Free memory was 257.8 MB in the beginning and 255.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 263.48 ms. Allocated memory is still 309.3 MB. Free memory was 255.8 MB in the beginning and 243.8 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 70236.52 ms. Allocated memory was 309.3 MB in the beginning and 965.2 MB in the end (delta: 655.9 MB). Free memory was 243.8 MB in the beginning and 397.4 MB in the end (delta: -153.6 MB). Peak memory consumption was 775.0 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 26 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 3552. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 70.1s OverallTime, 5 OverallIterations, 5 TraceHistogramMax, 2.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 46 SDtfs, 40 SDslu, 140 SDs, 0 SdLazy, 111 SolverSat, 55 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 87 GetRequests, 46 SyntacticMatches, 1 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 7.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=19occurred in iteration=4, 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, 4 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 8.2s InterpolantComputationTime, 111 NumberOfCodeBlocks, 111 NumberOfCodeBlocksAsserted, 11 NumberOfCheckSat, 104 ConstructedInterpolants, 0 QuantifiedInterpolants, 636008 SizeOfPredicates, 123 NumberOfNonLiveVariables, 441 ConjunctsInSsa, 75 ConjunctsInUnsatCore, 7 InterpolantComputations, 1 PerfectInterpolantSequences, 20/68 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/seq3.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-32-49-463.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/seq3.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-32-49-463.csv Completed graceful shutdown