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_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/seq3.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 05:52:29,924 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 05:52:29,929 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 05:52:29,945 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 05:52:29,945 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 05:52:29,946 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 05:52:29,949 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 05:52:29,951 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 05:52:29,953 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 05:52:29,955 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 05:52:29,956 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 05:52:29,956 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 05:52:29,957 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 05:52:29,962 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 05:52:29,963 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 05:52:29,964 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 05:52:29,974 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 05:52:29,976 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 05:52:29,977 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 05:52:29,979 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 05:52:29,983 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 05:52:29,985 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 05:52:29,986 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 05:52:29,989 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 05:52:29,990 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 05:52:29,991 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 05:52:29,992 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 05:52:29,993 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 05:52:29,995 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 05:52:29,995 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 05:52:29,996 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 05:52:29,996 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 05:52:29,997 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 05:52:29,997 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 05:52:30,003 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 05:52:30,003 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 05:52:30,026 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 05:52:30,026 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 05:52:30,027 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 05:52:30,027 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 05:52:30,028 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 05:52:30,029 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 05:52:30,029 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 05:52:30,029 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 05:52:30,029 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:52:30,029 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 05:52:30,030 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 05:52:30,030 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 05:52:30,030 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 05:52:30,030 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 05:52:30,030 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 05:52:30,030 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 05:52:30,030 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 05:52:30,033 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 05:52:30,033 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 05:52:30,097 INFO ]: Repository-Root is: /tmp [2018-06-22 05:52:30,111 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 05:52:30,115 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 05:52:30,117 INFO ]: Initializing SmtParser... [2018-06-22 05:52:30,118 INFO ]: SmtParser initialized [2018-06-22 05:52:30,122 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/seq3.c.smt2 [2018-06-22 05:52:30,124 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 05:52:30,219 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/seq3.c.smt2 unknown [2018-06-22 05:52:30,548 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/seq3.c.smt2 [2018-06-22 05:52:30,553 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 05:52:30,558 INFO ]: Walking toolchain with 4 elements. [2018-06-22 05:52:30,559 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 05:52:30,559 INFO ]: Initializing ChcToBoogie... [2018-06-22 05:52:30,559 INFO ]: ChcToBoogie initialized [2018-06-22 05:52:30,563 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:52:30" (1/1) ... [2018-06-22 05:52:30,622 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:52:30 Unit [2018-06-22 05:52:30,623 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 05:52:30,623 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 05:52:30,623 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 05:52:30,623 INFO ]: Boogie Preprocessor initialized [2018-06-22 05:52:30,644 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:52:30" (1/1) ... [2018-06-22 05:52:30,644 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:52:30" (1/1) ... [2018-06-22 05:52:30,652 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:52:30" (1/1) ... [2018-06-22 05:52:30,652 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:52:30" (1/1) ... [2018-06-22 05:52:30,668 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:52:30" (1/1) ... [2018-06-22 05:52:30,670 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:52:30" (1/1) ... [2018-06-22 05:52:30,671 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:52:30" (1/1) ... [2018-06-22 05:52:30,674 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 05:52:30,674 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 05:52:30,674 INFO ]: Initializing RCFGBuilder... [2018-06-22 05:52:30,674 INFO ]: RCFGBuilder initialized [2018-06-22 05:52:30,675 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:52:30" (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 05:52:30,709 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 05:52:30,709 INFO ]: Found specification of procedure gotoProc [2018-06-22 05:52:30,709 INFO ]: Found implementation of procedure gotoProc [2018-06-22 05:52:30,709 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 05:52:30,709 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 05:52:30,709 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 05:52:31,045 INFO ]: Using library mode [2018-06-22 05:52:31,046 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:52:31 BoogieIcfgContainer [2018-06-22 05:52:31,046 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 05:52:31,048 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 05:52:31,048 INFO ]: Initializing TraceAbstraction... [2018-06-22 05:52:31,053 INFO ]: TraceAbstraction initialized [2018-06-22 05:52:31,053 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:52:30" (1/3) ... [2018-06-22 05:52:31,054 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@39eec35 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 05:52:31, skipping insertion in model container [2018-06-22 05:52:31,054 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:52:30" (2/3) ... [2018-06-22 05:52:31,054 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@39eec35 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 05:52:31, skipping insertion in model container [2018-06-22 05:52:31,054 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:52:31" (3/3) ... [2018-06-22 05:52:31,056 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 05:52:31,066 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 05:52:31,077 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 05:52:31,126 INFO ]: Using default assertion order modulation [2018-06-22 05:52:31,127 INFO ]: Interprodecural is true [2018-06-22 05:52:31,127 INFO ]: Hoare is false [2018-06-22 05:52:31,127 INFO ]: Compute interpolants for FPandBP [2018-06-22 05:52:31,127 INFO ]: Backedges is TWOTRACK [2018-06-22 05:52:31,127 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 05:52:31,127 INFO ]: Difference is false [2018-06-22 05:52:31,127 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 05:52:31,127 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 05:52:31,145 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 05:52:31,157 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 05:52:31,158 INFO ]: Found error trace [2018-06-22 05:52:31,159 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:52:31,159 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:52:31,164 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-22 05:52:31,167 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:52:31,167 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:52:31,201 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:52:31,201 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:52:31,201 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:52:31,250 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:52:31,344 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:52:31,347 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 05:52:31,347 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 05:52:31,349 INFO ]: Interpolant automaton has 3 states [2018-06-22 05:52:31,366 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 05:52:31,366 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:52:31,369 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 05:52:31,425 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:52:31,425 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 05:52:31,430 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 05:52:31,431 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 05:52:31,431 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:52:31,441 INFO ]: With dead ends: 9 [2018-06-22 05:52:31,441 INFO ]: Without dead ends: 9 [2018-06-22 05:52:31,442 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-22 05:52:31,456 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 05:52:31,485 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 05:52:31,486 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 05:52:31,486 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 05:52:31,488 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 05:52:31,488 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:52:31,488 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 05:52:31,488 INFO ]: Interpolant automaton has 3 states. [2018-06-22 05:52:31,488 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 05:52:31,488 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 05:52:31,489 INFO ]: Found error trace [2018-06-22 05:52:31,489 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:52:31,489 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:52:31,489 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-22 05:52:31,489 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:52:31,489 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:52:31,490 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:52:31,490 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:52:31,490 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:52:31,557 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:52:31,693 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:52:31,693 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:52:31,693 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 05:52:31,700 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:52:31,763 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:52:31,774 INFO ]: Computing forward predicates... [2018-06-22 05:52:32,002 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:52:32,028 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:52:32,028 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 05:52:32,029 INFO ]: Interpolant automaton has 5 states [2018-06-22 05:52:32,029 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 05:52:32,029 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-22 05:52:32,029 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 05:52:32,182 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:52:32,182 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 05:52:32,183 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 05:52:32,183 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 05:52:32,183 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:52:32,183 INFO ]: With dead ends: 11 [2018-06-22 05:52:32,183 INFO ]: Without dead ends: 11 [2018-06-22 05:52:32,184 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:52:32,184 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 05:52:32,185 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 05:52:32,185 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 05:52:32,187 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 05:52:32,188 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-22 05:52:32,188 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:52:32,188 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 05:52:32,188 INFO ]: Interpolant automaton has 5 states. [2018-06-22 05:52:32,188 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 05:52:32,188 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 05:52:32,188 INFO ]: Found error trace [2018-06-22 05:52:32,188 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:52:32,188 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:52:32,189 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 2 times [2018-06-22 05:52:32,189 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:52:32,189 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:52:32,190 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:52:32,190 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:52:32,190 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:52:32,290 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:52:32,660 WARN ]: Spent 216.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 05:52:32,766 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:52:32,766 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:52:32,766 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 05:52:32,774 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 05:52:32,869 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 05:52:32,869 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:52:32,873 INFO ]: Computing forward predicates... [2018-06-22 05:52:36,341 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:52:36,372 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:52:36,372 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-22 05:52:36,372 INFO ]: Interpolant automaton has 7 states [2018-06-22 05:52:36,372 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 05:52:36,373 INFO ]: CoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2018-06-22 05:52:36,373 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-22 05:52:37,274 WARN ]: Spent 761.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 11 [2018-06-22 05:52:37,776 WARN ]: Spent 415.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 05:52:38,710 WARN ]: Spent 758.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 10 [2018-06-22 05:52:38,711 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:52:38,711 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-22 05:52:38,711 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 05:52:38,711 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-22 05:52:38,712 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:52:38,712 INFO ]: With dead ends: 13 [2018-06-22 05:52:38,712 INFO ]: Without dead ends: 13 [2018-06-22 05:52:38,712 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=39, Invalid=51, Unknown=0, NotChecked=0, Total=90 [2018-06-22 05:52:38,712 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 05:52:38,714 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 05:52:38,715 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 05:52:38,716 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-22 05:52:38,716 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 10 [2018-06-22 05:52:38,716 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:52:38,716 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-22 05:52:38,716 INFO ]: Interpolant automaton has 7 states. [2018-06-22 05:52:38,716 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-22 05:52:38,716 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 05:52:38,716 INFO ]: Found error trace [2018-06-22 05:52:38,716 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:52:38,717 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:52:38,717 INFO ]: Analyzing trace with hash -1502133097, now seen corresponding path program 3 times [2018-06-22 05:52:38,717 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:52:38,717 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:52:38,718 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:52:38,718 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:52:38,718 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:52:38,858 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:52:39,289 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:52:39,290 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:52:39,290 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:52:39,299 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 05:52:39,380 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 05:52:39,380 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:52:39,385 INFO ]: Computing forward predicates... [2018-06-22 05:52:47,665 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:53:25,087 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:53:25,110 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:53:25,114 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2018-06-22 05:53:25,114 INFO ]: Interpolant automaton has 10 states [2018-06-22 05:53:25,114 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 05:53:25,114 INFO ]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-06-22 05:53:25,114 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 10 states. [2018-06-22 05:53:25,345 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:53:25,345 INFO ]: Finished difference Result 15 states and 15 transitions. [2018-06-22 05:53:25,345 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 05:53:25,345 INFO ]: Start accepts. Automaton has 10 states. Word has length 12 [2018-06-22 05:53:25,345 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:53:25,345 INFO ]: With dead ends: 15 [2018-06-22 05:53:25,345 INFO ]: Without dead ends: 15 [2018-06-22 05:53:25,346 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 36 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=81, Invalid=159, Unknown=0, NotChecked=0, Total=240 [2018-06-22 05:53:25,346 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 05:53:25,349 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 05:53:25,349 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 05:53:25,350 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-06-22 05:53:25,350 INFO ]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 12 [2018-06-22 05:53:25,350 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:53:25,350 INFO ]: Abstraction has 15 states and 15 transitions. [2018-06-22 05:53:25,350 INFO ]: Interpolant automaton has 10 states. [2018-06-22 05:53:25,350 INFO ]: Start isEmpty. Operand 15 states and 15 transitions. [2018-06-22 05:53:25,350 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 05:53:25,350 INFO ]: Found error trace [2018-06-22 05:53:25,351 INFO ]: trace histogram [7, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:53:25,351 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:53:25,351 INFO ]: Analyzing trace with hash -414382217, now seen corresponding path program 4 times [2018-06-22 05:53:25,351 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:53:25,351 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:53:25,352 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:53:25,352 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:53:25,352 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:53:25,455 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:53:25,743 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:53:25,743 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:53:25,743 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 05:53:25,751 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 05:53:25,848 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 05:53:25,848 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:53:25,855 INFO ]: Computing forward predicates... [2018-06-22 05:53:26,520 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:53:26,600 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:53:30,109 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 19 Received shutdown request... [2018-06-22 05:53:33,863 INFO ]: Timeout while computing interpolants [2018-06-22 05:53:34,064 WARN ]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:53:34,064 WARN ]: Verification canceled [2018-06-22 05:53:34,067 WARN ]: Timeout [2018-06-22 05:53:34,068 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 05:53:34 BoogieIcfgContainer [2018-06-22 05:53:34,068 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 05:53:34,068 INFO ]: Toolchain (without parser) took 63514.91 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 259.7 MB in the beginning and 185.0 MB in the end (delta: 74.8 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 05:53:34,069 INFO ]: SmtParser took 0.13 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-22 05:53:34,070 INFO ]: ChcToBoogie took 63.99 ms. Allocated memory is still 309.3 MB. Free memory was 258.7 MB in the beginning and 256.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 05:53:34,070 INFO ]: Boogie Preprocessor took 50.39 ms. Allocated memory is still 309.3 MB. Free memory was 256.8 MB in the beginning and 255.8 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-22 05:53:34,071 INFO ]: RCFGBuilder took 372.27 ms. Allocated memory is still 309.3 MB. Free memory was 255.8 MB in the beginning and 243.7 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:53:34,071 INFO ]: TraceAbstraction took 63019.93 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 243.7 MB in the beginning and 185.0 MB in the end (delta: 58.8 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 05:53:34,076 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.13 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 63.99 ms. Allocated memory is still 309.3 MB. Free memory was 258.7 MB in the beginning and 256.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 50.39 ms. Allocated memory is still 309.3 MB. Free memory was 256.8 MB in the beginning and 255.8 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 372.27 ms. Allocated memory is still 309.3 MB. Free memory was 255.8 MB in the beginning and 243.7 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 63019.93 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 243.7 MB in the beginning and 185.0 MB in the end (delta: 58.8 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 15 with TraceHistMax 7, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 24 quantified variables from 13 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 62.9s OverallTime, 5 OverallIterations, 7 TraceHistogramMax, 2.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 28 SDtfs, 7 SDslu, 73 SDs, 0 SdLazy, 29 SolverSat, 20 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 58 GetRequests, 23 SyntacticMatches, 8 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 58 ImplicationChecksByTransitivity, 3.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=15occurred 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.5s SatisfiabilityAnalysisTime, 50.5s InterpolantComputationTime, 67 NumberOfCodeBlocks, 67 NumberOfCodeBlocksAsserted, 11 NumberOfCheckSat, 60 ConstructedInterpolants, 0 QuantifiedInterpolants, 2596 SizeOfPredicates, 15 NumberOfNonLiveVariables, 618 ConjunctsInSsa, 95 ConjunctsInUnsatCore, 7 InterpolantComputations, 1 PerfectInterpolantSequences, 0/44 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_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_05-53-34-089.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/seq3.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_05-53-34-089.csv Completed graceful shutdown