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_No_Goto.epf -i /storage/chc-comp/eldarica-misc/LIA/reve/020-horn.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 11:19:02,959 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 11:19:02,962 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 11:19:02,974 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 11:19:02,974 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 11:19:02,975 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 11:19:02,978 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 11:19:02,980 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 11:19:02,982 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 11:19:02,983 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 11:19:02,985 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 11:19:02,985 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 11:19:02,986 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 11:19:02,987 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 11:19:02,990 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 11:19:02,991 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 11:19:02,992 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 11:19:03,003 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 11:19:03,004 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 11:19:03,005 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 11:19:03,006 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 11:19:03,012 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 11:19:03,012 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 11:19:03,013 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 11:19:03,013 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 11:19:03,014 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 11:19:03,017 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 11:19:03,017 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 11:19:03,018 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 11:19:03,019 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 11:19:03,019 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 11:19:03,020 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 11:19:03,020 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 11:19:03,021 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 11:19:03,024 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 11:19:03,024 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 11:19:03,046 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 11:19:03,046 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 11:19:03,047 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 11:19:03,047 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 11:19:03,048 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 11:19:03,049 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 11:19:03,049 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 11:19:03,049 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 11:19:03,049 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 11:19:03,049 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 11:19:03,049 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 11:19:03,050 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 11:19:03,050 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 11:19:03,050 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 11:19:03,050 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 11:19:03,050 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 11:19:03,051 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 11:19:03,051 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 11:19:03,051 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 11:19:03,055 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 11:19:03,055 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 11:19:03,104 INFO ]: Repository-Root is: /tmp [2018-06-22 11:19:03,118 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 11:19:03,123 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 11:19:03,125 INFO ]: Initializing SmtParser... [2018-06-22 11:19:03,125 INFO ]: SmtParser initialized [2018-06-22 11:19:03,126 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/eldarica-misc/LIA/reve/020-horn.smt2 [2018-06-22 11:19:03,127 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 11:19:03,206 INFO ]: Executing SMT file /storage/chc-comp/eldarica-misc/LIA/reve/020-horn.smt2 unknown [2018-06-22 11:19:03,387 INFO ]: Succesfully executed SMT file /storage/chc-comp/eldarica-misc/LIA/reve/020-horn.smt2 [2018-06-22 11:19:03,392 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 11:19:03,399 INFO ]: Walking toolchain with 4 elements. [2018-06-22 11:19:03,400 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 11:19:03,400 INFO ]: Initializing ChcToBoogie... [2018-06-22 11:19:03,400 INFO ]: ChcToBoogie initialized [2018-06-22 11:19:03,403 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 11:19:03" (1/1) ... [2018-06-22 11:19:03,446 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 11:19:03 Unit [2018-06-22 11:19:03,446 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 11:19:03,446 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 11:19:03,446 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 11:19:03,446 INFO ]: Boogie Preprocessor initialized [2018-06-22 11:19:03,469 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 11:19:03" (1/1) ... [2018-06-22 11:19:03,470 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 11:19:03" (1/1) ... [2018-06-22 11:19:03,477 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 11:19:03" (1/1) ... [2018-06-22 11:19:03,477 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 11:19:03" (1/1) ... [2018-06-22 11:19:03,480 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 11:19:03" (1/1) ... [2018-06-22 11:19:03,484 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 11:19:03" (1/1) ... [2018-06-22 11:19:03,485 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 11:19:03" (1/1) ... [2018-06-22 11:19:03,487 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 11:19:03,487 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 11:19:03,487 INFO ]: Initializing RCFGBuilder... [2018-06-22 11:19:03,487 INFO ]: RCFGBuilder initialized [2018-06-22 11:19:03,488 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 11:19:03" (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 11:19:03,507 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 11:19:03,507 INFO ]: Found specification of procedure False [2018-06-22 11:19:03,507 INFO ]: Found implementation of procedure False [2018-06-22 11:19:03,507 INFO ]: Specification and implementation of procedure INV1 given in one single declaration [2018-06-22 11:19:03,507 INFO ]: Found specification of procedure INV1 [2018-06-22 11:19:03,507 INFO ]: Found implementation of procedure INV1 [2018-06-22 11:19:03,507 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 11:19:03,507 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 11:19:03,508 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 11:19:03,815 INFO ]: Using library mode [2018-06-22 11:19:03,815 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 11:19:03 BoogieIcfgContainer [2018-06-22 11:19:03,815 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 11:19:03,816 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 11:19:03,816 INFO ]: Initializing TraceAbstraction... [2018-06-22 11:19:03,819 INFO ]: TraceAbstraction initialized [2018-06-22 11:19:03,820 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 11:19:03" (1/3) ... [2018-06-22 11:19:03,821 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@395b7e31 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 11:19:03, skipping insertion in model container [2018-06-22 11:19:03,821 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 11:19:03" (2/3) ... [2018-06-22 11:19:03,821 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@395b7e31 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 11:19:03, skipping insertion in model container [2018-06-22 11:19:03,821 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 11:19:03" (3/3) ... [2018-06-22 11:19:03,829 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 11:19:03,849 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 11:19:03,858 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 11:19:03,897 INFO ]: Using default assertion order modulation [2018-06-22 11:19:03,898 INFO ]: Interprodecural is true [2018-06-22 11:19:03,898 INFO ]: Hoare is false [2018-06-22 11:19:03,898 INFO ]: Compute interpolants for FPandBP [2018-06-22 11:19:03,898 INFO ]: Backedges is TWOTRACK [2018-06-22 11:19:03,898 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 11:19:03,898 INFO ]: Difference is false [2018-06-22 11:19:03,898 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 11:19:03,898 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 11:19:03,913 INFO ]: Start isEmpty. Operand 15 states. [2018-06-22 11:19:03,922 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 11:19:03,922 INFO ]: Found error trace [2018-06-22 11:19:03,923 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:03,923 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:03,928 INFO ]: Analyzing trace with hash -1409059775, now seen corresponding path program 1 times [2018-06-22 11:19:03,929 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:03,930 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:03,961 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:03,961 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:03,961 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:04,002 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:04,139 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 11:19:04,141 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 11:19:04,141 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 11:19:04,142 INFO ]: Interpolant automaton has 4 states [2018-06-22 11:19:04,153 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 11:19:04,153 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 11:19:04,155 INFO ]: Start difference. First operand 15 states. Second operand 4 states. [2018-06-22 11:19:04,317 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:04,317 INFO ]: Finished difference Result 15 states and 22 transitions. [2018-06-22 11:19:04,318 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 11:19:04,319 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 11:19:04,320 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:04,328 INFO ]: With dead ends: 15 [2018-06-22 11:19:04,328 INFO ]: Without dead ends: 15 [2018-06-22 11:19:04,329 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 11:19:04,341 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 11:19:04,360 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 11:19:04,361 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 11:19:04,362 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 22 transitions. [2018-06-22 11:19:04,364 INFO ]: Start accepts. Automaton has 15 states and 22 transitions. Word has length 9 [2018-06-22 11:19:04,365 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:04,365 INFO ]: Abstraction has 15 states and 22 transitions. [2018-06-22 11:19:04,365 INFO ]: Interpolant automaton has 4 states. [2018-06-22 11:19:04,365 INFO ]: Start isEmpty. Operand 15 states and 22 transitions. [2018-06-22 11:19:04,367 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 11:19:04,367 INFO ]: Found error trace [2018-06-22 11:19:04,367 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:04,368 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:04,368 INFO ]: Analyzing trace with hash 1397489035, now seen corresponding path program 1 times [2018-06-22 11:19:04,368 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:04,368 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:04,369 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:04,369 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:04,369 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:04,384 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:04,607 INFO ]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 11:19:04,607 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 11:19:04,607 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 11:19:04,609 INFO ]: Interpolant automaton has 4 states [2018-06-22 11:19:04,609 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 11:19:04,609 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 11:19:04,609 INFO ]: Start difference. First operand 15 states and 22 transitions. Second operand 4 states. [2018-06-22 11:19:04,872 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:04,872 INFO ]: Finished difference Result 17 states and 26 transitions. [2018-06-22 11:19:04,872 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 11:19:04,872 INFO ]: Start accepts. Automaton has 4 states. Word has length 13 [2018-06-22 11:19:04,873 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:04,873 INFO ]: With dead ends: 17 [2018-06-22 11:19:04,873 INFO ]: Without dead ends: 17 [2018-06-22 11:19:04,874 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 11:19:04,874 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 11:19:04,879 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 15. [2018-06-22 11:19:04,879 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 11:19:04,879 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 21 transitions. [2018-06-22 11:19:04,879 INFO ]: Start accepts. Automaton has 15 states and 21 transitions. Word has length 13 [2018-06-22 11:19:04,879 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:04,879 INFO ]: Abstraction has 15 states and 21 transitions. [2018-06-22 11:19:04,880 INFO ]: Interpolant automaton has 4 states. [2018-06-22 11:19:04,880 INFO ]: Start isEmpty. Operand 15 states and 21 transitions. [2018-06-22 11:19:04,880 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 11:19:04,880 INFO ]: Found error trace [2018-06-22 11:19:04,880 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:04,881 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:04,881 INFO ]: Analyzing trace with hash 1152238182, now seen corresponding path program 1 times [2018-06-22 11:19:04,881 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:04,881 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:04,881 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:04,881 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:04,881 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:04,892 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:05,213 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 11:19:05,213 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:05,213 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 11:19:05,222 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:05,257 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:05,263 INFO ]: Computing forward predicates... [2018-06-22 11:19:05,367 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 11:19:05,390 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:05,390 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 11:19:05,390 INFO ]: Interpolant automaton has 9 states [2018-06-22 11:19:05,390 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 11:19:05,390 INFO ]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-06-22 11:19:05,391 INFO ]: Start difference. First operand 15 states and 21 transitions. Second operand 9 states. [2018-06-22 11:19:05,648 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:05,648 INFO ]: Finished difference Result 21 states and 34 transitions. [2018-06-22 11:19:05,650 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 11:19:05,650 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 11:19:05,650 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:05,651 INFO ]: With dead ends: 21 [2018-06-22 11:19:05,651 INFO ]: Without dead ends: 21 [2018-06-22 11:19:05,651 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 10 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2018-06-22 11:19:05,652 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 11:19:05,657 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 17. [2018-06-22 11:19:05,657 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 11:19:05,658 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 25 transitions. [2018-06-22 11:19:05,658 INFO ]: Start accepts. Automaton has 17 states and 25 transitions. Word has length 13 [2018-06-22 11:19:05,658 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:05,658 INFO ]: Abstraction has 17 states and 25 transitions. [2018-06-22 11:19:05,658 INFO ]: Interpolant automaton has 9 states. [2018-06-22 11:19:05,658 INFO ]: Start isEmpty. Operand 17 states and 25 transitions. [2018-06-22 11:19:05,659 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 11:19:05,659 INFO ]: Found error trace [2018-06-22 11:19:05,659 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:05,659 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:05,659 INFO ]: Analyzing trace with hash 1300014339, now seen corresponding path program 1 times [2018-06-22 11:19:05,659 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:05,659 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:05,660 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:05,660 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:05,660 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:05,669 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:05,770 INFO ]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 11:19:05,770 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 11:19:05,770 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 11:19:05,770 INFO ]: Interpolant automaton has 4 states [2018-06-22 11:19:05,770 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 11:19:05,770 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 11:19:05,771 INFO ]: Start difference. First operand 17 states and 25 transitions. Second operand 4 states. [2018-06-22 11:19:05,933 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:05,933 INFO ]: Finished difference Result 21 states and 33 transitions. [2018-06-22 11:19:05,934 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 11:19:05,934 INFO ]: Start accepts. Automaton has 4 states. Word has length 13 [2018-06-22 11:19:05,934 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:05,935 INFO ]: With dead ends: 21 [2018-06-22 11:19:05,935 INFO ]: Without dead ends: 21 [2018-06-22 11:19:05,935 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 11:19:05,935 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 11:19:05,940 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 17. [2018-06-22 11:19:05,940 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 11:19:05,940 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 24 transitions. [2018-06-22 11:19:05,941 INFO ]: Start accepts. Automaton has 17 states and 24 transitions. Word has length 13 [2018-06-22 11:19:05,941 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:05,941 INFO ]: Abstraction has 17 states and 24 transitions. [2018-06-22 11:19:05,941 INFO ]: Interpolant automaton has 4 states. [2018-06-22 11:19:05,941 INFO ]: Start isEmpty. Operand 17 states and 24 transitions. [2018-06-22 11:19:05,942 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 11:19:05,942 INFO ]: Found error trace [2018-06-22 11:19:05,942 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:05,942 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:05,943 INFO ]: Analyzing trace with hash -300198672, now seen corresponding path program 1 times [2018-06-22 11:19:05,943 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:05,943 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:05,944 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:05,944 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:05,944 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:05,963 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:06,390 INFO ]: Checked inductivity of 9 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-06-22 11:19:06,390 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:06,390 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 11:19:06,404 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:06,425 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:06,428 INFO ]: Computing forward predicates... [2018-06-22 11:19:06,530 INFO ]: Checked inductivity of 9 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 11:19:06,550 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:06,551 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 10 [2018-06-22 11:19:06,551 INFO ]: Interpolant automaton has 10 states [2018-06-22 11:19:06,551 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 11:19:06,551 INFO ]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2018-06-22 11:19:06,551 INFO ]: Start difference. First operand 17 states and 24 transitions. Second operand 10 states. [2018-06-22 11:19:06,821 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:06,822 INFO ]: Finished difference Result 29 states and 51 transitions. [2018-06-22 11:19:06,822 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 11:19:06,822 INFO ]: Start accepts. Automaton has 10 states. Word has length 17 [2018-06-22 11:19:06,822 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:06,823 INFO ]: With dead ends: 29 [2018-06-22 11:19:06,823 INFO ]: Without dead ends: 29 [2018-06-22 11:19:06,823 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 14 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2018-06-22 11:19:06,823 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 11:19:06,831 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 23. [2018-06-22 11:19:06,831 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 11:19:06,832 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 37 transitions. [2018-06-22 11:19:06,832 INFO ]: Start accepts. Automaton has 23 states and 37 transitions. Word has length 17 [2018-06-22 11:19:06,832 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:06,832 INFO ]: Abstraction has 23 states and 37 transitions. [2018-06-22 11:19:06,832 INFO ]: Interpolant automaton has 10 states. [2018-06-22 11:19:06,832 INFO ]: Start isEmpty. Operand 23 states and 37 transitions. [2018-06-22 11:19:06,834 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 11:19:06,834 INFO ]: Found error trace [2018-06-22 11:19:06,834 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:06,834 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:06,834 INFO ]: Analyzing trace with hash 937427787, now seen corresponding path program 2 times [2018-06-22 11:19:06,834 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:06,834 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:06,835 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:06,835 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:06,835 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:06,846 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:06,963 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 11:19:06,963 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:06,963 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 11:19:06,977 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:06,994 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 11:19:06,994 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:06,996 INFO ]: Computing forward predicates... [2018-06-22 11:19:07,164 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 11:19:07,198 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:07,198 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-22 11:19:07,198 INFO ]: Interpolant automaton has 13 states [2018-06-22 11:19:07,198 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 11:19:07,198 INFO ]: CoverageRelationStatistics Valid=28, Invalid=128, Unknown=0, NotChecked=0, Total=156 [2018-06-22 11:19:07,198 INFO ]: Start difference. First operand 23 states and 37 transitions. Second operand 13 states. [2018-06-22 11:19:07,441 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:07,441 INFO ]: Finished difference Result 33 states and 58 transitions. [2018-06-22 11:19:07,441 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 11:19:07,441 INFO ]: Start accepts. Automaton has 13 states. Word has length 17 [2018-06-22 11:19:07,441 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:07,442 INFO ]: With dead ends: 33 [2018-06-22 11:19:07,442 INFO ]: Without dead ends: 33 [2018-06-22 11:19:07,443 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 12 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=63, Invalid=209, Unknown=0, NotChecked=0, Total=272 [2018-06-22 11:19:07,443 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-22 11:19:07,450 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 25. [2018-06-22 11:19:07,450 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 11:19:07,451 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 41 transitions. [2018-06-22 11:19:07,451 INFO ]: Start accepts. Automaton has 25 states and 41 transitions. Word has length 17 [2018-06-22 11:19:07,452 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:07,452 INFO ]: Abstraction has 25 states and 41 transitions. [2018-06-22 11:19:07,452 INFO ]: Interpolant automaton has 13 states. [2018-06-22 11:19:07,452 INFO ]: Start isEmpty. Operand 25 states and 41 transitions. [2018-06-22 11:19:07,453 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 11:19:07,453 INFO ]: Found error trace [2018-06-22 11:19:07,453 INFO ]: trace histogram [4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:07,453 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:07,453 INFO ]: Analyzing trace with hash -1944211691, now seen corresponding path program 2 times [2018-06-22 11:19:07,453 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:07,453 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:07,454 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:07,454 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:07,454 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:07,467 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:07,568 INFO ]: Checked inductivity of 19 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 11:19:07,568 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:07,568 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 11:19:07,576 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 11:19:07,610 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 11:19:07,610 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:07,613 INFO ]: Computing forward predicates... [2018-06-22 11:19:07,742 INFO ]: Checked inductivity of 19 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 11:19:07,762 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:07,762 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2018-06-22 11:19:07,763 INFO ]: Interpolant automaton has 16 states [2018-06-22 11:19:07,763 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 11:19:07,763 INFO ]: CoverageRelationStatistics Valid=40, Invalid=200, Unknown=0, NotChecked=0, Total=240 [2018-06-22 11:19:07,763 INFO ]: Start difference. First operand 25 states and 41 transitions. Second operand 16 states. [2018-06-22 11:19:08,363 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:08,363 INFO ]: Finished difference Result 51 states and 95 transitions. [2018-06-22 11:19:08,363 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-22 11:19:08,363 INFO ]: Start accepts. Automaton has 16 states. Word has length 21 [2018-06-22 11:19:08,363 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:08,365 INFO ]: With dead ends: 51 [2018-06-22 11:19:08,365 INFO ]: Without dead ends: 51 [2018-06-22 11:19:08,365 INFO ]: 0 DeclaredPredicates, 40 GetRequests, 15 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=150, Invalid=500, Unknown=0, NotChecked=0, Total=650 [2018-06-22 11:19:08,366 INFO ]: Start minimizeSevpa. Operand 51 states. [2018-06-22 11:19:08,376 INFO ]: Finished minimizeSevpa. Reduced states from 51 to 27. [2018-06-22 11:19:08,377 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 11:19:08,378 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 45 transitions. [2018-06-22 11:19:08,378 INFO ]: Start accepts. Automaton has 27 states and 45 transitions. Word has length 21 [2018-06-22 11:19:08,378 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:08,378 INFO ]: Abstraction has 27 states and 45 transitions. [2018-06-22 11:19:08,378 INFO ]: Interpolant automaton has 16 states. [2018-06-22 11:19:08,378 INFO ]: Start isEmpty. Operand 27 states and 45 transitions. [2018-06-22 11:19:08,379 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 11:19:08,379 INFO ]: Found error trace [2018-06-22 11:19:08,379 INFO ]: trace histogram [4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:08,379 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:08,379 INFO ]: Analyzing trace with hash 803425997, now seen corresponding path program 1 times [2018-06-22 11:19:08,379 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:08,379 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:08,380 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:08,380 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:08,380 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:08,390 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:08,455 INFO ]: Checked inductivity of 19 backedges. 10 proven. 1 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-06-22 11:19:08,455 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:08,455 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 11:19:08,461 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:08,476 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:08,477 INFO ]: Computing forward predicates... [2018-06-22 11:19:08,485 INFO ]: Checked inductivity of 19 backedges. 10 proven. 1 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-06-22 11:19:08,504 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:08,504 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-22 11:19:08,504 INFO ]: Interpolant automaton has 4 states [2018-06-22 11:19:08,505 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 11:19:08,505 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 11:19:08,505 INFO ]: Start difference. First operand 27 states and 45 transitions. Second operand 4 states. [2018-06-22 11:19:08,542 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:08,542 INFO ]: Finished difference Result 48 states and 74 transitions. [2018-06-22 11:19:08,543 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 11:19:08,543 INFO ]: Start accepts. Automaton has 4 states. Word has length 21 [2018-06-22 11:19:08,543 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:08,544 INFO ]: With dead ends: 48 [2018-06-22 11:19:08,544 INFO ]: Without dead ends: 36 [2018-06-22 11:19:08,544 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 22 SyntacticMatches, 1 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 11:19:08,545 INFO ]: Start minimizeSevpa. Operand 36 states. [2018-06-22 11:19:08,553 INFO ]: Finished minimizeSevpa. Reduced states from 36 to 32. [2018-06-22 11:19:08,553 INFO ]: Start removeUnreachable. Operand 32 states. [2018-06-22 11:19:08,554 INFO ]: Finished removeUnreachable. Reduced from 32 states to 32 states and 54 transitions. [2018-06-22 11:19:08,554 INFO ]: Start accepts. Automaton has 32 states and 54 transitions. Word has length 21 [2018-06-22 11:19:08,554 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:08,554 INFO ]: Abstraction has 32 states and 54 transitions. [2018-06-22 11:19:08,554 INFO ]: Interpolant automaton has 4 states. [2018-06-22 11:19:08,554 INFO ]: Start isEmpty. Operand 32 states and 54 transitions. [2018-06-22 11:19:08,560 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 11:19:08,560 INFO ]: Found error trace [2018-06-22 11:19:08,560 INFO ]: trace histogram [4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:08,561 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:08,561 INFO ]: Analyzing trace with hash -1597297798, now seen corresponding path program 3 times [2018-06-22 11:19:08,561 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:08,561 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:08,561 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:08,561 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:08,561 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:08,580 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:08,651 INFO ]: Checked inductivity of 19 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 11:19:08,651 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:08,651 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:08,657 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 11:19:08,671 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 11:19:08,671 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:08,673 INFO ]: Computing forward predicates... [2018-06-22 11:19:08,753 INFO ]: Checked inductivity of 19 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 11:19:08,772 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:08,772 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-22 11:19:08,772 INFO ]: Interpolant automaton has 13 states [2018-06-22 11:19:08,772 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 11:19:08,772 INFO ]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2018-06-22 11:19:08,772 INFO ]: Start difference. First operand 32 states and 54 transitions. Second operand 13 states. [2018-06-22 11:19:09,099 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:09,099 INFO ]: Finished difference Result 38 states and 57 transitions. [2018-06-22 11:19:09,100 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 11:19:09,100 INFO ]: Start accepts. Automaton has 13 states. Word has length 21 [2018-06-22 11:19:09,100 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:09,101 INFO ]: With dead ends: 38 [2018-06-22 11:19:09,101 INFO ]: Without dead ends: 36 [2018-06-22 11:19:09,101 INFO ]: 0 DeclaredPredicates, 36 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=87, Invalid=333, Unknown=0, NotChecked=0, Total=420 [2018-06-22 11:19:09,101 INFO ]: Start minimizeSevpa. Operand 36 states. [2018-06-22 11:19:09,106 INFO ]: Finished minimizeSevpa. Reduced states from 36 to 28. [2018-06-22 11:19:09,106 INFO ]: Start removeUnreachable. Operand 28 states. [2018-06-22 11:19:09,107 INFO ]: Finished removeUnreachable. Reduced from 28 states to 28 states and 42 transitions. [2018-06-22 11:19:09,107 INFO ]: Start accepts. Automaton has 28 states and 42 transitions. Word has length 21 [2018-06-22 11:19:09,107 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:09,107 INFO ]: Abstraction has 28 states and 42 transitions. [2018-06-22 11:19:09,107 INFO ]: Interpolant automaton has 13 states. [2018-06-22 11:19:09,107 INFO ]: Start isEmpty. Operand 28 states and 42 transitions. [2018-06-22 11:19:09,108 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 11:19:09,108 INFO ]: Found error trace [2018-06-22 11:19:09,108 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:09,108 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:09,108 INFO ]: Analyzing trace with hash 248846066, now seen corresponding path program 1 times [2018-06-22 11:19:09,109 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:09,109 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:09,109 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:09,109 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:09,109 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:09,117 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:09,143 INFO ]: Checked inductivity of 18 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-06-22 11:19:09,144 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 11:19:09,144 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 11:19:09,144 INFO ]: Interpolant automaton has 4 states [2018-06-22 11:19:09,144 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 11:19:09,144 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 11:19:09,144 INFO ]: Start difference. First operand 28 states and 42 transitions. Second operand 4 states. [2018-06-22 11:19:09,178 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:09,178 INFO ]: Finished difference Result 43 states and 65 transitions. [2018-06-22 11:19:09,178 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 11:19:09,178 INFO ]: Start accepts. Automaton has 4 states. Word has length 21 [2018-06-22 11:19:09,179 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:09,179 INFO ]: With dead ends: 43 [2018-06-22 11:19:09,179 INFO ]: Without dead ends: 33 [2018-06-22 11:19:09,180 INFO ]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 11:19:09,180 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-22 11:19:09,185 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 31. [2018-06-22 11:19:09,185 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 11:19:09,186 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 47 transitions. [2018-06-22 11:19:09,186 INFO ]: Start accepts. Automaton has 31 states and 47 transitions. Word has length 21 [2018-06-22 11:19:09,186 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:09,186 INFO ]: Abstraction has 31 states and 47 transitions. [2018-06-22 11:19:09,186 INFO ]: Interpolant automaton has 4 states. [2018-06-22 11:19:09,186 INFO ]: Start isEmpty. Operand 31 states and 47 transitions. [2018-06-22 11:19:09,187 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 11:19:09,187 INFO ]: Found error trace [2018-06-22 11:19:09,187 INFO ]: trace histogram [5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:09,187 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:09,187 INFO ]: Analyzing trace with hash 1685655263, now seen corresponding path program 4 times [2018-06-22 11:19:09,187 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:09,187 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:09,188 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:09,188 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:09,188 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:09,199 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:09,312 INFO ]: Checked inductivity of 32 backedges. 0 proven. 17 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 11:19:09,312 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:09,312 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 11:19:09,321 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 11:19:09,352 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 11:19:09,352 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:09,355 INFO ]: Computing forward predicates... [2018-06-22 11:19:09,719 INFO ]: Checked inductivity of 32 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-06-22 11:19:09,740 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:09,740 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10] total 14 [2018-06-22 11:19:09,741 INFO ]: Interpolant automaton has 14 states [2018-06-22 11:19:09,741 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 11:19:09,741 INFO ]: CoverageRelationStatistics Valid=31, Invalid=151, Unknown=0, NotChecked=0, Total=182 [2018-06-22 11:19:09,741 INFO ]: Start difference. First operand 31 states and 47 transitions. Second operand 14 states. [2018-06-22 11:19:10,100 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:10,100 INFO ]: Finished difference Result 59 states and 96 transitions. [2018-06-22 11:19:10,100 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 11:19:10,100 INFO ]: Start accepts. Automaton has 14 states. Word has length 25 [2018-06-22 11:19:10,100 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:10,101 INFO ]: With dead ends: 59 [2018-06-22 11:19:10,101 INFO ]: Without dead ends: 59 [2018-06-22 11:19:10,102 INFO ]: 0 DeclaredPredicates, 44 GetRequests, 19 SyntacticMatches, 5 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=79, Invalid=383, Unknown=0, NotChecked=0, Total=462 [2018-06-22 11:19:10,102 INFO ]: Start minimizeSevpa. Operand 59 states. [2018-06-22 11:19:10,110 INFO ]: Finished minimizeSevpa. Reduced states from 59 to 49. [2018-06-22 11:19:10,110 INFO ]: Start removeUnreachable. Operand 49 states. [2018-06-22 11:19:10,111 INFO ]: Finished removeUnreachable. Reduced from 49 states to 49 states and 79 transitions. [2018-06-22 11:19:10,111 INFO ]: Start accepts. Automaton has 49 states and 79 transitions. Word has length 25 [2018-06-22 11:19:10,111 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:10,111 INFO ]: Abstraction has 49 states and 79 transitions. [2018-06-22 11:19:10,111 INFO ]: Interpolant automaton has 14 states. [2018-06-22 11:19:10,111 INFO ]: Start isEmpty. Operand 49 states and 79 transitions. [2018-06-22 11:19:10,112 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 11:19:10,112 INFO ]: Found error trace [2018-06-22 11:19:10,112 INFO ]: trace histogram [5, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:10,112 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:10,112 INFO ]: Analyzing trace with hash 565268538, now seen corresponding path program 5 times [2018-06-22 11:19:10,112 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:10,112 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:10,113 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:10,113 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:10,113 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:10,118 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:10,147 INFO ]: Checked inductivity of 33 backedges. 14 proven. 2 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-06-22 11:19:10,147 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:10,147 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 11:19:10,153 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 11:19:10,169 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-22 11:19:10,169 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:10,171 INFO ]: Computing forward predicates... [2018-06-22 11:19:10,195 INFO ]: Checked inductivity of 33 backedges. 14 proven. 2 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-06-22 11:19:10,226 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:10,226 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-22 11:19:10,226 INFO ]: Interpolant automaton has 4 states [2018-06-22 11:19:10,226 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 11:19:10,226 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 11:19:10,226 INFO ]: Start difference. First operand 49 states and 79 transitions. Second operand 4 states. [2018-06-22 11:19:10,254 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:10,254 INFO ]: Finished difference Result 33 states and 40 transitions. [2018-06-22 11:19:10,254 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 11:19:10,254 INFO ]: Start accepts. Automaton has 4 states. Word has length 25 [2018-06-22 11:19:10,254 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:10,255 INFO ]: With dead ends: 33 [2018-06-22 11:19:10,255 INFO ]: Without dead ends: 30 [2018-06-22 11:19:10,255 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 1 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 11:19:10,255 INFO ]: Start minimizeSevpa. Operand 30 states. [2018-06-22 11:19:10,258 INFO ]: Finished minimizeSevpa. Reduced states from 30 to 26. [2018-06-22 11:19:10,258 INFO ]: Start removeUnreachable. Operand 26 states. [2018-06-22 11:19:10,258 INFO ]: Finished removeUnreachable. Reduced from 26 states to 26 states and 31 transitions. [2018-06-22 11:19:10,258 INFO ]: Start accepts. Automaton has 26 states and 31 transitions. Word has length 25 [2018-06-22 11:19:10,258 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:10,258 INFO ]: Abstraction has 26 states and 31 transitions. [2018-06-22 11:19:10,258 INFO ]: Interpolant automaton has 4 states. [2018-06-22 11:19:10,258 INFO ]: Start isEmpty. Operand 26 states and 31 transitions. [2018-06-22 11:19:10,261 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 11:19:10,261 INFO ]: Found error trace [2018-06-22 11:19:10,261 INFO ]: trace histogram [6, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:10,261 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:10,261 INFO ]: Analyzing trace with hash 309453481, now seen corresponding path program 6 times [2018-06-22 11:19:10,261 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:10,261 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:10,261 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:10,261 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:10,262 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:10,275 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:10,401 INFO ]: Checked inductivity of 49 backedges. 12 proven. 21 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2018-06-22 11:19:10,401 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:10,401 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:10,407 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 11:19:10,450 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 6 check-sat command(s) [2018-06-22 11:19:10,450 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:10,453 INFO ]: Computing forward predicates... [2018-06-22 11:19:10,608 INFO ]: Checked inductivity of 49 backedges. 13 proven. 20 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2018-06-22 11:19:10,627 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:10,627 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 18 [2018-06-22 11:19:10,627 INFO ]: Interpolant automaton has 18 states [2018-06-22 11:19:10,627 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-22 11:19:10,627 INFO ]: CoverageRelationStatistics Valid=51, Invalid=255, Unknown=0, NotChecked=0, Total=306 [2018-06-22 11:19:10,628 INFO ]: Start difference. First operand 26 states and 31 transitions. Second operand 18 states. [2018-06-22 11:19:10,846 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:10,846 INFO ]: Finished difference Result 32 states and 37 transitions. [2018-06-22 11:19:10,846 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 11:19:10,846 INFO ]: Start accepts. Automaton has 18 states. Word has length 29 [2018-06-22 11:19:10,846 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:10,846 INFO ]: With dead ends: 32 [2018-06-22 11:19:10,846 INFO ]: Without dead ends: 26 [2018-06-22 11:19:10,846 INFO ]: 0 DeclaredPredicates, 46 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 84 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=109, Invalid=443, Unknown=0, NotChecked=0, Total=552 [2018-06-22 11:19:10,847 INFO ]: Start minimizeSevpa. Operand 26 states. [2018-06-22 11:19:10,849 INFO ]: Finished minimizeSevpa. Reduced states from 26 to 24. [2018-06-22 11:19:10,849 INFO ]: Start removeUnreachable. Operand 24 states. [2018-06-22 11:19:10,849 INFO ]: Finished removeUnreachable. Reduced from 24 states to 24 states and 28 transitions. [2018-06-22 11:19:10,849 INFO ]: Start accepts. Automaton has 24 states and 28 transitions. Word has length 29 [2018-06-22 11:19:10,849 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:10,850 INFO ]: Abstraction has 24 states and 28 transitions. [2018-06-22 11:19:10,850 INFO ]: Interpolant automaton has 18 states. [2018-06-22 11:19:10,850 INFO ]: Start isEmpty. Operand 24 states and 28 transitions. [2018-06-22 11:19:10,850 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 11:19:10,850 INFO ]: Found error trace [2018-06-22 11:19:10,850 INFO ]: trace histogram [6, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:10,850 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:10,850 INFO ]: Analyzing trace with hash -1261218556, now seen corresponding path program 7 times [2018-06-22 11:19:10,850 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:10,850 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:10,851 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:10,851 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:10,851 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:10,861 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:11,060 INFO ]: Checked inductivity of 49 backedges. 2 proven. 30 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-06-22 11:19:11,060 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:11,060 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 11:19:11,065 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:11,082 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:11,085 INFO ]: Computing forward predicates... [2018-06-22 11:19:11,314 INFO ]: Checked inductivity of 49 backedges. 0 proven. 32 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-06-22 11:19:11,334 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:11,334 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 20 [2018-06-22 11:19:11,334 INFO ]: Interpolant automaton has 20 states [2018-06-22 11:19:11,335 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 11:19:11,335 INFO ]: CoverageRelationStatistics Valid=58, Invalid=322, Unknown=0, NotChecked=0, Total=380 [2018-06-22 11:19:11,335 INFO ]: Start difference. First operand 24 states and 28 transitions. Second operand 20 states. [2018-06-22 11:19:11,637 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:11,637 INFO ]: Finished difference Result 46 states and 54 transitions. [2018-06-22 11:19:11,637 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-06-22 11:19:11,637 INFO ]: Start accepts. Automaton has 20 states. Word has length 29 [2018-06-22 11:19:11,637 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:11,638 INFO ]: With dead ends: 46 [2018-06-22 11:19:11,638 INFO ]: Without dead ends: 46 [2018-06-22 11:19:11,638 INFO ]: 0 DeclaredPredicates, 54 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 151 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=211, Invalid=781, Unknown=0, NotChecked=0, Total=992 [2018-06-22 11:19:11,638 INFO ]: Start minimizeSevpa. Operand 46 states. [2018-06-22 11:19:11,643 INFO ]: Finished minimizeSevpa. Reduced states from 46 to 26. [2018-06-22 11:19:11,643 INFO ]: Start removeUnreachable. Operand 26 states. [2018-06-22 11:19:11,644 INFO ]: Finished removeUnreachable. Reduced from 26 states to 26 states and 30 transitions. [2018-06-22 11:19:11,644 INFO ]: Start accepts. Automaton has 26 states and 30 transitions. Word has length 29 [2018-06-22 11:19:11,644 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:11,644 INFO ]: Abstraction has 26 states and 30 transitions. [2018-06-22 11:19:11,644 INFO ]: Interpolant automaton has 20 states. [2018-06-22 11:19:11,644 INFO ]: Start isEmpty. Operand 26 states and 30 transitions. [2018-06-22 11:19:11,645 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 11:19:11,645 INFO ]: Found error trace [2018-06-22 11:19:11,645 INFO ]: trace histogram [7, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:11,645 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:11,645 INFO ]: Analyzing trace with hash 973484558, now seen corresponding path program 8 times [2018-06-22 11:19:11,645 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:11,645 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:11,645 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:11,646 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:11,646 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:11,656 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:11,865 INFO ]: Checked inductivity of 69 backedges. 0 proven. 38 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-06-22 11:19:11,865 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:11,865 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 11:19:11,871 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 11:19:11,889 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 11:19:11,889 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:11,892 INFO ]: Computing forward predicates... [2018-06-22 11:19:12,187 INFO ]: Checked inductivity of 69 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2018-06-22 11:19:12,206 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:12,207 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 12] total 17 [2018-06-22 11:19:12,267 INFO ]: Interpolant automaton has 17 states [2018-06-22 11:19:12,267 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 11:19:12,267 INFO ]: CoverageRelationStatistics Valid=39, Invalid=233, Unknown=0, NotChecked=0, Total=272 [2018-06-22 11:19:12,268 INFO ]: Start difference. First operand 26 states and 30 transitions. Second operand 17 states. [2018-06-22 11:19:12,507 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:12,507 INFO ]: Finished difference Result 38 states and 44 transitions. [2018-06-22 11:19:12,507 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 11:19:12,507 INFO ]: Start accepts. Automaton has 17 states. Word has length 33 [2018-06-22 11:19:12,507 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:12,508 INFO ]: With dead ends: 38 [2018-06-22 11:19:12,508 INFO ]: Without dead ends: 38 [2018-06-22 11:19:12,508 INFO ]: 0 DeclaredPredicates, 54 GetRequests, 25 SyntacticMatches, 8 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 81 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=73, Invalid=433, Unknown=0, NotChecked=0, Total=506 [2018-06-22 11:19:12,508 INFO ]: Start minimizeSevpa. Operand 38 states. [2018-06-22 11:19:12,511 INFO ]: Finished minimizeSevpa. Reduced states from 38 to 30. [2018-06-22 11:19:12,511 INFO ]: Start removeUnreachable. Operand 30 states. [2018-06-22 11:19:12,512 INFO ]: Finished removeUnreachable. Reduced from 30 states to 30 states and 35 transitions. [2018-06-22 11:19:12,512 INFO ]: Start accepts. Automaton has 30 states and 35 transitions. Word has length 33 [2018-06-22 11:19:12,512 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:12,512 INFO ]: Abstraction has 30 states and 35 transitions. [2018-06-22 11:19:12,512 INFO ]: Interpolant automaton has 17 states. [2018-06-22 11:19:12,512 INFO ]: Start isEmpty. Operand 30 states and 35 transitions. [2018-06-22 11:19:12,513 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 11:19:12,513 INFO ]: Found error trace [2018-06-22 11:19:12,513 INFO ]: trace histogram [8, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:12,513 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:12,513 INFO ]: Analyzing trace with hash 470135576, now seen corresponding path program 9 times [2018-06-22 11:19:12,513 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:12,513 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:12,513 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:12,513 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:12,513 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:12,525 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:12,923 INFO ]: Checked inductivity of 93 backedges. 20 proven. 41 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2018-06-22 11:19:12,923 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:12,923 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 11:19:12,929 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 11:19:12,952 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-22 11:19:12,952 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:12,955 INFO ]: Computing forward predicates... [2018-06-22 11:19:13,181 INFO ]: Checked inductivity of 93 backedges. 22 proven. 39 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2018-06-22 11:19:13,205 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:13,205 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2018-06-22 11:19:13,206 INFO ]: Interpolant automaton has 22 states [2018-06-22 11:19:13,206 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-22 11:19:13,206 INFO ]: CoverageRelationStatistics Valid=73, Invalid=389, Unknown=0, NotChecked=0, Total=462 [2018-06-22 11:19:13,206 INFO ]: Start difference. First operand 30 states and 35 transitions. Second operand 22 states. [2018-06-22 11:19:13,410 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:13,410 INFO ]: Finished difference Result 38 states and 43 transitions. [2018-06-22 11:19:13,410 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 11:19:13,410 INFO ]: Start accepts. Automaton has 22 states. Word has length 37 [2018-06-22 11:19:13,411 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:13,411 INFO ]: With dead ends: 38 [2018-06-22 11:19:13,411 INFO ]: Without dead ends: 30 [2018-06-22 11:19:13,411 INFO ]: 0 DeclaredPredicates, 60 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 162 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=162, Invalid=708, Unknown=0, NotChecked=0, Total=870 [2018-06-22 11:19:13,412 INFO ]: Start minimizeSevpa. Operand 30 states. [2018-06-22 11:19:13,414 INFO ]: Finished minimizeSevpa. Reduced states from 30 to 28. [2018-06-22 11:19:13,414 INFO ]: Start removeUnreachable. Operand 28 states. [2018-06-22 11:19:13,414 INFO ]: Finished removeUnreachable. Reduced from 28 states to 28 states and 32 transitions. [2018-06-22 11:19:13,414 INFO ]: Start accepts. Automaton has 28 states and 32 transitions. Word has length 37 [2018-06-22 11:19:13,415 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:13,415 INFO ]: Abstraction has 28 states and 32 transitions. [2018-06-22 11:19:13,415 INFO ]: Interpolant automaton has 22 states. [2018-06-22 11:19:13,415 INFO ]: Start isEmpty. Operand 28 states and 32 transitions. [2018-06-22 11:19:13,415 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 11:19:13,415 INFO ]: Found error trace [2018-06-22 11:19:13,415 INFO ]: trace histogram [8, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:13,416 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:13,416 INFO ]: Analyzing trace with hash 1377846323, now seen corresponding path program 10 times [2018-06-22 11:19:13,416 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:13,416 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:13,416 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:13,416 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:13,416 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:13,426 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:13,577 INFO ]: Checked inductivity of 93 backedges. 6 proven. 53 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2018-06-22 11:19:13,577 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:13,577 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 11:19:13,582 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 11:19:13,617 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 11:19:13,617 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:13,620 INFO ]: Computing forward predicates... [2018-06-22 11:19:13,902 INFO ]: Checked inductivity of 93 backedges. 0 proven. 59 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2018-06-22 11:19:13,922 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:13,922 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 24 [2018-06-22 11:19:13,922 INFO ]: Interpolant automaton has 24 states [2018-06-22 11:19:13,922 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 11:19:13,922 INFO ]: CoverageRelationStatistics Valid=81, Invalid=471, Unknown=0, NotChecked=0, Total=552 [2018-06-22 11:19:13,922 INFO ]: Start difference. First operand 28 states and 32 transitions. Second operand 24 states. [2018-06-22 11:19:14,324 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:14,324 INFO ]: Finished difference Result 60 states and 69 transitions. [2018-06-22 11:19:14,325 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-06-22 11:19:14,325 INFO ]: Start accepts. Automaton has 24 states. Word has length 37 [2018-06-22 11:19:14,325 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:14,325 INFO ]: With dead ends: 60 [2018-06-22 11:19:14,325 INFO ]: Without dead ends: 60 [2018-06-22 11:19:14,326 INFO ]: 0 DeclaredPredicates, 72 GetRequests, 31 SyntacticMatches, 1 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 330 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=362, Invalid=1360, Unknown=0, NotChecked=0, Total=1722 [2018-06-22 11:19:14,326 INFO ]: Start minimizeSevpa. Operand 60 states. [2018-06-22 11:19:14,329 INFO ]: Finished minimizeSevpa. Reduced states from 60 to 30. [2018-06-22 11:19:14,329 INFO ]: Start removeUnreachable. Operand 30 states. [2018-06-22 11:19:14,330 INFO ]: Finished removeUnreachable. Reduced from 30 states to 30 states and 34 transitions. [2018-06-22 11:19:14,330 INFO ]: Start accepts. Automaton has 30 states and 34 transitions. Word has length 37 [2018-06-22 11:19:14,330 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:14,330 INFO ]: Abstraction has 30 states and 34 transitions. [2018-06-22 11:19:14,330 INFO ]: Interpolant automaton has 24 states. [2018-06-22 11:19:14,330 INFO ]: Start isEmpty. Operand 30 states and 34 transitions. [2018-06-22 11:19:14,332 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 11:19:14,332 INFO ]: Found error trace [2018-06-22 11:19:14,332 INFO ]: trace histogram [9, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:14,332 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:14,332 INFO ]: Analyzing trace with hash 1357926013, now seen corresponding path program 11 times [2018-06-22 11:19:14,332 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:14,332 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:14,333 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:14,333 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:14,333 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:14,345 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:14,811 INFO ]: Checked inductivity of 120 backedges. 0 proven. 67 refuted. 0 times theorem prover too weak. 53 trivial. 0 not checked. [2018-06-22 11:19:14,812 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:14,812 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 11:19:14,817 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 11:19:14,860 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2018-06-22 11:19:14,860 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:14,863 INFO ]: Computing forward predicates... [2018-06-22 11:19:15,046 INFO ]: Checked inductivity of 120 backedges. 0 proven. 72 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2018-06-22 11:19:15,065 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:15,065 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 14] total 20 [2018-06-22 11:19:15,065 INFO ]: Interpolant automaton has 20 states [2018-06-22 11:19:15,065 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 11:19:15,066 INFO ]: CoverageRelationStatistics Valid=47, Invalid=333, Unknown=0, NotChecked=0, Total=380 [2018-06-22 11:19:15,066 INFO ]: Start difference. First operand 30 states and 34 transitions. Second operand 20 states. [2018-06-22 11:19:15,291 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:15,291 INFO ]: Finished difference Result 44 states and 50 transitions. [2018-06-22 11:19:15,291 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 11:19:15,291 INFO ]: Start accepts. Automaton has 20 states. Word has length 41 [2018-06-22 11:19:15,291 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:15,292 INFO ]: With dead ends: 44 [2018-06-22 11:19:15,292 INFO ]: Without dead ends: 44 [2018-06-22 11:19:15,292 INFO ]: 0 DeclaredPredicates, 68 GetRequests, 31 SyntacticMatches, 11 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 139 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=92, Invalid=664, Unknown=0, NotChecked=0, Total=756 [2018-06-22 11:19:15,292 INFO ]: Start minimizeSevpa. Operand 44 states. [2018-06-22 11:19:15,295 INFO ]: Finished minimizeSevpa. Reduced states from 44 to 34. [2018-06-22 11:19:15,295 INFO ]: Start removeUnreachable. Operand 34 states. [2018-06-22 11:19:15,295 INFO ]: Finished removeUnreachable. Reduced from 34 states to 34 states and 39 transitions. [2018-06-22 11:19:15,295 INFO ]: Start accepts. Automaton has 34 states and 39 transitions. Word has length 41 [2018-06-22 11:19:15,296 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:15,296 INFO ]: Abstraction has 34 states and 39 transitions. [2018-06-22 11:19:15,296 INFO ]: Interpolant automaton has 20 states. [2018-06-22 11:19:15,296 INFO ]: Start isEmpty. Operand 34 states and 39 transitions. [2018-06-22 11:19:15,296 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 11:19:15,296 INFO ]: Found error trace [2018-06-22 11:19:15,296 INFO ]: trace histogram [10, 5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:15,296 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:15,296 INFO ]: Analyzing trace with hash 663760071, now seen corresponding path program 12 times [2018-06-22 11:19:15,296 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:15,296 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:15,297 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:15,297 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:15,297 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:15,309 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:16,199 INFO ]: Checked inductivity of 151 backedges. 30 proven. 67 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2018-06-22 11:19:16,199 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:16,199 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 11:19:16,207 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 11:19:16,238 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) [2018-06-22 11:19:16,239 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:16,242 INFO ]: Computing forward predicates... [2018-06-22 11:19:16,457 INFO ]: Checked inductivity of 151 backedges. 33 proven. 64 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2018-06-22 11:19:16,478 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:16,478 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 26 [2018-06-22 11:19:16,478 INFO ]: Interpolant automaton has 26 states [2018-06-22 11:19:16,478 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-22 11:19:16,478 INFO ]: CoverageRelationStatistics Valid=100, Invalid=550, Unknown=0, NotChecked=0, Total=650 [2018-06-22 11:19:16,478 INFO ]: Start difference. First operand 34 states and 39 transitions. Second operand 26 states. [2018-06-22 11:19:16,810 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:16,810 INFO ]: Finished difference Result 44 states and 49 transitions. [2018-06-22 11:19:16,811 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 11:19:16,811 INFO ]: Start accepts. Automaton has 26 states. Word has length 45 [2018-06-22 11:19:16,811 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:16,811 INFO ]: With dead ends: 44 [2018-06-22 11:19:16,811 INFO ]: Without dead ends: 34 [2018-06-22 11:19:16,812 INFO ]: 0 DeclaredPredicates, 74 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 264 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=225, Invalid=1035, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 11:19:16,812 INFO ]: Start minimizeSevpa. Operand 34 states. [2018-06-22 11:19:16,814 INFO ]: Finished minimizeSevpa. Reduced states from 34 to 32. [2018-06-22 11:19:16,814 INFO ]: Start removeUnreachable. Operand 32 states. [2018-06-22 11:19:16,815 INFO ]: Finished removeUnreachable. Reduced from 32 states to 32 states and 36 transitions. [2018-06-22 11:19:16,815 INFO ]: Start accepts. Automaton has 32 states and 36 transitions. Word has length 45 [2018-06-22 11:19:16,815 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:16,815 INFO ]: Abstraction has 32 states and 36 transitions. [2018-06-22 11:19:16,815 INFO ]: Interpolant automaton has 26 states. [2018-06-22 11:19:16,815 INFO ]: Start isEmpty. Operand 32 states and 36 transitions. [2018-06-22 11:19:16,815 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 11:19:16,815 INFO ]: Found error trace [2018-06-22 11:19:16,815 INFO ]: trace histogram [10, 5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:16,815 INFO ]: === Iteration 20 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:16,815 INFO ]: Analyzing trace with hash 412748962, now seen corresponding path program 13 times [2018-06-22 11:19:16,816 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:16,816 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:16,816 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:16,816 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:16,816 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:16,826 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:17,055 INFO ]: Checked inductivity of 151 backedges. 12 proven. 82 refuted. 0 times theorem prover too weak. 57 trivial. 0 not checked. [2018-06-22 11:19:17,055 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:17,055 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:17,068 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:17,093 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:17,096 INFO ]: Computing forward predicates... [2018-06-22 11:19:17,375 INFO ]: Checked inductivity of 151 backedges. 0 proven. 94 refuted. 0 times theorem prover too weak. 57 trivial. 0 not checked. [2018-06-22 11:19:17,393 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:17,395 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 28 [2018-06-22 11:19:17,395 INFO ]: Interpolant automaton has 28 states [2018-06-22 11:19:17,395 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-22 11:19:17,395 INFO ]: CoverageRelationStatistics Valid=109, Invalid=647, Unknown=0, NotChecked=0, Total=756 [2018-06-22 11:19:17,395 INFO ]: Start difference. First operand 32 states and 36 transitions. Second operand 28 states. [2018-06-22 11:19:17,966 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:17,966 INFO ]: Finished difference Result 76 states and 86 transitions. [2018-06-22 11:19:17,967 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-06-22 11:19:17,967 INFO ]: Start accepts. Automaton has 28 states. Word has length 45 [2018-06-22 11:19:17,967 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:17,968 INFO ]: With dead ends: 76 [2018-06-22 11:19:17,968 INFO ]: Without dead ends: 76 [2018-06-22 11:19:17,968 INFO ]: 0 DeclaredPredicates, 91 GetRequests, 39 SyntacticMatches, 1 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 615 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=582, Invalid=2174, Unknown=0, NotChecked=0, Total=2756 [2018-06-22 11:19:17,968 INFO ]: Start minimizeSevpa. Operand 76 states. [2018-06-22 11:19:17,972 INFO ]: Finished minimizeSevpa. Reduced states from 76 to 34. [2018-06-22 11:19:17,972 INFO ]: Start removeUnreachable. Operand 34 states. [2018-06-22 11:19:17,973 INFO ]: Finished removeUnreachable. Reduced from 34 states to 34 states and 38 transitions. [2018-06-22 11:19:17,973 INFO ]: Start accepts. Automaton has 34 states and 38 transitions. Word has length 45 [2018-06-22 11:19:17,973 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:17,973 INFO ]: Abstraction has 34 states and 38 transitions. [2018-06-22 11:19:17,973 INFO ]: Interpolant automaton has 28 states. [2018-06-22 11:19:17,973 INFO ]: Start isEmpty. Operand 34 states and 38 transitions. [2018-06-22 11:19:17,973 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 11:19:17,973 INFO ]: Found error trace [2018-06-22 11:19:17,974 INFO ]: trace histogram [11, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:17,974 INFO ]: === Iteration 21 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:17,974 INFO ]: Analyzing trace with hash 1806234668, now seen corresponding path program 14 times [2018-06-22 11:19:17,974 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:17,974 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:17,974 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:17,974 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:17,974 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:17,987 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:18,345 INFO ]: Checked inductivity of 185 backedges. 0 proven. 104 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2018-06-22 11:19:18,345 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:18,345 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:18,352 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 11:19:18,382 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 11:19:18,382 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:18,385 INFO ]: Computing forward predicates... [2018-06-22 11:19:18,707 INFO ]: Checked inductivity of 185 backedges. 0 proven. 110 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2018-06-22 11:19:18,726 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:18,726 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 16] total 23 [2018-06-22 11:19:18,727 INFO ]: Interpolant automaton has 23 states [2018-06-22 11:19:18,727 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 11:19:18,727 INFO ]: CoverageRelationStatistics Valid=55, Invalid=451, Unknown=0, NotChecked=0, Total=506 [2018-06-22 11:19:18,727 INFO ]: Start difference. First operand 34 states and 38 transitions. Second operand 23 states. [2018-06-22 11:19:19,003 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:19,003 INFO ]: Finished difference Result 50 states and 56 transitions. [2018-06-22 11:19:19,006 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-22 11:19:19,006 INFO ]: Start accepts. Automaton has 23 states. Word has length 49 [2018-06-22 11:19:19,006 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:19,007 INFO ]: With dead ends: 50 [2018-06-22 11:19:19,007 INFO ]: Without dead ends: 50 [2018-06-22 11:19:19,007 INFO ]: 0 DeclaredPredicates, 82 GetRequests, 37 SyntacticMatches, 14 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 213 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=111, Invalid=945, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 11:19:19,007 INFO ]: Start minimizeSevpa. Operand 50 states. [2018-06-22 11:19:19,014 INFO ]: Finished minimizeSevpa. Reduced states from 50 to 38. [2018-06-22 11:19:19,014 INFO ]: Start removeUnreachable. Operand 38 states. [2018-06-22 11:19:19,014 INFO ]: Finished removeUnreachable. Reduced from 38 states to 38 states and 43 transitions. [2018-06-22 11:19:19,014 INFO ]: Start accepts. Automaton has 38 states and 43 transitions. Word has length 49 [2018-06-22 11:19:19,015 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:19,015 INFO ]: Abstraction has 38 states and 43 transitions. [2018-06-22 11:19:19,015 INFO ]: Interpolant automaton has 23 states. [2018-06-22 11:19:19,015 INFO ]: Start isEmpty. Operand 38 states and 43 transitions. [2018-06-22 11:19:19,015 INFO ]: Finished isEmpty. Found accepting run of length 54 [2018-06-22 11:19:19,015 INFO ]: Found error trace [2018-06-22 11:19:19,015 INFO ]: trace histogram [12, 6, 6, 6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:19,015 INFO ]: === Iteration 22 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:19,016 INFO ]: Analyzing trace with hash -2028323247, now seen corresponding path program 15 times [2018-06-22 11:19:19,016 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:19,016 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:19,016 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:19,016 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:19,016 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:19,031 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:19,233 INFO ]: Checked inductivity of 223 backedges. 20 proven. 117 refuted. 0 times theorem prover too weak. 86 trivial. 0 not checked. [2018-06-22 11:19:19,234 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:19,234 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:19,240 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 11:19:19,348 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2018-06-22 11:19:19,348 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:19,351 INFO ]: Computing forward predicates... [2018-06-22 11:19:19,666 INFO ]: Checked inductivity of 223 backedges. 0 proven. 137 refuted. 0 times theorem prover too weak. 86 trivial. 0 not checked. [2018-06-22 11:19:19,686 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:19,686 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 32 [2018-06-22 11:19:19,686 INFO ]: Interpolant automaton has 32 states [2018-06-22 11:19:19,686 INFO ]: Constructing interpolant automaton starting with 32 interpolants. [2018-06-22 11:19:19,686 INFO ]: CoverageRelationStatistics Valid=142, Invalid=850, Unknown=0, NotChecked=0, Total=992 [2018-06-22 11:19:19,686 INFO ]: Start difference. First operand 38 states and 43 transitions. Second operand 32 states. [2018-06-22 11:19:20,778 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:20,778 INFO ]: Finished difference Result 106 states and 118 transitions. [2018-06-22 11:19:20,780 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2018-06-22 11:19:20,780 INFO ]: Start accepts. Automaton has 32 states. Word has length 53 [2018-06-22 11:19:20,780 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:20,780 INFO ]: With dead ends: 106 [2018-06-22 11:19:20,780 INFO ]: Without dead ends: 106 [2018-06-22 11:19:20,781 INFO ]: 0 DeclaredPredicates, 115 GetRequests, 47 SyntacticMatches, 1 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1206 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=1029, Invalid=3663, Unknown=0, NotChecked=0, Total=4692 [2018-06-22 11:19:20,781 INFO ]: Start minimizeSevpa. Operand 106 states. [2018-06-22 11:19:20,786 INFO ]: Finished minimizeSevpa. Reduced states from 106 to 36. [2018-06-22 11:19:20,786 INFO ]: Start removeUnreachable. Operand 36 states. [2018-06-22 11:19:20,787 INFO ]: Finished removeUnreachable. Reduced from 36 states to 36 states and 40 transitions. [2018-06-22 11:19:20,787 INFO ]: Start accepts. Automaton has 36 states and 40 transitions. Word has length 53 [2018-06-22 11:19:20,787 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:20,787 INFO ]: Abstraction has 36 states and 40 transitions. [2018-06-22 11:19:20,787 INFO ]: Interpolant automaton has 32 states. [2018-06-22 11:19:20,787 INFO ]: Start isEmpty. Operand 36 states and 40 transitions. [2018-06-22 11:19:20,788 INFO ]: Finished isEmpty. Found accepting run of length 54 [2018-06-22 11:19:20,788 INFO ]: Found error trace [2018-06-22 11:19:20,788 INFO ]: trace histogram [12, 6, 6, 6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:20,788 INFO ]: === Iteration 23 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:20,788 INFO ]: Analyzing trace with hash 2120146870, now seen corresponding path program 16 times [2018-06-22 11:19:20,788 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:20,788 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:20,789 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:20,789 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:20,789 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:20,804 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:21,022 INFO ]: Checked inductivity of 223 backedges. 42 proven. 99 refuted. 0 times theorem prover too weak. 82 trivial. 0 not checked. [2018-06-22 11:19:21,022 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:21,022 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:21,032 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 11:19:21,066 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 11:19:21,066 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:21,069 INFO ]: Computing forward predicates... [2018-06-22 11:19:21,302 INFO ]: Checked inductivity of 223 backedges. 46 proven. 95 refuted. 0 times theorem prover too weak. 82 trivial. 0 not checked. [2018-06-22 11:19:21,334 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:21,334 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 30 [2018-06-22 11:19:21,335 INFO ]: Interpolant automaton has 30 states [2018-06-22 11:19:21,335 INFO ]: Constructing interpolant automaton starting with 30 interpolants. [2018-06-22 11:19:21,335 INFO ]: CoverageRelationStatistics Valid=132, Invalid=738, Unknown=0, NotChecked=0, Total=870 [2018-06-22 11:19:21,335 INFO ]: Start difference. First operand 36 states and 40 transitions. Second operand 30 states. [2018-06-22 11:19:22,295 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:22,295 INFO ]: Finished difference Result 52 states and 57 transitions. [2018-06-22 11:19:22,296 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 11:19:22,296 INFO ]: Start accepts. Automaton has 30 states. Word has length 53 [2018-06-22 11:19:22,296 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:22,296 INFO ]: With dead ends: 52 [2018-06-22 11:19:22,296 INFO ]: Without dead ends: 40 [2018-06-22 11:19:22,297 INFO ]: 0 DeclaredPredicates, 88 GetRequests, 48 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 390 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=298, Invalid=1424, Unknown=0, NotChecked=0, Total=1722 [2018-06-22 11:19:22,297 INFO ]: Start minimizeSevpa. Operand 40 states. [2018-06-22 11:19:22,299 INFO ]: Finished minimizeSevpa. Reduced states from 40 to 38. [2018-06-22 11:19:22,299 INFO ]: Start removeUnreachable. Operand 38 states. [2018-06-22 11:19:22,299 INFO ]: Finished removeUnreachable. Reduced from 38 states to 38 states and 42 transitions. [2018-06-22 11:19:22,299 INFO ]: Start accepts. Automaton has 38 states and 42 transitions. Word has length 53 [2018-06-22 11:19:22,300 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:22,300 INFO ]: Abstraction has 38 states and 42 transitions. [2018-06-22 11:19:22,300 INFO ]: Interpolant automaton has 30 states. [2018-06-22 11:19:22,300 INFO ]: Start isEmpty. Operand 38 states and 42 transitions. [2018-06-22 11:19:22,300 INFO ]: Finished isEmpty. Found accepting run of length 58 [2018-06-22 11:19:22,300 INFO ]: Found error trace [2018-06-22 11:19:22,300 INFO ]: trace histogram [13, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:22,300 INFO ]: === Iteration 24 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:22,300 INFO ]: Analyzing trace with hash -1780108517, now seen corresponding path program 17 times [2018-06-22 11:19:22,300 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:22,300 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:22,301 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:22,301 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:22,301 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:22,317 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:22,728 INFO ]: Checked inductivity of 264 backedges. 0 proven. 149 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2018-06-22 11:19:22,728 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:22,728 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:22,735 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 11:19:22,772 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 13 check-sat command(s) [2018-06-22 11:19:22,772 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:22,776 INFO ]: Computing forward predicates... [2018-06-22 11:19:23,065 INFO ]: Checked inductivity of 264 backedges. 0 proven. 156 refuted. 0 times theorem prover too weak. 108 trivial. 0 not checked. [2018-06-22 11:19:23,084 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:23,084 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 18] total 26 [2018-06-22 11:19:23,084 INFO ]: Interpolant automaton has 26 states [2018-06-22 11:19:23,084 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-22 11:19:23,085 INFO ]: CoverageRelationStatistics Valid=63, Invalid=587, Unknown=0, NotChecked=0, Total=650 [2018-06-22 11:19:23,085 INFO ]: Start difference. First operand 38 states and 42 transitions. Second operand 26 states. [2018-06-22 11:19:23,357 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:23,357 INFO ]: Finished difference Result 56 states and 62 transitions. [2018-06-22 11:19:23,357 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-06-22 11:19:23,357 INFO ]: Start accepts. Automaton has 26 states. Word has length 57 [2018-06-22 11:19:23,358 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:23,358 INFO ]: With dead ends: 56 [2018-06-22 11:19:23,358 INFO ]: Without dead ends: 56 [2018-06-22 11:19:23,359 INFO ]: 0 DeclaredPredicates, 96 GetRequests, 43 SyntacticMatches, 17 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 303 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=130, Invalid=1276, Unknown=0, NotChecked=0, Total=1406 [2018-06-22 11:19:23,359 INFO ]: Start minimizeSevpa. Operand 56 states. [2018-06-22 11:19:23,362 INFO ]: Finished minimizeSevpa. Reduced states from 56 to 42. [2018-06-22 11:19:23,362 INFO ]: Start removeUnreachable. Operand 42 states. [2018-06-22 11:19:23,362 INFO ]: Finished removeUnreachable. Reduced from 42 states to 42 states and 47 transitions. [2018-06-22 11:19:23,362 INFO ]: Start accepts. Automaton has 42 states and 47 transitions. Word has length 57 [2018-06-22 11:19:23,362 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:23,363 INFO ]: Abstraction has 42 states and 47 transitions. [2018-06-22 11:19:23,363 INFO ]: Interpolant automaton has 26 states. [2018-06-22 11:19:23,363 INFO ]: Start isEmpty. Operand 42 states and 47 transitions. [2018-06-22 11:19:23,363 INFO ]: Finished isEmpty. Found accepting run of length 62 [2018-06-22 11:19:23,363 INFO ]: Found error trace [2018-06-22 11:19:23,363 INFO ]: trace histogram [14, 7, 7, 7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:23,363 INFO ]: === Iteration 25 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:23,363 INFO ]: Analyzing trace with hash -809604800, now seen corresponding path program 18 times [2018-06-22 11:19:23,363 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:23,363 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:23,364 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:23,364 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:23,364 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:23,376 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:23,681 INFO ]: Checked inductivity of 309 backedges. 30 proven. 158 refuted. 0 times theorem prover too weak. 121 trivial. 0 not checked. [2018-06-22 11:19:23,681 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:23,681 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:23,686 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 11:19:23,735 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 14 check-sat command(s) [2018-06-22 11:19:23,735 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:23,739 INFO ]: Computing forward predicates... [2018-06-22 11:19:24,029 INFO ]: Checked inductivity of 309 backedges. 0 proven. 188 refuted. 0 times theorem prover too weak. 121 trivial. 0 not checked. [2018-06-22 11:19:24,048 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:24,048 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 36 [2018-06-22 11:19:24,048 INFO ]: Interpolant automaton has 36 states [2018-06-22 11:19:24,048 INFO ]: Constructing interpolant automaton starting with 36 interpolants. [2018-06-22 11:19:24,049 INFO ]: CoverageRelationStatistics Valid=180, Invalid=1080, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 11:19:24,049 INFO ]: Start difference. First operand 42 states and 47 transitions. Second operand 36 states. [2018-06-22 11:19:25,735 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:25,735 INFO ]: Finished difference Result 128 states and 141 transitions. [2018-06-22 11:19:25,735 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2018-06-22 11:19:25,735 INFO ]: Start accepts. Automaton has 36 states. Word has length 61 [2018-06-22 11:19:25,736 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:25,736 INFO ]: With dead ends: 128 [2018-06-22 11:19:25,736 INFO ]: Without dead ends: 128 [2018-06-22 11:19:25,738 INFO ]: 0 DeclaredPredicates, 137 GetRequests, 55 SyntacticMatches, 1 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1879 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=1518, Invalid=5288, Unknown=0, NotChecked=0, Total=6806 [2018-06-22 11:19:25,738 INFO ]: Start minimizeSevpa. Operand 128 states. [2018-06-22 11:19:25,742 INFO ]: Finished minimizeSevpa. Reduced states from 128 to 40. [2018-06-22 11:19:25,742 INFO ]: Start removeUnreachable. Operand 40 states. [2018-06-22 11:19:25,743 INFO ]: Finished removeUnreachable. Reduced from 40 states to 40 states and 44 transitions. [2018-06-22 11:19:25,743 INFO ]: Start accepts. Automaton has 40 states and 44 transitions. Word has length 61 [2018-06-22 11:19:25,744 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:25,744 INFO ]: Abstraction has 40 states and 44 transitions. [2018-06-22 11:19:25,744 INFO ]: Interpolant automaton has 36 states. [2018-06-22 11:19:25,744 INFO ]: Start isEmpty. Operand 40 states and 44 transitions. [2018-06-22 11:19:25,744 INFO ]: Finished isEmpty. Found accepting run of length 62 [2018-06-22 11:19:25,744 INFO ]: Found error trace [2018-06-22 11:19:25,744 INFO ]: trace histogram [14, 7, 7, 7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:25,744 INFO ]: === Iteration 26 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:25,744 INFO ]: Analyzing trace with hash 1912822757, now seen corresponding path program 19 times [2018-06-22 11:19:25,745 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:25,745 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:25,745 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:25,745 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:25,745 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:25,757 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:26,183 INFO ]: Checked inductivity of 309 backedges. 56 proven. 137 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2018-06-22 11:19:26,183 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:26,183 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:26,188 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:26,246 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:26,251 INFO ]: Computing forward predicates... [2018-06-22 11:19:26,812 INFO ]: Checked inductivity of 309 backedges. 61 proven. 132 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2018-06-22 11:19:26,830 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:26,830 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 34 [2018-06-22 11:19:26,831 INFO ]: Interpolant automaton has 34 states [2018-06-22 11:19:26,831 INFO ]: Constructing interpolant automaton starting with 34 interpolants. [2018-06-22 11:19:26,831 INFO ]: CoverageRelationStatistics Valid=169, Invalid=953, Unknown=0, NotChecked=0, Total=1122 [2018-06-22 11:19:26,831 INFO ]: Start difference. First operand 40 states and 44 transitions. Second operand 34 states. [2018-06-22 11:19:27,705 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 17 [2018-06-22 11:19:27,740 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:27,740 INFO ]: Finished difference Result 58 states and 63 transitions. [2018-06-22 11:19:27,741 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-06-22 11:19:27,741 INFO ]: Start accepts. Automaton has 34 states. Word has length 61 [2018-06-22 11:19:27,741 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:27,742 INFO ]: With dead ends: 58 [2018-06-22 11:19:27,742 INFO ]: Without dead ends: 44 [2018-06-22 11:19:27,743 INFO ]: 0 DeclaredPredicates, 102 GetRequests, 56 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 540 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=381, Invalid=1875, Unknown=0, NotChecked=0, Total=2256 [2018-06-22 11:19:27,743 INFO ]: Start minimizeSevpa. Operand 44 states. [2018-06-22 11:19:27,744 INFO ]: Finished minimizeSevpa. Reduced states from 44 to 42. [2018-06-22 11:19:27,744 INFO ]: Start removeUnreachable. Operand 42 states. [2018-06-22 11:19:27,745 INFO ]: Finished removeUnreachable. Reduced from 42 states to 42 states and 46 transitions. [2018-06-22 11:19:27,745 INFO ]: Start accepts. Automaton has 42 states and 46 transitions. Word has length 61 [2018-06-22 11:19:27,745 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:27,745 INFO ]: Abstraction has 42 states and 46 transitions. [2018-06-22 11:19:27,745 INFO ]: Interpolant automaton has 34 states. [2018-06-22 11:19:27,745 INFO ]: Start isEmpty. Operand 42 states and 46 transitions. [2018-06-22 11:19:27,746 INFO ]: Finished isEmpty. Found accepting run of length 66 [2018-06-22 11:19:27,746 INFO ]: Found error trace [2018-06-22 11:19:27,746 INFO ]: trace histogram [15, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:27,746 INFO ]: === Iteration 27 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:27,746 INFO ]: Analyzing trace with hash -845145270, now seen corresponding path program 20 times [2018-06-22 11:19:27,746 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:27,746 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:27,747 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:27,747 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:27,747 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:27,758 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:28,029 INFO ]: Checked inductivity of 357 backedges. 0 proven. 202 refuted. 0 times theorem prover too weak. 155 trivial. 0 not checked. [2018-06-22 11:19:28,029 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:28,029 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 11:19:28,043 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:28,082 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 11:19:28,082 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:28,085 INFO ]: Computing forward predicates... [2018-06-22 11:19:28,438 INFO ]: Checked inductivity of 357 backedges. 0 proven. 210 refuted. 0 times theorem prover too weak. 147 trivial. 0 not checked. [2018-06-22 11:19:28,469 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:28,470 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 20] total 29 [2018-06-22 11:19:28,470 INFO ]: Interpolant automaton has 29 states [2018-06-22 11:19:28,470 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-22 11:19:28,470 INFO ]: CoverageRelationStatistics Valid=71, Invalid=741, Unknown=0, NotChecked=0, Total=812 [2018-06-22 11:19:28,470 INFO ]: Start difference. First operand 42 states and 46 transitions. Second operand 29 states. [2018-06-22 11:19:28,892 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:28,892 INFO ]: Finished difference Result 62 states and 68 transitions. [2018-06-22 11:19:28,893 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-06-22 11:19:28,893 INFO ]: Start accepts. Automaton has 29 states. Word has length 65 [2018-06-22 11:19:28,893 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:28,894 INFO ]: With dead ends: 62 [2018-06-22 11:19:28,894 INFO ]: Without dead ends: 62 [2018-06-22 11:19:28,894 INFO ]: 0 DeclaredPredicates, 110 GetRequests, 49 SyntacticMatches, 20 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 409 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=149, Invalid=1657, Unknown=0, NotChecked=0, Total=1806 [2018-06-22 11:19:28,894 INFO ]: Start minimizeSevpa. Operand 62 states. [2018-06-22 11:19:28,899 INFO ]: Finished minimizeSevpa. Reduced states from 62 to 46. [2018-06-22 11:19:28,899 INFO ]: Start removeUnreachable. Operand 46 states. [2018-06-22 11:19:28,899 INFO ]: Finished removeUnreachable. Reduced from 46 states to 46 states and 51 transitions. [2018-06-22 11:19:28,899 INFO ]: Start accepts. Automaton has 46 states and 51 transitions. Word has length 65 [2018-06-22 11:19:28,900 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:28,900 INFO ]: Abstraction has 46 states and 51 transitions. [2018-06-22 11:19:28,900 INFO ]: Interpolant automaton has 29 states. [2018-06-22 11:19:28,900 INFO ]: Start isEmpty. Operand 46 states and 51 transitions. [2018-06-22 11:19:28,900 INFO ]: Finished isEmpty. Found accepting run of length 70 [2018-06-22 11:19:28,900 INFO ]: Found error trace [2018-06-22 11:19:28,900 INFO ]: trace histogram [16, 8, 8, 8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:28,901 INFO ]: === Iteration 28 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:28,901 INFO ]: Analyzing trace with hash 15211887, now seen corresponding path program 21 times [2018-06-22 11:19:28,901 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:28,901 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:28,901 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:28,901 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:28,901 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:28,916 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:29,138 INFO ]: Checked inductivity of 409 backedges. 42 proven. 205 refuted. 0 times theorem prover too weak. 162 trivial. 0 not checked. [2018-06-22 11:19:29,138 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:29,138 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:29,145 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 11:19:29,197 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2018-06-22 11:19:29,197 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:29,201 INFO ]: Computing forward predicates... [2018-06-22 11:19:29,556 INFO ]: Checked inductivity of 409 backedges. 0 proven. 247 refuted. 0 times theorem prover too weak. 162 trivial. 0 not checked. [2018-06-22 11:19:29,575 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:29,575 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 40 [2018-06-22 11:19:29,575 INFO ]: Interpolant automaton has 40 states [2018-06-22 11:19:29,576 INFO ]: Constructing interpolant automaton starting with 40 interpolants. [2018-06-22 11:19:29,576 INFO ]: CoverageRelationStatistics Valid=223, Invalid=1337, Unknown=0, NotChecked=0, Total=1560 [2018-06-22 11:19:29,576 INFO ]: Start difference. First operand 46 states and 51 transitions. Second operand 40 states. [2018-06-22 11:19:31,067 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:31,067 INFO ]: Finished difference Result 152 states and 166 transitions. [2018-06-22 11:19:31,067 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 63 states. [2018-06-22 11:19:31,067 INFO ]: Start accepts. Automaton has 40 states. Word has length 69 [2018-06-22 11:19:31,068 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:31,069 INFO ]: With dead ends: 152 [2018-06-22 11:19:31,069 INFO ]: Without dead ends: 152 [2018-06-22 11:19:31,071 INFO ]: 0 DeclaredPredicates, 160 GetRequests, 63 SyntacticMatches, 1 SemanticMatches, 96 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2773 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=2156, Invalid=7350, Unknown=0, NotChecked=0, Total=9506 [2018-06-22 11:19:31,072 INFO ]: Start minimizeSevpa. Operand 152 states. [2018-06-22 11:19:31,077 INFO ]: Finished minimizeSevpa. Reduced states from 152 to 44. [2018-06-22 11:19:31,077 INFO ]: Start removeUnreachable. Operand 44 states. [2018-06-22 11:19:31,077 INFO ]: Finished removeUnreachable. Reduced from 44 states to 44 states and 48 transitions. [2018-06-22 11:19:31,077 INFO ]: Start accepts. Automaton has 44 states and 48 transitions. Word has length 69 [2018-06-22 11:19:31,077 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:31,077 INFO ]: Abstraction has 44 states and 48 transitions. [2018-06-22 11:19:31,077 INFO ]: Interpolant automaton has 40 states. [2018-06-22 11:19:31,077 INFO ]: Start isEmpty. Operand 44 states and 48 transitions. [2018-06-22 11:19:31,078 INFO ]: Finished isEmpty. Found accepting run of length 70 [2018-06-22 11:19:31,078 INFO ]: Found error trace [2018-06-22 11:19:31,078 INFO ]: trace histogram [16, 8, 8, 8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:31,078 INFO ]: === Iteration 29 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:31,078 INFO ]: Analyzing trace with hash -984403628, now seen corresponding path program 22 times [2018-06-22 11:19:31,078 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:31,078 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:31,079 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:31,079 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:31,079 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:31,093 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:31,377 INFO ]: Checked inductivity of 409 backedges. 72 proven. 181 refuted. 0 times theorem prover too weak. 156 trivial. 0 not checked. [2018-06-22 11:19:31,377 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:31,377 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:31,384 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 11:19:31,433 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 11:19:31,433 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:31,437 INFO ]: Computing forward predicates... [2018-06-22 11:19:31,833 INFO ]: Checked inductivity of 409 backedges. 78 proven. 175 refuted. 0 times theorem prover too weak. 156 trivial. 0 not checked. [2018-06-22 11:19:31,852 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:31,852 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 38 [2018-06-22 11:19:31,852 INFO ]: Interpolant automaton has 38 states [2018-06-22 11:19:31,852 INFO ]: Constructing interpolant automaton starting with 38 interpolants. [2018-06-22 11:19:31,852 INFO ]: CoverageRelationStatistics Valid=211, Invalid=1195, Unknown=0, NotChecked=0, Total=1406 [2018-06-22 11:19:31,853 INFO ]: Start difference. First operand 44 states and 48 transitions. Second operand 38 states. [2018-06-22 11:19:32,278 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:32,278 INFO ]: Finished difference Result 64 states and 69 transitions. [2018-06-22 11:19:32,279 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-22 11:19:32,279 INFO ]: Start accepts. Automaton has 38 states. Word has length 69 [2018-06-22 11:19:32,279 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:32,279 INFO ]: With dead ends: 64 [2018-06-22 11:19:32,279 INFO ]: Without dead ends: 48 [2018-06-22 11:19:32,280 INFO ]: 0 DeclaredPredicates, 116 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 714 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=474, Invalid=2388, Unknown=0, NotChecked=0, Total=2862 [2018-06-22 11:19:32,280 INFO ]: Start minimizeSevpa. Operand 48 states. [2018-06-22 11:19:32,283 INFO ]: Finished minimizeSevpa. Reduced states from 48 to 46. [2018-06-22 11:19:32,283 INFO ]: Start removeUnreachable. Operand 46 states. [2018-06-22 11:19:32,285 INFO ]: Finished removeUnreachable. Reduced from 46 states to 46 states and 50 transitions. [2018-06-22 11:19:32,285 INFO ]: Start accepts. Automaton has 46 states and 50 transitions. Word has length 69 [2018-06-22 11:19:32,285 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:32,285 INFO ]: Abstraction has 46 states and 50 transitions. [2018-06-22 11:19:32,285 INFO ]: Interpolant automaton has 38 states. [2018-06-22 11:19:32,285 INFO ]: Start isEmpty. Operand 46 states and 50 transitions. [2018-06-22 11:19:32,286 INFO ]: Finished isEmpty. Found accepting run of length 74 [2018-06-22 11:19:32,286 INFO ]: Found error trace [2018-06-22 11:19:32,286 INFO ]: trace histogram [17, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:32,286 INFO ]: === Iteration 30 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:32,286 INFO ]: Analyzing trace with hash -334119751, now seen corresponding path program 23 times [2018-06-22 11:19:32,286 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:32,286 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:32,286 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:32,286 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:32,286 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:32,303 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:33,423 INFO ]: Checked inductivity of 464 backedges. 0 proven. 263 refuted. 0 times theorem prover too weak. 201 trivial. 0 not checked. [2018-06-22 11:19:33,423 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:33,451 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:33,460 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 11:19:33,514 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 17 check-sat command(s) [2018-06-22 11:19:33,514 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:33,518 INFO ]: Computing forward predicates... [2018-06-22 11:19:34,059 INFO ]: Checked inductivity of 464 backedges. 0 proven. 272 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2018-06-22 11:19:34,077 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:34,078 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 22] total 32 [2018-06-22 11:19:34,078 INFO ]: Interpolant automaton has 32 states [2018-06-22 11:19:34,078 INFO ]: Constructing interpolant automaton starting with 32 interpolants. [2018-06-22 11:19:34,078 INFO ]: CoverageRelationStatistics Valid=79, Invalid=913, Unknown=0, NotChecked=0, Total=992 [2018-06-22 11:19:34,078 INFO ]: Start difference. First operand 46 states and 50 transitions. Second operand 32 states. [2018-06-22 11:19:34,515 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:34,515 INFO ]: Finished difference Result 68 states and 74 transitions. [2018-06-22 11:19:34,515 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-06-22 11:19:34,515 INFO ]: Start accepts. Automaton has 32 states. Word has length 73 [2018-06-22 11:19:34,515 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:34,515 INFO ]: With dead ends: 68 [2018-06-22 11:19:34,515 INFO ]: Without dead ends: 68 [2018-06-22 11:19:34,516 INFO ]: 0 DeclaredPredicates, 124 GetRequests, 55 SyntacticMatches, 23 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 531 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=168, Invalid=2088, Unknown=0, NotChecked=0, Total=2256 [2018-06-22 11:19:34,516 INFO ]: Start minimizeSevpa. Operand 68 states. [2018-06-22 11:19:34,519 INFO ]: Finished minimizeSevpa. Reduced states from 68 to 50. [2018-06-22 11:19:34,519 INFO ]: Start removeUnreachable. Operand 50 states. [2018-06-22 11:19:34,520 INFO ]: Finished removeUnreachable. Reduced from 50 states to 50 states and 55 transitions. [2018-06-22 11:19:34,520 INFO ]: Start accepts. Automaton has 50 states and 55 transitions. Word has length 73 [2018-06-22 11:19:34,520 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:34,520 INFO ]: Abstraction has 50 states and 55 transitions. [2018-06-22 11:19:34,520 INFO ]: Interpolant automaton has 32 states. [2018-06-22 11:19:34,520 INFO ]: Start isEmpty. Operand 50 states and 55 transitions. [2018-06-22 11:19:34,521 INFO ]: Finished isEmpty. Found accepting run of length 78 [2018-06-22 11:19:34,521 INFO ]: Found error trace [2018-06-22 11:19:34,521 INFO ]: trace histogram [18, 9, 9, 9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:34,521 INFO ]: === Iteration 31 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:34,521 INFO ]: Analyzing trace with hash 1849486046, now seen corresponding path program 24 times [2018-06-22 11:19:34,521 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:34,522 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:34,522 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:34,522 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:34,522 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:34,538 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:34,862 INFO ]: Checked inductivity of 523 backedges. 56 proven. 258 refuted. 0 times theorem prover too weak. 209 trivial. 0 not checked. [2018-06-22 11:19:34,862 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:34,862 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:34,868 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 11:19:34,927 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) [2018-06-22 11:19:34,927 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:34,932 INFO ]: Computing forward predicates... [2018-06-22 11:19:35,423 INFO ]: Checked inductivity of 523 backedges. 0 proven. 314 refuted. 0 times theorem prover too weak. 209 trivial. 0 not checked. [2018-06-22 11:19:35,444 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:35,444 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 44 [2018-06-22 11:19:35,444 INFO ]: Interpolant automaton has 44 states [2018-06-22 11:19:35,445 INFO ]: Constructing interpolant automaton starting with 44 interpolants. [2018-06-22 11:19:35,445 INFO ]: CoverageRelationStatistics Valid=271, Invalid=1621, Unknown=0, NotChecked=0, Total=1892 [2018-06-22 11:19:35,445 INFO ]: Start difference. First operand 50 states and 55 transitions. Second operand 44 states. [2018-06-22 11:19:37,301 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:37,302 INFO ]: Finished difference Result 178 states and 193 transitions. [2018-06-22 11:19:37,302 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 75 states. [2018-06-22 11:19:37,302 INFO ]: Start accepts. Automaton has 44 states. Word has length 77 [2018-06-22 11:19:37,302 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:37,303 INFO ]: With dead ends: 178 [2018-06-22 11:19:37,303 INFO ]: Without dead ends: 178 [2018-06-22 11:19:37,304 INFO ]: 0 DeclaredPredicates, 184 GetRequests, 71 SyntacticMatches, 1 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4184 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=2969, Invalid=9913, Unknown=0, NotChecked=0, Total=12882 [2018-06-22 11:19:37,304 INFO ]: Start minimizeSevpa. Operand 178 states. [2018-06-22 11:19:37,310 INFO ]: Finished minimizeSevpa. Reduced states from 178 to 48. [2018-06-22 11:19:37,310 INFO ]: Start removeUnreachable. Operand 48 states. [2018-06-22 11:19:37,310 INFO ]: Finished removeUnreachable. Reduced from 48 states to 48 states and 52 transitions. [2018-06-22 11:19:37,310 INFO ]: Start accepts. Automaton has 48 states and 52 transitions. Word has length 77 [2018-06-22 11:19:37,310 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:37,310 INFO ]: Abstraction has 48 states and 52 transitions. [2018-06-22 11:19:37,310 INFO ]: Interpolant automaton has 44 states. [2018-06-22 11:19:37,310 INFO ]: Start isEmpty. Operand 48 states and 52 transitions. [2018-06-22 11:19:37,311 INFO ]: Finished isEmpty. Found accepting run of length 78 [2018-06-22 11:19:37,311 INFO ]: Found error trace [2018-06-22 11:19:37,311 INFO ]: trace histogram [18, 9, 9, 9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:37,311 INFO ]: === Iteration 32 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:37,311 INFO ]: Analyzing trace with hash 1432875011, now seen corresponding path program 25 times [2018-06-22 11:19:37,311 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:37,311 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:37,311 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:37,311 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:37,311 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:37,325 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:37,905 INFO ]: Checked inductivity of 523 backedges. 90 proven. 231 refuted. 0 times theorem prover too weak. 202 trivial. 0 not checked. [2018-06-22 11:19:37,905 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:37,905 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:37,912 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:37,962 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:37,967 INFO ]: Computing forward predicates... [2018-06-22 11:19:38,347 INFO ]: Checked inductivity of 523 backedges. 97 proven. 224 refuted. 0 times theorem prover too weak. 202 trivial. 0 not checked. [2018-06-22 11:19:38,366 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:38,366 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23] total 42 [2018-06-22 11:19:38,366 INFO ]: Interpolant automaton has 42 states [2018-06-22 11:19:38,366 INFO ]: Constructing interpolant automaton starting with 42 interpolants. [2018-06-22 11:19:38,366 INFO ]: CoverageRelationStatistics Valid=258, Invalid=1464, Unknown=0, NotChecked=0, Total=1722 [2018-06-22 11:19:38,366 INFO ]: Start difference. First operand 48 states and 52 transitions. Second operand 42 states. [2018-06-22 11:19:38,865 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:38,865 INFO ]: Finished difference Result 70 states and 75 transitions. [2018-06-22 11:19:38,884 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-06-22 11:19:38,884 INFO ]: Start accepts. Automaton has 42 states. Word has length 77 [2018-06-22 11:19:38,885 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:38,885 INFO ]: With dead ends: 70 [2018-06-22 11:19:38,885 INFO ]: Without dead ends: 52 [2018-06-22 11:19:38,886 INFO ]: 0 DeclaredPredicates, 130 GetRequests, 72 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 912 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=577, Invalid=2963, Unknown=0, NotChecked=0, Total=3540 [2018-06-22 11:19:38,886 INFO ]: Start minimizeSevpa. Operand 52 states. [2018-06-22 11:19:38,888 INFO ]: Finished minimizeSevpa. Reduced states from 52 to 50. [2018-06-22 11:19:38,888 INFO ]: Start removeUnreachable. Operand 50 states. [2018-06-22 11:19:38,888 INFO ]: Finished removeUnreachable. Reduced from 50 states to 50 states and 54 transitions. [2018-06-22 11:19:38,888 INFO ]: Start accepts. Automaton has 50 states and 54 transitions. Word has length 77 [2018-06-22 11:19:38,888 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:38,888 INFO ]: Abstraction has 50 states and 54 transitions. [2018-06-22 11:19:38,888 INFO ]: Interpolant automaton has 42 states. [2018-06-22 11:19:38,889 INFO ]: Start isEmpty. Operand 50 states and 54 transitions. [2018-06-22 11:19:38,889 INFO ]: Finished isEmpty. Found accepting run of length 82 [2018-06-22 11:19:38,889 INFO ]: Found error trace [2018-06-22 11:19:38,889 INFO ]: trace histogram [19, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:38,889 INFO ]: === Iteration 33 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:38,889 INFO ]: Analyzing trace with hash -825743512, now seen corresponding path program 26 times [2018-06-22 11:19:38,889 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:38,889 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:38,890 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:38,890 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:38,890 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:38,906 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:39,317 INFO ]: Checked inductivity of 585 backedges. 0 proven. 332 refuted. 0 times theorem prover too weak. 253 trivial. 0 not checked. [2018-06-22 11:19:39,317 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:39,317 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:39,322 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 11:19:39,401 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 11:19:39,401 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:39,412 INFO ]: Computing forward predicates... [2018-06-22 11:19:40,074 INFO ]: Checked inductivity of 585 backedges. 0 proven. 342 refuted. 0 times theorem prover too weak. 243 trivial. 0 not checked. [2018-06-22 11:19:40,093 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:40,093 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 24] total 35 [2018-06-22 11:19:40,093 INFO ]: Interpolant automaton has 35 states [2018-06-22 11:19:40,093 INFO ]: Constructing interpolant automaton starting with 35 interpolants. [2018-06-22 11:19:40,093 INFO ]: CoverageRelationStatistics Valid=87, Invalid=1103, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 11:19:40,094 INFO ]: Start difference. First operand 50 states and 54 transitions. Second operand 35 states. [2018-06-22 11:19:40,712 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:40,712 INFO ]: Finished difference Result 74 states and 80 transitions. [2018-06-22 11:19:40,712 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-06-22 11:19:40,712 INFO ]: Start accepts. Automaton has 35 states. Word has length 81 [2018-06-22 11:19:40,712 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:40,712 INFO ]: With dead ends: 74 [2018-06-22 11:19:40,712 INFO ]: Without dead ends: 74 [2018-06-22 11:19:40,713 INFO ]: 0 DeclaredPredicates, 138 GetRequests, 61 SyntacticMatches, 26 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 669 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=187, Invalid=2569, Unknown=0, NotChecked=0, Total=2756 [2018-06-22 11:19:40,713 INFO ]: Start minimizeSevpa. Operand 74 states. [2018-06-22 11:19:40,715 INFO ]: Finished minimizeSevpa. Reduced states from 74 to 54. [2018-06-22 11:19:40,715 INFO ]: Start removeUnreachable. Operand 54 states. [2018-06-22 11:19:40,715 INFO ]: Finished removeUnreachable. Reduced from 54 states to 54 states and 59 transitions. [2018-06-22 11:19:40,715 INFO ]: Start accepts. Automaton has 54 states and 59 transitions. Word has length 81 [2018-06-22 11:19:40,715 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:40,715 INFO ]: Abstraction has 54 states and 59 transitions. [2018-06-22 11:19:40,715 INFO ]: Interpolant automaton has 35 states. [2018-06-22 11:19:40,715 INFO ]: Start isEmpty. Operand 54 states and 59 transitions. [2018-06-22 11:19:40,716 INFO ]: Finished isEmpty. Found accepting run of length 86 [2018-06-22 11:19:40,716 INFO ]: Found error trace [2018-06-22 11:19:40,716 INFO ]: trace histogram [20, 10, 10, 10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:40,716 INFO ]: === Iteration 34 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:40,716 INFO ]: Analyzing trace with hash 1504076173, now seen corresponding path program 27 times [2018-06-22 11:19:40,716 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:40,716 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:40,716 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:40,716 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:40,716 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:40,729 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:41,703 INFO ]: Checked inductivity of 651 backedges. 72 proven. 317 refuted. 0 times theorem prover too weak. 262 trivial. 0 not checked. [2018-06-22 11:19:41,703 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:41,703 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:41,709 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 11:19:41,773 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2018-06-22 11:19:41,773 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:41,777 INFO ]: Computing forward predicates... [2018-06-22 11:19:42,260 INFO ]: Checked inductivity of 651 backedges. 0 proven. 389 refuted. 0 times theorem prover too weak. 262 trivial. 0 not checked. [2018-06-22 11:19:42,281 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:42,281 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 26] total 48 [2018-06-22 11:19:42,281 INFO ]: Interpolant automaton has 48 states [2018-06-22 11:19:42,281 INFO ]: Constructing interpolant automaton starting with 48 interpolants. [2018-06-22 11:19:42,281 INFO ]: CoverageRelationStatistics Valid=324, Invalid=1932, Unknown=0, NotChecked=0, Total=2256 [2018-06-22 11:19:42,281 INFO ]: Start difference. First operand 54 states and 59 transitions. Second operand 48 states. [2018-06-22 11:19:44,644 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:44,644 INFO ]: Finished difference Result 206 states and 222 transitions. [2018-06-22 11:19:44,644 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 88 states. [2018-06-22 11:19:44,645 INFO ]: Start accepts. Automaton has 48 states. Word has length 85 [2018-06-22 11:19:44,645 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:44,645 INFO ]: With dead ends: 206 [2018-06-22 11:19:44,645 INFO ]: Without dead ends: 206 [2018-06-22 11:19:44,647 INFO ]: 0 DeclaredPredicates, 209 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 129 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5383 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=3985, Invalid=13045, Unknown=0, NotChecked=0, Total=17030 [2018-06-22 11:19:44,647 INFO ]: Start minimizeSevpa. Operand 206 states. [2018-06-22 11:19:44,655 INFO ]: Finished minimizeSevpa. Reduced states from 206 to 52. [2018-06-22 11:19:44,655 INFO ]: Start removeUnreachable. Operand 52 states. [2018-06-22 11:19:44,655 INFO ]: Finished removeUnreachable. Reduced from 52 states to 52 states and 56 transitions. [2018-06-22 11:19:44,655 INFO ]: Start accepts. Automaton has 52 states and 56 transitions. Word has length 85 [2018-06-22 11:19:44,655 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:44,655 INFO ]: Abstraction has 52 states and 56 transitions. [2018-06-22 11:19:44,655 INFO ]: Interpolant automaton has 48 states. [2018-06-22 11:19:44,655 INFO ]: Start isEmpty. Operand 52 states and 56 transitions. [2018-06-22 11:19:44,656 INFO ]: Finished isEmpty. Found accepting run of length 86 [2018-06-22 11:19:44,656 INFO ]: Found error trace [2018-06-22 11:19:44,657 INFO ]: trace histogram [20, 10, 10, 10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:44,657 INFO ]: === Iteration 35 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:44,657 INFO ]: Analyzing trace with hash 43984882, now seen corresponding path program 28 times [2018-06-22 11:19:44,657 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:44,657 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:44,657 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:44,657 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:44,657 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:44,672 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:44,972 INFO ]: Checked inductivity of 651 backedges. 110 proven. 287 refuted. 0 times theorem prover too weak. 254 trivial. 0 not checked. [2018-06-22 11:19:44,972 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:44,972 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:44,977 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 11:19:45,026 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 11:19:45,026 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:45,032 INFO ]: Computing forward predicates... [2018-06-22 11:19:45,615 INFO ]: Checked inductivity of 651 backedges. 118 proven. 279 refuted. 0 times theorem prover too weak. 254 trivial. 0 not checked. [2018-06-22 11:19:45,633 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:45,633 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 46 [2018-06-22 11:19:45,633 INFO ]: Interpolant automaton has 46 states [2018-06-22 11:19:45,634 INFO ]: Constructing interpolant automaton starting with 46 interpolants. [2018-06-22 11:19:45,634 INFO ]: CoverageRelationStatistics Valid=310, Invalid=1760, Unknown=0, NotChecked=0, Total=2070 [2018-06-22 11:19:45,634 INFO ]: Start difference. First operand 52 states and 56 transitions. Second operand 46 states. [2018-06-22 11:19:46,241 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:46,241 INFO ]: Finished difference Result 76 states and 81 transitions. [2018-06-22 11:19:46,241 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-06-22 11:19:46,242 INFO ]: Start accepts. Automaton has 46 states. Word has length 85 [2018-06-22 11:19:46,242 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:46,242 INFO ]: With dead ends: 76 [2018-06-22 11:19:46,242 INFO ]: Without dead ends: 56 [2018-06-22 11:19:46,243 INFO ]: 0 DeclaredPredicates, 144 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1134 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=690, Invalid=3600, Unknown=0, NotChecked=0, Total=4290 [2018-06-22 11:19:46,243 INFO ]: Start minimizeSevpa. Operand 56 states. [2018-06-22 11:19:46,245 INFO ]: Finished minimizeSevpa. Reduced states from 56 to 54. [2018-06-22 11:19:46,245 INFO ]: Start removeUnreachable. Operand 54 states. [2018-06-22 11:19:46,246 INFO ]: Finished removeUnreachable. Reduced from 54 states to 54 states and 58 transitions. [2018-06-22 11:19:46,246 INFO ]: Start accepts. Automaton has 54 states and 58 transitions. Word has length 85 [2018-06-22 11:19:46,246 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:46,246 INFO ]: Abstraction has 54 states and 58 transitions. [2018-06-22 11:19:46,246 INFO ]: Interpolant automaton has 46 states. [2018-06-22 11:19:46,246 INFO ]: Start isEmpty. Operand 54 states and 58 transitions. [2018-06-22 11:19:46,247 INFO ]: Finished isEmpty. Found accepting run of length 90 [2018-06-22 11:19:46,247 INFO ]: Found error trace [2018-06-22 11:19:46,247 INFO ]: trace histogram [21, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:46,247 INFO ]: === Iteration 36 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:46,247 INFO ]: Analyzing trace with hash -1065555113, now seen corresponding path program 29 times [2018-06-22 11:19:46,247 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:46,247 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:46,248 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:46,248 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:46,248 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:46,263 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:46,621 INFO ]: Checked inductivity of 720 backedges. 0 proven. 409 refuted. 0 times theorem prover too weak. 311 trivial. 0 not checked. [2018-06-22 11:19:46,621 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:46,621 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 34 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 34 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:46,626 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 11:19:46,687 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 21 check-sat command(s) [2018-06-22 11:19:46,687 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:46,695 INFO ]: Computing forward predicates... [2018-06-22 11:19:48,467 INFO ]: Checked inductivity of 720 backedges. 0 proven. 420 refuted. 0 times theorem prover too weak. 300 trivial. 0 not checked. [2018-06-22 11:19:48,487 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:48,487 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 26] total 38 [2018-06-22 11:19:48,487 INFO ]: Interpolant automaton has 38 states [2018-06-22 11:19:48,487 INFO ]: Constructing interpolant automaton starting with 38 interpolants. [2018-06-22 11:19:48,487 INFO ]: CoverageRelationStatistics Valid=95, Invalid=1311, Unknown=0, NotChecked=0, Total=1406 [2018-06-22 11:19:48,487 INFO ]: Start difference. First operand 54 states and 58 transitions. Second operand 38 states. [2018-06-22 11:19:49,130 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:49,130 INFO ]: Finished difference Result 80 states and 86 transitions. [2018-06-22 11:19:49,130 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-06-22 11:19:49,130 INFO ]: Start accepts. Automaton has 38 states. Word has length 89 [2018-06-22 11:19:49,131 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:49,131 INFO ]: With dead ends: 80 [2018-06-22 11:19:49,131 INFO ]: Without dead ends: 80 [2018-06-22 11:19:49,131 INFO ]: 0 DeclaredPredicates, 152 GetRequests, 67 SyntacticMatches, 29 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 823 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=206, Invalid=3100, Unknown=0, NotChecked=0, Total=3306 [2018-06-22 11:19:49,131 INFO ]: Start minimizeSevpa. Operand 80 states. [2018-06-22 11:19:49,133 INFO ]: Finished minimizeSevpa. Reduced states from 80 to 58. [2018-06-22 11:19:49,133 INFO ]: Start removeUnreachable. Operand 58 states. [2018-06-22 11:19:49,134 INFO ]: Finished removeUnreachable. Reduced from 58 states to 58 states and 63 transitions. [2018-06-22 11:19:49,134 INFO ]: Start accepts. Automaton has 58 states and 63 transitions. Word has length 89 [2018-06-22 11:19:49,134 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:49,134 INFO ]: Abstraction has 58 states and 63 transitions. [2018-06-22 11:19:49,134 INFO ]: Interpolant automaton has 38 states. [2018-06-22 11:19:49,134 INFO ]: Start isEmpty. Operand 58 states and 63 transitions. [2018-06-22 11:19:49,137 INFO ]: Finished isEmpty. Found accepting run of length 94 [2018-06-22 11:19:49,137 INFO ]: Found error trace [2018-06-22 11:19:49,137 INFO ]: trace histogram [22, 11, 11, 11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:49,138 INFO ]: === Iteration 37 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:49,138 INFO ]: Analyzing trace with hash -598601348, now seen corresponding path program 30 times [2018-06-22 11:19:49,138 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:49,138 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:49,138 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:49,138 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:49,138 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:49,154 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:49,553 INFO ]: Checked inductivity of 793 backedges. 90 proven. 382 refuted. 0 times theorem prover too weak. 321 trivial. 0 not checked. [2018-06-22 11:19:49,553 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:49,573 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 35 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 35 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:49,579 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 11:19:49,651 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 22 check-sat command(s) [2018-06-22 11:19:49,651 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:49,656 INFO ]: Computing forward predicates... [2018-06-22 11:19:50,284 INFO ]: Checked inductivity of 793 backedges. 0 proven. 472 refuted. 0 times theorem prover too weak. 321 trivial. 0 not checked. [2018-06-22 11:19:50,303 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:50,303 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28] total 52 [2018-06-22 11:19:50,303 INFO ]: Interpolant automaton has 52 states [2018-06-22 11:19:50,304 INFO ]: Constructing interpolant automaton starting with 52 interpolants. [2018-06-22 11:19:50,304 INFO ]: CoverageRelationStatistics Valid=382, Invalid=2270, Unknown=0, NotChecked=0, Total=2652 [2018-06-22 11:19:50,304 INFO ]: Start difference. First operand 58 states and 63 transitions. Second operand 52 states. [2018-06-22 11:19:52,753 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:52,753 INFO ]: Finished difference Result 236 states and 253 transitions. [2018-06-22 11:19:52,753 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 102 states. [2018-06-22 11:19:52,753 INFO ]: Start accepts. Automaton has 52 states. Word has length 93 [2018-06-22 11:19:52,753 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:52,754 INFO ]: With dead ends: 236 [2018-06-22 11:19:52,754 INFO ]: Without dead ends: 236 [2018-06-22 11:19:52,755 INFO ]: 0 DeclaredPredicates, 235 GetRequests, 87 SyntacticMatches, 1 SemanticMatches, 147 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7883 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=5234, Invalid=16818, Unknown=0, NotChecked=0, Total=22052 [2018-06-22 11:19:52,755 INFO ]: Start minimizeSevpa. Operand 236 states. [2018-06-22 11:19:52,761 INFO ]: Finished minimizeSevpa. Reduced states from 236 to 56. [2018-06-22 11:19:52,761 INFO ]: Start removeUnreachable. Operand 56 states. [2018-06-22 11:19:52,761 INFO ]: Finished removeUnreachable. Reduced from 56 states to 56 states and 60 transitions. [2018-06-22 11:19:52,761 INFO ]: Start accepts. Automaton has 56 states and 60 transitions. Word has length 93 [2018-06-22 11:19:52,762 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:52,762 INFO ]: Abstraction has 56 states and 60 transitions. [2018-06-22 11:19:52,762 INFO ]: Interpolant automaton has 52 states. [2018-06-22 11:19:52,762 INFO ]: Start isEmpty. Operand 56 states and 60 transitions. [2018-06-22 11:19:52,762 INFO ]: Finished isEmpty. Found accepting run of length 94 [2018-06-22 11:19:52,762 INFO ]: Found error trace [2018-06-22 11:19:52,762 INFO ]: trace histogram [22, 11, 11, 11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:52,762 INFO ]: === Iteration 38 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:52,762 INFO ]: Analyzing trace with hash -644191967, now seen corresponding path program 31 times [2018-06-22 11:19:52,762 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:52,763 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:52,763 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:52,763 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:52,763 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:52,777 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:53,131 INFO ]: Checked inductivity of 793 backedges. 132 proven. 349 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2018-06-22 11:19:53,131 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:53,131 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 36 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 36 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:53,137 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:53,192 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:53,198 INFO ]: Computing forward predicates... [2018-06-22 11:19:53,836 INFO ]: Checked inductivity of 793 backedges. 141 proven. 340 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2018-06-22 11:19:53,858 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:53,858 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 27] total 50 [2018-06-22 11:19:53,858 INFO ]: Interpolant automaton has 50 states [2018-06-22 11:19:53,858 INFO ]: Constructing interpolant automaton starting with 50 interpolants. [2018-06-22 11:19:53,859 INFO ]: CoverageRelationStatistics Valid=367, Invalid=2083, Unknown=0, NotChecked=0, Total=2450 [2018-06-22 11:19:53,859 INFO ]: Start difference. First operand 56 states and 60 transitions. Second operand 50 states. [2018-06-22 11:19:54,500 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:54,500 INFO ]: Finished difference Result 82 states and 87 transitions. [2018-06-22 11:19:54,500 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-06-22 11:19:54,500 INFO ]: Start accepts. Automaton has 50 states. Word has length 93 [2018-06-22 11:19:54,500 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:54,500 INFO ]: With dead ends: 82 [2018-06-22 11:19:54,500 INFO ]: Without dead ends: 60 [2018-06-22 11:19:54,501 INFO ]: 0 DeclaredPredicates, 158 GetRequests, 88 SyntacticMatches, 0 SemanticMatches, 70 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1380 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=813, Invalid=4299, Unknown=0, NotChecked=0, Total=5112 [2018-06-22 11:19:54,501 INFO ]: Start minimizeSevpa. Operand 60 states. [2018-06-22 11:19:54,503 INFO ]: Finished minimizeSevpa. Reduced states from 60 to 58. [2018-06-22 11:19:54,503 INFO ]: Start removeUnreachable. Operand 58 states. [2018-06-22 11:19:54,504 INFO ]: Finished removeUnreachable. Reduced from 58 states to 58 states and 62 transitions. [2018-06-22 11:19:54,504 INFO ]: Start accepts. Automaton has 58 states and 62 transitions. Word has length 93 [2018-06-22 11:19:54,504 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:54,504 INFO ]: Abstraction has 58 states and 62 transitions. [2018-06-22 11:19:54,504 INFO ]: Interpolant automaton has 50 states. [2018-06-22 11:19:54,504 INFO ]: Start isEmpty. Operand 58 states and 62 transitions. [2018-06-22 11:19:54,504 INFO ]: Finished isEmpty. Found accepting run of length 98 [2018-06-22 11:19:54,504 INFO ]: Found error trace [2018-06-22 11:19:54,505 INFO ]: trace histogram [23, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:54,505 INFO ]: === Iteration 39 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:54,505 INFO ]: Analyzing trace with hash 574462086, now seen corresponding path program 32 times [2018-06-22 11:19:54,505 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:54,505 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:54,505 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:54,505 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 11:19:54,505 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:54,521 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:54,862 INFO ]: Checked inductivity of 869 backedges. 0 proven. 494 refuted. 0 times theorem prover too weak. 375 trivial. 0 not checked. [2018-06-22 11:19:54,862 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:54,862 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 37 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 37 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:54,867 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 11:19:54,922 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 11:19:54,922 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:54,927 INFO ]: Computing forward predicates... [2018-06-22 11:19:55,586 INFO ]: Checked inductivity of 869 backedges. 0 proven. 506 refuted. 0 times theorem prover too weak. 363 trivial. 0 not checked. [2018-06-22 11:19:55,605 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:55,605 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 28] total 41 [2018-06-22 11:19:55,605 INFO ]: Interpolant automaton has 41 states [2018-06-22 11:19:55,605 INFO ]: Constructing interpolant automaton starting with 41 interpolants. [2018-06-22 11:19:55,605 INFO ]: CoverageRelationStatistics Valid=103, Invalid=1537, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 11:19:55,605 INFO ]: Start difference. First operand 58 states and 62 transitions. Second operand 41 states. [2018-06-22 11:19:56,123 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:19:56,123 INFO ]: Finished difference Result 86 states and 92 transitions. [2018-06-22 11:19:56,123 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-06-22 11:19:56,123 INFO ]: Start accepts. Automaton has 41 states. Word has length 97 [2018-06-22 11:19:56,124 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:19:56,124 INFO ]: With dead ends: 86 [2018-06-22 11:19:56,124 INFO ]: Without dead ends: 86 [2018-06-22 11:19:56,125 INFO ]: 0 DeclaredPredicates, 166 GetRequests, 73 SyntacticMatches, 32 SemanticMatches, 61 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 993 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=225, Invalid=3681, Unknown=0, NotChecked=0, Total=3906 [2018-06-22 11:19:56,125 INFO ]: Start minimizeSevpa. Operand 86 states. [2018-06-22 11:19:56,128 INFO ]: Finished minimizeSevpa. Reduced states from 86 to 62. [2018-06-22 11:19:56,128 INFO ]: Start removeUnreachable. Operand 62 states. [2018-06-22 11:19:56,129 INFO ]: Finished removeUnreachable. Reduced from 62 states to 62 states and 67 transitions. [2018-06-22 11:19:56,129 INFO ]: Start accepts. Automaton has 62 states and 67 transitions. Word has length 97 [2018-06-22 11:19:56,129 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:19:56,129 INFO ]: Abstraction has 62 states and 67 transitions. [2018-06-22 11:19:56,129 INFO ]: Interpolant automaton has 41 states. [2018-06-22 11:19:56,129 INFO ]: Start isEmpty. Operand 62 states and 67 transitions. [2018-06-22 11:19:56,130 INFO ]: Finished isEmpty. Found accepting run of length 102 [2018-06-22 11:19:56,130 INFO ]: Found error trace [2018-06-22 11:19:56,130 INFO ]: trace histogram [24, 12, 12, 12, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:19:56,130 INFO ]: === Iteration 40 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:19:56,130 INFO ]: Analyzing trace with hash 263293611, now seen corresponding path program 33 times [2018-06-22 11:19:56,130 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:19:56,130 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:19:56,130 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:56,130 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:19:56,130 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:19:56,148 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:56,756 INFO ]: Checked inductivity of 949 backedges. 110 proven. 453 refuted. 0 times theorem prover too weak. 386 trivial. 0 not checked. [2018-06-22 11:19:56,757 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:19:56,757 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 38 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 38 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:19:56,762 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 11:19:56,834 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 13 check-sat command(s) [2018-06-22 11:19:56,834 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:19:56,839 INFO ]: Computing forward predicates... [2018-06-22 11:19:57,487 INFO ]: Checked inductivity of 949 backedges. 0 proven. 563 refuted. 0 times theorem prover too weak. 386 trivial. 0 not checked. [2018-06-22 11:19:57,509 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:19:57,509 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 30] total 56 [2018-06-22 11:19:57,510 INFO ]: Interpolant automaton has 56 states [2018-06-22 11:19:57,510 INFO ]: Constructing interpolant automaton starting with 56 interpolants. [2018-06-22 11:19:57,510 INFO ]: CoverageRelationStatistics Valid=445, Invalid=2635, Unknown=0, NotChecked=0, Total=3080 [2018-06-22 11:19:57,510 INFO ]: Start difference. First operand 62 states and 67 transitions. Second operand 56 states. [2018-06-22 11:20:00,494 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:20:00,494 INFO ]: Finished difference Result 268 states and 286 transitions. [2018-06-22 11:20:00,495 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-06-22 11:20:00,495 INFO ]: Start accepts. Automaton has 56 states. Word has length 101 [2018-06-22 11:20:00,495 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:20:00,496 INFO ]: With dead ends: 268 [2018-06-22 11:20:00,496 INFO ]: Without dead ends: 268 [2018-06-22 11:20:00,498 INFO ]: 0 DeclaredPredicates, 262 GetRequests, 95 SyntacticMatches, 1 SemanticMatches, 166 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10437 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=6748, Invalid=21308, Unknown=0, NotChecked=0, Total=28056 [2018-06-22 11:20:00,498 INFO ]: Start minimizeSevpa. Operand 268 states. [2018-06-22 11:20:00,506 INFO ]: Finished minimizeSevpa. Reduced states from 268 to 60. [2018-06-22 11:20:00,506 INFO ]: Start removeUnreachable. Operand 60 states. [2018-06-22 11:20:00,506 INFO ]: Finished removeUnreachable. Reduced from 60 states to 60 states and 64 transitions. [2018-06-22 11:20:00,506 INFO ]: Start accepts. Automaton has 60 states and 64 transitions. Word has length 101 [2018-06-22 11:20:00,506 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:20:00,506 INFO ]: Abstraction has 60 states and 64 transitions. [2018-06-22 11:20:00,506 INFO ]: Interpolant automaton has 56 states. [2018-06-22 11:20:00,507 INFO ]: Start isEmpty. Operand 60 states and 64 transitions. [2018-06-22 11:20:00,507 INFO ]: Finished isEmpty. Found accepting run of length 102 [2018-06-22 11:20:00,507 INFO ]: Found error trace [2018-06-22 11:20:00,507 INFO ]: trace histogram [24, 12, 12, 12, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:20:00,507 INFO ]: === Iteration 41 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:20:00,507 INFO ]: Analyzing trace with hash 2084520848, now seen corresponding path program 34 times [2018-06-22 11:20:00,507 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:20:00,507 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:20:00,508 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:20:00,508 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:20:00,508 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:20:00,523 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:20:00,925 INFO ]: Checked inductivity of 949 backedges. 156 proven. 417 refuted. 0 times theorem prover too weak. 376 trivial. 0 not checked. [2018-06-22 11:20:00,925 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 11:20:00,925 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 39 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 39 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 11:20:00,931 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 11:20:00,988 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 11:20:00,988 INFO ]: Conjunction of SSA is unsat [2018-06-22 11:20:00,994 INFO ]: Computing forward predicates... [2018-06-22 11:20:01,582 INFO ]: Checked inductivity of 949 backedges. 166 proven. 407 refuted. 0 times theorem prover too weak. 376 trivial. 0 not checked. [2018-06-22 11:20:01,601 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 11:20:01,602 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 29] total 54 [2018-06-22 11:20:01,602 INFO ]: Interpolant automaton has 54 states [2018-06-22 11:20:01,602 INFO ]: Constructing interpolant automaton starting with 54 interpolants. [2018-06-22 11:20:01,602 INFO ]: CoverageRelationStatistics Valid=429, Invalid=2433, Unknown=0, NotChecked=0, Total=2862 [2018-06-22 11:20:01,602 INFO ]: Start difference. First operand 60 states and 64 transitions. Second operand 54 states. [2018-06-22 11:20:02,632 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 11:20:02,632 INFO ]: Finished difference Result 88 states and 93 transitions. [2018-06-22 11:20:02,632 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-06-22 11:20:02,632 INFO ]: Start accepts. Automaton has 54 states. Word has length 101 [2018-06-22 11:20:02,633 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 11:20:02,633 INFO ]: With dead ends: 88 [2018-06-22 11:20:02,633 INFO ]: Without dead ends: 64 [2018-06-22 11:20:02,633 INFO ]: 0 DeclaredPredicates, 172 GetRequests, 96 SyntacticMatches, 0 SemanticMatches, 76 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1650 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=946, Invalid=5060, Unknown=0, NotChecked=0, Total=6006 [2018-06-22 11:20:02,633 INFO ]: Start minimizeSevpa. Operand 64 states. [2018-06-22 11:20:02,635 INFO ]: Finished minimizeSevpa. Reduced states from 64 to 62. [2018-06-22 11:20:02,635 INFO ]: Start removeUnreachable. Operand 62 states. [2018-06-22 11:20:02,635 INFO ]: Finished removeUnreachable. Reduced from 62 states to 62 states and 66 transitions. [2018-06-22 11:20:02,635 INFO ]: Start accepts. Automaton has 62 states and 66 transitions. Word has length 101 [2018-06-22 11:20:02,635 INFO ]: Finished accepts. word is rejected. [2018-06-22 11:20:02,635 INFO ]: Abstraction has 62 states and 66 transitions. [2018-06-22 11:20:02,635 INFO ]: Interpolant automaton has 54 states. [2018-06-22 11:20:02,635 INFO ]: Start isEmpty. Operand 62 states and 66 transitions. [2018-06-22 11:20:02,636 INFO ]: Finished isEmpty. Found accepting run of length 106 [2018-06-22 11:20:02,636 INFO ]: Found error trace [2018-06-22 11:20:02,636 INFO ]: trace histogram [25, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 11:20:02,636 INFO ]: === Iteration 42 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 11:20:02,636 INFO ]: Analyzing trace with hash 1415036661, now seen corresponding path program 35 times [2018-06-22 11:20:02,636 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 11:20:02,636 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 11:20:02,636 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:20:02,636 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 11:20:02,636 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 11:20:02,650 INFO ]: Conjunction of SSA is unsat Received shutdown request... [2018-06-22 11:20:02,977 WARN ]: Verification canceled [2018-06-22 11:20:03,162 WARN ]: Timeout [2018-06-22 11:20:03,162 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 11:20:03 BoogieIcfgContainer [2018-06-22 11:20:03,162 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 11:20:03,166 INFO ]: Toolchain (without parser) took 59773.34 ms. Allocated memory was 308.8 MB in the beginning and 836.2 MB in the end (delta: 527.4 MB). Free memory was 265.2 MB in the beginning and 806.6 MB in the end (delta: -541.4 MB). Peak memory consumption was 275.7 MB. Max. memory is 3.6 GB. [2018-06-22 11:20:03,167 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 11:20:03,167 INFO ]: ChcToBoogie took 46.17 ms. Allocated memory is still 308.8 MB. Free memory was 265.2 MB in the beginning and 263.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 11:20:03,167 INFO ]: Boogie Preprocessor took 40.61 ms. Allocated memory is still 308.8 MB. Free memory was 263.2 MB in the beginning and 261.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 11:20:03,168 INFO ]: RCFGBuilder took 328.16 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 253.2 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-22 11:20:03,168 INFO ]: TraceAbstraction took 59345.86 ms. Allocated memory was 308.8 MB in the beginning and 836.2 MB in the end (delta: 527.4 MB). Free memory was 253.2 MB in the beginning and 809.9 MB in the end (delta: -556.7 MB). Peak memory consumption was 263.8 MB. Max. memory is 3.6 GB. [2018-06-22 11:20:03,173 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 46.17 ms. Allocated memory is still 308.8 MB. Free memory was 265.2 MB in the beginning and 263.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 40.61 ms. Allocated memory is still 308.8 MB. Free memory was 263.2 MB in the beginning and 261.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 328.16 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 253.2 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 59345.86 ms. Allocated memory was 308.8 MB in the beginning and 836.2 MB in the end (delta: 527.4 MB). Free memory was 253.2 MB in the beginning and 809.9 MB in the end (delta: -556.7 MB). Peak memory consumption was 263.8 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 analyzing trace of length 106 with TraceHistMax 25, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateComparison was comparing new predicate (quantifier-free) to 4 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 15 locations, 1 error locations. TIMEOUT Result, 59.2s OverallTime, 42 OverallIterations, 25 TraceHistogramMax, 27.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 898 SDtfs, 1084 SDslu, 9272 SDs, 0 SdLazy, 11410 SolverSat, 2015 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 8.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 3867 GetRequests, 1774 SyntacticMatches, 202 SemanticMatches, 1891 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46472 ImplicationChecksByTransitivity, 42.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=62occurred in iteration=39, 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.2s AutomataMinimizationTime, 41 MinimizatonAttempts, 1270 StatesRemovedByMinimization, 40 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 1.8s SatisfiabilityAnalysisTime, 27.2s InterpolantComputationTime, 4146 NumberOfCodeBlocks, 4065 NumberOfCodeBlocksAsserted, 251 NumberOfCheckSat, 4068 ConstructedInterpolants, 0 QuantifiedInterpolants, 1725072 SizeOfPredicates, 730 NumberOfNonLiveVariables, 12474 ConjunctsInSsa, 2322 ConjunctsInUnsatCore, 78 InterpolantComputations, 4 PerfectInterpolantSequences, 11724/24178 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/020-horn.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_11-20-03-185.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/020-horn.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_11-20-03-185.csv Completed graceful shutdown