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/lustre/metros_1.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 16:33:50,199 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 16:33:50,201 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 16:33:50,213 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 16:33:50,214 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 16:33:50,214 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 16:33:50,216 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 16:33:50,219 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 16:33:50,221 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 16:33:50,221 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 16:33:50,223 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 16:33:50,223 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 16:33:50,224 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 16:33:50,225 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 16:33:50,226 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 16:33:50,226 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 16:33:50,230 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 16:33:50,240 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 16:33:50,242 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 16:33:50,243 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 16:33:50,244 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 16:33:50,246 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 16:33:50,251 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 16:33:50,251 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 16:33:50,252 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 16:33:50,253 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 16:33:50,254 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 16:33:50,254 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 16:33:50,255 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 16:33:50,255 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 16:33:50,260 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 16:33:50,261 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 16:33:50,261 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 16:33:50,262 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 16:33:50,263 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 16:33:50,264 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 16:33:50,291 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 16:33:50,294 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 16:33:50,295 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 16:33:50,295 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 16:33:50,296 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 16:33:50,296 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 16:33:50,296 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 16:33:50,296 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 16:33:50,297 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 16:33:50,297 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 16:33:50,297 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 16:33:50,297 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 16:33:50,297 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 16:33:50,297 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 16:33:50,298 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 16:33:50,301 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 16:33:50,301 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 16:33:50,301 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 16:33:50,302 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 16:33:50,302 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 16:33:50,302 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 16:33:50,303 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 16:33:50,303 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 16:33:50,355 INFO ]: Repository-Root is: /tmp [2018-06-25 16:33:50,373 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 16:33:50,377 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 16:33:50,379 INFO ]: Initializing SmtParser... [2018-06-25 16:33:50,379 INFO ]: SmtParser initialized [2018-06-25 16:33:50,379 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_1.smt2 [2018-06-25 16:33:50,381 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 16:33:50,471 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_1.smt2 unknown [2018-06-25 16:33:50,974 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_1.smt2 [2018-06-25 16:33:50,979 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 16:33:50,985 INFO ]: Walking toolchain with 4 elements. [2018-06-25 16:33:50,986 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 16:33:50,986 INFO ]: Initializing ChcToBoogie... [2018-06-25 16:33:50,986 INFO ]: ChcToBoogie initialized [2018-06-25 16:33:50,989 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 04:33:50" (1/1) ... [2018-06-25 16:33:51,084 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 04:33:51 Unit [2018-06-25 16:33:51,084 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 16:33:51,085 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 16:33:51,085 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 16:33:51,085 INFO ]: Boogie Preprocessor initialized [2018-06-25 16:33:51,111 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 04:33:51" (1/1) ... [2018-06-25 16:33:51,112 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 04:33:51" (1/1) ... [2018-06-25 16:33:51,134 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 04:33:51" (1/1) ... [2018-06-25 16:33:51,134 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 04:33:51" (1/1) ... [2018-06-25 16:33:51,140 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 04:33:51" (1/1) ... [2018-06-25 16:33:51,151 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 04:33:51" (1/1) ... [2018-06-25 16:33:51,153 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 04:33:51" (1/1) ... [2018-06-25 16:33:51,162 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 16:33:51,163 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 16:33:51,163 INFO ]: Initializing RCFGBuilder... [2018-06-25 16:33:51,163 INFO ]: RCFGBuilder initialized [2018-06-25 16:33:51,164 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 04:33:51" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 16:33:51,191 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 16:33:51,191 INFO ]: Found specification of procedure gotoProc [2018-06-25 16:33:51,191 INFO ]: Found implementation of procedure gotoProc [2018-06-25 16:33:51,191 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 16:33:51,191 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 16:33:51,191 INFO ]: Found implementation of procedure Ultimate.START [2018-06-25 16:33:51,614 INFO ]: Using library mode [2018-06-25 16:33:51,615 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 04:33:51 BoogieIcfgContainer [2018-06-25 16:33:51,615 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 16:33:51,617 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 16:33:51,617 INFO ]: Initializing TraceAbstraction... [2018-06-25 16:33:51,620 INFO ]: TraceAbstraction initialized [2018-06-25 16:33:51,621 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 04:33:50" (1/3) ... [2018-06-25 16:33:51,622 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@19255082 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 04:33:51, skipping insertion in model container [2018-06-25 16:33:51,622 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 04:33:51" (2/3) ... [2018-06-25 16:33:51,622 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@19255082 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 04:33:51, skipping insertion in model container [2018-06-25 16:33:51,622 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 04:33:51" (3/3) ... [2018-06-25 16:33:51,624 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 16:33:51,634 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 16:33:51,645 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 16:33:51,698 INFO ]: Using default assertion order modulation [2018-06-25 16:33:51,699 INFO ]: Interprodecural is true [2018-06-25 16:33:51,699 INFO ]: Hoare is false [2018-06-25 16:33:51,699 INFO ]: Compute interpolants for FPandBP [2018-06-25 16:33:51,699 INFO ]: Backedges is TWOTRACK [2018-06-25 16:33:51,699 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 16:33:51,699 INFO ]: Difference is false [2018-06-25 16:33:51,699 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 16:33:51,699 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 16:33:51,717 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 16:33:51,732 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 16:33:51,732 INFO ]: Found error trace [2018-06-25 16:33:51,733 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 16:33:51,733 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 16:33:51,739 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 16:33:51,742 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 16:33:51,742 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 16:33:51,793 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 16:33:51,793 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 16:33:51,793 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 16:33:51,903 INFO ]: Conjunction of SSA is unsat [2018-06-25 16:33:52,015 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 16:33:52,017 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 16:33:52,017 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 16:33:52,020 INFO ]: Interpolant automaton has 3 states [2018-06-25 16:33:52,036 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 16:33:52,036 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 16:33:52,040 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 16:33:52,147 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 16:33:52,147 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 16:33:52,149 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 16:33:52,151 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 16:33:52,151 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 16:33:52,164 INFO ]: With dead ends: 9 [2018-06-25 16:33:52,164 INFO ]: Without dead ends: 9 [2018-06-25 16:33:52,166 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 16:33:52,183 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 16:33:52,210 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 16:33:52,211 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 16:33:52,211 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 16:33:52,213 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 16:33:52,213 INFO ]: Finished accepts. word is rejected. [2018-06-25 16:33:52,213 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 16:33:52,214 INFO ]: Interpolant automaton has 3 states. [2018-06-25 16:33:52,214 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 16:33:52,214 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 16:33:52,214 INFO ]: Found error trace [2018-06-25 16:33:52,214 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 16:33:52,214 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 16:33:52,214 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 16:33:52,214 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 16:33:52,214 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 16:33:52,215 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 16:33:52,215 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 16:33:52,215 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 16:33:52,330 INFO ]: Conjunction of SSA is unsat [2018-06-25 16:33:52,497 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 16:33:52,497 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 16:33:52,497 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 16:33:52,504 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 16:33:52,680 INFO ]: Conjunction of SSA is unsat [2018-06-25 16:33:52,690 INFO ]: Computing forward predicates... [2018-06-25 16:33:52,846 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 16:33:52,883 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 16:33:52,883 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 16:33:52,884 INFO ]: Interpolant automaton has 5 states [2018-06-25 16:33:52,884 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 16:33:52,884 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-25 16:33:52,884 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 16:33:53,013 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 16:33:53,013 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 16:33:53,014 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-25 16:33:53,014 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 16:33:53,014 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 16:33:53,014 INFO ]: With dead ends: 10 [2018-06-25 16:33:53,014 INFO ]: Without dead ends: 10 [2018-06-25 16:33:53,015 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-25 16:33:53,015 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 16:33:53,016 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 16:33:53,016 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 16:33:53,017 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 16:33:53,017 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 16:33:53,017 INFO ]: Finished accepts. word is rejected. [2018-06-25 16:33:53,017 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 16:33:53,017 INFO ]: Interpolant automaton has 5 states. [2018-06-25 16:33:53,017 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 16:33:53,017 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 16:33:53,017 INFO ]: Found error trace [2018-06-25 16:33:53,017 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 16:33:53,017 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 16:33:53,017 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-25 16:33:53,017 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 16:33:53,017 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 16:33:53,020 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 16:33:53,020 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 16:33:53,020 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 16:33:53,120 INFO ]: Conjunction of SSA is unsat [2018-06-25 16:33:53,393 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 16:33:53,393 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 16:33:53,393 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 16:33:53,399 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 16:33:53,578 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 16:33:53,578 INFO ]: Conjunction of SSA is unsat [2018-06-25 16:33:53,584 INFO ]: Computing forward predicates... [2018-06-25 16:33:54,112 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 16:33:54,140 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 16:33:54,140 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-06-25 16:33:54,140 INFO ]: Interpolant automaton has 8 states [2018-06-25 16:33:54,140 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-25 16:33:54,140 INFO ]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2018-06-25 16:33:54,141 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 8 states. [2018-06-25 16:33:54,508 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 16:33:54,508 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 16:33:54,509 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 16:33:54,509 INFO ]: Start accepts. Automaton has 8 states. Word has length 9 [2018-06-25 16:33:54,509 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 16:33:54,509 INFO ]: With dead ends: 11 [2018-06-25 16:33:54,509 INFO ]: Without dead ends: 11 [2018-06-25 16:33:54,510 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2018-06-25 16:33:54,510 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 16:33:54,511 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 16:33:54,511 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 16:33:54,511 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 16:33:54,511 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 16:33:54,511 INFO ]: Finished accepts. word is rejected. [2018-06-25 16:33:54,511 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 16:33:54,511 INFO ]: Interpolant automaton has 8 states. [2018-06-25 16:33:54,511 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 16:33:54,512 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 16:33:54,512 INFO ]: Found error trace [2018-06-25 16:33:54,512 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 16:33:54,512 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 16:33:54,512 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 3 times [2018-06-25 16:33:54,512 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 16:33:54,512 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 16:33:54,514 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 16:33:54,514 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 16:33:54,514 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 16:33:54,675 INFO ]: Conjunction of SSA is unsat [2018-06-25 16:33:55,186 WARN ]: Spent 215.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 37 [2018-06-25 16:33:55,365 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 16:33:55,366 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 16:33:55,366 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 16:33:55,380 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 16:33:55,577 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 16:33:55,577 INFO ]: Conjunction of SSA is unsat [2018-06-25 16:33:55,587 INFO ]: Computing forward predicates... [2018-06-25 16:33:55,996 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 16:33:56,517 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 16:33:56,975 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 16:33:57,399 WARN ]: expecting exponential blowup for input size 11 [2018-06-25 16:33:57,608 WARN ]: Simplifying disjunction of 24192 conjuctions. This might take some time... Received shutdown request... [2018-06-25 16:35:10,673 INFO ]: Timeout while computing interpolants [2018-06-25 16:35:10,873 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 16:35:10,873 WARN ]: Verification canceled [2018-06-25 16:35:10,877 WARN ]: Timeout [2018-06-25 16:35:10,877 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 04:35:10 BoogieIcfgContainer [2018-06-25 16:35:10,877 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 16:35:10,878 INFO ]: Toolchain (without parser) took 79898.86 ms. Allocated memory was 303.6 MB in the beginning and 1.4 GB in the end (delta: 1.1 GB). Free memory was 244.1 MB in the beginning and 554.7 MB in the end (delta: -310.6 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 16:35:10,879 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 303.6 MB. Free memory is still 268.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 16:35:10,879 INFO ]: ChcToBoogie took 98.68 ms. Allocated memory is still 303.6 MB. Free memory was 244.1 MB in the beginning and 240.2 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-25 16:35:10,880 INFO ]: Boogie Preprocessor took 77.48 ms. Allocated memory is still 303.6 MB. Free memory is still 240.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 16:35:10,880 INFO ]: RCFGBuilder took 452.12 ms. Allocated memory is still 303.6 MB. Free memory was 240.2 MB in the beginning and 206.2 MB in the end (delta: 34.0 MB). Peak memory consumption was 34.0 MB. Max. memory is 3.6 GB. [2018-06-25 16:35:10,880 INFO ]: TraceAbstraction took 79260.34 ms. Allocated memory was 303.6 MB in the beginning and 1.4 GB in the end (delta: 1.1 GB). Free memory was 206.2 MB in the beginning and 554.7 MB in the end (delta: -348.5 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 16:35:10,883 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 303.6 MB. Free memory is still 268.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 98.68 ms. Allocated memory is still 303.6 MB. Free memory was 244.1 MB in the beginning and 240.2 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 77.48 ms. Allocated memory is still 303.6 MB. Free memory is still 240.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * RCFGBuilder took 452.12 ms. Allocated memory is still 303.6 MB. Free memory was 240.2 MB in the beginning and 206.2 MB in the end (delta: 34.0 MB). Peak memory consumption was 34.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 79260.34 ms. Allocated memory was 303.6 MB in the beginning and 1.4 GB in the end (delta: 1.1 GB). Free memory was 206.2 MB in the beginning and 554.7 MB in the end (delta: -348.5 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 11 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was XNF transformer was simplifying 24192 conjuctions. . - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 79.1s OverallTime, 4 OverallIterations, 3 TraceHistogramMax, 0.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 21 SDtfs, 0 SDslu, 40 SDs, 0 SdLazy, 34 SolverSat, 0 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 29 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=11occurred 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.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 1.2s InterpolantComputationTime, 41 NumberOfCodeBlocks, 41 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 36 ConstructedInterpolants, 0 QuantifiedInterpolants, 405 SizeOfPredicates, 8 NumberOfNonLiveVariables, 1252 ConjunctsInSsa, 24 ConjunctsInUnsatCore, 5 InterpolantComputations, 1 PerfectInterpolantSequences, 0/8 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/metros_1.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_16-35-10-901.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/metros_1.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_16-35-10-901.csv Completed graceful shutdown