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/lustre/metros_1_e1_846_e2_1394.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 08:56:15,167 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 08:56:15,169 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 08:56:15,180 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 08:56:15,180 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 08:56:15,181 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 08:56:15,182 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 08:56:15,184 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 08:56:15,186 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 08:56:15,187 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 08:56:15,187 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 08:56:15,188 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 08:56:15,189 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 08:56:15,193 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 08:56:15,194 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 08:56:15,194 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 08:56:15,196 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 08:56:15,208 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 08:56:15,209 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 08:56:15,210 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 08:56:15,211 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 08:56:15,214 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 08:56:15,214 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 08:56:15,214 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 08:56:15,215 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 08:56:15,223 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 08:56:15,224 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 08:56:15,225 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 08:56:15,226 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 08:56:15,226 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 08:56:15,227 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 08:56:15,227 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 08:56:15,227 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 08:56:15,228 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 08:56:15,229 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 08:56:15,229 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 08:56:15,253 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 08:56:15,253 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 08:56:15,254 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 08:56:15,257 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 08:56:15,258 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 08:56:15,258 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 08:56:15,258 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 08:56:15,259 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 08:56:15,259 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 08:56:15,259 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 08:56:15,259 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 08:56:15,259 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 08:56:15,260 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 08:56:15,260 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 08:56:15,260 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 08:56:15,260 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 08:56:15,260 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 08:56:15,263 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 08:56:15,263 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 08:56:15,316 INFO ]: Repository-Root is: /tmp [2018-06-22 08:56:15,329 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 08:56:15,333 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 08:56:15,334 INFO ]: Initializing SmtParser... [2018-06-22 08:56:15,334 INFO ]: SmtParser initialized [2018-06-22 08:56:15,335 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_1_e1_846_e2_1394.smt2 [2018-06-22 08:56:15,336 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 08:56:15,417 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_1_e1_846_e2_1394.smt2 unknown [2018-06-22 08:56:15,955 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_1_e1_846_e2_1394.smt2 [2018-06-22 08:56:15,967 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 08:56:15,972 INFO ]: Walking toolchain with 4 elements. [2018-06-22 08:56:15,973 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 08:56:15,973 INFO ]: Initializing ChcToBoogie... [2018-06-22 08:56:15,973 INFO ]: ChcToBoogie initialized [2018-06-22 08:56:15,979 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 08:56:15" (1/1) ... [2018-06-22 08:56:16,049 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:56:16 Unit [2018-06-22 08:56:16,049 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 08:56:16,049 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 08:56:16,049 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 08:56:16,049 INFO ]: Boogie Preprocessor initialized [2018-06-22 08:56:16,071 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:56:16" (1/1) ... [2018-06-22 08:56:16,071 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:56:16" (1/1) ... [2018-06-22 08:56:16,091 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:56:16" (1/1) ... [2018-06-22 08:56:16,091 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:56:16" (1/1) ... [2018-06-22 08:56:16,104 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:56:16" (1/1) ... [2018-06-22 08:56:16,105 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:56:16" (1/1) ... [2018-06-22 08:56:16,108 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:56:16" (1/1) ... [2018-06-22 08:56:16,119 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 08:56:16,120 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 08:56:16,120 INFO ]: Initializing RCFGBuilder... [2018-06-22 08:56:16,120 INFO ]: RCFGBuilder initialized [2018-06-22 08:56:16,121 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:56:16" (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 08:56:16,148 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 08:56:16,148 INFO ]: Found specification of procedure gotoProc [2018-06-22 08:56:16,148 INFO ]: Found implementation of procedure gotoProc [2018-06-22 08:56:16,148 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 08:56:16,148 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 08:56:16,148 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 08:56:16,612 INFO ]: Using library mode [2018-06-22 08:56:16,613 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 08:56:16 BoogieIcfgContainer [2018-06-22 08:56:16,613 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 08:56:16,615 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 08:56:16,615 INFO ]: Initializing TraceAbstraction... [2018-06-22 08:56:16,619 INFO ]: TraceAbstraction initialized [2018-06-22 08:56:16,619 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 08:56:15" (1/3) ... [2018-06-22 08:56:16,620 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@413bf65 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 08:56:16, skipping insertion in model container [2018-06-22 08:56:16,620 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:56:16" (2/3) ... [2018-06-22 08:56:16,621 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@413bf65 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 08:56:16, skipping insertion in model container [2018-06-22 08:56:16,621 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 08:56:16" (3/3) ... [2018-06-22 08:56:16,623 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 08:56:16,632 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 08:56:16,640 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 08:56:16,697 INFO ]: Using default assertion order modulation [2018-06-22 08:56:16,697 INFO ]: Interprodecural is true [2018-06-22 08:56:16,697 INFO ]: Hoare is false [2018-06-22 08:56:16,697 INFO ]: Compute interpolants for FPandBP [2018-06-22 08:56:16,697 INFO ]: Backedges is TWOTRACK [2018-06-22 08:56:16,697 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 08:56:16,697 INFO ]: Difference is false [2018-06-22 08:56:16,697 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 08:56:16,697 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 08:56:16,715 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 08:56:16,727 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 08:56:16,727 INFO ]: Found error trace [2018-06-22 08:56:16,728 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 08:56:16,728 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 08:56:16,734 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-22 08:56:16,736 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 08:56:16,736 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 08:56:16,784 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:56:16,784 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 08:56:16,785 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:56:16,902 INFO ]: Conjunction of SSA is unsat [2018-06-22 08:56:17,081 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 08:56:17,084 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 08:56:17,084 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 08:56:17,086 INFO ]: Interpolant automaton has 3 states [2018-06-22 08:56:17,103 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 08:56:17,104 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 08:56:17,107 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 08:56:17,205 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 08:56:17,205 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 08:56:17,206 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 08:56:17,207 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 08:56:17,207 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 08:56:17,219 INFO ]: With dead ends: 9 [2018-06-22 08:56:17,219 INFO ]: Without dead ends: 9 [2018-06-22 08:56:17,222 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 08:56:17,243 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 08:56:17,288 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 08:56:17,289 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 08:56:17,290 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 08:56:17,291 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 08:56:17,291 INFO ]: Finished accepts. word is rejected. [2018-06-22 08:56:17,291 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 08:56:17,291 INFO ]: Interpolant automaton has 3 states. [2018-06-22 08:56:17,291 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 08:56:17,291 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 08:56:17,291 INFO ]: Found error trace [2018-06-22 08:56:17,292 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 08:56:17,293 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 08:56:17,294 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-22 08:56:17,294 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 08:56:17,294 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 08:56:17,295 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:56:17,295 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 08:56:17,295 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:56:17,376 INFO ]: Conjunction of SSA is unsat [2018-06-22 08:56:17,543 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 08:56:17,543 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 08:56:17,543 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) [2018-06-22 08:56:17,559 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 08:56:17,771 INFO ]: Conjunction of SSA is unsat [2018-06-22 08:56:17,782 INFO ]: Computing forward predicates... [2018-06-22 08:56:17,885 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 08:56:17,907 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 08:56:17,907 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 08:56:17,907 INFO ]: Interpolant automaton has 5 states [2018-06-22 08:56:17,907 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 08:56:17,908 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-22 08:56:17,908 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 08:56:18,033 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 08:56:18,033 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-22 08:56:18,034 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 08:56:18,034 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 08:56:18,035 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 08:56:18,035 INFO ]: With dead ends: 10 [2018-06-22 08:56:18,035 INFO ]: Without dead ends: 10 [2018-06-22 08:56:18,036 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-22 08:56:18,036 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 08:56:18,037 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 08:56:18,037 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 08:56:18,037 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-22 08:56:18,037 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-22 08:56:18,037 INFO ]: Finished accepts. word is rejected. [2018-06-22 08:56:18,037 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-22 08:56:18,037 INFO ]: Interpolant automaton has 5 states. [2018-06-22 08:56:18,037 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-22 08:56:18,037 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 08:56:18,037 INFO ]: Found error trace [2018-06-22 08:56:18,038 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 08:56:18,038 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 08:56:18,038 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-22 08:56:18,038 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 08:56:18,038 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 08:56:18,039 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:56:18,039 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 08:56:18,039 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:56:18,162 INFO ]: Conjunction of SSA is unsat [2018-06-22 08:56:18,458 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 08:56:18,459 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 08:56:18,459 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 08:56:18,466 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 08:56:18,653 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 08:56:18,653 INFO ]: Conjunction of SSA is unsat [2018-06-22 08:56:18,659 INFO ]: Computing forward predicates... [2018-06-22 08:56:19,271 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 08:56:19,295 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 08:56:19,295 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-06-22 08:56:19,295 INFO ]: Interpolant automaton has 8 states [2018-06-22 08:56:19,295 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 08:56:19,295 INFO ]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2018-06-22 08:56:19,296 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 8 states. [2018-06-22 08:56:19,597 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 08:56:19,597 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 08:56:19,598 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 08:56:19,598 INFO ]: Start accepts. Automaton has 8 states. Word has length 9 [2018-06-22 08:56:19,598 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 08:56:19,599 INFO ]: With dead ends: 11 [2018-06-22 08:56:19,599 INFO ]: Without dead ends: 11 [2018-06-22 08:56:19,599 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2018-06-22 08:56:19,599 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 08:56:19,600 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 08:56:19,600 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 08:56:19,600 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 08:56:19,600 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-22 08:56:19,601 INFO ]: Finished accepts. word is rejected. [2018-06-22 08:56:19,601 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 08:56:19,601 INFO ]: Interpolant automaton has 8 states. [2018-06-22 08:56:19,601 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 08:56:19,601 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 08:56:19,601 INFO ]: Found error trace [2018-06-22 08:56:19,601 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 08:56:19,601 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 08:56:19,601 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 3 times [2018-06-22 08:56:19,601 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 08:56:19,601 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 08:56:19,602 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:56:19,602 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 08:56:19,602 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:56:19,774 INFO ]: Conjunction of SSA is unsat [2018-06-22 08:56:20,194 WARN ]: Spent 159.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 18 [2018-06-22 08:56:20,216 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 08:56:20,218 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 08:56:20,218 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 08:56:20,226 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 08:56:20,404 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 08:56:20,404 INFO ]: Conjunction of SSA is unsat [2018-06-22 08:56:20,413 INFO ]: Computing forward predicates... [2018-06-22 08:56:20,802 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:56:21,444 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 08:56:22,022 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 08:56:22,473 WARN ]: expecting exponential blowup for input size 11 [2018-06-22 08:56:22,720 WARN ]: Simplifying disjunction of 24192 conjuctions. This might take some time... Received shutdown request... [2018-06-22 08:57:35,417 INFO ]: Timeout while computing interpolants [2018-06-22 08:57:35,618 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 08:57:35,618 WARN ]: Verification canceled [2018-06-22 08:57:35,621 WARN ]: Timeout [2018-06-22 08:57:35,622 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 08:57:35 BoogieIcfgContainer [2018-06-22 08:57:35,622 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 08:57:35,622 INFO ]: Toolchain (without parser) took 79655.22 ms. Allocated memory was 308.8 MB in the beginning and 1.3 GB in the end (delta: 989.9 MB). Free memory was 247.3 MB in the beginning and 451.0 MB in the end (delta: -203.8 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 08:57:35,623 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 274.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 08:57:35,624 INFO ]: ChcToBoogie took 76.21 ms. Allocated memory is still 308.8 MB. Free memory was 247.3 MB in the beginning and 244.3 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-22 08:57:35,624 INFO ]: Boogie Preprocessor took 69.93 ms. Allocated memory is still 308.8 MB. Free memory was 244.3 MB in the beginning and 243.2 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. [2018-06-22 08:57:35,624 INFO ]: RCFGBuilder took 493.20 ms. Allocated memory is still 308.8 MB. Free memory was 243.2 MB in the beginning and 210.9 MB in the end (delta: 32.3 MB). Peak memory consumption was 32.3 MB. Max. memory is 3.6 GB. [2018-06-22 08:57:35,625 INFO ]: TraceAbstraction took 79007.10 ms. Allocated memory was 308.8 MB in the beginning and 1.3 GB in the end (delta: 989.9 MB). Free memory was 209.9 MB in the beginning and 451.0 MB in the end (delta: -241.1 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 08:57:35,634 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 308.8 MB. Free memory is still 274.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 76.21 ms. Allocated memory is still 308.8 MB. Free memory was 247.3 MB in the beginning and 244.3 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 69.93 ms. Allocated memory is still 308.8 MB. Free memory was 244.3 MB in the beginning and 243.2 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. * RCFGBuilder took 493.20 ms. Allocated memory is still 308.8 MB. Free memory was 243.2 MB in the beginning and 210.9 MB in the end (delta: 32.3 MB). Peak memory consumption was 32.3 MB. Max. memory is 3.6 GB. * TraceAbstraction took 79007.10 ms. Allocated memory was 308.8 MB in the beginning and 1.3 GB in the end (delta: 989.9 MB). Free memory was 209.9 MB in the beginning and 451.0 MB in the end (delta: -241.1 MB). Peak memory consumption was 1.2 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, 78.9s OverallTime, 4 OverallIterations, 3 TraceHistogramMax, 0.5s 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.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 29 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.8s 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.3s 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_e1_846_e2_1394.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_08-57-35-650.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/metros_1_e1_846_e2_1394.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_08-57-35-650.csv Completed graceful shutdown