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/hopv/lia/termination/Ackermann02.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 01:52:15,975 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 01:52:15,978 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 01:52:15,993 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 01:52:15,993 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 01:52:15,994 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 01:52:15,995 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 01:52:15,999 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 01:52:16,001 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 01:52:16,003 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 01:52:16,004 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 01:52:16,004 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 01:52:16,005 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 01:52:16,009 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 01:52:16,010 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 01:52:16,011 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 01:52:16,023 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 01:52:16,025 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 01:52:16,027 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 01:52:16,028 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 01:52:16,029 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 01:52:16,031 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 01:52:16,031 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 01:52:16,031 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 01:52:16,036 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 01:52:16,037 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 01:52:16,038 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 01:52:16,038 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 01:52:16,043 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 01:52:16,044 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 01:52:16,044 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 01:52:16,045 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 01:52:16,045 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 01:52:16,046 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 01:52:16,046 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 01:52:16,048 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 01:52:16,066 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 01:52:16,066 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 01:52:16,067 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 01:52:16,067 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 01:52:16,068 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 01:52:16,068 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 01:52:16,068 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 01:52:16,069 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 01:52:16,072 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 01:52:16,073 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 01:52:16,073 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 01:52:16,073 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 01:52:16,073 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 01:52:16,073 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 01:52:16,073 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 01:52:16,074 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 01:52:16,074 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 01:52:16,075 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 01:52:16,076 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 01:52:16,136 INFO ]: Repository-Root is: /tmp [2018-06-22 01:52:16,155 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 01:52:16,159 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 01:52:16,160 INFO ]: Initializing SmtParser... [2018-06-22 01:52:16,161 INFO ]: SmtParser initialized [2018-06-22 01:52:16,161 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/hopv/lia/termination/Ackermann02.smt2 [2018-06-22 01:52:16,163 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 01:52:16,260 INFO ]: Executing SMT file /storage/chc-comp/hopv/lia/termination/Ackermann02.smt2 unknown [2018-06-22 01:52:16,795 INFO ]: Succesfully executed SMT file /storage/chc-comp/hopv/lia/termination/Ackermann02.smt2 [2018-06-22 01:52:16,809 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 01:52:16,814 INFO ]: Walking toolchain with 4 elements. [2018-06-22 01:52:16,815 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 01:52:16,815 INFO ]: Initializing ChcToBoogie... [2018-06-22 01:52:16,815 INFO ]: ChcToBoogie initialized [2018-06-22 01:52:16,828 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:52:16" (1/1) ... [2018-06-22 01:52:16,965 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:52:16 Unit [2018-06-22 01:52:16,965 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 01:52:16,966 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 01:52:16,966 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 01:52:16,970 INFO ]: Boogie Preprocessor initialized [2018-06-22 01:52:17,010 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:52:16" (1/1) ... [2018-06-22 01:52:17,010 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:52:16" (1/1) ... [2018-06-22 01:52:17,022 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:52:16" (1/1) ... [2018-06-22 01:52:17,023 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:52:16" (1/1) ... [2018-06-22 01:52:17,044 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:52:16" (1/1) ... [2018-06-22 01:52:17,051 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:52:16" (1/1) ... [2018-06-22 01:52:17,053 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:52:16" (1/1) ... [2018-06-22 01:52:17,057 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 01:52:17,058 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 01:52:17,058 INFO ]: Initializing RCFGBuilder... [2018-06-22 01:52:17,058 INFO ]: RCFGBuilder initialized [2018-06-22 01:52:17,059 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:52: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 01:52:17,074 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 01:52:17,074 INFO ]: Found specification of procedure gotoProc [2018-06-22 01:52:17,074 INFO ]: Found implementation of procedure gotoProc [2018-06-22 01:52:17,074 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 01:52:17,074 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 01:52:17,074 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 01:52:18,323 INFO ]: Using library mode [2018-06-22 01:52:18,323 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:52:18 BoogieIcfgContainer [2018-06-22 01:52:18,324 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 01:52:18,326 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 01:52:18,326 INFO ]: Initializing TraceAbstraction... [2018-06-22 01:52:18,329 INFO ]: TraceAbstraction initialized [2018-06-22 01:52:18,330 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:52:16" (1/3) ... [2018-06-22 01:52:18,331 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c92241b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 01:52:18, skipping insertion in model container [2018-06-22 01:52:18,331 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:52:16" (2/3) ... [2018-06-22 01:52:18,333 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c92241b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 01:52:18, skipping insertion in model container [2018-06-22 01:52:18,333 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:52:18" (3/3) ... [2018-06-22 01:52:18,336 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 01:52:18,345 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 01:52:18,354 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 01:52:18,399 INFO ]: Using default assertion order modulation [2018-06-22 01:52:18,400 INFO ]: Interprodecural is true [2018-06-22 01:52:18,400 INFO ]: Hoare is false [2018-06-22 01:52:18,400 INFO ]: Compute interpolants for FPandBP [2018-06-22 01:52:18,400 INFO ]: Backedges is TWOTRACK [2018-06-22 01:52:18,400 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 01:52:18,400 INFO ]: Difference is false [2018-06-22 01:52:18,400 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 01:52:18,400 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 01:52:18,425 INFO ]: Start isEmpty. Operand 48 states. [2018-06-22 01:52:18,444 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 01:52:18,445 INFO ]: Found error trace [2018-06-22 01:52:18,446 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:18,446 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:18,452 INFO ]: Analyzing trace with hash 1724798604, now seen corresponding path program 1 times [2018-06-22 01:52:18,454 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:18,454 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:18,498 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:18,498 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:18,498 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:18,551 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:18,695 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:52:18,697 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:52:18,698 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:52:18,699 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:52:18,711 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:52:18,712 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:52:18,715 INFO ]: Start difference. First operand 48 states. Second operand 4 states. [2018-06-22 01:52:19,835 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:52:19,835 INFO ]: Finished difference Result 83 states and 132 transitions. [2018-06-22 01:52:19,836 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:52:19,837 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 01:52:19,838 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:52:19,854 INFO ]: With dead ends: 83 [2018-06-22 01:52:19,854 INFO ]: Without dead ends: 79 [2018-06-22 01:52:19,856 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:52:19,876 INFO ]: Start minimizeSevpa. Operand 79 states. [2018-06-22 01:52:19,912 INFO ]: Finished minimizeSevpa. Reduced states from 79 to 79. [2018-06-22 01:52:19,914 INFO ]: Start removeUnreachable. Operand 79 states. [2018-06-22 01:52:19,918 INFO ]: Finished removeUnreachable. Reduced from 79 states to 79 states and 126 transitions. [2018-06-22 01:52:19,920 INFO ]: Start accepts. Automaton has 79 states and 126 transitions. Word has length 9 [2018-06-22 01:52:19,921 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:52:19,921 INFO ]: Abstraction has 79 states and 126 transitions. [2018-06-22 01:52:19,921 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:52:19,921 INFO ]: Start isEmpty. Operand 79 states and 126 transitions. [2018-06-22 01:52:19,925 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 01:52:19,925 INFO ]: Found error trace [2018-06-22 01:52:19,925 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:19,925 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:19,925 INFO ]: Analyzing trace with hash -896558405, now seen corresponding path program 1 times [2018-06-22 01:52:19,925 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:19,925 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:19,926 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:19,926 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:19,926 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:19,938 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:20,065 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:52:20,065 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:52:20,065 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:52:20,067 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:52:20,067 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:52:20,067 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:52:20,067 INFO ]: Start difference. First operand 79 states and 126 transitions. Second operand 4 states. [2018-06-22 01:52:20,992 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:52:20,992 INFO ]: Finished difference Result 106 states and 168 transitions. [2018-06-22 01:52:20,993 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:52:20,993 INFO ]: Start accepts. Automaton has 4 states. Word has length 13 [2018-06-22 01:52:20,993 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:52:20,999 INFO ]: With dead ends: 106 [2018-06-22 01:52:20,999 INFO ]: Without dead ends: 106 [2018-06-22 01:52:21,000 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:52:21,001 INFO ]: Start minimizeSevpa. Operand 106 states. [2018-06-22 01:52:21,021 INFO ]: Finished minimizeSevpa. Reduced states from 106 to 106. [2018-06-22 01:52:21,021 INFO ]: Start removeUnreachable. Operand 106 states. [2018-06-22 01:52:21,026 INFO ]: Finished removeUnreachable. Reduced from 106 states to 106 states and 168 transitions. [2018-06-22 01:52:21,027 INFO ]: Start accepts. Automaton has 106 states and 168 transitions. Word has length 13 [2018-06-22 01:52:21,027 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:52:21,027 INFO ]: Abstraction has 106 states and 168 transitions. [2018-06-22 01:52:21,027 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:52:21,027 INFO ]: Start isEmpty. Operand 106 states and 168 transitions. [2018-06-22 01:52:21,031 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-22 01:52:21,031 INFO ]: Found error trace [2018-06-22 01:52:21,031 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:21,031 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:21,031 INFO ]: Analyzing trace with hash -69804647, now seen corresponding path program 1 times [2018-06-22 01:52:21,031 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:21,031 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:21,032 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:21,032 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:21,032 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:21,065 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:21,269 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:52:21,269 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:52:21,269 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:52:21,269 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:52:21,269 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:52:21,270 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:52:21,270 INFO ]: Start difference. First operand 106 states and 168 transitions. Second operand 4 states. [2018-06-22 01:52:21,550 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:52:21,551 INFO ]: Finished difference Result 247 states and 498 transitions. [2018-06-22 01:52:21,552 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:52:21,552 INFO ]: Start accepts. Automaton has 4 states. Word has length 16 [2018-06-22 01:52:21,552 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:52:21,584 INFO ]: With dead ends: 247 [2018-06-22 01:52:21,584 INFO ]: Without dead ends: 247 [2018-06-22 01:52:21,584 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:52:21,585 INFO ]: Start minimizeSevpa. Operand 247 states. [2018-06-22 01:52:21,638 INFO ]: Finished minimizeSevpa. Reduced states from 247 to 112. [2018-06-22 01:52:21,638 INFO ]: Start removeUnreachable. Operand 112 states. [2018-06-22 01:52:21,642 INFO ]: Finished removeUnreachable. Reduced from 112 states to 112 states and 177 transitions. [2018-06-22 01:52:21,642 INFO ]: Start accepts. Automaton has 112 states and 177 transitions. Word has length 16 [2018-06-22 01:52:21,642 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:52:21,642 INFO ]: Abstraction has 112 states and 177 transitions. [2018-06-22 01:52:21,642 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:52:21,642 INFO ]: Start isEmpty. Operand 112 states and 177 transitions. [2018-06-22 01:52:21,662 INFO ]: Finished isEmpty. Found accepting run of length 31 [2018-06-22 01:52:21,662 INFO ]: Found error trace [2018-06-22 01:52:21,662 INFO ]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:21,662 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:21,663 INFO ]: Analyzing trace with hash -215003191, now seen corresponding path program 1 times [2018-06-22 01:52:21,663 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:21,663 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:21,664 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:21,664 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:21,664 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:21,693 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:21,763 INFO ]: Checked inductivity of 13 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 01:52:21,763 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:52:21,763 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:52:21,763 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:52:21,764 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:52:21,764 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:52:21,764 INFO ]: Start difference. First operand 112 states and 177 transitions. Second operand 4 states. [2018-06-22 01:52:22,649 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:52:22,649 INFO ]: Finished difference Result 174 states and 278 transitions. [2018-06-22 01:52:22,650 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:52:22,650 INFO ]: Start accepts. Automaton has 4 states. Word has length 30 [2018-06-22 01:52:22,650 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:52:22,654 INFO ]: With dead ends: 174 [2018-06-22 01:52:22,654 INFO ]: Without dead ends: 149 [2018-06-22 01:52:22,655 INFO ]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:52:22,655 INFO ]: Start minimizeSevpa. Operand 149 states. [2018-06-22 01:52:22,670 INFO ]: Finished minimizeSevpa. Reduced states from 149 to 149. [2018-06-22 01:52:22,670 INFO ]: Start removeUnreachable. Operand 149 states. [2018-06-22 01:52:22,673 INFO ]: Finished removeUnreachable. Reduced from 149 states to 149 states and 233 transitions. [2018-06-22 01:52:22,673 INFO ]: Start accepts. Automaton has 149 states and 233 transitions. Word has length 30 [2018-06-22 01:52:22,673 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:52:22,673 INFO ]: Abstraction has 149 states and 233 transitions. [2018-06-22 01:52:22,673 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:52:22,673 INFO ]: Start isEmpty. Operand 149 states and 233 transitions. [2018-06-22 01:52:22,677 INFO ]: Finished isEmpty. Found accepting run of length 32 [2018-06-22 01:52:22,677 INFO ]: Found error trace [2018-06-22 01:52:22,678 INFO ]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:22,678 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:22,678 INFO ]: Analyzing trace with hash 1251301023, now seen corresponding path program 1 times [2018-06-22 01:52:22,678 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:22,678 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:22,679 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:22,679 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:22,679 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:22,755 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:23,011 WARN ]: Spent 120.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 01:52:23,198 INFO ]: Checked inductivity of 13 backedges. 5 proven. 2 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 01:52:23,198 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:52:23,198 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:52:23,207 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:23,279 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:23,291 INFO ]: Computing forward predicates... [2018-06-22 01:52:23,607 INFO ]: Checked inductivity of 13 backedges. 5 proven. 2 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 01:52:23,630 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:52:23,630 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 01:52:23,631 INFO ]: Interpolant automaton has 8 states [2018-06-22 01:52:23,631 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 01:52:23,631 INFO ]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:52:23,631 INFO ]: Start difference. First operand 149 states and 233 transitions. Second operand 8 states. [2018-06-22 01:52:26,042 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:52:26,042 INFO ]: Finished difference Result 438 states and 1193 transitions. [2018-06-22 01:52:26,043 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 01:52:26,043 INFO ]: Start accepts. Automaton has 8 states. Word has length 31 [2018-06-22 01:52:26,043 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:52:26,069 INFO ]: With dead ends: 438 [2018-06-22 01:52:26,069 INFO ]: Without dead ends: 407 [2018-06-22 01:52:26,070 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 29 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=43, Invalid=113, Unknown=0, NotChecked=0, Total=156 [2018-06-22 01:52:26,070 INFO ]: Start minimizeSevpa. Operand 407 states. [2018-06-22 01:52:26,153 INFO ]: Finished minimizeSevpa. Reduced states from 407 to 177. [2018-06-22 01:52:26,153 INFO ]: Start removeUnreachable. Operand 177 states. [2018-06-22 01:52:26,158 INFO ]: Finished removeUnreachable. Reduced from 177 states to 177 states and 316 transitions. [2018-06-22 01:52:26,158 INFO ]: Start accepts. Automaton has 177 states and 316 transitions. Word has length 31 [2018-06-22 01:52:26,158 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:52:26,158 INFO ]: Abstraction has 177 states and 316 transitions. [2018-06-22 01:52:26,158 INFO ]: Interpolant automaton has 8 states. [2018-06-22 01:52:26,158 INFO ]: Start isEmpty. Operand 177 states and 316 transitions. [2018-06-22 01:52:26,162 INFO ]: Finished isEmpty. Found accepting run of length 32 [2018-06-22 01:52:26,162 INFO ]: Found error trace [2018-06-22 01:52:26,163 INFO ]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:26,163 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:26,163 INFO ]: Analyzing trace with hash 89556552, now seen corresponding path program 1 times [2018-06-22 01:52:26,163 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:26,163 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:26,164 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:26,164 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:26,164 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:26,196 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:26,289 INFO ]: Checked inductivity of 13 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 01:52:26,289 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:52:26,290 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 01:52:26,298 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:26,357 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:26,360 INFO ]: Computing forward predicates... [2018-06-22 01:52:26,447 INFO ]: Checked inductivity of 13 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 01:52:26,479 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 01:52:26,479 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [4] total 5 [2018-06-22 01:52:26,480 INFO ]: Interpolant automaton has 5 states [2018-06-22 01:52:26,480 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 01:52:26,480 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:52:26,480 INFO ]: Start difference. First operand 177 states and 316 transitions. Second operand 5 states. [2018-06-22 01:52:26,616 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:52:26,616 INFO ]: Finished difference Result 220 states and 408 transitions. [2018-06-22 01:52:26,617 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 01:52:26,617 INFO ]: Start accepts. Automaton has 5 states. Word has length 31 [2018-06-22 01:52:26,617 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:52:26,623 INFO ]: With dead ends: 220 [2018-06-22 01:52:26,623 INFO ]: Without dead ends: 217 [2018-06-22 01:52:26,624 INFO ]: 0 DeclaredPredicates, 36 GetRequests, 33 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 01:52:26,624 INFO ]: Start minimizeSevpa. Operand 217 states. [2018-06-22 01:52:26,641 INFO ]: Finished minimizeSevpa. Reduced states from 217 to 177. [2018-06-22 01:52:26,641 INFO ]: Start removeUnreachable. Operand 177 states. [2018-06-22 01:52:26,644 INFO ]: Finished removeUnreachable. Reduced from 177 states to 177 states and 312 transitions. [2018-06-22 01:52:26,644 INFO ]: Start accepts. Automaton has 177 states and 312 transitions. Word has length 31 [2018-06-22 01:52:26,645 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:52:26,645 INFO ]: Abstraction has 177 states and 312 transitions. [2018-06-22 01:52:26,645 INFO ]: Interpolant automaton has 5 states. [2018-06-22 01:52:26,645 INFO ]: Start isEmpty. Operand 177 states and 312 transitions. [2018-06-22 01:52:26,652 INFO ]: Finished isEmpty. Found accepting run of length 47 [2018-06-22 01:52:26,653 INFO ]: Found error trace [2018-06-22 01:52:26,653 INFO ]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:26,653 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:26,653 INFO ]: Analyzing trace with hash -1547946146, now seen corresponding path program 1 times [2018-06-22 01:52:26,653 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:26,653 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:26,654 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:26,654 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:26,654 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:26,665 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:26,918 INFO ]: Checked inductivity of 37 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2018-06-22 01:52:26,919 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:52:26,919 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 01:52:26,933 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:52:27,018 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:27,023 INFO ]: Computing forward predicates... [2018-06-22 01:52:27,093 INFO ]: Checked inductivity of 37 backedges. 24 proven. 0 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-06-22 01:52:27,128 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 01:52:27,128 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [5] total 7 [2018-06-22 01:52:27,128 INFO ]: Interpolant automaton has 7 states [2018-06-22 01:52:27,128 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 01:52:27,128 INFO ]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:52:27,128 INFO ]: Start difference. First operand 177 states and 312 transitions. Second operand 7 states. [2018-06-22 01:52:27,433 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:52:27,433 INFO ]: Finished difference Result 270 states and 626 transitions. [2018-06-22 01:52:27,434 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 01:52:27,434 INFO ]: Start accepts. Automaton has 7 states. Word has length 46 [2018-06-22 01:52:27,434 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:52:27,444 INFO ]: With dead ends: 270 [2018-06-22 01:52:27,444 INFO ]: Without dead ends: 270 [2018-06-22 01:52:27,445 INFO ]: 0 DeclaredPredicates, 59 GetRequests, 48 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=54, Invalid=102, Unknown=0, NotChecked=0, Total=156 [2018-06-22 01:52:27,445 INFO ]: Start minimizeSevpa. Operand 270 states. [2018-06-22 01:52:27,471 INFO ]: Finished minimizeSevpa. Reduced states from 270 to 170. [2018-06-22 01:52:27,471 INFO ]: Start removeUnreachable. Operand 170 states. [2018-06-22 01:52:27,474 INFO ]: Finished removeUnreachable. Reduced from 170 states to 170 states and 294 transitions. [2018-06-22 01:52:27,474 INFO ]: Start accepts. Automaton has 170 states and 294 transitions. Word has length 46 [2018-06-22 01:52:27,474 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:52:27,474 INFO ]: Abstraction has 170 states and 294 transitions. [2018-06-22 01:52:27,474 INFO ]: Interpolant automaton has 7 states. [2018-06-22 01:52:27,474 INFO ]: Start isEmpty. Operand 170 states and 294 transitions. [2018-06-22 01:52:27,481 INFO ]: Finished isEmpty. Found accepting run of length 47 [2018-06-22 01:52:27,481 INFO ]: Found error trace [2018-06-22 01:52:27,481 INFO ]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:27,481 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:27,481 INFO ]: Analyzing trace with hash 363713622, now seen corresponding path program 1 times [2018-06-22 01:52:27,481 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:27,481 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:27,482 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:27,482 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:27,482 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:27,501 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:27,589 INFO ]: Checked inductivity of 37 backedges. 27 proven. 0 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 01:52:27,589 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:52:27,589 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:52:27,589 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:52:27,590 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:52:27,590 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:52:27,590 INFO ]: Start difference. First operand 170 states and 294 transitions. Second operand 4 states. [2018-06-22 01:52:27,835 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:52:27,835 INFO ]: Finished difference Result 237 states and 378 transitions. [2018-06-22 01:52:27,835 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:52:27,835 INFO ]: Start accepts. Automaton has 4 states. Word has length 46 [2018-06-22 01:52:27,836 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:52:27,839 INFO ]: With dead ends: 237 [2018-06-22 01:52:27,839 INFO ]: Without dead ends: 207 [2018-06-22 01:52:27,840 INFO ]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:52:27,840 INFO ]: Start minimizeSevpa. Operand 207 states. [2018-06-22 01:52:27,851 INFO ]: Finished minimizeSevpa. Reduced states from 207 to 207. [2018-06-22 01:52:27,851 INFO ]: Start removeUnreachable. Operand 207 states. [2018-06-22 01:52:27,854 INFO ]: Finished removeUnreachable. Reduced from 207 states to 207 states and 324 transitions. [2018-06-22 01:52:27,854 INFO ]: Start accepts. Automaton has 207 states and 324 transitions. Word has length 46 [2018-06-22 01:52:27,854 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:52:27,854 INFO ]: Abstraction has 207 states and 324 transitions. [2018-06-22 01:52:27,854 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:52:27,854 INFO ]: Start isEmpty. Operand 207 states and 324 transitions. [2018-06-22 01:52:27,859 INFO ]: Finished isEmpty. Found accepting run of length 51 [2018-06-22 01:52:27,859 INFO ]: Found error trace [2018-06-22 01:52:27,859 INFO ]: trace histogram [4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:27,859 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:27,859 INFO ]: Analyzing trace with hash 1011952495, now seen corresponding path program 1 times [2018-06-22 01:52:27,860 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:27,860 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:27,860 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:27,860 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:27,860 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:27,870 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:27,946 INFO ]: Checked inductivity of 48 backedges. 25 proven. 3 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2018-06-22 01:52:27,946 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:52:27,946 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:52:27,952 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:28,037 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:28,042 INFO ]: Computing forward predicates... [2018-06-22 01:52:28,050 INFO ]: Checked inductivity of 48 backedges. 25 proven. 3 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2018-06-22 01:52:28,080 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:52:28,080 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-22 01:52:28,080 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:52:28,080 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:52:28,080 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:52:28,080 INFO ]: Start difference. First operand 207 states and 324 transitions. Second operand 4 states. [2018-06-22 01:52:28,300 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:52:28,300 INFO ]: Finished difference Result 295 states and 468 transitions. [2018-06-22 01:52:28,300 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:52:28,300 INFO ]: Start accepts. Automaton has 4 states. Word has length 50 [2018-06-22 01:52:28,300 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:52:28,304 INFO ]: With dead ends: 295 [2018-06-22 01:52:28,304 INFO ]: Without dead ends: 227 [2018-06-22 01:52:28,304 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 52 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:52:28,304 INFO ]: Start minimizeSevpa. Operand 227 states. [2018-06-22 01:52:28,316 INFO ]: Finished minimizeSevpa. Reduced states from 227 to 227. [2018-06-22 01:52:28,316 INFO ]: Start removeUnreachable. Operand 227 states. [2018-06-22 01:52:28,319 INFO ]: Finished removeUnreachable. Reduced from 227 states to 227 states and 352 transitions. [2018-06-22 01:52:28,319 INFO ]: Start accepts. Automaton has 227 states and 352 transitions. Word has length 50 [2018-06-22 01:52:28,320 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:52:28,320 INFO ]: Abstraction has 227 states and 352 transitions. [2018-06-22 01:52:28,320 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:52:28,320 INFO ]: Start isEmpty. Operand 227 states and 352 transitions. [2018-06-22 01:52:28,325 INFO ]: Finished isEmpty. Found accepting run of length 66 [2018-06-22 01:52:28,325 INFO ]: Found error trace [2018-06-22 01:52:28,325 INFO ]: trace histogram [5, 5, 5, 5, 4, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:28,326 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:28,326 INFO ]: Analyzing trace with hash -807727976, now seen corresponding path program 1 times [2018-06-22 01:52:28,326 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:28,326 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:28,326 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:28,326 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:28,326 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:28,344 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:28,442 INFO ]: Checked inductivity of 86 backedges. 38 proven. 2 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2018-06-22 01:52:28,442 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:52:28,442 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:52:28,453 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:28,584 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:28,591 INFO ]: Computing forward predicates... [2018-06-22 01:52:28,809 INFO ]: Checked inductivity of 86 backedges. 31 proven. 12 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2018-06-22 01:52:28,830 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:52:28,830 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2018-06-22 01:52:28,830 INFO ]: Interpolant automaton has 16 states [2018-06-22 01:52:28,830 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 01:52:28,831 INFO ]: CoverageRelationStatistics Valid=30, Invalid=210, Unknown=0, NotChecked=0, Total=240 [2018-06-22 01:52:28,831 INFO ]: Start difference. First operand 227 states and 352 transitions. Second operand 16 states. [2018-06-22 01:52:39,936 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:52:39,936 INFO ]: Finished difference Result 1391 states and 4127 transitions. [2018-06-22 01:52:39,937 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 147 states. [2018-06-22 01:52:39,937 INFO ]: Start accepts. Automaton has 16 states. Word has length 65 [2018-06-22 01:52:39,938 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:52:39,981 INFO ]: With dead ends: 1391 [2018-06-22 01:52:39,981 INFO ]: Without dead ends: 1026 [2018-06-22 01:52:39,987 INFO ]: 0 DeclaredPredicates, 281 GetRequests, 127 SyntacticMatches, 0 SemanticMatches, 154 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9387 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=2324, Invalid=21856, Unknown=0, NotChecked=0, Total=24180 [2018-06-22 01:52:39,988 INFO ]: Start minimizeSevpa. Operand 1026 states. [2018-06-22 01:52:40,177 INFO ]: Finished minimizeSevpa. Reduced states from 1026 to 388. [2018-06-22 01:52:40,177 INFO ]: Start removeUnreachable. Operand 388 states. [2018-06-22 01:52:40,188 INFO ]: Finished removeUnreachable. Reduced from 388 states to 388 states and 684 transitions. [2018-06-22 01:52:40,188 INFO ]: Start accepts. Automaton has 388 states and 684 transitions. Word has length 65 [2018-06-22 01:52:40,189 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:52:40,189 INFO ]: Abstraction has 388 states and 684 transitions. [2018-06-22 01:52:40,189 INFO ]: Interpolant automaton has 16 states. [2018-06-22 01:52:40,189 INFO ]: Start isEmpty. Operand 388 states and 684 transitions. [2018-06-22 01:52:40,203 INFO ]: Finished isEmpty. Found accepting run of length 82 [2018-06-22 01:52:40,204 INFO ]: Found error trace [2018-06-22 01:52:40,204 INFO ]: trace histogram [6, 6, 6, 6, 5, 5, 4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:40,204 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:40,204 INFO ]: Analyzing trace with hash -2015460926, now seen corresponding path program 1 times [2018-06-22 01:52:40,204 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:40,204 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:40,205 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:40,205 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:40,205 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:40,219 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:40,292 INFO ]: Checked inductivity of 145 backedges. 33 proven. 34 refuted. 0 times theorem prover too weak. 78 trivial. 0 not checked. [2018-06-22 01:52:40,293 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:52:40,293 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:52:40,300 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:40,447 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:40,455 INFO ]: Computing forward predicates... [2018-06-22 01:52:40,471 INFO ]: Checked inductivity of 145 backedges. 77 proven. 0 refuted. 0 times theorem prover too weak. 68 trivial. 0 not checked. [2018-06-22 01:52:40,506 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 01:52:40,506 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2018-06-22 01:52:40,506 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:52:40,506 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:52:40,506 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:52:40,507 INFO ]: Start difference. First operand 388 states and 684 transitions. Second operand 4 states. [2018-06-22 01:52:41,342 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:52:41,342 INFO ]: Finished difference Result 414 states and 730 transitions. [2018-06-22 01:52:41,342 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:52:41,342 INFO ]: Start accepts. Automaton has 4 states. Word has length 81 [2018-06-22 01:52:41,343 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:52:41,353 INFO ]: With dead ends: 414 [2018-06-22 01:52:41,353 INFO ]: Without dead ends: 384 [2018-06-22 01:52:41,354 INFO ]: 0 DeclaredPredicates, 86 GetRequests, 83 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:52:41,355 INFO ]: Start minimizeSevpa. Operand 384 states. [2018-06-22 01:52:41,382 INFO ]: Finished minimizeSevpa. Reduced states from 384 to 384. [2018-06-22 01:52:41,382 INFO ]: Start removeUnreachable. Operand 384 states. [2018-06-22 01:52:41,389 INFO ]: Finished removeUnreachable. Reduced from 384 states to 384 states and 675 transitions. [2018-06-22 01:52:41,389 INFO ]: Start accepts. Automaton has 384 states and 675 transitions. Word has length 81 [2018-06-22 01:52:41,389 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:52:41,389 INFO ]: Abstraction has 384 states and 675 transitions. [2018-06-22 01:52:41,389 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:52:41,389 INFO ]: Start isEmpty. Operand 384 states and 675 transitions. [2018-06-22 01:52:41,397 INFO ]: Finished isEmpty. Found accepting run of length 96 [2018-06-22 01:52:41,397 INFO ]: Found error trace [2018-06-22 01:52:41,398 INFO ]: trace histogram [7, 7, 7, 7, 6, 5, 5, 5, 5, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:41,398 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:41,398 INFO ]: Analyzing trace with hash -1247167864, now seen corresponding path program 2 times [2018-06-22 01:52:41,398 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:41,398 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:41,398 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:41,398 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:41,398 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:41,434 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:41,869 INFO ]: Checked inductivity of 213 backedges. 58 proven. 48 refuted. 0 times theorem prover too weak. 107 trivial. 0 not checked. [2018-06-22 01:52:41,869 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:52:41,869 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:52:41,907 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:52:42,031 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:52:42,031 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:42,042 INFO ]: Computing forward predicates... [2018-06-22 01:52:42,202 INFO ]: Checked inductivity of 213 backedges. 58 proven. 48 refuted. 0 times theorem prover too weak. 107 trivial. 0 not checked. [2018-06-22 01:52:42,226 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:52:42,226 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 20 [2018-06-22 01:52:42,227 INFO ]: Interpolant automaton has 20 states [2018-06-22 01:52:42,227 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 01:52:42,227 INFO ]: CoverageRelationStatistics Valid=46, Invalid=334, Unknown=0, NotChecked=0, Total=380 [2018-06-22 01:52:42,227 INFO ]: Start difference. First operand 384 states and 675 transitions. Second operand 20 states. [2018-06-22 01:52:52,398 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:52:52,398 INFO ]: Finished difference Result 1785 states and 6711 transitions. [2018-06-22 01:52:52,398 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-06-22 01:52:52,398 INFO ]: Start accepts. Automaton has 20 states. Word has length 95 [2018-06-22 01:52:52,398 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:52:52,467 INFO ]: With dead ends: 1785 [2018-06-22 01:52:52,467 INFO ]: Without dead ends: 1785 [2018-06-22 01:52:52,469 INFO ]: 0 DeclaredPredicates, 271 GetRequests, 149 SyntacticMatches, 0 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5238 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=1607, Invalid=13645, Unknown=0, NotChecked=0, Total=15252 [2018-06-22 01:52:52,470 INFO ]: Start minimizeSevpa. Operand 1785 states. [2018-06-22 01:52:53,189 INFO ]: Finished minimizeSevpa. Reduced states from 1785 to 511. [2018-06-22 01:52:53,189 INFO ]: Start removeUnreachable. Operand 511 states. [2018-06-22 01:52:53,198 INFO ]: Finished removeUnreachable. Reduced from 511 states to 511 states and 938 transitions. [2018-06-22 01:52:53,198 INFO ]: Start accepts. Automaton has 511 states and 938 transitions. Word has length 95 [2018-06-22 01:52:53,198 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:52:53,198 INFO ]: Abstraction has 511 states and 938 transitions. [2018-06-22 01:52:53,198 INFO ]: Interpolant automaton has 20 states. [2018-06-22 01:52:53,198 INFO ]: Start isEmpty. Operand 511 states and 938 transitions. [2018-06-22 01:52:53,213 INFO ]: Finished isEmpty. Found accepting run of length 105 [2018-06-22 01:52:53,213 INFO ]: Found error trace [2018-06-22 01:52:53,213 INFO ]: trace histogram [8, 8, 8, 8, 6, 5, 5, 5, 5, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:53,213 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:53,215 INFO ]: Analyzing trace with hash 1121032004, now seen corresponding path program 1 times [2018-06-22 01:52:53,215 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:53,215 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:53,216 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:53,216 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:52:53,216 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:53,254 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:54,470 INFO ]: Checked inductivity of 259 backedges. 67 proven. 71 refuted. 0 times theorem prover too weak. 121 trivial. 0 not checked. [2018-06-22 01:52:54,470 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:52:54,470 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:52:54,476 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:54,628 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:54,633 INFO ]: Computing forward predicates... [2018-06-22 01:52:54,655 INFO ]: Checked inductivity of 259 backedges. 121 proven. 0 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2018-06-22 01:52:54,682 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 01:52:54,683 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [15] total 16 [2018-06-22 01:52:54,683 INFO ]: Interpolant automaton has 16 states [2018-06-22 01:52:54,683 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 01:52:54,683 INFO ]: CoverageRelationStatistics Valid=29, Invalid=211, Unknown=0, NotChecked=0, Total=240 [2018-06-22 01:52:54,683 INFO ]: Start difference. First operand 511 states and 938 transitions. Second operand 16 states. [2018-06-22 01:52:58,045 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:52:58,045 INFO ]: Finished difference Result 1165 states and 3246 transitions. [2018-06-22 01:52:58,046 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-06-22 01:52:58,046 INFO ]: Start accepts. Automaton has 16 states. Word has length 104 [2018-06-22 01:52:58,046 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:52:58,078 INFO ]: With dead ends: 1165 [2018-06-22 01:52:58,078 INFO ]: Without dead ends: 1165 [2018-06-22 01:52:58,079 INFO ]: 0 DeclaredPredicates, 199 GetRequests, 136 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1106 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=467, Invalid=3693, Unknown=0, NotChecked=0, Total=4160 [2018-06-22 01:52:58,080 INFO ]: Start minimizeSevpa. Operand 1165 states. [2018-06-22 01:52:58,262 INFO ]: Finished minimizeSevpa. Reduced states from 1165 to 523. [2018-06-22 01:52:58,262 INFO ]: Start removeUnreachable. Operand 523 states. [2018-06-22 01:52:58,270 INFO ]: Finished removeUnreachable. Reduced from 523 states to 523 states and 965 transitions. [2018-06-22 01:52:58,271 INFO ]: Start accepts. Automaton has 523 states and 965 transitions. Word has length 104 [2018-06-22 01:52:58,271 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:52:58,271 INFO ]: Abstraction has 523 states and 965 transitions. [2018-06-22 01:52:58,271 INFO ]: Interpolant automaton has 16 states. [2018-06-22 01:52:58,271 INFO ]: Start isEmpty. Operand 523 states and 965 transitions. [2018-06-22 01:52:58,286 INFO ]: Finished isEmpty. Found accepting run of length 120 [2018-06-22 01:52:58,286 INFO ]: Found error trace [2018-06-22 01:52:58,286 INFO ]: trace histogram [9, 9, 9, 9, 7, 6, 6, 6, 6, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:52:58,286 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:52:58,287 INFO ]: Analyzing trace with hash 936005750, now seen corresponding path program 2 times [2018-06-22 01:52:58,287 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:52:58,287 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:52:58,287 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:58,287 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:52:58,287 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:52:58,346 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:59,286 WARN ]: Spent 196.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 01:52:59,502 INFO ]: Checked inductivity of 355 backedges. 143 proven. 18 refuted. 0 times theorem prover too weak. 194 trivial. 0 not checked. [2018-06-22 01:52:59,502 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:52:59,502 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:52:59,510 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:52:59,710 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:52:59,710 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:52:59,725 INFO ]: Computing forward predicates... [2018-06-22 01:52:59,884 INFO ]: Checked inductivity of 355 backedges. 193 proven. 6 refuted. 0 times theorem prover too weak. 156 trivial. 0 not checked. [2018-06-22 01:52:59,914 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:52:59,914 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 15 [2018-06-22 01:52:59,914 INFO ]: Interpolant automaton has 15 states [2018-06-22 01:52:59,914 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 01:52:59,915 INFO ]: CoverageRelationStatistics Valid=32, Invalid=178, Unknown=0, NotChecked=0, Total=210 [2018-06-22 01:52:59,915 INFO ]: Start difference. First operand 523 states and 965 transitions. Second operand 15 states. [2018-06-22 01:53:01,175 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:53:01,175 INFO ]: Finished difference Result 817 states and 1619 transitions. [2018-06-22 01:53:01,176 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-22 01:53:01,176 INFO ]: Start accepts. Automaton has 15 states. Word has length 119 [2018-06-22 01:53:01,176 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:53:01,192 INFO ]: With dead ends: 817 [2018-06-22 01:53:01,192 INFO ]: Without dead ends: 817 [2018-06-22 01:53:01,192 INFO ]: 0 DeclaredPredicates, 148 GetRequests, 123 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=119, Invalid=583, Unknown=0, NotChecked=0, Total=702 [2018-06-22 01:53:01,192 INFO ]: Start minimizeSevpa. Operand 817 states. [2018-06-22 01:53:01,252 INFO ]: Finished minimizeSevpa. Reduced states from 817 to 589. [2018-06-22 01:53:01,252 INFO ]: Start removeUnreachable. Operand 589 states. [2018-06-22 01:53:01,264 INFO ]: Finished removeUnreachable. Reduced from 589 states to 589 states and 1099 transitions. [2018-06-22 01:53:01,264 INFO ]: Start accepts. Automaton has 589 states and 1099 transitions. Word has length 119 [2018-06-22 01:53:01,264 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:53:01,264 INFO ]: Abstraction has 589 states and 1099 transitions. [2018-06-22 01:53:01,264 INFO ]: Interpolant automaton has 15 states. [2018-06-22 01:53:01,264 INFO ]: Start isEmpty. Operand 589 states and 1099 transitions. [2018-06-22 01:53:01,285 INFO ]: Finished isEmpty. Found accepting run of length 121 [2018-06-22 01:53:01,286 INFO ]: Found error trace [2018-06-22 01:53:01,287 INFO ]: trace histogram [9, 9, 9, 9, 7, 6, 6, 6, 6, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:53:01,287 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:53:01,287 INFO ]: Analyzing trace with hash -2030396783, now seen corresponding path program 1 times [2018-06-22 01:53:01,287 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:53:01,287 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:53:01,288 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:53:01,288 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:53:01,288 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:53:01,347 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:53:02,174 INFO ]: Checked inductivity of 368 backedges. 141 proven. 26 refuted. 0 times theorem prover too weak. 201 trivial. 0 not checked. [2018-06-22 01:53:02,174 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:53:02,174 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:53:02,181 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:53:02,374 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:53:02,384 INFO ]: Computing forward predicates... [2018-06-22 01:53:02,593 INFO ]: Checked inductivity of 368 backedges. 84 proven. 113 refuted. 0 times theorem prover too weak. 171 trivial. 0 not checked. [2018-06-22 01:53:02,620 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:53:02,620 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 15] total 25 [2018-06-22 01:53:02,620 INFO ]: Interpolant automaton has 25 states [2018-06-22 01:53:02,620 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-22 01:53:02,621 INFO ]: CoverageRelationStatistics Valid=50, Invalid=550, Unknown=0, NotChecked=0, Total=600 [2018-06-22 01:53:02,621 INFO ]: Start difference. First operand 589 states and 1099 transitions. Second operand 25 states. [2018-06-22 01:53:07,460 WARN ]: Spent 146.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 26 [2018-06-22 01:53:08,682 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 27 Received shutdown request... [2018-06-22 01:53:13,697 WARN ]: Removed 7 from assertion stack [2018-06-22 01:53:13,697 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 270 states. [2018-06-22 01:53:13,698 WARN ]: Verification canceled [2018-06-22 01:53:13,703 WARN ]: Timeout [2018-06-22 01:53:13,703 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 01:53:13 BoogieIcfgContainer [2018-06-22 01:53:13,703 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 01:53:13,704 INFO ]: Toolchain (without parser) took 56894.39 ms. Allocated memory was 307.8 MB in the beginning and 893.4 MB in the end (delta: 585.6 MB). Free memory was 246.2 MB in the beginning and 453.9 MB in the end (delta: -207.7 MB). Peak memory consumption was 377.9 MB. Max. memory is 3.6 GB. [2018-06-22 01:53:13,704 INFO ]: SmtParser took 0.11 ms. Allocated memory is still 307.8 MB. Free memory is still 272.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 01:53:13,705 INFO ]: ChcToBoogie took 150.39 ms. Allocated memory is still 307.8 MB. Free memory was 246.2 MB in the beginning and 242.2 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:53:13,705 INFO ]: Boogie Preprocessor took 91.93 ms. Allocated memory is still 307.8 MB. Free memory was 242.2 MB in the beginning and 238.2 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:53:13,705 INFO ]: RCFGBuilder took 1265.50 ms. Allocated memory is still 307.8 MB. Free memory was 238.2 MB in the beginning and 202.3 MB in the end (delta: 36.0 MB). Peak memory consumption was 36.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:53:13,706 INFO ]: TraceAbstraction took 55376.98 ms. Allocated memory was 307.8 MB in the beginning and 893.4 MB in the end (delta: 585.6 MB). Free memory was 202.3 MB in the beginning and 453.9 MB in the end (delta: -251.7 MB). Peak memory consumption was 333.9 MB. Max. memory is 3.6 GB. [2018-06-22 01:53:13,708 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.11 ms. Allocated memory is still 307.8 MB. Free memory is still 272.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 150.39 ms. Allocated memory is still 307.8 MB. Free memory was 246.2 MB in the beginning and 242.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 91.93 ms. Allocated memory is still 307.8 MB. Free memory was 242.2 MB in the beginning and 238.2 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 1265.50 ms. Allocated memory is still 307.8 MB. Free memory was 238.2 MB in the beginning and 202.3 MB in the end (delta: 36.0 MB). Peak memory consumption was 36.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 55376.98 ms. Allocated memory was 307.8 MB in the beginning and 893.4 MB in the end (delta: 585.6 MB). Free memory was 202.3 MB in the beginning and 453.9 MB in the end (delta: -251.7 MB). Peak memory consumption was 333.9 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was constructing difference of abstraction (589states) and interpolant automaton (currently 270 states, 25 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 17. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 48 locations, 1 error locations. TIMEOUT Result, 55.3s OverallTime, 15 OverallIterations, 9 TraceHistogramMax, 44.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 2179 SDtfs, 3383 SDslu, 10098 SDs, 0 SdLazy, 30864 SolverSat, 6155 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 26.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1625 GetRequests, 929 SyntacticMatches, 1 SemanticMatches, 694 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49913 ImplicationChecksByTransitivity, 18.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=589occurred in iteration=14, 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: 1.5s AutomataMinimizationTime, 14 MinimizatonAttempts, 3287 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 1.3s SatisfiabilityAnalysisTime, 6.6s InterpolantComputationTime, 1598 NumberOfCodeBlocks, 1598 NumberOfCodeBlocksAsserted, 27 NumberOfCheckSat, 1573 ConstructedInterpolants, 0 QuantifiedInterpolants, 221063 SizeOfPredicates, 48 NumberOfNonLiveVariables, 8589 ConjunctsInSsa, 139 ConjunctsInUnsatCore, 25 InterpolantComputations, 9 PerfectInterpolantSequences, 2734/3124 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/Ackermann02.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_01-53-13-717.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/Ackermann02.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_01-53-13-717.csv Completed graceful shutdown