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/mochi/gib.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 01:47:14,041 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 01:47:14,043 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 01:47:14,057 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 01:47:14,057 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 01:47:14,058 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 01:47:14,059 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 01:47:14,060 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 01:47:14,062 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 01:47:14,063 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 01:47:14,063 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 01:47:14,064 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 01:47:14,065 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 01:47:14,067 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 01:47:14,068 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 01:47:14,069 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 01:47:14,072 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 01:47:14,074 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 01:47:14,081 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 01:47:14,082 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 01:47:14,084 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 01:47:14,086 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 01:47:14,086 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 01:47:14,086 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 01:47:14,087 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 01:47:14,088 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 01:47:14,088 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 01:47:14,089 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 01:47:14,090 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 01:47:14,090 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 01:47:14,091 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 01:47:14,091 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 01:47:14,091 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 01:47:14,092 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 01:47:14,093 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 01:47:14,093 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:47:14,114 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 01:47:14,114 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 01:47:14,114 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 01:47:14,114 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 01:47:14,115 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 01:47:14,116 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 01:47:14,116 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 01:47:14,116 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 01:47:14,116 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 01:47:14,116 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 01:47:14,117 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 01:47:14,117 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 01:47:14,117 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 01:47:14,117 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 01:47:14,117 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 01:47:14,117 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 01:47:14,118 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 01:47:14,119 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 01:47:14,119 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 01:47:14,164 INFO ]: Repository-Root is: /tmp [2018-06-22 01:47:14,179 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 01:47:14,186 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 01:47:14,187 INFO ]: Initializing SmtParser... [2018-06-22 01:47:14,188 INFO ]: SmtParser initialized [2018-06-22 01:47:14,188 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/hopv/lia/mochi/gib.smt2 [2018-06-22 01:47:14,189 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:47:14,280 INFO ]: Executing SMT file /storage/chc-comp/hopv/lia/mochi/gib.smt2 unknown [2018-06-22 01:47:14,472 INFO ]: Succesfully executed SMT file /storage/chc-comp/hopv/lia/mochi/gib.smt2 [2018-06-22 01:47:14,476 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 01:47:14,482 INFO ]: Walking toolchain with 4 elements. [2018-06-22 01:47:14,482 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 01:47:14,483 INFO ]: Initializing ChcToBoogie... [2018-06-22 01:47:14,483 INFO ]: ChcToBoogie initialized [2018-06-22 01:47:14,487 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:47:14" (1/1) ... [2018-06-22 01:47:14,542 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:47:14 Unit [2018-06-22 01:47:14,542 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 01:47:14,543 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 01:47:14,543 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 01:47:14,543 INFO ]: Boogie Preprocessor initialized [2018-06-22 01:47:14,566 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:47:14" (1/1) ... [2018-06-22 01:47:14,566 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:47:14" (1/1) ... [2018-06-22 01:47:14,572 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:47:14" (1/1) ... [2018-06-22 01:47:14,572 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:47:14" (1/1) ... [2018-06-22 01:47:14,575 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:47:14" (1/1) ... [2018-06-22 01:47:14,578 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:47:14" (1/1) ... [2018-06-22 01:47:14,579 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:47:14" (1/1) ... [2018-06-22 01:47:14,581 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 01:47:14,582 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 01:47:14,583 INFO ]: Initializing RCFGBuilder... [2018-06-22 01:47:14,583 INFO ]: RCFGBuilder initialized [2018-06-22 01:47:14,583 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:47:14" (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:47:14,596 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 01:47:14,596 INFO ]: Found specification of procedure gotoProc [2018-06-22 01:47:14,596 INFO ]: Found implementation of procedure gotoProc [2018-06-22 01:47:14,596 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 01:47:14,596 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 01:47:14,596 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:47:14,876 INFO ]: Using library mode [2018-06-22 01:47:14,876 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:47:14 BoogieIcfgContainer [2018-06-22 01:47:14,877 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 01:47:14,882 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 01:47:14,882 INFO ]: Initializing TraceAbstraction... [2018-06-22 01:47:14,884 INFO ]: TraceAbstraction initialized [2018-06-22 01:47:14,885 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:47:14" (1/3) ... [2018-06-22 01:47:14,885 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@610ed29c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 01:47:14, skipping insertion in model container [2018-06-22 01:47:14,885 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:47:14" (2/3) ... [2018-06-22 01:47:14,886 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@610ed29c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 01:47:14, skipping insertion in model container [2018-06-22 01:47:14,886 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:47:14" (3/3) ... [2018-06-22 01:47:14,887 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 01:47:14,893 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 01:47:14,899 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 01:47:14,933 INFO ]: Using default assertion order modulation [2018-06-22 01:47:14,934 INFO ]: Interprodecural is true [2018-06-22 01:47:14,934 INFO ]: Hoare is false [2018-06-22 01:47:14,934 INFO ]: Compute interpolants for FPandBP [2018-06-22 01:47:14,934 INFO ]: Backedges is TWOTRACK [2018-06-22 01:47:14,934 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 01:47:14,934 INFO ]: Difference is false [2018-06-22 01:47:14,934 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 01:47:14,934 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 01:47:14,947 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 01:47:14,957 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 01:47:14,957 INFO ]: Found error trace [2018-06-22 01:47:14,958 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:47:14,958 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:14,964 INFO ]: Analyzing trace with hash 1539992467, now seen corresponding path program 1 times [2018-06-22 01:47:14,966 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:14,966 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:15,001 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:15,001 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:47:15,001 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:15,033 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:15,115 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:47:15,117 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:47:15,117 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:47:15,119 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:47:15,129 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:47:15,130 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:47:15,132 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 01:47:15,268 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:15,268 INFO ]: Finished difference Result 19 states and 25 transitions. [2018-06-22 01:47:15,269 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:47:15,270 INFO ]: Start accepts. Automaton has 4 states. Word has length 7 [2018-06-22 01:47:15,270 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:15,278 INFO ]: With dead ends: 19 [2018-06-22 01:47:15,278 INFO ]: Without dead ends: 19 [2018-06-22 01:47:15,279 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 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:47:15,293 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 01:47:15,322 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 01:47:15,323 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 01:47:15,324 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 25 transitions. [2018-06-22 01:47:15,325 INFO ]: Start accepts. Automaton has 19 states and 25 transitions. Word has length 7 [2018-06-22 01:47:15,326 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:15,326 INFO ]: Abstraction has 19 states and 25 transitions. [2018-06-22 01:47:15,326 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:47:15,326 INFO ]: Start isEmpty. Operand 19 states and 25 transitions. [2018-06-22 01:47:15,329 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:47:15,329 INFO ]: Found error trace [2018-06-22 01:47:15,329 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:47:15,329 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:15,329 INFO ]: Analyzing trace with hash 528305941, now seen corresponding path program 1 times [2018-06-22 01:47:15,329 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:15,329 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:15,330 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:15,330 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:47:15,330 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:15,352 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:15,437 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:47:15,437 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:47:15,437 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:47:15,438 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:47:15,439 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:47:15,439 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:47:15,439 INFO ]: Start difference. First operand 19 states and 25 transitions. Second operand 3 states. [2018-06-22 01:47:15,575 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:15,575 INFO ]: Finished difference Result 29 states and 42 transitions. [2018-06-22 01:47:15,576 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:47:15,576 INFO ]: Start accepts. Automaton has 3 states. Word has length 8 [2018-06-22 01:47:15,576 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:15,579 INFO ]: With dead ends: 29 [2018-06-22 01:47:15,579 INFO ]: Without dead ends: 29 [2018-06-22 01:47:15,580 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:47:15,581 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 01:47:15,587 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 21. [2018-06-22 01:47:15,587 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 01:47:15,587 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 29 transitions. [2018-06-22 01:47:15,588 INFO ]: Start accepts. Automaton has 21 states and 29 transitions. Word has length 8 [2018-06-22 01:47:15,588 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:15,590 INFO ]: Abstraction has 21 states and 29 transitions. [2018-06-22 01:47:15,590 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:47:15,590 INFO ]: Start isEmpty. Operand 21 states and 29 transitions. [2018-06-22 01:47:15,591 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:47:15,591 INFO ]: Found error trace [2018-06-22 01:47:15,591 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:47:15,591 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:15,591 INFO ]: Analyzing trace with hash 528335732, now seen corresponding path program 1 times [2018-06-22 01:47:15,591 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:15,591 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:15,592 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:15,592 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:47:15,592 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:15,607 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:15,683 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:47:15,683 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:47:15,683 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:47:15,684 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:47:15,684 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:47:15,684 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:47:15,684 INFO ]: Start difference. First operand 21 states and 29 transitions. Second operand 3 states. [2018-06-22 01:47:15,750 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:15,750 INFO ]: Finished difference Result 25 states and 33 transitions. [2018-06-22 01:47:15,750 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:47:15,750 INFO ]: Start accepts. Automaton has 3 states. Word has length 8 [2018-06-22 01:47:15,751 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:15,751 INFO ]: With dead ends: 25 [2018-06-22 01:47:15,751 INFO ]: Without dead ends: 25 [2018-06-22 01:47:15,752 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:47:15,752 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 01:47:15,755 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 21. [2018-06-22 01:47:15,755 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 01:47:15,756 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 27 transitions. [2018-06-22 01:47:15,756 INFO ]: Start accepts. Automaton has 21 states and 27 transitions. Word has length 8 [2018-06-22 01:47:15,756 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:15,756 INFO ]: Abstraction has 21 states and 27 transitions. [2018-06-22 01:47:15,756 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:47:15,756 INFO ]: Start isEmpty. Operand 21 states and 27 transitions. [2018-06-22 01:47:15,757 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-22 01:47:15,757 INFO ]: Found error trace [2018-06-22 01:47:15,757 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:47:15,757 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:15,757 INFO ]: Analyzing trace with hash 1949983771, now seen corresponding path program 1 times [2018-06-22 01:47:15,757 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:15,757 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:15,758 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:15,758 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:47:15,758 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:15,793 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:16,150 INFO ]: Checked inductivity of 7 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:47:16,150 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:47:16,150 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:47:16,159 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:47:16,207 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:16,216 INFO ]: Computing forward predicates... [2018-06-22 01:47:16,327 INFO ]: Checked inductivity of 7 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:47:16,352 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:47:16,352 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2018-06-22 01:47:16,352 INFO ]: Interpolant automaton has 7 states [2018-06-22 01:47:16,352 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 01:47:16,352 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:47:16,352 INFO ]: Start difference. First operand 21 states and 27 transitions. Second operand 7 states. [2018-06-22 01:47:17,518 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:17,518 INFO ]: Finished difference Result 54 states and 95 transitions. [2018-06-22 01:47:17,519 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-06-22 01:47:17,519 INFO ]: Start accepts. Automaton has 7 states. Word has length 16 [2018-06-22 01:47:17,519 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:17,521 INFO ]: With dead ends: 54 [2018-06-22 01:47:17,521 INFO ]: Without dead ends: 41 [2018-06-22 01:47:17,521 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 56 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=90, Invalid=252, Unknown=0, NotChecked=0, Total=342 [2018-06-22 01:47:17,521 INFO ]: Start minimizeSevpa. Operand 41 states. [2018-06-22 01:47:17,530 INFO ]: Finished minimizeSevpa. Reduced states from 41 to 30. [2018-06-22 01:47:17,530 INFO ]: Start removeUnreachable. Operand 30 states. [2018-06-22 01:47:17,531 INFO ]: Finished removeUnreachable. Reduced from 30 states to 30 states and 44 transitions. [2018-06-22 01:47:17,531 INFO ]: Start accepts. Automaton has 30 states and 44 transitions. Word has length 16 [2018-06-22 01:47:17,531 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:17,531 INFO ]: Abstraction has 30 states and 44 transitions. [2018-06-22 01:47:17,531 INFO ]: Interpolant automaton has 7 states. [2018-06-22 01:47:17,531 INFO ]: Start isEmpty. Operand 30 states and 44 transitions. [2018-06-22 01:47:17,532 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-22 01:47:17,532 INFO ]: Found error trace [2018-06-22 01:47:17,532 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:47:17,532 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:17,532 INFO ]: Analyzing trace with hash 1950013562, now seen corresponding path program 1 times [2018-06-22 01:47:17,532 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:17,532 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:17,533 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:17,533 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:47:17,533 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:17,549 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:17,626 INFO ]: Checked inductivity of 7 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:47:17,626 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:47:17,626 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:47:17,633 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:47:17,667 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:17,669 INFO ]: Computing forward predicates... [2018-06-22 01:47:18,073 INFO ]: Checked inductivity of 7 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:47:18,104 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:47:18,104 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-22 01:47:18,104 INFO ]: Interpolant automaton has 13 states [2018-06-22 01:47:18,105 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 01:47:18,105 INFO ]: CoverageRelationStatistics Valid=28, Invalid=128, Unknown=0, NotChecked=0, Total=156 [2018-06-22 01:47:18,105 INFO ]: Start difference. First operand 30 states and 44 transitions. Second operand 13 states. [2018-06-22 01:47:18,826 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:18,826 INFO ]: Finished difference Result 53 states and 85 transitions. [2018-06-22 01:47:18,827 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-06-22 01:47:18,827 INFO ]: Start accepts. Automaton has 13 states. Word has length 16 [2018-06-22 01:47:18,827 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:18,828 INFO ]: With dead ends: 53 [2018-06-22 01:47:18,829 INFO ]: Without dead ends: 53 [2018-06-22 01:47:18,829 INFO ]: 0 DeclaredPredicates, 36 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 105 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=167, Invalid=483, Unknown=0, NotChecked=0, Total=650 [2018-06-22 01:47:18,829 INFO ]: Start minimizeSevpa. Operand 53 states. [2018-06-22 01:47:18,838 INFO ]: Finished minimizeSevpa. Reduced states from 53 to 40. [2018-06-22 01:47:18,838 INFO ]: Start removeUnreachable. Operand 40 states. [2018-06-22 01:47:18,840 INFO ]: Finished removeUnreachable. Reduced from 40 states to 40 states and 69 transitions. [2018-06-22 01:47:18,840 INFO ]: Start accepts. Automaton has 40 states and 69 transitions. Word has length 16 [2018-06-22 01:47:18,840 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:18,840 INFO ]: Abstraction has 40 states and 69 transitions. [2018-06-22 01:47:18,840 INFO ]: Interpolant automaton has 13 states. [2018-06-22 01:47:18,840 INFO ]: Start isEmpty. Operand 40 states and 69 transitions. [2018-06-22 01:47:18,841 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-22 01:47:18,841 INFO ]: Found error trace [2018-06-22 01:47:18,841 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:47:18,841 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:18,842 INFO ]: Analyzing trace with hash -602143399, now seen corresponding path program 1 times [2018-06-22 01:47:18,842 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:18,842 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:18,842 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:18,842 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:47:18,842 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:18,855 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:18,996 INFO ]: Checked inductivity of 7 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:47:18,996 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:47:18,996 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:47:19,006 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:47:19,022 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:19,024 INFO ]: Computing forward predicates... [2018-06-22 01:47:19,051 INFO ]: Checked inductivity of 7 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:47:19,086 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:47:19,086 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2018-06-22 01:47:19,086 INFO ]: Interpolant automaton has 7 states [2018-06-22 01:47:19,086 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 01:47:19,086 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:47:19,086 INFO ]: Start difference. First operand 40 states and 69 transitions. Second operand 7 states. [2018-06-22 01:47:19,728 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:19,728 INFO ]: Finished difference Result 52 states and 90 transitions. [2018-06-22 01:47:19,729 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 01:47:19,729 INFO ]: Start accepts. Automaton has 7 states. Word has length 16 [2018-06-22 01:47:19,729 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:19,730 INFO ]: With dead ends: 52 [2018-06-22 01:47:19,730 INFO ]: Without dead ends: 41 [2018-06-22 01:47:19,731 INFO ]: 0 DeclaredPredicates, 31 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=62, Invalid=178, Unknown=0, NotChecked=0, Total=240 [2018-06-22 01:47:19,731 INFO ]: Start minimizeSevpa. Operand 41 states. [2018-06-22 01:47:19,736 INFO ]: Finished minimizeSevpa. Reduced states from 41 to 38. [2018-06-22 01:47:19,736 INFO ]: Start removeUnreachable. Operand 38 states. [2018-06-22 01:47:19,737 INFO ]: Finished removeUnreachable. Reduced from 38 states to 38 states and 59 transitions. [2018-06-22 01:47:19,737 INFO ]: Start accepts. Automaton has 38 states and 59 transitions. Word has length 16 [2018-06-22 01:47:19,737 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:19,737 INFO ]: Abstraction has 38 states and 59 transitions. [2018-06-22 01:47:19,737 INFO ]: Interpolant automaton has 7 states. [2018-06-22 01:47:19,737 INFO ]: Start isEmpty. Operand 38 states and 59 transitions. [2018-06-22 01:47:19,739 INFO ]: Finished isEmpty. Found accepting run of length 25 [2018-06-22 01:47:19,739 INFO ]: Found error trace [2018-06-22 01:47:19,739 INFO ]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2018-06-22 01:47:19,739 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:19,739 INFO ]: Analyzing trace with hash -1427070208, now seen corresponding path program 2 times [2018-06-22 01:47:19,739 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:19,739 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:19,740 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:19,740 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:47:19,740 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:19,763 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:19,908 INFO ]: Checked inductivity of 24 backedges. 4 proven. 14 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 01:47:19,935 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:47:19,936 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:47:19,942 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:47:19,977 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:47:19,977 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:19,980 INFO ]: Computing forward predicates... [2018-06-22 01:47:20,166 INFO ]: Checked inductivity of 24 backedges. 4 proven. 14 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 01:47:20,190 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:47:20,190 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2018-06-22 01:47:20,190 INFO ]: Interpolant automaton has 22 states [2018-06-22 01:47:20,191 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-22 01:47:20,191 INFO ]: CoverageRelationStatistics Valid=52, Invalid=410, Unknown=0, NotChecked=0, Total=462 [2018-06-22 01:47:20,191 INFO ]: Start difference. First operand 38 states and 59 transitions. Second operand 22 states. [2018-06-22 01:47:21,287 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:21,287 INFO ]: Finished difference Result 70 states and 117 transitions. [2018-06-22 01:47:21,288 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-06-22 01:47:21,288 INFO ]: Start accepts. Automaton has 22 states. Word has length 24 [2018-06-22 01:47:21,288 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:21,289 INFO ]: With dead ends: 70 [2018-06-22 01:47:21,289 INFO ]: Without dead ends: 70 [2018-06-22 01:47:21,290 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 276 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=264, Invalid=1296, Unknown=0, NotChecked=0, Total=1560 [2018-06-22 01:47:21,291 INFO ]: Start minimizeSevpa. Operand 70 states. [2018-06-22 01:47:21,301 INFO ]: Finished minimizeSevpa. Reduced states from 70 to 45. [2018-06-22 01:47:21,301 INFO ]: Start removeUnreachable. Operand 45 states. [2018-06-22 01:47:21,302 INFO ]: Finished removeUnreachable. Reduced from 45 states to 45 states and 77 transitions. [2018-06-22 01:47:21,302 INFO ]: Start accepts. Automaton has 45 states and 77 transitions. Word has length 24 [2018-06-22 01:47:21,302 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:21,302 INFO ]: Abstraction has 45 states and 77 transitions. [2018-06-22 01:47:21,302 INFO ]: Interpolant automaton has 22 states. [2018-06-22 01:47:21,302 INFO ]: Start isEmpty. Operand 45 states and 77 transitions. [2018-06-22 01:47:21,304 INFO ]: Finished isEmpty. Found accepting run of length 33 [2018-06-22 01:47:21,304 INFO ]: Found error trace [2018-06-22 01:47:21,304 INFO ]: trace histogram [4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1] [2018-06-22 01:47:21,305 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:21,305 INFO ]: Analyzing trace with hash -1602770298, now seen corresponding path program 3 times [2018-06-22 01:47:21,305 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:21,305 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:21,306 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:21,306 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:47:21,306 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:21,337 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:21,414 INFO ]: Checked inductivity of 51 backedges. 22 proven. 9 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2018-06-22 01:47:21,414 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:47:21,414 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:47:21,422 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:47:21,471 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 01:47:21,471 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:21,474 INFO ]: Computing forward predicates... [2018-06-22 01:47:21,952 INFO ]: Checked inductivity of 51 backedges. 6 proven. 31 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2018-06-22 01:47:21,987 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:47:21,987 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 16] total 23 [2018-06-22 01:47:21,987 INFO ]: Interpolant automaton has 23 states [2018-06-22 01:47:21,987 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 01:47:21,988 INFO ]: CoverageRelationStatistics Valid=45, Invalid=461, Unknown=0, NotChecked=0, Total=506 [2018-06-22 01:47:21,991 INFO ]: Start difference. First operand 45 states and 77 transitions. Second operand 23 states. [2018-06-22 01:47:25,681 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:25,760 INFO ]: Finished difference Result 132 states and 316 transitions. [2018-06-22 01:47:25,762 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2018-06-22 01:47:25,762 INFO ]: Start accepts. Automaton has 23 states. Word has length 32 [2018-06-22 01:47:25,762 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:25,773 INFO ]: With dead ends: 132 [2018-06-22 01:47:25,773 INFO ]: Without dead ends: 132 [2018-06-22 01:47:25,775 INFO ]: 0 DeclaredPredicates, 85 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 944 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=543, Invalid=4013, Unknown=0, NotChecked=0, Total=4556 [2018-06-22 01:47:25,777 INFO ]: Start minimizeSevpa. Operand 132 states. [2018-06-22 01:47:25,820 INFO ]: Finished minimizeSevpa. Reduced states from 132 to 71. [2018-06-22 01:47:25,820 INFO ]: Start removeUnreachable. Operand 71 states. [2018-06-22 01:47:25,822 INFO ]: Finished removeUnreachable. Reduced from 71 states to 71 states and 133 transitions. [2018-06-22 01:47:25,822 INFO ]: Start accepts. Automaton has 71 states and 133 transitions. Word has length 32 [2018-06-22 01:47:25,822 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:25,822 INFO ]: Abstraction has 71 states and 133 transitions. [2018-06-22 01:47:25,822 INFO ]: Interpolant automaton has 23 states. [2018-06-22 01:47:25,822 INFO ]: Start isEmpty. Operand 71 states and 133 transitions. [2018-06-22 01:47:25,831 INFO ]: Finished isEmpty. Found accepting run of length 41 [2018-06-22 01:47:25,831 INFO ]: Found error trace [2018-06-22 01:47:25,831 INFO ]: trace histogram [5, 5, 4, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1] [2018-06-22 01:47:25,831 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:25,831 INFO ]: Analyzing trace with hash 1166618314, now seen corresponding path program 4 times [2018-06-22 01:47:25,831 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:25,831 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:25,832 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:25,832 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:47:25,832 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:25,877 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:26,118 INFO ]: Checked inductivity of 88 backedges. 22 proven. 23 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2018-06-22 01:47:26,118 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:47:26,118 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) [2018-06-22 01:47:26,135 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:47:26,191 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:47:26,191 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:26,195 INFO ]: Computing forward predicates... [2018-06-22 01:47:26,506 INFO ]: Checked inductivity of 88 backedges. 34 proven. 30 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-06-22 01:47:26,533 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:47:26,533 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 13] total 18 [2018-06-22 01:47:26,533 INFO ]: Interpolant automaton has 18 states [2018-06-22 01:47:26,533 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-22 01:47:26,534 INFO ]: CoverageRelationStatistics Valid=43, Invalid=263, Unknown=0, NotChecked=0, Total=306 [2018-06-22 01:47:26,534 INFO ]: Start difference. First operand 71 states and 133 transitions. Second operand 18 states. [2018-06-22 01:47:27,609 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:27,610 INFO ]: Finished difference Result 103 states and 248 transitions. [2018-06-22 01:47:27,610 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-06-22 01:47:27,610 INFO ]: Start accepts. Automaton has 18 states. Word has length 40 [2018-06-22 01:47:27,610 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:27,612 INFO ]: With dead ends: 103 [2018-06-22 01:47:27,612 INFO ]: Without dead ends: 99 [2018-06-22 01:47:27,613 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 322 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=298, Invalid=1424, Unknown=0, NotChecked=0, Total=1722 [2018-06-22 01:47:27,613 INFO ]: Start minimizeSevpa. Operand 99 states. [2018-06-22 01:47:27,627 INFO ]: Finished minimizeSevpa. Reduced states from 99 to 53. [2018-06-22 01:47:27,627 INFO ]: Start removeUnreachable. Operand 53 states. [2018-06-22 01:47:27,628 INFO ]: Finished removeUnreachable. Reduced from 53 states to 53 states and 84 transitions. [2018-06-22 01:47:27,628 INFO ]: Start accepts. Automaton has 53 states and 84 transitions. Word has length 40 [2018-06-22 01:47:27,628 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:27,628 INFO ]: Abstraction has 53 states and 84 transitions. [2018-06-22 01:47:27,628 INFO ]: Interpolant automaton has 18 states. [2018-06-22 01:47:27,628 INFO ]: Start isEmpty. Operand 53 states and 84 transitions. [2018-06-22 01:47:27,629 INFO ]: Finished isEmpty. Found accepting run of length 33 [2018-06-22 01:47:27,629 INFO ]: Found error trace [2018-06-22 01:47:27,630 INFO ]: trace histogram [4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1] [2018-06-22 01:47:27,630 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:27,630 INFO ]: Analyzing trace with hash 140040037, now seen corresponding path program 5 times [2018-06-22 01:47:27,630 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:27,630 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:27,630 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:27,630 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:47:27,631 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:27,643 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:27,749 INFO ]: Checked inductivity of 51 backedges. 22 proven. 15 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2018-06-22 01:47:27,749 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:47:27,749 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:47:27,756 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:47:27,789 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2018-06-22 01:47:27,789 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:27,791 INFO ]: Computing forward predicates... [2018-06-22 01:47:27,816 INFO ]: Checked inductivity of 51 backedges. 29 proven. 5 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-06-22 01:47:27,843 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:47:27,843 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 13 [2018-06-22 01:47:27,844 INFO ]: Interpolant automaton has 13 states [2018-06-22 01:47:27,844 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 01:47:27,844 INFO ]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2018-06-22 01:47:27,845 INFO ]: Start difference. First operand 53 states and 84 transitions. Second operand 13 states. [2018-06-22 01:47:28,307 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:28,307 INFO ]: Finished difference Result 119 states and 234 transitions. [2018-06-22 01:47:28,307 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-06-22 01:47:28,307 INFO ]: Start accepts. Automaton has 13 states. Word has length 32 [2018-06-22 01:47:28,308 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:28,309 INFO ]: With dead ends: 119 [2018-06-22 01:47:28,309 INFO ]: Without dead ends: 119 [2018-06-22 01:47:28,310 INFO ]: 0 DeclaredPredicates, 73 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 196 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=301, Invalid=889, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 01:47:28,310 INFO ]: Start minimizeSevpa. Operand 119 states. [2018-06-22 01:47:28,320 INFO ]: Finished minimizeSevpa. Reduced states from 119 to 63. [2018-06-22 01:47:28,320 INFO ]: Start removeUnreachable. Operand 63 states. [2018-06-22 01:47:28,322 INFO ]: Finished removeUnreachable. Reduced from 63 states to 63 states and 103 transitions. [2018-06-22 01:47:28,322 INFO ]: Start accepts. Automaton has 63 states and 103 transitions. Word has length 32 [2018-06-22 01:47:28,322 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:28,322 INFO ]: Abstraction has 63 states and 103 transitions. [2018-06-22 01:47:28,322 INFO ]: Interpolant automaton has 13 states. [2018-06-22 01:47:28,322 INFO ]: Start isEmpty. Operand 63 states and 103 transitions. [2018-06-22 01:47:28,323 INFO ]: Finished isEmpty. Found accepting run of length 41 [2018-06-22 01:47:28,323 INFO ]: Found error trace [2018-06-22 01:47:28,323 INFO ]: trace histogram [5, 5, 4, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1] [2018-06-22 01:47:28,323 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:28,324 INFO ]: Analyzing trace with hash 551498475, now seen corresponding path program 6 times [2018-06-22 01:47:28,324 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:28,324 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:28,324 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:28,324 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:47:28,324 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:28,347 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:28,673 INFO ]: Checked inductivity of 88 backedges. 8 proven. 57 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2018-06-22 01:47:28,673 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:47:28,673 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:47:28,679 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:47:28,713 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2018-06-22 01:47:28,713 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:28,717 INFO ]: Computing forward predicates... [2018-06-22 01:47:29,601 INFO ]: Checked inductivity of 88 backedges. 10 proven. 53 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2018-06-22 01:47:29,620 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:47:29,620 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 19] total 35 [2018-06-22 01:47:29,621 INFO ]: Interpolant automaton has 35 states [2018-06-22 01:47:29,621 INFO ]: Constructing interpolant automaton starting with 35 interpolants. [2018-06-22 01:47:29,621 INFO ]: CoverageRelationStatistics Valid=89, Invalid=1101, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 01:47:29,621 INFO ]: Start difference. First operand 63 states and 103 transitions. Second operand 35 states. [2018-06-22 01:47:30,868 WARN ]: Spent 226.00 ms on a formula simplification that was a NOOP. DAG size: 31 [2018-06-22 01:47:33,085 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:33,085 INFO ]: Finished difference Result 139 states and 234 transitions. [2018-06-22 01:47:33,085 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-06-22 01:47:33,085 INFO ]: Start accepts. Automaton has 35 states. Word has length 40 [2018-06-22 01:47:33,086 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:33,087 INFO ]: With dead ends: 139 [2018-06-22 01:47:33,087 INFO ]: Without dead ends: 133 [2018-06-22 01:47:33,088 INFO ]: 0 DeclaredPredicates, 97 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 860 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=742, Invalid=3950, Unknown=0, NotChecked=0, Total=4692 [2018-06-22 01:47:33,089 INFO ]: Start minimizeSevpa. Operand 133 states. [2018-06-22 01:47:33,100 INFO ]: Finished minimizeSevpa. Reduced states from 133 to 77. [2018-06-22 01:47:33,100 INFO ]: Start removeUnreachable. Operand 77 states. [2018-06-22 01:47:33,102 INFO ]: Finished removeUnreachable. Reduced from 77 states to 77 states and 144 transitions. [2018-06-22 01:47:33,102 INFO ]: Start accepts. Automaton has 77 states and 144 transitions. Word has length 40 [2018-06-22 01:47:33,102 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:33,102 INFO ]: Abstraction has 77 states and 144 transitions. [2018-06-22 01:47:33,102 INFO ]: Interpolant automaton has 35 states. [2018-06-22 01:47:33,103 INFO ]: Start isEmpty. Operand 77 states and 144 transitions. [2018-06-22 01:47:33,105 INFO ]: Finished isEmpty. Found accepting run of length 57 [2018-06-22 01:47:33,105 INFO ]: Found error trace [2018-06-22 01:47:33,105 INFO ]: trace histogram [7, 7, 6, 6, 6, 6, 6, 4, 3, 1, 1, 1, 1, 1] [2018-06-22 01:47:33,105 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:33,105 INFO ]: Analyzing trace with hash -1756357930, now seen corresponding path program 7 times [2018-06-22 01:47:33,105 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:33,105 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:33,106 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:33,106 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:47:33,106 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:33,128 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:33,318 INFO ]: Checked inductivity of 192 backedges. 54 proven. 43 refuted. 0 times theorem prover too weak. 95 trivial. 0 not checked. [2018-06-22 01:47:33,318 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:47:33,318 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) [2018-06-22 01:47:33,332 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:47:33,371 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:33,375 INFO ]: Computing forward predicates... [2018-06-22 01:47:33,609 INFO ]: Checked inductivity of 192 backedges. 92 proven. 59 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2018-06-22 01:47:33,630 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:47:33,630 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 15] total 22 [2018-06-22 01:47:33,631 INFO ]: Interpolant automaton has 22 states [2018-06-22 01:47:33,631 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-22 01:47:33,631 INFO ]: CoverageRelationStatistics Valid=54, Invalid=408, Unknown=0, NotChecked=0, Total=462 [2018-06-22 01:47:33,631 INFO ]: Start difference. First operand 77 states and 144 transitions. Second operand 22 states. [2018-06-22 01:47:35,090 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:35,090 INFO ]: Finished difference Result 152 states and 361 transitions. [2018-06-22 01:47:35,090 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-06-22 01:47:35,091 INFO ]: Start accepts. Automaton has 22 states. Word has length 56 [2018-06-22 01:47:35,091 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:35,093 INFO ]: With dead ends: 152 [2018-06-22 01:47:35,093 INFO ]: Without dead ends: 144 [2018-06-22 01:47:35,094 INFO ]: 0 DeclaredPredicates, 102 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 777 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=538, Invalid=3002, Unknown=0, NotChecked=0, Total=3540 [2018-06-22 01:47:35,095 INFO ]: Start minimizeSevpa. Operand 144 states. [2018-06-22 01:47:35,115 INFO ]: Finished minimizeSevpa. Reduced states from 144 to 77. [2018-06-22 01:47:35,115 INFO ]: Start removeUnreachable. Operand 77 states. [2018-06-22 01:47:35,116 INFO ]: Finished removeUnreachable. Reduced from 77 states to 77 states and 129 transitions. [2018-06-22 01:47:35,116 INFO ]: Start accepts. Automaton has 77 states and 129 transitions. Word has length 56 [2018-06-22 01:47:35,117 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:35,117 INFO ]: Abstraction has 77 states and 129 transitions. [2018-06-22 01:47:35,117 INFO ]: Interpolant automaton has 22 states. [2018-06-22 01:47:35,117 INFO ]: Start isEmpty. Operand 77 states and 129 transitions. [2018-06-22 01:47:35,118 INFO ]: Finished isEmpty. Found accepting run of length 57 [2018-06-22 01:47:35,118 INFO ]: Found error trace [2018-06-22 01:47:35,118 INFO ]: trace histogram [7, 7, 6, 6, 6, 6, 6, 4, 3, 1, 1, 1, 1, 1] [2018-06-22 01:47:35,119 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:35,119 INFO ]: Analyzing trace with hash -1160635818, now seen corresponding path program 8 times [2018-06-22 01:47:35,119 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:35,119 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:35,119 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:35,119 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:47:35,119 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:35,138 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:36,136 INFO ]: Checked inductivity of 192 backedges. 88 proven. 27 refuted. 0 times theorem prover too weak. 77 trivial. 0 not checked. [2018-06-22 01:47:36,136 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:47:36,136 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:47:36,143 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:47:36,201 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:47:36,201 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:36,206 INFO ]: Computing forward predicates... [2018-06-22 01:47:36,289 INFO ]: Checked inductivity of 192 backedges. 68 proven. 70 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2018-06-22 01:47:36,334 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:47:36,334 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 18 [2018-06-22 01:47:36,335 INFO ]: Interpolant automaton has 18 states [2018-06-22 01:47:36,335 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-22 01:47:36,335 INFO ]: CoverageRelationStatistics Valid=43, Invalid=263, Unknown=0, NotChecked=0, Total=306 [2018-06-22 01:47:36,335 INFO ]: Start difference. First operand 77 states and 129 transitions. Second operand 18 states. [2018-06-22 01:47:36,776 WARN ]: Spent 139.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 13 [2018-06-22 01:47:38,960 WARN ]: Spent 100.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-22 01:47:39,290 WARN ]: Spent 120.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 01:47:39,661 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:39,661 INFO ]: Finished difference Result 178 states and 348 transitions. [2018-06-22 01:47:39,661 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2018-06-22 01:47:39,661 INFO ]: Start accepts. Automaton has 18 states. Word has length 56 [2018-06-22 01:47:39,661 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:39,665 INFO ]: With dead ends: 178 [2018-06-22 01:47:39,665 INFO ]: Without dead ends: 178 [2018-06-22 01:47:39,669 INFO ]: 0 DeclaredPredicates, 120 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1302 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=816, Invalid=3876, Unknown=0, NotChecked=0, Total=4692 [2018-06-22 01:47:39,669 INFO ]: Start minimizeSevpa. Operand 178 states. [2018-06-22 01:47:39,680 INFO ]: Finished minimizeSevpa. Reduced states from 178 to 98. [2018-06-22 01:47:39,680 INFO ]: Start removeUnreachable. Operand 98 states. [2018-06-22 01:47:39,686 INFO ]: Finished removeUnreachable. Reduced from 98 states to 98 states and 176 transitions. [2018-06-22 01:47:39,687 INFO ]: Start accepts. Automaton has 98 states and 176 transitions. Word has length 56 [2018-06-22 01:47:39,687 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:39,687 INFO ]: Abstraction has 98 states and 176 transitions. [2018-06-22 01:47:39,687 INFO ]: Interpolant automaton has 18 states. [2018-06-22 01:47:39,687 INFO ]: Start isEmpty. Operand 98 states and 176 transitions. [2018-06-22 01:47:39,688 INFO ]: Finished isEmpty. Found accepting run of length 65 [2018-06-22 01:47:39,688 INFO ]: Found error trace [2018-06-22 01:47:39,688 INFO ]: trace histogram [8, 8, 7, 7, 7, 7, 7, 5, 3, 1, 1, 1, 1, 1] [2018-06-22 01:47:39,688 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:39,689 INFO ]: Analyzing trace with hash 897992924, now seen corresponding path program 9 times [2018-06-22 01:47:39,689 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:39,689 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:39,689 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:39,689 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:47:39,689 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:39,728 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:40,405 INFO ]: Checked inductivity of 259 backedges. 14 proven. 174 refuted. 0 times theorem prover too weak. 71 trivial. 0 not checked. [2018-06-22 01:47:40,405 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:47:40,405 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:47:40,413 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:47:40,467 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2018-06-22 01:47:40,467 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:40,472 INFO ]: Computing forward predicates... [2018-06-22 01:47:41,791 INFO ]: Checked inductivity of 259 backedges. 18 proven. 160 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2018-06-22 01:47:41,811 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:47:41,812 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 25] total 48 [2018-06-22 01:47:41,812 INFO ]: Interpolant automaton has 48 states [2018-06-22 01:47:41,812 INFO ]: Constructing interpolant automaton starting with 48 interpolants. [2018-06-22 01:47:41,813 INFO ]: CoverageRelationStatistics Valid=122, Invalid=2134, Unknown=0, NotChecked=0, Total=2256 [2018-06-22 01:47:41,813 INFO ]: Start difference. First operand 98 states and 176 transitions. Second operand 48 states. [2018-06-22 01:47:45,462 WARN ]: Spent 227.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 40 [2018-06-22 01:47:46,228 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:46,229 INFO ]: Finished difference Result 220 states and 407 transitions. [2018-06-22 01:47:46,230 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2018-06-22 01:47:46,230 INFO ]: Start accepts. Automaton has 48 states. Word has length 64 [2018-06-22 01:47:46,231 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:46,233 INFO ]: With dead ends: 220 [2018-06-22 01:47:46,233 INFO ]: Without dead ends: 205 [2018-06-22 01:47:46,236 INFO ]: 0 DeclaredPredicates, 141 GetRequests, 55 SyntacticMatches, 1 SemanticMatches, 85 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1363 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=936, Invalid=6546, Unknown=0, NotChecked=0, Total=7482 [2018-06-22 01:47:46,236 INFO ]: Start minimizeSevpa. Operand 205 states. [2018-06-22 01:47:46,252 INFO ]: Finished minimizeSevpa. Reduced states from 205 to 129. [2018-06-22 01:47:46,290 INFO ]: Start removeUnreachable. Operand 129 states. [2018-06-22 01:47:46,294 INFO ]: Finished removeUnreachable. Reduced from 129 states to 129 states and 280 transitions. [2018-06-22 01:47:46,294 INFO ]: Start accepts. Automaton has 129 states and 280 transitions. Word has length 64 [2018-06-22 01:47:46,295 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:46,295 INFO ]: Abstraction has 129 states and 280 transitions. [2018-06-22 01:47:46,295 INFO ]: Interpolant automaton has 48 states. [2018-06-22 01:47:46,295 INFO ]: Start isEmpty. Operand 129 states and 280 transitions. [2018-06-22 01:47:46,298 INFO ]: Finished isEmpty. Found accepting run of length 89 [2018-06-22 01:47:46,298 INFO ]: Found error trace [2018-06-22 01:47:46,298 INFO ]: trace histogram [11, 11, 10, 10, 10, 10, 10, 7, 4, 1, 1, 1, 1, 1] [2018-06-22 01:47:46,298 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:46,298 INFO ]: Analyzing trace with hash -1240752819, now seen corresponding path program 10 times [2018-06-22 01:47:46,298 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:46,298 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:46,299 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:46,299 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:47:46,299 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:46,336 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:46,536 INFO ]: Checked inductivity of 520 backedges. 88 proven. 100 refuted. 0 times theorem prover too weak. 332 trivial. 0 not checked. [2018-06-22 01:47:46,536 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:47:46,537 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:47:46,547 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:47:46,603 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:47:46,603 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:46,608 INFO ]: Computing forward predicates... [2018-06-22 01:47:46,815 INFO ]: Checked inductivity of 520 backedges. 240 proven. 170 refuted. 0 times theorem prover too weak. 110 trivial. 0 not checked. [2018-06-22 01:47:46,835 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:47:46,835 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 17] total 23 [2018-06-22 01:47:46,835 INFO ]: Interpolant automaton has 23 states [2018-06-22 01:47:46,835 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 01:47:46,835 INFO ]: CoverageRelationStatistics Valid=59, Invalid=447, Unknown=0, NotChecked=0, Total=506 [2018-06-22 01:47:46,835 INFO ]: Start difference. First operand 129 states and 280 transitions. Second operand 23 states. [2018-06-22 01:47:48,426 WARN ]: Spent 113.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 01:47:49,384 WARN ]: Spent 176.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 14 [2018-06-22 01:47:51,702 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:47:51,702 INFO ]: Finished difference Result 343 states and 888 transitions. [2018-06-22 01:47:51,702 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 103 states. [2018-06-22 01:47:51,702 INFO ]: Start accepts. Automaton has 23 states. Word has length 88 [2018-06-22 01:47:51,702 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:47:51,712 INFO ]: With dead ends: 343 [2018-06-22 01:47:51,712 INFO ]: Without dead ends: 279 [2018-06-22 01:47:51,720 INFO ]: 0 DeclaredPredicates, 195 GetRequests, 79 SyntacticMatches, 0 SemanticMatches, 116 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4942 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=1900, Invalid=11906, Unknown=0, NotChecked=0, Total=13806 [2018-06-22 01:47:51,721 INFO ]: Start minimizeSevpa. Operand 279 states. [2018-06-22 01:47:51,750 INFO ]: Finished minimizeSevpa. Reduced states from 279 to 151. [2018-06-22 01:47:51,750 INFO ]: Start removeUnreachable. Operand 151 states. [2018-06-22 01:47:51,752 INFO ]: Finished removeUnreachable. Reduced from 151 states to 151 states and 303 transitions. [2018-06-22 01:47:51,752 INFO ]: Start accepts. Automaton has 151 states and 303 transitions. Word has length 88 [2018-06-22 01:47:51,753 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:47:51,753 INFO ]: Abstraction has 151 states and 303 transitions. [2018-06-22 01:47:51,753 INFO ]: Interpolant automaton has 23 states. [2018-06-22 01:47:51,753 INFO ]: Start isEmpty. Operand 151 states and 303 transitions. [2018-06-22 01:47:51,757 INFO ]: Finished isEmpty. Found accepting run of length 129 [2018-06-22 01:47:51,757 INFO ]: Found error trace [2018-06-22 01:47:51,757 INFO ]: trace histogram [16, 16, 15, 15, 15, 15, 15, 10, 6, 1, 1, 1, 1, 1] [2018-06-22 01:47:51,757 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:47:51,757 INFO ]: Analyzing trace with hash -1650814423, now seen corresponding path program 11 times [2018-06-22 01:47:51,757 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:47:51,757 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:47:51,758 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:51,758 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:47:51,758 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:47:51,786 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:52,034 INFO ]: Checked inductivity of 1155 backedges. 231 proven. 67 refuted. 0 times theorem prover too weak. 857 trivial. 0 not checked. [2018-06-22 01:47:52,034 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:47:52,034 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:47:52,040 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:47:52,138 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 15 check-sat command(s) [2018-06-22 01:47:52,138 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:47:52,143 INFO ]: Computing forward predicates... [2018-06-22 01:47:52,389 INFO ]: Checked inductivity of 1155 backedges. 553 proven. 257 refuted. 0 times theorem prover too weak. 345 trivial. 0 not checked. [2018-06-22 01:47:52,409 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:47:52,409 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 20] total 27 [2018-06-22 01:47:52,409 INFO ]: Interpolant automaton has 27 states [2018-06-22 01:47:52,410 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-22 01:47:52,410 INFO ]: CoverageRelationStatistics Valid=67, Invalid=635, Unknown=0, NotChecked=0, Total=702 [2018-06-22 01:47:52,410 INFO ]: Start difference. First operand 151 states and 303 transitions. Second operand 27 states. [2018-06-22 01:47:58,949 WARN ]: Spent 178.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 18 [2018-06-22 01:48:00,640 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:48:00,640 INFO ]: Finished difference Result 973 states and 2197 transitions. [2018-06-22 01:48:00,640 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 235 states. [2018-06-22 01:48:00,641 INFO ]: Start accepts. Automaton has 27 states. Word has length 128 [2018-06-22 01:48:00,641 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:48:00,678 INFO ]: With dead ends: 973 [2018-06-22 01:48:00,678 INFO ]: Without dead ends: 929 [2018-06-22 01:48:00,687 INFO ]: 0 DeclaredPredicates, 366 GetRequests, 115 SyntacticMatches, 0 SemanticMatches, 251 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26036 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=5827, Invalid=57929, Unknown=0, NotChecked=0, Total=63756 [2018-06-22 01:48:00,688 INFO ]: Start minimizeSevpa. Operand 929 states. [2018-06-22 01:48:00,751 INFO ]: Finished minimizeSevpa. Reduced states from 929 to 569. [2018-06-22 01:48:00,751 INFO ]: Start removeUnreachable. Operand 569 states. [2018-06-22 01:48:00,762 INFO ]: Finished removeUnreachable. Reduced from 569 states to 569 states and 1354 transitions. [2018-06-22 01:48:00,762 INFO ]: Start accepts. Automaton has 569 states and 1354 transitions. Word has length 128 [2018-06-22 01:48:00,763 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:48:00,763 INFO ]: Abstraction has 569 states and 1354 transitions. [2018-06-22 01:48:00,763 INFO ]: Interpolant automaton has 27 states. [2018-06-22 01:48:00,763 INFO ]: Start isEmpty. Operand 569 states and 1354 transitions. [2018-06-22 01:48:00,769 INFO ]: Finished isEmpty. Found accepting run of length 105 [2018-06-22 01:48:00,769 INFO ]: Found error trace [2018-06-22 01:48:00,769 INFO ]: trace histogram [13, 13, 12, 12, 12, 12, 12, 8, 5, 1, 1, 1, 1, 1] [2018-06-22 01:48:00,769 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:48:00,769 INFO ]: Analyzing trace with hash 1840652856, now seen corresponding path program 12 times [2018-06-22 01:48:00,769 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:48:00,769 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:48:00,770 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:48:00,770 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:48:00,770 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:48:00,820 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:48:01,719 INFO ]: Checked inductivity of 744 backedges. 24 proven. 510 refuted. 0 times theorem prover too weak. 210 trivial. 0 not checked. [2018-06-22 01:48:01,719 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:48:01,719 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:48:01,726 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:48:01,809 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 13 check-sat command(s) [2018-06-22 01:48:01,809 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:48:01,819 INFO ]: Computing forward predicates... [2018-06-22 01:48:04,106 INFO ]: Checked inductivity of 744 backedges. 38 proven. 462 refuted. 0 times theorem prover too weak. 244 trivial. 0 not checked. [2018-06-22 01:48:04,126 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:48:04,126 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [40, 34] total 67 [2018-06-22 01:48:04,126 INFO ]: Interpolant automaton has 67 states [2018-06-22 01:48:04,126 INFO ]: Constructing interpolant automaton starting with 67 interpolants. [2018-06-22 01:48:04,126 INFO ]: CoverageRelationStatistics Valid=179, Invalid=4243, Unknown=0, NotChecked=0, Total=4422 [2018-06-22 01:48:04,127 INFO ]: Start difference. First operand 569 states and 1354 transitions. Second operand 67 states. [2018-06-22 01:48:06,505 WARN ]: Spent 148.00 ms on a formula simplification that was a NOOP. DAG size: 26 [2018-06-22 01:48:10,200 WARN ]: Spent 328.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 40 [2018-06-22 01:48:11,252 WARN ]: Spent 109.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 50 [2018-06-22 01:48:12,423 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 49 [2018-06-22 01:48:13,060 WARN ]: Spent 194.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 24 [2018-06-22 01:48:13,722 WARN ]: Spent 123.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 50 [2018-06-22 01:48:13,864 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:48:13,864 INFO ]: Finished difference Result 1048 states and 2133 transitions. [2018-06-22 01:48:13,867 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-06-22 01:48:13,867 INFO ]: Start accepts. Automaton has 67 states. Word has length 104 [2018-06-22 01:48:13,867 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:48:13,888 INFO ]: With dead ends: 1048 [2018-06-22 01:48:13,888 INFO ]: Without dead ends: 993 [2018-06-22 01:48:13,890 INFO ]: 0 DeclaredPredicates, 216 GetRequests, 100 SyntacticMatches, 2 SemanticMatches, 114 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2253 ImplicationChecksByTransitivity, 8.1s TimeCoverageRelationStatistics Valid=1483, Invalid=11857, Unknown=0, NotChecked=0, Total=13340 [2018-06-22 01:48:13,890 INFO ]: Start minimizeSevpa. Operand 993 states. [2018-06-22 01:48:13,946 INFO ]: Finished minimizeSevpa. Reduced states from 993 to 609. [2018-06-22 01:48:13,946 INFO ]: Start removeUnreachable. Operand 609 states. [2018-06-22 01:48:13,964 INFO ]: Finished removeUnreachable. Reduced from 609 states to 609 states and 1551 transitions. [2018-06-22 01:48:13,964 INFO ]: Start accepts. Automaton has 609 states and 1551 transitions. Word has length 104 [2018-06-22 01:48:13,965 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:48:13,965 INFO ]: Abstraction has 609 states and 1551 transitions. [2018-06-22 01:48:13,965 INFO ]: Interpolant automaton has 67 states. [2018-06-22 01:48:13,965 INFO ]: Start isEmpty. Operand 609 states and 1551 transitions. [2018-06-22 01:48:13,972 INFO ]: Finished isEmpty. Found accepting run of length 145 [2018-06-22 01:48:13,972 INFO ]: Found error trace [2018-06-22 01:48:13,973 INFO ]: trace histogram [18, 18, 17, 17, 17, 17, 17, 11, 7, 1, 1, 1, 1, 1] [2018-06-22 01:48:13,973 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:48:13,973 INFO ]: Analyzing trace with hash -1111806572, now seen corresponding path program 13 times [2018-06-22 01:48:13,973 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:48:13,973 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:48:13,974 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:48:13,974 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:48:13,974 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:48:14,006 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:48:14,465 INFO ]: Checked inductivity of 1479 backedges. 416 proven. 130 refuted. 0 times theorem prover too weak. 933 trivial. 0 not checked. [2018-06-22 01:48:14,465 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:48:14,465 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:48:14,471 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:48:14,591 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:48:14,598 INFO ]: Computing forward predicates... [2018-06-22 01:48:14,929 INFO ]: Checked inductivity of 1479 backedges. 541 proven. 517 refuted. 0 times theorem prover too weak. 421 trivial. 0 not checked. [2018-06-22 01:48:14,949 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:48:14,949 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 19] total 27 [2018-06-22 01:48:14,949 INFO ]: Interpolant automaton has 27 states [2018-06-22 01:48:14,949 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-22 01:48:14,949 INFO ]: CoverageRelationStatistics Valid=79, Invalid=623, Unknown=0, NotChecked=0, Total=702 [2018-06-22 01:48:14,950 INFO ]: Start difference. First operand 609 states and 1551 transitions. Second operand 27 states. Received shutdown request... [2018-06-22 01:48:17,918 WARN ]: Removed 2 from assertion stack [2018-06-22 01:48:17,918 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2018-06-22 01:48:17,918 WARN ]: Verification canceled [2018-06-22 01:48:17,922 WARN ]: Timeout [2018-06-22 01:48:17,923 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 01:48:17 BoogieIcfgContainer [2018-06-22 01:48:17,923 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 01:48:17,923 INFO ]: Toolchain (without parser) took 63446.71 ms. Allocated memory was 307.8 MB in the beginning and 714.6 MB in the end (delta: 406.8 MB). Free memory was 263.1 MB in the beginning and 213.8 MB in the end (delta: 49.4 MB). Peak memory consumption was 456.2 MB. Max. memory is 3.6 GB. [2018-06-22 01:48:17,924 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 307.8 MB. Free memory is still 273.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 01:48:17,924 INFO ]: ChcToBoogie took 59.85 ms. Allocated memory is still 307.8 MB. Free memory was 263.1 MB in the beginning and 261.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:48:17,924 INFO ]: Boogie Preprocessor took 37.89 ms. Allocated memory is still 307.8 MB. Free memory was 261.1 MB in the beginning and 260.1 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-22 01:48:17,925 INFO ]: RCFGBuilder took 294.10 ms. Allocated memory is still 307.8 MB. Free memory was 260.1 MB in the beginning and 251.1 MB in the end (delta: 9.1 MB). Peak memory consumption was 9.1 MB. Max. memory is 3.6 GB. [2018-06-22 01:48:17,925 INFO ]: TraceAbstraction took 63045.02 ms. Allocated memory was 307.8 MB in the beginning and 714.6 MB in the end (delta: 406.8 MB). Free memory was 251.1 MB in the beginning and 213.8 MB in the end (delta: 37.3 MB). Peak memory consumption was 444.2 MB. Max. memory is 3.6 GB. [2018-06-22 01:48:17,928 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 307.8 MB. Free memory is still 273.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 59.85 ms. Allocated memory is still 307.8 MB. Free memory was 263.1 MB in the beginning and 261.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 37.89 ms. Allocated memory is still 307.8 MB. Free memory was 261.1 MB in the beginning and 260.1 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 294.10 ms. Allocated memory is still 307.8 MB. Free memory was 260.1 MB in the beginning and 251.1 MB in the end (delta: 9.1 MB). Peak memory consumption was 9.1 MB. Max. memory is 3.6 GB. * TraceAbstraction took 63045.02 ms. Allocated memory was 307.8 MB in the beginning and 714.6 MB in the end (delta: 406.8 MB). Free memory was 251.1 MB in the beginning and 213.8 MB in the end (delta: 37.3 MB). Peak memory consumption was 444.2 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 (609states) and interpolant automaton (currently 94 states, 27 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 9. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 13 locations, 1 error locations. TIMEOUT Result, 62.9s OverallTime, 18 OverallIterations, 18 TraceHistogramMax, 47.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 344 SDtfs, 1083 SDslu, 2606 SDs, 0 SdLazy, 19599 SolverSat, 5502 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 18.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1879 GetRequests, 770 SyntacticMatches, 3 SemanticMatches, 1105 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43816 ImplicationChecksByTransitivity, 36.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=609occurred in iteration=17, 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.4s AutomataMinimizationTime, 17 MinimizatonAttempts, 1378 StatesRemovedByMinimization, 16 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 1.0s SatisfiabilityAnalysisTime, 12.5s InterpolantComputationTime, 1735 NumberOfCodeBlocks, 1704 NumberOfCodeBlocksAsserted, 77 NumberOfCheckSat, 1702 ConstructedInterpolants, 35 QuantifiedInterpolants, 442983 SizeOfPredicates, 266 NumberOfNonLiveVariables, 5256 ConjunctsInSsa, 501 ConjunctsInUnsatCore, 33 InterpolantComputations, 3 PerfectInterpolantSequences, 6721/9728 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/gib.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_01-48-18-037.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/gib.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_01-48-18-037.csv Completed graceful shutdown