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/FIREFLY_luke_1a.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 15:47:17,872 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 15:47:17,874 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 15:47:17,888 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 15:47:17,888 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 15:47:17,889 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 15:47:17,890 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 15:47:17,896 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 15:47:17,898 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 15:47:17,899 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 15:47:17,900 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 15:47:17,903 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 15:47:17,904 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 15:47:17,905 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 15:47:17,906 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 15:47:17,909 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 15:47:17,910 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 15:47:17,915 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 15:47:17,916 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 15:47:17,917 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 15:47:17,918 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 15:47:17,921 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 15:47:17,921 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 15:47:17,921 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 15:47:17,922 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 15:47:17,923 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 15:47:17,923 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 15:47:17,924 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 15:47:17,925 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 15:47:17,925 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 15:47:17,926 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 15:47:17,927 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 15:47:17,927 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 15:47:17,928 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 15:47:17,928 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 15:47:17,929 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 15:47:17,942 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 15:47:17,945 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 15:47:17,945 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 15:47:17,945 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 15:47:17,946 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 15:47:17,946 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 15:47:17,946 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 15:47:17,947 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 15:47:17,947 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 15:47:17,947 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 15:47:17,947 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 15:47:17,947 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 15:47:17,947 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 15:47:17,948 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 15:47:17,948 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 15:47:17,948 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 15:47:17,948 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 15:47:17,948 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 15:47:17,948 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 15:47:17,949 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 15:47:17,949 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 15:47:17,950 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 15:47:17,950 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 15:47:18,003 INFO ]: Repository-Root is: /tmp [2018-06-25 15:47:18,015 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 15:47:18,019 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 15:47:18,020 INFO ]: Initializing SmtParser... [2018-06-25 15:47:18,020 INFO ]: SmtParser initialized [2018-06-25 15:47:18,021 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/FIREFLY_luke_1a.smt2 [2018-06-25 15:47:18,027 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 15:47:18,118 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/FIREFLY_luke_1a.smt2 unknown [2018-06-25 15:47:18,654 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/FIREFLY_luke_1a.smt2 [2018-06-25 15:47:18,659 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 15:47:18,664 INFO ]: Walking toolchain with 4 elements. [2018-06-25 15:47:18,665 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 15:47:18,665 INFO ]: Initializing ChcToBoogie... [2018-06-25 15:47:18,665 INFO ]: ChcToBoogie initialized [2018-06-25 15:47:18,674 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 03:47:18" (1/1) ... [2018-06-25 15:47:18,774 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 03:47:18 Unit [2018-06-25 15:47:18,774 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 15:47:18,774 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 15:47:18,774 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 15:47:18,774 INFO ]: Boogie Preprocessor initialized [2018-06-25 15:47:18,810 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 03:47:18" (1/1) ... [2018-06-25 15:47:18,810 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 03:47:18" (1/1) ... [2018-06-25 15:47:18,834 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 03:47:18" (1/1) ... [2018-06-25 15:47:18,835 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 03:47:18" (1/1) ... [2018-06-25 15:47:18,847 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 03:47:18" (1/1) ... [2018-06-25 15:47:18,849 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 03:47:18" (1/1) ... [2018-06-25 15:47:18,852 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 03:47:18" (1/1) ... [2018-06-25 15:47:18,856 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 15:47:18,857 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 15:47:18,857 INFO ]: Initializing RCFGBuilder... [2018-06-25 15:47:18,857 INFO ]: RCFGBuilder initialized [2018-06-25 15:47:18,858 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 03:47:18" (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 15:47:18,874 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 15:47:18,874 INFO ]: Found specification of procedure gotoProc [2018-06-25 15:47:18,874 INFO ]: Found implementation of procedure gotoProc [2018-06-25 15:47:18,874 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 15:47:18,874 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 15:47:18,874 INFO ]: Found implementation of procedure Ultimate.START [2018-06-25 15:47:19,323 INFO ]: Using library mode [2018-06-25 15:47:19,324 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 03:47:19 BoogieIcfgContainer [2018-06-25 15:47:19,324 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 15:47:19,325 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 15:47:19,325 INFO ]: Initializing TraceAbstraction... [2018-06-25 15:47:19,330 INFO ]: TraceAbstraction initialized [2018-06-25 15:47:19,330 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 03:47:18" (1/3) ... [2018-06-25 15:47:19,331 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6e9e861f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 03:47:19, skipping insertion in model container [2018-06-25 15:47:19,331 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 03:47:18" (2/3) ... [2018-06-25 15:47:19,331 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6e9e861f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 03:47:19, skipping insertion in model container [2018-06-25 15:47:19,331 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 03:47:19" (3/3) ... [2018-06-25 15:47:19,333 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 15:47:19,343 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 15:47:19,351 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 15:47:19,384 INFO ]: Using default assertion order modulation [2018-06-25 15:47:19,385 INFO ]: Interprodecural is true [2018-06-25 15:47:19,385 INFO ]: Hoare is false [2018-06-25 15:47:19,385 INFO ]: Compute interpolants for FPandBP [2018-06-25 15:47:19,385 INFO ]: Backedges is TWOTRACK [2018-06-25 15:47:19,385 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 15:47:19,385 INFO ]: Difference is false [2018-06-25 15:47:19,385 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 15:47:19,385 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 15:47:19,397 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 15:47:19,417 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 15:47:19,417 INFO ]: Found error trace [2018-06-25 15:47:19,418 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 15:47:19,418 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 15:47:19,424 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 15:47:19,425 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 15:47:19,426 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 15:47:19,459 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 15:47:19,459 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 15:47:19,459 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 15:47:19,589 INFO ]: Conjunction of SSA is unsat [2018-06-25 15:47:19,791 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 15:47:19,794 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 15:47:19,794 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 15:47:19,796 INFO ]: Interpolant automaton has 3 states [2018-06-25 15:47:19,811 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 15:47:19,812 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 15:47:19,814 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 15:47:19,910 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 15:47:19,910 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 15:47:19,913 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 15:47:19,914 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 15:47:19,914 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 15:47:19,926 INFO ]: With dead ends: 9 [2018-06-25 15:47:19,926 INFO ]: Without dead ends: 9 [2018-06-25 15:47:19,928 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 15:47:19,945 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 15:47:19,979 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 15:47:19,981 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 15:47:19,981 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 15:47:19,982 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 15:47:19,982 INFO ]: Finished accepts. word is rejected. [2018-06-25 15:47:19,982 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 15:47:19,982 INFO ]: Interpolant automaton has 3 states. [2018-06-25 15:47:19,983 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 15:47:19,983 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 15:47:19,983 INFO ]: Found error trace [2018-06-25 15:47:19,983 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 15:47:19,983 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 15:47:19,983 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 15:47:19,983 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 15:47:19,983 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 15:47:19,984 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 15:47:19,984 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 15:47:19,984 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 15:47:20,113 INFO ]: Conjunction of SSA is unsat [2018-06-25 15:47:20,386 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 15:47:20,386 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 15:47:20,386 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 15:47:20,395 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 15:47:20,614 INFO ]: Conjunction of SSA is unsat [2018-06-25 15:47:20,629 INFO ]: Computing forward predicates... [2018-06-25 15:47:21,978 WARN ]: expecting exponential blowup for input size 15 [2018-06-25 15:47:23,037 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 15:47:23,041 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 15:47:23,043 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 15:47:23,046 WARN ]: expecting exponential blowup for input size 11 [2018-06-25 15:47:23,095 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 15:47:23,102 WARN ]: expecting exponential blowup for input size 12 [2018-06-25 15:47:23,113 WARN ]: expecting exponential blowup for input size 13 [2018-06-25 15:47:23,169 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 15:47:23,170 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 15:47:23,179 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 15:47:23,194 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 15:47:23,217 WARN ]: expecting exponential blowup for input size 10 [2018-06-25 15:47:23,231 WARN ]: expecting exponential blowup for input size 11 [2018-06-25 15:47:23,293 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 15:47:23,366 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 15:47:23,368 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 15:47:23,371 WARN ]: expecting exponential blowup for input size 10 [2018-06-25 15:47:23,384 WARN ]: expecting exponential blowup for input size 11 [2018-06-25 15:47:23,430 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 15:47:23,442 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 15:47:23,444 WARN ]: expecting exponential blowup for input size 11 [2018-06-25 15:47:23,461 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 15:47:23,462 WARN ]: expecting exponential blowup for input size 10 [2018-06-25 15:47:23,541 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 15:47:23,545 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 15:47:23,555 WARN ]: expecting exponential blowup for input size 11 [2018-06-25 15:47:23,563 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 15:47:23,580 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 15:47:23,691 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 15:47:23,694 WARN ]: expecting exponential blowup for input size 12 [2018-06-25 15:47:23,714 WARN ]: expecting exponential blowup for input size 11 [2018-06-25 15:47:24,693 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 15:47:24,696 WARN ]: expecting exponential blowup for input size 10 [2018-06-25 15:47:24,727 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 15:47:24,729 WARN ]: expecting exponential blowup for input size 11 [2018-06-25 15:47:24,735 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 15:47:24,739 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 15:47:24,743 WARN ]: expecting exponential blowup for input size 10 [2018-06-25 15:47:24,858 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 15:47:24,862 WARN ]: expecting exponential blowup for input size 10 [2018-06-25 15:47:24,872 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 15:47:24,885 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 15:47:24,890 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 15:47:56,581 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 8 [2018-06-25 15:47:56,584 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 15:47:56,605 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 15:47:56,605 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 15:47:56,606 INFO ]: Interpolant automaton has 5 states [2018-06-25 15:47:56,606 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 15:47:56,606 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-25 15:47:56,606 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 15:47:56,638 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 15:47:56,638 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 15:47:56,639 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-25 15:47:56,639 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 15:47:56,639 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 15:47:56,639 INFO ]: With dead ends: 10 [2018-06-25 15:47:56,639 INFO ]: Without dead ends: 10 [2018-06-25 15:47:56,640 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-25 15:47:56,640 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 15:47:56,640 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 15:47:56,641 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 15:47:56,641 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 15:47:56,641 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 15:47:56,641 INFO ]: Finished accepts. word is rejected. [2018-06-25 15:47:56,641 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 15:47:56,641 INFO ]: Interpolant automaton has 5 states. [2018-06-25 15:47:56,641 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 15:47:56,641 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 15:47:56,641 INFO ]: Found error trace [2018-06-25 15:47:56,641 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 15:47:56,642 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 15:47:56,642 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-25 15:47:56,642 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 15:47:56,642 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 15:47:56,643 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 15:47:56,643 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 15:47:56,643 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 15:47:56,869 INFO ]: Conjunction of SSA is unsat [2018-06-25 15:47:57,175 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 15:47:57,175 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 15:47:57,175 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 15:47:57,183 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 15:47:57,324 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 15:47:57,324 INFO ]: Conjunction of SSA is unsat [2018-06-25 15:47:57,334 INFO ]: Computing forward predicates... [2018-06-25 15:47:58,499 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 15:47:58,501 WARN ]: expecting exponential blowup for input size 17 Received shutdown request... [2018-06-25 15:48:15,633 INFO ]: Timeout while computing interpolants [2018-06-25 15:48:15,833 WARN ]: Destroyed unattended storables created during the last iteration: 4 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 15:48:15,833 WARN ]: Verification canceled [2018-06-25 15:48:15,837 WARN ]: Timeout [2018-06-25 15:48:15,837 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 03:48:15 BoogieIcfgContainer [2018-06-25 15:48:15,837 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 15:48:15,838 INFO ]: Toolchain (without parser) took 57178.78 ms. Allocated memory was 302.5 MB in the beginning and 2.5 GB in the end (delta: 2.2 GB). Free memory was 236.1 MB in the beginning and 1.5 GB in the end (delta: -1.2 GB). Peak memory consumption was 2.5 GB. Max. memory is 3.6 GB. [2018-06-25 15:48:15,839 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 302.5 MB. Free memory is still 267.1 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 15:48:15,839 INFO ]: ChcToBoogie took 109.13 ms. Allocated memory is still 302.5 MB. Free memory was 236.1 MB in the beginning and 234.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 15:48:15,840 INFO ]: Boogie Preprocessor took 81.87 ms. Allocated memory is still 302.5 MB. Free memory was 234.1 MB in the beginning and 232.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 15:48:15,840 INFO ]: RCFGBuilder took 466.99 ms. Allocated memory is still 302.5 MB. Free memory was 232.1 MB in the beginning and 194.2 MB in the end (delta: 37.9 MB). Peak memory consumption was 37.9 MB. Max. memory is 3.6 GB. [2018-06-25 15:48:15,841 INFO ]: TraceAbstraction took 56512.14 ms. Allocated memory was 302.5 MB in the beginning and 2.5 GB in the end (delta: 2.2 GB). Free memory was 194.2 MB in the beginning and 1.5 GB in the end (delta: -1.3 GB). Peak memory consumption was 2.5 GB. Max. memory is 3.6 GB. [2018-06-25 15:48:15,843 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 302.5 MB. Free memory is still 267.1 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 109.13 ms. Allocated memory is still 302.5 MB. Free memory was 236.1 MB in the beginning and 234.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 81.87 ms. Allocated memory is still 302.5 MB. Free memory was 234.1 MB in the beginning and 232.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 466.99 ms. Allocated memory is still 302.5 MB. Free memory was 232.1 MB in the beginning and 194.2 MB in the end (delta: 37.9 MB). Peak memory consumption was 37.9 MB. Max. memory is 3.6 GB. * TraceAbstraction took 56512.14 ms. Allocated memory was 302.5 MB in the beginning and 2.5 GB in the end (delta: 2.2 GB). Free memory was 194.2 MB in the beginning and 1.5 GB in the end (delta: -1.3 GB). Peak memory consumption was 2.5 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 10 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was transforming 17 conjuction. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 56.4s OverallTime, 3 OverallIterations, 2 TraceHistogramMax, 0.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 14 SDtfs, 0 SDslu, 20 SDs, 0 SdLazy, 14 SolverSat, 0 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 14 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=10occurred in iteration=0, 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, 2 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 36.4s InterpolantComputationTime, 23 NumberOfCodeBlocks, 23 NumberOfCodeBlocksAsserted, 3 NumberOfCheckSat, 20 ConstructedInterpolants, 0 QuantifiedInterpolants, 287 SizeOfPredicates, 2 NumberOfNonLiveVariables, 652 ConjunctsInSsa, 38 ConjunctsInUnsatCore, 3 InterpolantComputations, 1 PerfectInterpolantSequences, 0/2 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/FIREFLY_luke_1a.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_15-48-15-854.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/FIREFLY_luke_1a.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_15-48-15-854.csv Completed graceful shutdown