java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/hopv/lia/mochi/enc-rev_append.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 01:43:12,386 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 01:43:12,388 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 01:43:12,402 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 01:43:12,402 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 01:43:12,403 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 01:43:12,405 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 01:43:12,406 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 01:43:12,407 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 01:43:12,408 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 01:43:12,409 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 01:43:12,409 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 01:43:12,410 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 01:43:12,411 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 01:43:12,412 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 01:43:12,412 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 01:43:12,417 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 01:43:12,418 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 01:43:12,422 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 01:43:12,423 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 01:43:12,424 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 01:43:12,427 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 01:43:12,427 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 01:43:12,427 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 01:43:12,428 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 01:43:12,429 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 01:43:12,430 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 01:43:12,466 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 01:43:12,467 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 01:43:12,467 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 01:43:12,468 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 01:43:12,468 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 01:43:12,468 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 01:43:12,469 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 01:43:12,470 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 01:43:12,470 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 01:43:12,485 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 01:43:12,486 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 01:43:12,486 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 01:43:12,486 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 01:43:12,487 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 01:43:12,487 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 01:43:12,488 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 01:43:12,488 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 01:43:12,488 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 01:43:12,488 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 01:43:12,488 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 01:43:12,488 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 01:43:12,489 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 01:43:12,489 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 01:43:12,489 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 01:43:12,489 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 01:43:12,489 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 01:43:12,491 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 01:43:12,491 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 01:43:12,540 INFO ]: Repository-Root is: /tmp [2018-06-22 01:43:12,552 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 01:43:12,556 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 01:43:12,557 INFO ]: Initializing SmtParser... [2018-06-22 01:43:12,558 INFO ]: SmtParser initialized [2018-06-22 01:43:12,558 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/hopv/lia/mochi/enc-rev_append.smt2 [2018-06-22 01:43:12,559 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 01:43:12,650 INFO ]: Executing SMT file /storage/chc-comp/hopv/lia/mochi/enc-rev_append.smt2 unknown [2018-06-22 01:43:12,815 INFO ]: Succesfully executed SMT file /storage/chc-comp/hopv/lia/mochi/enc-rev_append.smt2 [2018-06-22 01:43:12,820 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 01:43:12,826 INFO ]: Walking toolchain with 4 elements. [2018-06-22 01:43:12,827 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 01:43:12,827 INFO ]: Initializing ChcToBoogie... [2018-06-22 01:43:12,827 INFO ]: ChcToBoogie initialized [2018-06-22 01:43:12,830 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:43:12" (1/1) ... [2018-06-22 01:43:12,919 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:43:12 Unit [2018-06-22 01:43:12,919 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 01:43:12,920 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 01:43:12,920 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 01:43:12,920 INFO ]: Boogie Preprocessor initialized [2018-06-22 01:43:12,941 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:43:12" (1/1) ... [2018-06-22 01:43:12,941 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:43:12" (1/1) ... [2018-06-22 01:43:12,947 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:43:12" (1/1) ... [2018-06-22 01:43:12,947 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:43:12" (1/1) ... [2018-06-22 01:43:12,950 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:43:12" (1/1) ... [2018-06-22 01:43:12,953 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:43:12" (1/1) ... [2018-06-22 01:43:12,954 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:43:12" (1/1) ... [2018-06-22 01:43:12,957 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 01:43:12,958 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 01:43:12,958 INFO ]: Initializing RCFGBuilder... [2018-06-22 01:43:12,958 INFO ]: RCFGBuilder initialized [2018-06-22 01:43:12,959 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:43:12" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 01:43:12,978 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 01:43:12,978 INFO ]: Found specification of procedure gotoProc [2018-06-22 01:43:12,978 INFO ]: Found implementation of procedure gotoProc [2018-06-22 01:43:12,978 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 01:43:12,978 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 01:43:12,978 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 01:43:13,385 INFO ]: Using library mode [2018-06-22 01:43:13,386 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:43:13 BoogieIcfgContainer [2018-06-22 01:43:13,386 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 01:43:13,390 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 01:43:13,390 INFO ]: Initializing TraceAbstraction... [2018-06-22 01:43:13,394 INFO ]: TraceAbstraction initialized [2018-06-22 01:43:13,394 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:43:12" (1/3) ... [2018-06-22 01:43:13,395 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c235c9d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 01:43:13, skipping insertion in model container [2018-06-22 01:43:13,395 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:43:12" (2/3) ... [2018-06-22 01:43:13,396 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c235c9d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 01:43:13, skipping insertion in model container [2018-06-22 01:43:13,396 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:43:13" (3/3) ... [2018-06-22 01:43:13,398 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 01:43:13,407 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 01:43:13,417 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 01:43:13,456 INFO ]: Using default assertion order modulation [2018-06-22 01:43:13,457 INFO ]: Interprodecural is true [2018-06-22 01:43:13,457 INFO ]: Hoare is false [2018-06-22 01:43:13,457 INFO ]: Compute interpolants for FPandBP [2018-06-22 01:43:13,457 INFO ]: Backedges is TWOTRACK [2018-06-22 01:43:13,457 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 01:43:13,457 INFO ]: Difference is false [2018-06-22 01:43:13,457 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 01:43:13,457 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 01:43:13,470 INFO ]: Start isEmpty. Operand 16 states. [2018-06-22 01:43:13,480 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 01:43:13,481 INFO ]: Found error trace [2018-06-22 01:43:13,483 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:13,483 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:13,488 INFO ]: Analyzing trace with hash -837351749, now seen corresponding path program 1 times [2018-06-22 01:43:13,490 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:13,490 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:13,523 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:13,523 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:13,523 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:13,556 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:13,632 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:43:13,635 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:43:13,635 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:43:13,636 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:43:13,647 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:43:13,647 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:43:13,649 INFO ]: Start difference. First operand 16 states. Second operand 4 states. [2018-06-22 01:43:13,810 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:13,810 INFO ]: Finished difference Result 25 states and 35 transitions. [2018-06-22 01:43:13,810 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:43:13,811 INFO ]: Start accepts. Automaton has 4 states. Word has length 7 [2018-06-22 01:43:13,811 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:13,821 INFO ]: With dead ends: 25 [2018-06-22 01:43:13,821 INFO ]: Without dead ends: 25 [2018-06-22 01:43:13,823 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:43:13,836 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 01:43:13,852 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 01:43:13,854 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 01:43:13,855 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 35 transitions. [2018-06-22 01:43:13,856 INFO ]: Start accepts. Automaton has 25 states and 35 transitions. Word has length 7 [2018-06-22 01:43:13,857 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:13,857 INFO ]: Abstraction has 25 states and 35 transitions. [2018-06-22 01:43:13,857 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:43:13,857 INFO ]: Start isEmpty. Operand 25 states and 35 transitions. [2018-06-22 01:43:13,859 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:43:13,859 INFO ]: Found error trace [2018-06-22 01:43:13,859 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:13,859 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:13,859 INFO ]: Analyzing trace with hash -159629556, now seen corresponding path program 1 times [2018-06-22 01:43:13,859 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:13,859 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:13,860 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:13,860 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:13,860 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:13,871 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:13,943 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:43:13,943 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:43:13,944 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:43:13,945 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:43:13,945 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:43:13,945 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:43:13,946 INFO ]: Start difference. First operand 25 states and 35 transitions. Second operand 3 states. [2018-06-22 01:43:14,014 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:14,014 INFO ]: Finished difference Result 34 states and 50 transitions. [2018-06-22 01:43:14,015 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:43:14,015 INFO ]: Start accepts. Automaton has 3 states. Word has length 8 [2018-06-22 01:43:14,015 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:14,018 INFO ]: With dead ends: 34 [2018-06-22 01:43:14,018 INFO ]: Without dead ends: 34 [2018-06-22 01:43:14,019 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:43:14,019 INFO ]: Start minimizeSevpa. Operand 34 states. [2018-06-22 01:43:14,028 INFO ]: Finished minimizeSevpa. Reduced states from 34 to 26. [2018-06-22 01:43:14,109 INFO ]: Start removeUnreachable. Operand 26 states. [2018-06-22 01:43:14,110 INFO ]: Finished removeUnreachable. Reduced from 26 states to 26 states and 35 transitions. [2018-06-22 01:43:14,111 INFO ]: Start accepts. Automaton has 26 states and 35 transitions. Word has length 8 [2018-06-22 01:43:14,111 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:14,111 INFO ]: Abstraction has 26 states and 35 transitions. [2018-06-22 01:43:14,111 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:43:14,111 INFO ]: Start isEmpty. Operand 26 states and 35 transitions. [2018-06-22 01:43:14,112 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-22 01:43:14,112 INFO ]: Found error trace [2018-06-22 01:43:14,112 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:14,112 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:14,112 INFO ]: Analyzing trace with hash 681851595, now seen corresponding path program 1 times [2018-06-22 01:43:14,112 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:14,112 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:14,115 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:14,115 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:14,115 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:14,141 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:14,486 WARN ]: Spent 297.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 14 [2018-06-22 01:43:14,583 INFO ]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:43:14,583 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:43:14,583 INFO ]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-06-22 01:43:14,584 INFO ]: Interpolant automaton has 7 states [2018-06-22 01:43:14,584 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 01:43:14,584 INFO ]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:43:14,584 INFO ]: Start difference. First operand 26 states and 35 transitions. Second operand 7 states. [2018-06-22 01:43:14,904 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:14,904 INFO ]: Finished difference Result 41 states and 65 transitions. [2018-06-22 01:43:14,904 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 01:43:14,904 INFO ]: Start accepts. Automaton has 7 states. Word has length 15 [2018-06-22 01:43:14,905 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:14,907 INFO ]: With dead ends: 41 [2018-06-22 01:43:14,907 INFO ]: Without dead ends: 37 [2018-06-22 01:43:14,907 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:43:14,907 INFO ]: Start minimizeSevpa. Operand 37 states. [2018-06-22 01:43:14,914 INFO ]: Finished minimizeSevpa. Reduced states from 37 to 32. [2018-06-22 01:43:14,914 INFO ]: Start removeUnreachable. Operand 32 states. [2018-06-22 01:43:14,916 INFO ]: Finished removeUnreachable. Reduced from 32 states to 32 states and 43 transitions. [2018-06-22 01:43:14,916 INFO ]: Start accepts. Automaton has 32 states and 43 transitions. Word has length 15 [2018-06-22 01:43:14,916 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:14,916 INFO ]: Abstraction has 32 states and 43 transitions. [2018-06-22 01:43:14,916 INFO ]: Interpolant automaton has 7 states. [2018-06-22 01:43:14,916 INFO ]: Start isEmpty. Operand 32 states and 43 transitions. [2018-06-22 01:43:14,917 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-22 01:43:14,917 INFO ]: Found error trace [2018-06-22 01:43:14,917 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:14,917 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:14,917 INFO ]: Analyzing trace with hash -336820733, now seen corresponding path program 1 times [2018-06-22 01:43:14,918 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:14,918 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:14,919 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:14,919 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:14,919 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:14,931 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:14,996 INFO ]: Checked inductivity of 5 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:43:14,996 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:43:14,996 INFO ]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-06-22 01:43:14,996 INFO ]: Interpolant automaton has 7 states [2018-06-22 01:43:14,996 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 01:43:14,996 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:43:14,997 INFO ]: Start difference. First operand 32 states and 43 transitions. Second operand 7 states. [2018-06-22 01:43:15,689 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:15,689 INFO ]: Finished difference Result 37 states and 53 transitions. [2018-06-22 01:43:15,690 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 01:43:15,690 INFO ]: Start accepts. Automaton has 7 states. Word has length 16 [2018-06-22 01:43:15,690 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:15,691 INFO ]: With dead ends: 37 [2018-06-22 01:43:15,691 INFO ]: Without dead ends: 33 [2018-06-22 01:43:15,691 INFO ]: 0 DeclaredPredicates, 13 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2018-06-22 01:43:15,691 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-22 01:43:15,696 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 28. [2018-06-22 01:43:15,696 INFO ]: Start removeUnreachable. Operand 28 states. [2018-06-22 01:43:15,696 INFO ]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2018-06-22 01:43:15,697 INFO ]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 16 [2018-06-22 01:43:15,697 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:15,697 INFO ]: Abstraction has 28 states and 37 transitions. [2018-06-22 01:43:15,697 INFO ]: Interpolant automaton has 7 states. [2018-06-22 01:43:15,697 INFO ]: Start isEmpty. Operand 28 states and 37 transitions. [2018-06-22 01:43:15,698 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-22 01:43:15,698 INFO ]: Found error trace [2018-06-22 01:43:15,698 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:15,698 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:15,698 INFO ]: Analyzing trace with hash 266276282, now seen corresponding path program 1 times [2018-06-22 01:43:15,698 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:15,698 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:15,699 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:15,699 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:15,699 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:15,710 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:15,870 INFO ]: Checked inductivity of 5 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:43:15,871 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:15,871 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:15,879 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:15,899 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:15,906 INFO ]: Computing forward predicates... [2018-06-22 01:43:16,062 INFO ]: Checked inductivity of 5 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:43:16,082 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:16,082 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 01:43:16,082 INFO ]: Interpolant automaton has 11 states [2018-06-22 01:43:16,082 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 01:43:16,082 INFO ]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:43:16,082 INFO ]: Start difference. First operand 28 states and 37 transitions. Second operand 11 states. [2018-06-22 01:43:16,270 WARN ]: Spent 152.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-22 01:43:16,709 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:16,709 INFO ]: Finished difference Result 43 states and 65 transitions. [2018-06-22 01:43:16,710 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 01:43:16,710 INFO ]: Start accepts. Automaton has 11 states. Word has length 16 [2018-06-22 01:43:16,710 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:16,711 INFO ]: With dead ends: 43 [2018-06-22 01:43:16,711 INFO ]: Without dead ends: 43 [2018-06-22 01:43:16,712 INFO ]: 0 DeclaredPredicates, 31 GetRequests, 13 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=76, Invalid=266, Unknown=0, NotChecked=0, Total=342 [2018-06-22 01:43:16,712 INFO ]: Start minimizeSevpa. Operand 43 states. [2018-06-22 01:43:16,718 INFO ]: Finished minimizeSevpa. Reduced states from 43 to 33. [2018-06-22 01:43:16,718 INFO ]: Start removeUnreachable. Operand 33 states. [2018-06-22 01:43:16,719 INFO ]: Finished removeUnreachable. Reduced from 33 states to 33 states and 44 transitions. [2018-06-22 01:43:16,719 INFO ]: Start accepts. Automaton has 33 states and 44 transitions. Word has length 16 [2018-06-22 01:43:16,719 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:16,719 INFO ]: Abstraction has 33 states and 44 transitions. [2018-06-22 01:43:16,719 INFO ]: Interpolant automaton has 11 states. [2018-06-22 01:43:16,719 INFO ]: Start isEmpty. Operand 33 states and 44 transitions. [2018-06-22 01:43:16,720 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 01:43:16,720 INFO ]: Found error trace [2018-06-22 01:43:16,721 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:16,721 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:16,721 INFO ]: Analyzing trace with hash -334753548, now seen corresponding path program 1 times [2018-06-22 01:43:16,721 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:16,721 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:16,722 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:16,725 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:16,725 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:16,736 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:16,804 INFO ]: Checked inductivity of 6 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:43:16,804 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:43:16,804 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-06-22 01:43:16,804 INFO ]: Interpolant automaton has 6 states [2018-06-22 01:43:16,805 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 01:43:16,805 INFO ]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-06-22 01:43:16,805 INFO ]: Start difference. First operand 33 states and 44 transitions. Second operand 6 states. [2018-06-22 01:43:16,927 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:16,928 INFO ]: Finished difference Result 39 states and 53 transitions. [2018-06-22 01:43:16,928 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 01:43:16,928 INFO ]: Start accepts. Automaton has 6 states. Word has length 17 [2018-06-22 01:43:16,928 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:16,929 INFO ]: With dead ends: 39 [2018-06-22 01:43:16,929 INFO ]: Without dead ends: 35 [2018-06-22 01:43:16,929 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:43:16,929 INFO ]: Start minimizeSevpa. Operand 35 states. [2018-06-22 01:43:16,933 INFO ]: Finished minimizeSevpa. Reduced states from 35 to 31. [2018-06-22 01:43:16,933 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 01:43:16,934 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 40 transitions. [2018-06-22 01:43:16,934 INFO ]: Start accepts. Automaton has 31 states and 40 transitions. Word has length 17 [2018-06-22 01:43:16,934 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:16,934 INFO ]: Abstraction has 31 states and 40 transitions. [2018-06-22 01:43:16,934 INFO ]: Interpolant automaton has 6 states. [2018-06-22 01:43:16,934 INFO ]: Start isEmpty. Operand 31 states and 40 transitions. [2018-06-22 01:43:16,937 INFO ]: Finished isEmpty. Found accepting run of length 24 [2018-06-22 01:43:16,937 INFO ]: Found error trace [2018-06-22 01:43:16,937 INFO ]: trace histogram [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:16,937 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:16,938 INFO ]: Analyzing trace with hash 1340738681, now seen corresponding path program 1 times [2018-06-22 01:43:16,938 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:16,938 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:16,938 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:16,938 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:16,938 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:16,950 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:16,990 INFO ]: Checked inductivity of 14 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 01:43:16,990 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:16,990 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:16,997 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:17,013 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:17,015 INFO ]: Computing forward predicates... [2018-06-22 01:43:17,205 INFO ]: Checked inductivity of 14 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:43:17,227 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:17,227 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 8] total 12 [2018-06-22 01:43:17,227 INFO ]: Interpolant automaton has 12 states [2018-06-22 01:43:17,227 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 01:43:17,227 INFO ]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2018-06-22 01:43:17,227 INFO ]: Start difference. First operand 31 states and 40 transitions. Second operand 12 states. [2018-06-22 01:43:17,605 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:17,605 INFO ]: Finished difference Result 47 states and 66 transitions. [2018-06-22 01:43:17,605 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-06-22 01:43:17,605 INFO ]: Start accepts. Automaton has 12 states. Word has length 23 [2018-06-22 01:43:17,605 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:17,606 INFO ]: With dead ends: 47 [2018-06-22 01:43:17,606 INFO ]: Without dead ends: 47 [2018-06-22 01:43:17,606 INFO ]: 0 DeclaredPredicates, 39 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=84, Invalid=336, Unknown=0, NotChecked=0, Total=420 [2018-06-22 01:43:17,607 INFO ]: Start minimizeSevpa. Operand 47 states. [2018-06-22 01:43:17,613 INFO ]: Finished minimizeSevpa. Reduced states from 47 to 39. [2018-06-22 01:43:17,613 INFO ]: Start removeUnreachable. Operand 39 states. [2018-06-22 01:43:17,614 INFO ]: Finished removeUnreachable. Reduced from 39 states to 39 states and 53 transitions. [2018-06-22 01:43:17,614 INFO ]: Start accepts. Automaton has 39 states and 53 transitions. Word has length 23 [2018-06-22 01:43:17,614 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:17,614 INFO ]: Abstraction has 39 states and 53 transitions. [2018-06-22 01:43:17,614 INFO ]: Interpolant automaton has 12 states. [2018-06-22 01:43:17,614 INFO ]: Start isEmpty. Operand 39 states and 53 transitions. [2018-06-22 01:43:17,615 INFO ]: Finished isEmpty. Found accepting run of length 25 [2018-06-22 01:43:17,615 INFO ]: Found error trace [2018-06-22 01:43:17,616 INFO ]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:17,616 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:17,616 INFO ]: Analyzing trace with hash -497465496, now seen corresponding path program 2 times [2018-06-22 01:43:17,616 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:17,616 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:17,617 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:17,617 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:17,617 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:17,627 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:17,727 INFO ]: Checked inductivity of 18 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:43:17,727 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:17,727 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:17,742 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:43:17,766 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:43:17,766 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:17,768 INFO ]: Computing forward predicates... [2018-06-22 01:43:18,037 INFO ]: Checked inductivity of 18 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:43:18,059 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:18,059 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2018-06-22 01:43:18,059 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:43:18,060 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:43:18,060 INFO ]: CoverageRelationStatistics Valid=30, Invalid=152, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:43:18,060 INFO ]: Start difference. First operand 39 states and 53 transitions. Second operand 14 states. [2018-06-22 01:43:18,258 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:18,273 INFO ]: Finished difference Result 48 states and 67 transitions. [2018-06-22 01:43:18,274 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 01:43:18,274 INFO ]: Start accepts. Automaton has 14 states. Word has length 24 [2018-06-22 01:43:18,274 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:18,275 INFO ]: With dead ends: 48 [2018-06-22 01:43:18,275 INFO ]: Without dead ends: 48 [2018-06-22 01:43:18,275 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=86, Invalid=334, Unknown=0, NotChecked=0, Total=420 [2018-06-22 01:43:18,275 INFO ]: Start minimizeSevpa. Operand 48 states. [2018-06-22 01:43:18,282 INFO ]: Finished minimizeSevpa. Reduced states from 48 to 43. [2018-06-22 01:43:18,282 INFO ]: Start removeUnreachable. Operand 43 states. [2018-06-22 01:43:18,283 INFO ]: Finished removeUnreachable. Reduced from 43 states to 43 states and 57 transitions. [2018-06-22 01:43:18,283 INFO ]: Start accepts. Automaton has 43 states and 57 transitions. Word has length 24 [2018-06-22 01:43:18,283 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:18,283 INFO ]: Abstraction has 43 states and 57 transitions. [2018-06-22 01:43:18,283 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:43:18,283 INFO ]: Start isEmpty. Operand 43 states and 57 transitions. [2018-06-22 01:43:18,285 INFO ]: Finished isEmpty. Found accepting run of length 25 [2018-06-22 01:43:18,285 INFO ]: Found error trace [2018-06-22 01:43:18,285 INFO ]: trace histogram [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:18,286 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:18,286 INFO ]: Analyzing trace with hash -1386157547, now seen corresponding path program 1 times [2018-06-22 01:43:18,286 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:18,286 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:18,287 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:18,287 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:18,287 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:18,309 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:18,375 INFO ]: Checked inductivity of 16 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-06-22 01:43:18,375 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:18,375 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:18,382 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:18,398 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:18,400 INFO ]: Computing forward predicates... [2018-06-22 01:43:18,572 INFO ]: Checked inductivity of 16 backedges. 4 proven. 5 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:43:18,592 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:18,593 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 10] total 12 [2018-06-22 01:43:18,593 INFO ]: Interpolant automaton has 12 states [2018-06-22 01:43:18,593 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 01:43:18,593 INFO ]: CoverageRelationStatistics Valid=23, Invalid=109, Unknown=0, NotChecked=0, Total=132 [2018-06-22 01:43:18,593 INFO ]: Start difference. First operand 43 states and 57 transitions. Second operand 12 states. [2018-06-22 01:43:19,058 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:19,058 INFO ]: Finished difference Result 57 states and 75 transitions. [2018-06-22 01:43:19,058 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-06-22 01:43:19,058 INFO ]: Start accepts. Automaton has 12 states. Word has length 24 [2018-06-22 01:43:19,058 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:19,059 INFO ]: With dead ends: 57 [2018-06-22 01:43:19,059 INFO ]: Without dead ends: 57 [2018-06-22 01:43:19,060 INFO ]: 0 DeclaredPredicates, 44 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 135 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=113, Invalid=643, Unknown=0, NotChecked=0, Total=756 [2018-06-22 01:43:19,060 INFO ]: Start minimizeSevpa. Operand 57 states. [2018-06-22 01:43:19,065 INFO ]: Finished minimizeSevpa. Reduced states from 57 to 43. [2018-06-22 01:43:19,065 INFO ]: Start removeUnreachable. Operand 43 states. [2018-06-22 01:43:19,065 INFO ]: Finished removeUnreachable. Reduced from 43 states to 43 states and 57 transitions. [2018-06-22 01:43:19,065 INFO ]: Start accepts. Automaton has 43 states and 57 transitions. Word has length 24 [2018-06-22 01:43:19,066 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:19,066 INFO ]: Abstraction has 43 states and 57 transitions. [2018-06-22 01:43:19,066 INFO ]: Interpolant automaton has 12 states. [2018-06-22 01:43:19,066 INFO ]: Start isEmpty. Operand 43 states and 57 transitions. [2018-06-22 01:43:19,067 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 01:43:19,067 INFO ]: Found error trace [2018-06-22 01:43:19,067 INFO ]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:19,067 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:19,067 INFO ]: Analyzing trace with hash 1759055110, now seen corresponding path program 2 times [2018-06-22 01:43:19,067 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:19,067 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:19,068 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:19,068 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:19,068 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:19,080 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:19,301 INFO ]: Checked inductivity of 20 backedges. 4 proven. 9 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:43:19,301 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:19,301 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:19,307 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:43:19,337 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:43:19,337 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:19,340 INFO ]: Computing forward predicates... [2018-06-22 01:43:19,430 INFO ]: Checked inductivity of 20 backedges. 4 proven. 9 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:43:19,449 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:19,449 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 15 [2018-06-22 01:43:19,449 INFO ]: Interpolant automaton has 15 states [2018-06-22 01:43:19,450 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 01:43:19,450 INFO ]: CoverageRelationStatistics Valid=31, Invalid=179, Unknown=0, NotChecked=0, Total=210 [2018-06-22 01:43:19,450 INFO ]: Start difference. First operand 43 states and 57 transitions. Second operand 15 states. [2018-06-22 01:43:19,954 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:19,955 INFO ]: Finished difference Result 59 states and 83 transitions. [2018-06-22 01:43:19,955 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-06-22 01:43:19,955 INFO ]: Start accepts. Automaton has 15 states. Word has length 25 [2018-06-22 01:43:19,955 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:19,956 INFO ]: With dead ends: 59 [2018-06-22 01:43:19,956 INFO ]: Without dead ends: 59 [2018-06-22 01:43:19,957 INFO ]: 0 DeclaredPredicates, 54 GetRequests, 21 SyntacticMatches, 2 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=144, Invalid=912, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 01:43:19,957 INFO ]: Start minimizeSevpa. Operand 59 states. [2018-06-22 01:43:19,963 INFO ]: Finished minimizeSevpa. Reduced states from 59 to 47. [2018-06-22 01:43:19,963 INFO ]: Start removeUnreachable. Operand 47 states. [2018-06-22 01:43:19,964 INFO ]: Finished removeUnreachable. Reduced from 47 states to 47 states and 65 transitions. [2018-06-22 01:43:19,964 INFO ]: Start accepts. Automaton has 47 states and 65 transitions. Word has length 25 [2018-06-22 01:43:19,964 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:19,964 INFO ]: Abstraction has 47 states and 65 transitions. [2018-06-22 01:43:19,964 INFO ]: Interpolant automaton has 15 states. [2018-06-22 01:43:19,964 INFO ]: Start isEmpty. Operand 47 states and 65 transitions. [2018-06-22 01:43:19,965 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 01:43:19,965 INFO ]: Found error trace [2018-06-22 01:43:19,965 INFO ]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:19,965 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:19,965 INFO ]: Analyzing trace with hash -20594695, now seen corresponding path program 2 times [2018-06-22 01:43:19,965 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:19,965 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:19,966 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:19,966 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:19,966 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:19,976 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:20,069 INFO ]: Checked inductivity of 19 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 01:43:20,070 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:20,070 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:20,088 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:43:20,142 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:43:20,142 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:20,144 INFO ]: Computing forward predicates... [2018-06-22 01:43:20,247 INFO ]: Checked inductivity of 19 backedges. 7 proven. 5 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:43:20,270 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:20,271 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 17 [2018-06-22 01:43:20,271 INFO ]: Interpolant automaton has 17 states [2018-06-22 01:43:20,271 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 01:43:20,271 INFO ]: CoverageRelationStatistics Valid=38, Invalid=234, Unknown=0, NotChecked=0, Total=272 [2018-06-22 01:43:20,271 INFO ]: Start difference. First operand 47 states and 65 transitions. Second operand 17 states. [2018-06-22 01:43:20,808 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:20,808 INFO ]: Finished difference Result 58 states and 81 transitions. [2018-06-22 01:43:20,808 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-06-22 01:43:20,808 INFO ]: Start accepts. Automaton has 17 states. Word has length 25 [2018-06-22 01:43:20,809 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:20,809 INFO ]: With dead ends: 58 [2018-06-22 01:43:20,809 INFO ]: Without dead ends: 50 [2018-06-22 01:43:20,810 INFO ]: 0 DeclaredPredicates, 58 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 127 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=172, Invalid=884, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 01:43:20,810 INFO ]: Start minimizeSevpa. Operand 50 states. [2018-06-22 01:43:20,814 INFO ]: Finished minimizeSevpa. Reduced states from 50 to 50. [2018-06-22 01:43:20,814 INFO ]: Start removeUnreachable. Operand 50 states. [2018-06-22 01:43:20,815 INFO ]: Finished removeUnreachable. Reduced from 50 states to 50 states and 69 transitions. [2018-06-22 01:43:20,815 INFO ]: Start accepts. Automaton has 50 states and 69 transitions. Word has length 25 [2018-06-22 01:43:20,815 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:20,815 INFO ]: Abstraction has 50 states and 69 transitions. [2018-06-22 01:43:20,815 INFO ]: Interpolant automaton has 17 states. [2018-06-22 01:43:20,815 INFO ]: Start isEmpty. Operand 50 states and 69 transitions. [2018-06-22 01:43:20,816 INFO ]: Finished isEmpty. Found accepting run of length 27 [2018-06-22 01:43:20,816 INFO ]: Found error trace [2018-06-22 01:43:20,816 INFO ]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:20,817 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:20,817 INFO ]: Analyzing trace with hash -1303250136, now seen corresponding path program 3 times [2018-06-22 01:43:20,817 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:20,817 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:20,817 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:20,817 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:20,817 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:20,826 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:20,939 INFO ]: Checked inductivity of 23 backedges. 8 proven. 8 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:43:20,939 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:20,939 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:20,946 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:43:20,998 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 01:43:20,998 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:21,000 INFO ]: Computing forward predicates... [2018-06-22 01:43:21,302 INFO ]: Checked inductivity of 23 backedges. 11 proven. 5 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:43:21,321 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:21,321 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2018-06-22 01:43:21,322 INFO ]: Interpolant automaton has 16 states [2018-06-22 01:43:21,322 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 01:43:21,322 INFO ]: CoverageRelationStatistics Valid=37, Invalid=203, Unknown=0, NotChecked=0, Total=240 [2018-06-22 01:43:21,322 INFO ]: Start difference. First operand 50 states and 69 transitions. Second operand 16 states. [2018-06-22 01:43:21,520 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:21,520 INFO ]: Finished difference Result 63 states and 80 transitions. [2018-06-22 01:43:21,520 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-22 01:43:21,520 INFO ]: Start accepts. Automaton has 16 states. Word has length 26 [2018-06-22 01:43:21,520 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:21,520 INFO ]: With dead ends: 63 [2018-06-22 01:43:21,520 INFO ]: Without dead ends: 57 [2018-06-22 01:43:21,521 INFO ]: 0 DeclaredPredicates, 51 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 129 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=122, Invalid=634, Unknown=0, NotChecked=0, Total=756 [2018-06-22 01:43:21,521 INFO ]: Start minimizeSevpa. Operand 57 states. [2018-06-22 01:43:21,527 INFO ]: Finished minimizeSevpa. Reduced states from 57 to 57. [2018-06-22 01:43:21,527 INFO ]: Start removeUnreachable. Operand 57 states. [2018-06-22 01:43:21,527 INFO ]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2018-06-22 01:43:21,527 INFO ]: Start accepts. Automaton has 57 states and 74 transitions. Word has length 26 [2018-06-22 01:43:21,528 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:21,528 INFO ]: Abstraction has 57 states and 74 transitions. [2018-06-22 01:43:21,528 INFO ]: Interpolant automaton has 16 states. [2018-06-22 01:43:21,528 INFO ]: Start isEmpty. Operand 57 states and 74 transitions. [2018-06-22 01:43:21,529 INFO ]: Finished isEmpty. Found accepting run of length 35 [2018-06-22 01:43:21,529 INFO ]: Found error trace [2018-06-22 01:43:21,529 INFO ]: trace histogram [4, 4, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:21,529 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:21,529 INFO ]: Analyzing trace with hash 2033294678, now seen corresponding path program 4 times [2018-06-22 01:43:21,529 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:21,529 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:21,530 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:21,530 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:21,530 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:21,541 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:21,608 INFO ]: Checked inductivity of 46 backedges. 18 proven. 10 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-06-22 01:43:21,608 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:21,608 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:21,614 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:43:21,633 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:43:21,633 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:21,637 INFO ]: Computing forward predicates... [2018-06-22 01:43:21,753 INFO ]: Checked inductivity of 46 backedges. 19 proven. 9 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-06-22 01:43:21,772 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:21,772 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2018-06-22 01:43:21,772 INFO ]: Interpolant automaton has 16 states [2018-06-22 01:43:21,772 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 01:43:21,772 INFO ]: CoverageRelationStatistics Valid=39, Invalid=201, Unknown=0, NotChecked=0, Total=240 [2018-06-22 01:43:21,773 INFO ]: Start difference. First operand 57 states and 74 transitions. Second operand 16 states. [2018-06-22 01:43:21,926 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:21,926 INFO ]: Finished difference Result 62 states and 79 transitions. [2018-06-22 01:43:21,926 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 01:43:21,926 INFO ]: Start accepts. Automaton has 16 states. Word has length 34 [2018-06-22 01:43:21,926 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:21,927 INFO ]: With dead ends: 62 [2018-06-22 01:43:21,927 INFO ]: Without dead ends: 62 [2018-06-22 01:43:21,927 INFO ]: 0 DeclaredPredicates, 51 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 68 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=106, Invalid=446, Unknown=0, NotChecked=0, Total=552 [2018-06-22 01:43:21,927 INFO ]: Start minimizeSevpa. Operand 62 states. [2018-06-22 01:43:21,932 INFO ]: Finished minimizeSevpa. Reduced states from 62 to 58. [2018-06-22 01:43:21,932 INFO ]: Start removeUnreachable. Operand 58 states. [2018-06-22 01:43:21,932 INFO ]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2018-06-22 01:43:21,933 INFO ]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 34 [2018-06-22 01:43:21,933 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:21,933 INFO ]: Abstraction has 58 states and 75 transitions. [2018-06-22 01:43:21,933 INFO ]: Interpolant automaton has 16 states. [2018-06-22 01:43:21,933 INFO ]: Start isEmpty. Operand 58 states and 75 transitions. [2018-06-22 01:43:21,934 INFO ]: Finished isEmpty. Found accepting run of length 36 [2018-06-22 01:43:21,934 INFO ]: Found error trace [2018-06-22 01:43:21,934 INFO ]: trace histogram [4, 4, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:21,934 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:21,934 INFO ]: Analyzing trace with hash -1391758120, now seen corresponding path program 5 times [2018-06-22 01:43:21,934 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:21,934 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:21,934 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:21,934 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:21,934 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:21,952 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:22,084 INFO ]: Checked inductivity of 51 backedges. 6 proven. 28 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-06-22 01:43:22,134 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:22,134 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:22,145 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:43:22,184 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-22 01:43:22,184 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:22,188 INFO ]: Computing forward predicates... [2018-06-22 01:43:22,336 INFO ]: Checked inductivity of 51 backedges. 6 proven. 28 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-06-22 01:43:22,359 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:22,359 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 18 [2018-06-22 01:43:22,359 INFO ]: Interpolant automaton has 18 states [2018-06-22 01:43:22,359 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-22 01:43:22,359 INFO ]: CoverageRelationStatistics Valid=38, Invalid=268, Unknown=0, NotChecked=0, Total=306 [2018-06-22 01:43:22,359 INFO ]: Start difference. First operand 58 states and 75 transitions. Second operand 18 states. [2018-06-22 01:43:22,889 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:22,889 INFO ]: Finished difference Result 81 states and 108 transitions. [2018-06-22 01:43:22,890 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-06-22 01:43:22,890 INFO ]: Start accepts. Automaton has 18 states. Word has length 35 [2018-06-22 01:43:22,890 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:22,891 INFO ]: With dead ends: 81 [2018-06-22 01:43:22,891 INFO ]: Without dead ends: 81 [2018-06-22 01:43:22,891 INFO ]: 0 DeclaredPredicates, 74 GetRequests, 31 SyntacticMatches, 3 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 364 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=194, Invalid=1528, Unknown=0, NotChecked=0, Total=1722 [2018-06-22 01:43:22,892 INFO ]: Start minimizeSevpa. Operand 81 states. [2018-06-22 01:43:22,897 INFO ]: Finished minimizeSevpa. Reduced states from 81 to 67. [2018-06-22 01:43:22,897 INFO ]: Start removeUnreachable. Operand 67 states. [2018-06-22 01:43:22,898 INFO ]: Finished removeUnreachable. Reduced from 67 states to 67 states and 88 transitions. [2018-06-22 01:43:22,898 INFO ]: Start accepts. Automaton has 67 states and 88 transitions. Word has length 35 [2018-06-22 01:43:22,898 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:22,899 INFO ]: Abstraction has 67 states and 88 transitions. [2018-06-22 01:43:22,899 INFO ]: Interpolant automaton has 18 states. [2018-06-22 01:43:22,899 INFO ]: Start isEmpty. Operand 67 states and 88 transitions. [2018-06-22 01:43:22,900 INFO ]: Finished isEmpty. Found accepting run of length 35 [2018-06-22 01:43:22,900 INFO ]: Found error trace [2018-06-22 01:43:22,900 INFO ]: trace histogram [4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:22,900 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:22,900 INFO ]: Analyzing trace with hash 182308569, now seen corresponding path program 3 times [2018-06-22 01:43:22,900 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:22,900 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:22,900 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:22,900 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:22,900 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:22,915 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:23,045 INFO ]: Checked inductivity of 44 backedges. 17 proven. 12 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 01:43:23,045 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:23,045 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:23,050 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:43:23,066 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 01:43:23,066 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:23,069 INFO ]: Computing forward predicates... [2018-06-22 01:43:23,108 INFO ]: Checked inductivity of 44 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2018-06-22 01:43:23,127 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 01:43:23,127 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [12] total 14 [2018-06-22 01:43:23,128 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:43:23,128 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:43:23,128 INFO ]: CoverageRelationStatistics Valid=29, Invalid=153, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:43:23,128 INFO ]: Start difference. First operand 67 states and 88 transitions. Second operand 14 states. [2018-06-22 01:43:23,423 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:23,423 INFO ]: Finished difference Result 84 states and 110 transitions. [2018-06-22 01:43:23,423 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-22 01:43:23,423 INFO ]: Start accepts. Automaton has 14 states. Word has length 34 [2018-06-22 01:43:23,423 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:23,423 INFO ]: With dead ends: 84 [2018-06-22 01:43:23,423 INFO ]: Without dead ends: 66 [2018-06-22 01:43:23,424 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 77 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=88, Invalid=512, Unknown=0, NotChecked=0, Total=600 [2018-06-22 01:43:23,424 INFO ]: Start minimizeSevpa. Operand 66 states. [2018-06-22 01:43:23,430 INFO ]: Finished minimizeSevpa. Reduced states from 66 to 63. [2018-06-22 01:43:23,430 INFO ]: Start removeUnreachable. Operand 63 states. [2018-06-22 01:43:23,431 INFO ]: Finished removeUnreachable. Reduced from 63 states to 63 states and 76 transitions. [2018-06-22 01:43:23,431 INFO ]: Start accepts. Automaton has 63 states and 76 transitions. Word has length 34 [2018-06-22 01:43:23,431 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:23,431 INFO ]: Abstraction has 63 states and 76 transitions. [2018-06-22 01:43:23,431 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:43:23,431 INFO ]: Start isEmpty. Operand 63 states and 76 transitions. [2018-06-22 01:43:23,432 INFO ]: Finished isEmpty. Found accepting run of length 37 [2018-06-22 01:43:23,432 INFO ]: Found error trace [2018-06-22 01:43:23,432 INFO ]: trace histogram [4, 4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:23,432 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:23,432 INFO ]: Analyzing trace with hash -194212458, now seen corresponding path program 6 times [2018-06-22 01:43:23,432 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:23,432 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:23,433 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:23,433 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:23,433 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:23,444 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:24,265 INFO ]: Checked inductivity of 57 backedges. 21 proven. 18 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-06-22 01:43:24,265 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:24,265 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:24,271 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:43:24,313 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-22 01:43:24,313 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:24,315 INFO ]: Computing forward predicates... [2018-06-22 01:43:24,407 INFO ]: Checked inductivity of 57 backedges. 25 proven. 14 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-06-22 01:43:24,429 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:24,429 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 20 [2018-06-22 01:43:24,429 INFO ]: Interpolant automaton has 20 states [2018-06-22 01:43:24,430 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 01:43:24,430 INFO ]: CoverageRelationStatistics Valid=56, Invalid=324, Unknown=0, NotChecked=0, Total=380 [2018-06-22 01:43:24,430 INFO ]: Start difference. First operand 63 states and 76 transitions. Second operand 20 states. [2018-06-22 01:43:24,944 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:24,944 INFO ]: Finished difference Result 82 states and 96 transitions. [2018-06-22 01:43:24,944 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-06-22 01:43:24,944 INFO ]: Start accepts. Automaton has 20 states. Word has length 36 [2018-06-22 01:43:24,944 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:24,944 INFO ]: With dead ends: 82 [2018-06-22 01:43:24,944 INFO ]: Without dead ends: 74 [2018-06-22 01:43:24,945 INFO ]: 0 DeclaredPredicates, 69 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 370 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=228, Invalid=1332, Unknown=0, NotChecked=0, Total=1560 [2018-06-22 01:43:24,945 INFO ]: Start minimizeSevpa. Operand 74 states. [2018-06-22 01:43:24,952 INFO ]: Finished minimizeSevpa. Reduced states from 74 to 70. [2018-06-22 01:43:24,952 INFO ]: Start removeUnreachable. Operand 70 states. [2018-06-22 01:43:24,953 INFO ]: Finished removeUnreachable. Reduced from 70 states to 70 states and 84 transitions. [2018-06-22 01:43:24,953 INFO ]: Start accepts. Automaton has 70 states and 84 transitions. Word has length 36 [2018-06-22 01:43:24,953 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:24,953 INFO ]: Abstraction has 70 states and 84 transitions. [2018-06-22 01:43:24,953 INFO ]: Interpolant automaton has 20 states. [2018-06-22 01:43:24,953 INFO ]: Start isEmpty. Operand 70 states and 84 transitions. [2018-06-22 01:43:24,954 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 01:43:24,954 INFO ]: Found error trace [2018-06-22 01:43:24,954 INFO ]: trace histogram [5, 5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:24,954 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:24,954 INFO ]: Analyzing trace with hash 156330154, now seen corresponding path program 7 times [2018-06-22 01:43:24,954 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:24,954 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:24,955 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:24,955 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:24,955 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:24,970 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:25,224 INFO ]: Checked inductivity of 98 backedges. 38 proven. 21 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2018-06-22 01:43:25,224 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:25,224 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:25,240 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:25,276 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:25,280 INFO ]: Computing forward predicates... [2018-06-22 01:43:25,757 INFO ]: Checked inductivity of 98 backedges. 41 proven. 18 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2018-06-22 01:43:25,778 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:25,778 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2018-06-22 01:43:25,778 INFO ]: Interpolant automaton has 19 states [2018-06-22 01:43:25,778 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 01:43:25,778 INFO ]: CoverageRelationStatistics Valid=53, Invalid=289, Unknown=0, NotChecked=0, Total=342 [2018-06-22 01:43:25,778 INFO ]: Start difference. First operand 70 states and 84 transitions. Second operand 19 states. [2018-06-22 01:43:26,075 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:26,075 INFO ]: Finished difference Result 73 states and 87 transitions. [2018-06-22 01:43:26,075 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-22 01:43:26,075 INFO ]: Start accepts. Automaton has 19 states. Word has length 45 [2018-06-22 01:43:26,075 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:26,076 INFO ]: With dead ends: 73 [2018-06-22 01:43:26,076 INFO ]: Without dead ends: 73 [2018-06-22 01:43:26,077 INFO ]: 0 DeclaredPredicates, 67 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=160, Invalid=710, Unknown=0, NotChecked=0, Total=870 [2018-06-22 01:43:26,077 INFO ]: Start minimizeSevpa. Operand 73 states. [2018-06-22 01:43:26,080 INFO ]: Finished minimizeSevpa. Reduced states from 73 to 73. [2018-06-22 01:43:26,080 INFO ]: Start removeUnreachable. Operand 73 states. [2018-06-22 01:43:26,081 INFO ]: Finished removeUnreachable. Reduced from 73 states to 73 states and 87 transitions. [2018-06-22 01:43:26,081 INFO ]: Start accepts. Automaton has 73 states and 87 transitions. Word has length 45 [2018-06-22 01:43:26,081 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:26,081 INFO ]: Abstraction has 73 states and 87 transitions. [2018-06-22 01:43:26,081 INFO ]: Interpolant automaton has 19 states. [2018-06-22 01:43:26,081 INFO ]: Start isEmpty. Operand 73 states and 87 transitions. [2018-06-22 01:43:26,082 INFO ]: Finished isEmpty. Found accepting run of length 47 [2018-06-22 01:43:26,082 INFO ]: Found error trace [2018-06-22 01:43:26,082 INFO ]: trace histogram [6, 5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:26,082 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:26,082 INFO ]: Analyzing trace with hash 551883780, now seen corresponding path program 8 times [2018-06-22 01:43:26,082 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:26,082 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:26,083 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:26,083 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:26,083 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:26,097 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:26,394 INFO ]: Checked inductivity of 107 backedges. 8 proven. 66 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2018-06-22 01:43:26,394 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:26,394 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:26,399 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:43:26,426 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:43:26,426 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:26,430 INFO ]: Computing forward predicates... [2018-06-22 01:43:26,566 INFO ]: Checked inductivity of 107 backedges. 8 proven. 66 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2018-06-22 01:43:26,585 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:26,585 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 21 [2018-06-22 01:43:26,585 INFO ]: Interpolant automaton has 21 states [2018-06-22 01:43:26,585 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 01:43:26,585 INFO ]: CoverageRelationStatistics Valid=45, Invalid=375, Unknown=0, NotChecked=0, Total=420 [2018-06-22 01:43:26,586 INFO ]: Start difference. First operand 73 states and 87 transitions. Second operand 21 states. [2018-06-22 01:43:27,177 WARN ]: Spent 105.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-22 01:43:27,337 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:27,337 INFO ]: Finished difference Result 89 states and 105 transitions. [2018-06-22 01:43:27,340 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-06-22 01:43:27,340 INFO ]: Start accepts. Automaton has 21 states. Word has length 46 [2018-06-22 01:43:27,340 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:27,341 INFO ]: With dead ends: 89 [2018-06-22 01:43:27,341 INFO ]: Without dead ends: 89 [2018-06-22 01:43:27,342 INFO ]: 0 DeclaredPredicates, 92 GetRequests, 42 SyntacticMatches, 4 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 485 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=223, Invalid=2033, Unknown=0, NotChecked=0, Total=2256 [2018-06-22 01:43:27,342 INFO ]: Start minimizeSevpa. Operand 89 states. [2018-06-22 01:43:27,346 INFO ]: Finished minimizeSevpa. Reduced states from 89 to 83. [2018-06-22 01:43:27,346 INFO ]: Start removeUnreachable. Operand 83 states. [2018-06-22 01:43:27,347 INFO ]: Finished removeUnreachable. Reduced from 83 states to 83 states and 99 transitions. [2018-06-22 01:43:27,347 INFO ]: Start accepts. Automaton has 83 states and 99 transitions. Word has length 46 [2018-06-22 01:43:27,347 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:27,347 INFO ]: Abstraction has 83 states and 99 transitions. [2018-06-22 01:43:27,347 INFO ]: Interpolant automaton has 21 states. [2018-06-22 01:43:27,347 INFO ]: Start isEmpty. Operand 83 states and 99 transitions. [2018-06-22 01:43:27,351 INFO ]: Finished isEmpty. Found accepting run of length 48 [2018-06-22 01:43:27,351 INFO ]: Found error trace [2018-06-22 01:43:27,351 INFO ]: trace histogram [7, 5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:27,351 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:27,351 INFO ]: Analyzing trace with hash -70855702, now seen corresponding path program 9 times [2018-06-22 01:43:27,351 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:27,351 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:27,352 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:27,352 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:27,352 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:27,367 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:27,963 INFO ]: Checked inductivity of 117 backedges. 47 proven. 31 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2018-06-22 01:43:27,963 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:27,963 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:27,974 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:43:28,006 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-22 01:43:28,006 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:28,009 INFO ]: Computing forward predicates... [2018-06-22 01:43:28,150 INFO ]: Checked inductivity of 117 backedges. 54 proven. 24 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2018-06-22 01:43:28,172 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:28,172 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 21 [2018-06-22 01:43:28,172 INFO ]: Interpolant automaton has 21 states [2018-06-22 01:43:28,173 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 01:43:28,173 INFO ]: CoverageRelationStatistics Valid=69, Invalid=351, Unknown=0, NotChecked=0, Total=420 [2018-06-22 01:43:28,173 INFO ]: Start difference. First operand 83 states and 99 transitions. Second operand 21 states. [2018-06-22 01:43:28,520 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:28,520 INFO ]: Finished difference Result 114 states and 136 transitions. [2018-06-22 01:43:28,520 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-06-22 01:43:28,520 INFO ]: Start accepts. Automaton has 21 states. Word has length 47 [2018-06-22 01:43:28,520 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:28,521 INFO ]: With dead ends: 114 [2018-06-22 01:43:28,521 INFO ]: Without dead ends: 101 [2018-06-22 01:43:28,522 INFO ]: 0 DeclaredPredicates, 80 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 337 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=301, Invalid=1339, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 01:43:28,522 INFO ]: Start minimizeSevpa. Operand 101 states. [2018-06-22 01:43:28,526 INFO ]: Finished minimizeSevpa. Reduced states from 101 to 91. [2018-06-22 01:43:28,526 INFO ]: Start removeUnreachable. Operand 91 states. [2018-06-22 01:43:28,527 INFO ]: Finished removeUnreachable. Reduced from 91 states to 91 states and 108 transitions. [2018-06-22 01:43:28,527 INFO ]: Start accepts. Automaton has 91 states and 108 transitions. Word has length 47 [2018-06-22 01:43:28,528 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:28,528 INFO ]: Abstraction has 91 states and 108 transitions. [2018-06-22 01:43:28,528 INFO ]: Interpolant automaton has 21 states. [2018-06-22 01:43:28,528 INFO ]: Start isEmpty. Operand 91 states and 108 transitions. [2018-06-22 01:43:28,528 INFO ]: Finished isEmpty. Found accepting run of length 58 [2018-06-22 01:43:28,529 INFO ]: Found error trace [2018-06-22 01:43:28,529 INFO ]: trace histogram [9, 6, 6, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:28,530 INFO ]: === Iteration 20 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:28,530 INFO ]: Analyzing trace with hash -1820690372, now seen corresponding path program 10 times [2018-06-22 01:43:28,530 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:28,530 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:28,531 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:28,531 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:28,531 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:28,548 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:28,769 INFO ]: Checked inductivity of 186 backedges. 75 proven. 35 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2018-06-22 01:43:28,769 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:28,769 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:28,775 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:43:28,809 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:43:28,809 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:28,812 INFO ]: Computing forward predicates... [2018-06-22 01:43:28,932 INFO ]: Checked inductivity of 186 backedges. 80 proven. 30 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2018-06-22 01:43:28,951 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:28,951 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 22 [2018-06-22 01:43:28,951 INFO ]: Interpolant automaton has 22 states [2018-06-22 01:43:28,951 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-22 01:43:28,951 INFO ]: CoverageRelationStatistics Valid=71, Invalid=391, Unknown=0, NotChecked=0, Total=462 [2018-06-22 01:43:28,951 INFO ]: Start difference. First operand 91 states and 108 transitions. Second operand 22 states. [2018-06-22 01:43:29,422 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:29,422 INFO ]: Finished difference Result 94 states and 111 transitions. [2018-06-22 01:43:29,424 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-06-22 01:43:29,424 INFO ]: Start accepts. Automaton has 22 states. Word has length 57 [2018-06-22 01:43:29,424 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:29,424 INFO ]: With dead ends: 94 [2018-06-22 01:43:29,424 INFO ]: Without dead ends: 94 [2018-06-22 01:43:29,426 INFO ]: 0 DeclaredPredicates, 84 GetRequests, 50 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 194 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=230, Invalid=1030, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 01:43:29,426 INFO ]: Start minimizeSevpa. Operand 94 states. [2018-06-22 01:43:29,429 INFO ]: Finished minimizeSevpa. Reduced states from 94 to 94. [2018-06-22 01:43:29,429 INFO ]: Start removeUnreachable. Operand 94 states. [2018-06-22 01:43:29,430 INFO ]: Finished removeUnreachable. Reduced from 94 states to 94 states and 111 transitions. [2018-06-22 01:43:29,430 INFO ]: Start accepts. Automaton has 94 states and 111 transitions. Word has length 57 [2018-06-22 01:43:29,431 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:29,431 INFO ]: Abstraction has 94 states and 111 transitions. [2018-06-22 01:43:29,431 INFO ]: Interpolant automaton has 22 states. [2018-06-22 01:43:29,431 INFO ]: Start isEmpty. Operand 94 states and 111 transitions. [2018-06-22 01:43:29,431 INFO ]: Finished isEmpty. Found accepting run of length 59 [2018-06-22 01:43:29,431 INFO ]: Found error trace [2018-06-22 01:43:29,432 INFO ]: trace histogram [10, 6, 6, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:29,432 INFO ]: === Iteration 21 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:29,438 INFO ]: Analyzing trace with hash -606210382, now seen corresponding path program 11 times [2018-06-22 01:43:29,438 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:29,438 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:29,438 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:29,438 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:29,438 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:29,467 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:30,304 INFO ]: Checked inductivity of 200 backedges. 10 proven. 134 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2018-06-22 01:43:30,304 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:30,304 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 01:43:30,311 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:43:30,429 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2018-06-22 01:43:30,429 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:30,433 INFO ]: Computing forward predicates... [2018-06-22 01:43:30,709 INFO ]: Checked inductivity of 200 backedges. 10 proven. 134 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2018-06-22 01:43:30,730 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:30,730 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 24 [2018-06-22 01:43:30,730 INFO ]: Interpolant automaton has 24 states [2018-06-22 01:43:30,730 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 01:43:30,730 INFO ]: CoverageRelationStatistics Valid=52, Invalid=500, Unknown=0, NotChecked=0, Total=552 [2018-06-22 01:43:30,731 INFO ]: Start difference. First operand 94 states and 111 transitions. Second operand 24 states. [2018-06-22 01:43:31,869 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:31,869 INFO ]: Finished difference Result 113 states and 132 transitions. [2018-06-22 01:43:31,871 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2018-06-22 01:43:31,871 INFO ]: Start accepts. Automaton has 24 states. Word has length 58 [2018-06-22 01:43:31,871 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:31,871 INFO ]: With dead ends: 113 [2018-06-22 01:43:31,871 INFO ]: Without dead ends: 113 [2018-06-22 01:43:31,872 INFO ]: 0 DeclaredPredicates, 113 GetRequests, 54 SyntacticMatches, 5 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 677 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=270, Invalid=2810, Unknown=0, NotChecked=0, Total=3080 [2018-06-22 01:43:31,873 INFO ]: Start minimizeSevpa. Operand 113 states. [2018-06-22 01:43:31,877 INFO ]: Finished minimizeSevpa. Reduced states from 113 to 105. [2018-06-22 01:43:31,877 INFO ]: Start removeUnreachable. Operand 105 states. [2018-06-22 01:43:31,878 INFO ]: Finished removeUnreachable. Reduced from 105 states to 105 states and 124 transitions. [2018-06-22 01:43:31,878 INFO ]: Start accepts. Automaton has 105 states and 124 transitions. Word has length 58 [2018-06-22 01:43:31,879 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:31,879 INFO ]: Abstraction has 105 states and 124 transitions. [2018-06-22 01:43:31,879 INFO ]: Interpolant automaton has 24 states. [2018-06-22 01:43:31,879 INFO ]: Start isEmpty. Operand 105 states and 124 transitions. [2018-06-22 01:43:31,879 INFO ]: Finished isEmpty. Found accepting run of length 60 [2018-06-22 01:43:31,880 INFO ]: Found error trace [2018-06-22 01:43:31,880 INFO ]: trace histogram [11, 6, 6, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:31,880 INFO ]: === Iteration 22 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:31,880 INFO ]: Analyzing trace with hash -1612036356, now seen corresponding path program 12 times [2018-06-22 01:43:31,880 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:31,880 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:31,880 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:31,880 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:31,880 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:31,905 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:32,087 INFO ]: Checked inductivity of 215 backedges. 92 proven. 47 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2018-06-22 01:43:32,087 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:32,087 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 01:43:32,093 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:43:32,136 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 01:43:32,136 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:32,139 INFO ]: Computing forward predicates... [2018-06-22 01:43:32,327 INFO ]: Checked inductivity of 215 backedges. 101 proven. 38 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2018-06-22 01:43:32,355 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:32,355 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 24 [2018-06-22 01:43:32,355 INFO ]: Interpolant automaton has 24 states [2018-06-22 01:43:32,355 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 01:43:32,355 INFO ]: CoverageRelationStatistics Valid=91, Invalid=461, Unknown=0, NotChecked=0, Total=552 [2018-06-22 01:43:32,355 INFO ]: Start difference. First operand 105 states and 124 transitions. Second operand 24 states. [2018-06-22 01:43:33,242 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:33,242 INFO ]: Finished difference Result 147 states and 172 transitions. [2018-06-22 01:43:33,245 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-06-22 01:43:33,245 INFO ]: Start accepts. Automaton has 24 states. Word has length 59 [2018-06-22 01:43:33,246 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:33,247 INFO ]: With dead ends: 147 [2018-06-22 01:43:33,247 INFO ]: Without dead ends: 132 [2018-06-22 01:43:33,247 INFO ]: 0 DeclaredPredicates, 98 GetRequests, 52 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 506 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=418, Invalid=1838, Unknown=0, NotChecked=0, Total=2256 [2018-06-22 01:43:33,247 INFO ]: Start minimizeSevpa. Operand 132 states. [2018-06-22 01:43:33,258 INFO ]: Finished minimizeSevpa. Reduced states from 132 to 114. [2018-06-22 01:43:33,258 INFO ]: Start removeUnreachable. Operand 114 states. [2018-06-22 01:43:33,259 INFO ]: Finished removeUnreachable. Reduced from 114 states to 114 states and 134 transitions. [2018-06-22 01:43:33,259 INFO ]: Start accepts. Automaton has 114 states and 134 transitions. Word has length 59 [2018-06-22 01:43:33,259 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:33,259 INFO ]: Abstraction has 114 states and 134 transitions. [2018-06-22 01:43:33,259 INFO ]: Interpolant automaton has 24 states. [2018-06-22 01:43:33,259 INFO ]: Start isEmpty. Operand 114 states and 134 transitions. [2018-06-22 01:43:33,260 INFO ]: Finished isEmpty. Found accepting run of length 71 [2018-06-22 01:43:33,260 INFO ]: Found error trace [2018-06-22 01:43:33,260 INFO ]: trace histogram [14, 7, 7, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:33,260 INFO ]: === Iteration 23 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:33,260 INFO ]: Analyzing trace with hash -216828320, now seen corresponding path program 13 times [2018-06-22 01:43:33,260 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:33,260 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:33,261 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:33,261 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:33,261 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:33,279 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:34,353 INFO ]: Checked inductivity of 325 backedges. 135 proven. 52 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2018-06-22 01:43:34,353 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:34,354 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 01:43:34,364 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:34,424 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:34,427 INFO ]: Computing forward predicates... [2018-06-22 01:43:34,608 INFO ]: Checked inductivity of 325 backedges. 142 proven. 45 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2018-06-22 01:43:34,628 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:34,628 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 25 [2018-06-22 01:43:34,629 INFO ]: Interpolant automaton has 25 states [2018-06-22 01:43:34,629 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-22 01:43:34,629 INFO ]: CoverageRelationStatistics Valid=93, Invalid=507, Unknown=0, NotChecked=0, Total=600 [2018-06-22 01:43:34,629 INFO ]: Start difference. First operand 114 states and 134 transitions. Second operand 25 states. [2018-06-22 01:43:34,954 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:34,954 INFO ]: Finished difference Result 117 states and 137 transitions. [2018-06-22 01:43:34,954 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-06-22 01:43:34,954 INFO ]: Start accepts. Automaton has 25 states. Word has length 70 [2018-06-22 01:43:34,954 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:34,955 INFO ]: With dead ends: 117 [2018-06-22 01:43:34,955 INFO ]: Without dead ends: 117 [2018-06-22 01:43:34,956 INFO ]: 0 DeclaredPredicates, 102 GetRequests, 62 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 283 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=316, Invalid=1406, Unknown=0, NotChecked=0, Total=1722 [2018-06-22 01:43:34,956 INFO ]: Start minimizeSevpa. Operand 117 states. [2018-06-22 01:43:34,960 INFO ]: Finished minimizeSevpa. Reduced states from 117 to 117. [2018-06-22 01:43:34,960 INFO ]: Start removeUnreachable. Operand 117 states. [2018-06-22 01:43:34,961 INFO ]: Finished removeUnreachable. Reduced from 117 states to 117 states and 137 transitions. [2018-06-22 01:43:34,961 INFO ]: Start accepts. Automaton has 117 states and 137 transitions. Word has length 70 [2018-06-22 01:43:34,961 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:34,961 INFO ]: Abstraction has 117 states and 137 transitions. [2018-06-22 01:43:34,961 INFO ]: Interpolant automaton has 25 states. [2018-06-22 01:43:34,961 INFO ]: Start isEmpty. Operand 117 states and 137 transitions. [2018-06-22 01:43:34,962 INFO ]: Finished isEmpty. Found accepting run of length 72 [2018-06-22 01:43:34,962 INFO ]: Found error trace [2018-06-22 01:43:34,962 INFO ]: trace histogram [15, 7, 7, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:34,962 INFO ]: === Iteration 24 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:34,963 INFO ]: Analyzing trace with hash 1868872974, now seen corresponding path program 14 times [2018-06-22 01:43:34,963 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:34,963 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:34,963 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:34,963 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:34,963 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:34,984 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:35,226 INFO ]: Checked inductivity of 345 backedges. 12 proven. 246 refuted. 0 times theorem prover too weak. 87 trivial. 0 not checked. [2018-06-22 01:43:35,294 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:35,294 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 01:43:35,317 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:43:35,373 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:43:35,373 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:35,376 INFO ]: Computing forward predicates... [2018-06-22 01:43:35,777 WARN ]: Spent 122.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 01:43:35,991 INFO ]: Checked inductivity of 345 backedges. 12 proven. 246 refuted. 0 times theorem prover too weak. 87 trivial. 0 not checked. [2018-06-22 01:43:36,011 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:36,011 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 27 [2018-06-22 01:43:36,011 INFO ]: Interpolant automaton has 27 states [2018-06-22 01:43:36,011 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-22 01:43:36,011 INFO ]: CoverageRelationStatistics Valid=59, Invalid=643, Unknown=0, NotChecked=0, Total=702 [2018-06-22 01:43:36,011 INFO ]: Start difference. First operand 117 states and 137 transitions. Second operand 27 states. [2018-06-22 01:43:36,762 WARN ]: Spent 150.00 ms on a formula simplification that was a NOOP. DAG size: 33 [2018-06-22 01:43:37,434 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:37,434 INFO ]: Finished difference Result 139 states and 161 transitions. [2018-06-22 01:43:37,440 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2018-06-22 01:43:37,440 INFO ]: Start accepts. Automaton has 27 states. Word has length 71 [2018-06-22 01:43:37,440 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:37,441 INFO ]: With dead ends: 139 [2018-06-22 01:43:37,441 INFO ]: Without dead ends: 139 [2018-06-22 01:43:37,442 INFO ]: 0 DeclaredPredicates, 135 GetRequests, 67 SyntacticMatches, 6 SemanticMatches, 62 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 909 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=319, Invalid=3713, Unknown=0, NotChecked=0, Total=4032 [2018-06-22 01:43:37,442 INFO ]: Start minimizeSevpa. Operand 139 states. [2018-06-22 01:43:37,447 INFO ]: Finished minimizeSevpa. Reduced states from 139 to 129. [2018-06-22 01:43:37,447 INFO ]: Start removeUnreachable. Operand 129 states. [2018-06-22 01:43:37,449 INFO ]: Finished removeUnreachable. Reduced from 129 states to 129 states and 151 transitions. [2018-06-22 01:43:37,449 INFO ]: Start accepts. Automaton has 129 states and 151 transitions. Word has length 71 [2018-06-22 01:43:37,449 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:37,449 INFO ]: Abstraction has 129 states and 151 transitions. [2018-06-22 01:43:37,449 INFO ]: Interpolant automaton has 27 states. [2018-06-22 01:43:37,449 INFO ]: Start isEmpty. Operand 129 states and 151 transitions. [2018-06-22 01:43:37,452 INFO ]: Finished isEmpty. Found accepting run of length 73 [2018-06-22 01:43:37,518 INFO ]: Found error trace [2018-06-22 01:43:37,518 INFO ]: trace histogram [16, 7, 7, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:37,518 INFO ]: === Iteration 25 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:37,518 INFO ]: Analyzing trace with hash 2101103648, now seen corresponding path program 15 times [2018-06-22 01:43:37,519 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:37,519 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:37,519 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:37,519 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:37,519 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:37,539 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:37,760 INFO ]: Checked inductivity of 366 backedges. 162 proven. 66 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2018-06-22 01:43:37,760 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:37,760 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 01:43:37,766 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:43:37,827 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2018-06-22 01:43:37,827 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:37,830 INFO ]: Computing forward predicates... [2018-06-22 01:43:38,390 INFO ]: Checked inductivity of 366 backedges. 173 proven. 55 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2018-06-22 01:43:38,423 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:38,423 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 27 [2018-06-22 01:43:38,423 INFO ]: Interpolant automaton has 27 states [2018-06-22 01:43:38,423 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-22 01:43:38,423 INFO ]: CoverageRelationStatistics Valid=117, Invalid=585, Unknown=0, NotChecked=0, Total=702 [2018-06-22 01:43:38,423 INFO ]: Start difference. First operand 129 states and 151 transitions. Second operand 27 states. [2018-06-22 01:43:39,201 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:39,201 INFO ]: Finished difference Result 184 states and 212 transitions. [2018-06-22 01:43:39,201 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-06-22 01:43:39,201 INFO ]: Start accepts. Automaton has 27 states. Word has length 72 [2018-06-22 01:43:39,202 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:39,203 INFO ]: With dead ends: 184 [2018-06-22 01:43:39,203 INFO ]: Without dead ends: 167 [2018-06-22 01:43:39,204 INFO ]: 0 DeclaredPredicates, 117 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 708 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=557, Invalid=2413, Unknown=0, NotChecked=0, Total=2970 [2018-06-22 01:43:39,204 INFO ]: Start minimizeSevpa. Operand 167 states. [2018-06-22 01:43:39,213 INFO ]: Finished minimizeSevpa. Reduced states from 167 to 139. [2018-06-22 01:43:39,213 INFO ]: Start removeUnreachable. Operand 139 states. [2018-06-22 01:43:39,214 INFO ]: Finished removeUnreachable. Reduced from 139 states to 139 states and 162 transitions. [2018-06-22 01:43:39,214 INFO ]: Start accepts. Automaton has 139 states and 162 transitions. Word has length 72 [2018-06-22 01:43:39,214 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:39,214 INFO ]: Abstraction has 139 states and 162 transitions. [2018-06-22 01:43:39,214 INFO ]: Interpolant automaton has 27 states. [2018-06-22 01:43:39,214 INFO ]: Start isEmpty. Operand 139 states and 162 transitions. [2018-06-22 01:43:39,215 INFO ]: Finished isEmpty. Found accepting run of length 85 [2018-06-22 01:43:39,215 INFO ]: Found error trace [2018-06-22 01:43:39,215 INFO ]: trace histogram [20, 8, 8, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:39,215 INFO ]: === Iteration 26 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:39,215 INFO ]: Analyzing trace with hash 734520910, now seen corresponding path program 16 times [2018-06-22 01:43:39,215 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:39,215 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:39,217 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:39,217 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:39,217 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:39,236 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:39,794 INFO ]: Checked inductivity of 533 backedges. 224 proven. 72 refuted. 0 times theorem prover too weak. 237 trivial. 0 not checked. [2018-06-22 01:43:39,794 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:39,794 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 01:43:39,799 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:43:39,884 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:43:39,884 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:39,889 INFO ]: Computing forward predicates... [2018-06-22 01:43:40,103 INFO ]: Checked inductivity of 533 backedges. 233 proven. 63 refuted. 0 times theorem prover too weak. 237 trivial. 0 not checked. [2018-06-22 01:43:40,123 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:40,123 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 28 [2018-06-22 01:43:40,124 INFO ]: Interpolant automaton has 28 states [2018-06-22 01:43:40,124 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-22 01:43:40,124 INFO ]: CoverageRelationStatistics Valid=119, Invalid=637, Unknown=0, NotChecked=0, Total=756 [2018-06-22 01:43:40,124 INFO ]: Start difference. First operand 139 states and 162 transitions. Second operand 28 states. [2018-06-22 01:43:40,761 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:42,357 INFO ]: Finished difference Result 142 states and 165 transitions. [2018-06-22 01:43:42,358 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-06-22 01:43:42,358 INFO ]: Start accepts. Automaton has 28 states. Word has length 84 [2018-06-22 01:43:42,359 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:42,361 INFO ]: With dead ends: 142 [2018-06-22 01:43:42,361 INFO ]: Without dead ends: 142 [2018-06-22 01:43:42,362 INFO ]: 0 DeclaredPredicates, 121 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 387 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=418, Invalid=1838, Unknown=0, NotChecked=0, Total=2256 [2018-06-22 01:43:42,362 INFO ]: Start minimizeSevpa. Operand 142 states. [2018-06-22 01:43:42,375 INFO ]: Finished minimizeSevpa. Reduced states from 142 to 142. [2018-06-22 01:43:42,375 INFO ]: Start removeUnreachable. Operand 142 states. [2018-06-22 01:43:42,377 INFO ]: Finished removeUnreachable. Reduced from 142 states to 142 states and 165 transitions. [2018-06-22 01:43:42,377 INFO ]: Start accepts. Automaton has 142 states and 165 transitions. Word has length 84 [2018-06-22 01:43:42,377 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:42,377 INFO ]: Abstraction has 142 states and 165 transitions. [2018-06-22 01:43:42,377 INFO ]: Interpolant automaton has 28 states. [2018-06-22 01:43:42,377 INFO ]: Start isEmpty. Operand 142 states and 165 transitions. [2018-06-22 01:43:42,381 INFO ]: Finished isEmpty. Found accepting run of length 86 [2018-06-22 01:43:42,381 INFO ]: Found error trace [2018-06-22 01:43:42,381 INFO ]: trace histogram [21, 8, 8, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:42,382 INFO ]: === Iteration 27 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:42,382 INFO ]: Analyzing trace with hash 1295928032, now seen corresponding path program 17 times [2018-06-22 01:43:42,382 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:42,382 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:42,383 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:42,383 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:42,383 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:42,424 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:42,951 INFO ]: Checked inductivity of 560 backedges. 14 proven. 419 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2018-06-22 01:43:42,952 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:42,952 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 01:43:42,957 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:43:43,027 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2018-06-22 01:43:43,027 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:43,031 INFO ]: Computing forward predicates... [2018-06-22 01:43:43,355 INFO ]: Checked inductivity of 560 backedges. 14 proven. 419 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2018-06-22 01:43:43,374 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:43,374 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 30 [2018-06-22 01:43:43,374 INFO ]: Interpolant automaton has 30 states [2018-06-22 01:43:43,374 INFO ]: Constructing interpolant automaton starting with 30 interpolants. [2018-06-22 01:43:43,375 INFO ]: CoverageRelationStatistics Valid=66, Invalid=804, Unknown=0, NotChecked=0, Total=870 [2018-06-22 01:43:43,375 INFO ]: Start difference. First operand 142 states and 165 transitions. Second operand 30 states. [2018-06-22 01:43:44,055 WARN ]: Spent 114.00 ms on a formula simplification that was a NOOP. DAG size: 38 [2018-06-22 01:43:44,998 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:44,998 INFO ]: Finished difference Result 167 states and 192 transitions. [2018-06-22 01:43:44,998 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-06-22 01:43:44,998 INFO ]: Start accepts. Automaton has 30 states. Word has length 85 [2018-06-22 01:43:44,998 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:44,999 INFO ]: With dead ends: 167 [2018-06-22 01:43:44,999 INFO ]: Without dead ends: 167 [2018-06-22 01:43:45,001 INFO ]: 0 DeclaredPredicates, 158 GetRequests, 81 SyntacticMatches, 7 SemanticMatches, 70 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1175 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=370, Invalid=4742, Unknown=0, NotChecked=0, Total=5112 [2018-06-22 01:43:45,001 INFO ]: Start minimizeSevpa. Operand 167 states. [2018-06-22 01:43:45,006 INFO ]: Finished minimizeSevpa. Reduced states from 167 to 155. [2018-06-22 01:43:45,007 INFO ]: Start removeUnreachable. Operand 155 states. [2018-06-22 01:43:45,008 INFO ]: Finished removeUnreachable. Reduced from 155 states to 155 states and 180 transitions. [2018-06-22 01:43:45,008 INFO ]: Start accepts. Automaton has 155 states and 180 transitions. Word has length 85 [2018-06-22 01:43:45,008 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:45,008 INFO ]: Abstraction has 155 states and 180 transitions. [2018-06-22 01:43:45,008 INFO ]: Interpolant automaton has 30 states. [2018-06-22 01:43:45,008 INFO ]: Start isEmpty. Operand 155 states and 180 transitions. [2018-06-22 01:43:45,009 INFO ]: Finished isEmpty. Found accepting run of length 87 [2018-06-22 01:43:45,009 INFO ]: Found error trace [2018-06-22 01:43:45,009 INFO ]: trace histogram [22, 8, 8, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:45,009 INFO ]: === Iteration 28 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:45,009 INFO ]: Analyzing trace with hash 1519679630, now seen corresponding path program 18 times [2018-06-22 01:43:45,009 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:45,009 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:45,010 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:45,010 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:45,010 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:45,029 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:45,436 INFO ]: Checked inductivity of 588 backedges. 263 proven. 88 refuted. 0 times theorem prover too weak. 237 trivial. 0 not checked. [2018-06-22 01:43:45,436 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:45,436 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) Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:43:45,442 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:43:45,509 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) [2018-06-22 01:43:45,509 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:45,513 INFO ]: Computing forward predicates... [2018-06-22 01:43:45,662 INFO ]: Checked inductivity of 588 backedges. 276 proven. 75 refuted. 0 times theorem prover too weak. 237 trivial. 0 not checked. [2018-06-22 01:43:45,682 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:45,682 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 30 [2018-06-22 01:43:45,682 INFO ]: Interpolant automaton has 30 states [2018-06-22 01:43:45,682 INFO ]: Constructing interpolant automaton starting with 30 interpolants. [2018-06-22 01:43:45,682 INFO ]: CoverageRelationStatistics Valid=147, Invalid=723, Unknown=0, NotChecked=0, Total=870 [2018-06-22 01:43:45,683 INFO ]: Start difference. First operand 155 states and 180 transitions. Second operand 30 states. [2018-06-22 01:43:46,544 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:46,544 INFO ]: Finished difference Result 225 states and 256 transitions. [2018-06-22 01:43:46,544 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-06-22 01:43:46,544 INFO ]: Start accepts. Automaton has 30 states. Word has length 86 [2018-06-22 01:43:46,544 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:46,545 INFO ]: With dead ends: 225 [2018-06-22 01:43:46,545 INFO ]: Without dead ends: 206 [2018-06-22 01:43:46,546 INFO ]: 0 DeclaredPredicates, 137 GetRequests, 77 SyntacticMatches, 0 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 943 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=718, Invalid=3064, Unknown=0, NotChecked=0, Total=3782 [2018-06-22 01:43:46,546 INFO ]: Start minimizeSevpa. Operand 206 states. [2018-06-22 01:43:46,553 INFO ]: Finished minimizeSevpa. Reduced states from 206 to 166. [2018-06-22 01:43:46,553 INFO ]: Start removeUnreachable. Operand 166 states. [2018-06-22 01:43:46,554 INFO ]: Finished removeUnreachable. Reduced from 166 states to 166 states and 192 transitions. [2018-06-22 01:43:46,554 INFO ]: Start accepts. Automaton has 166 states and 192 transitions. Word has length 86 [2018-06-22 01:43:46,554 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:46,554 INFO ]: Abstraction has 166 states and 192 transitions. [2018-06-22 01:43:46,554 INFO ]: Interpolant automaton has 30 states. [2018-06-22 01:43:46,554 INFO ]: Start isEmpty. Operand 166 states and 192 transitions. [2018-06-22 01:43:46,555 INFO ]: Finished isEmpty. Found accepting run of length 100 [2018-06-22 01:43:46,555 INFO ]: Found error trace [2018-06-22 01:43:46,555 INFO ]: trace histogram [27, 9, 9, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:46,556 INFO ]: === Iteration 29 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:46,556 INFO ]: Analyzing trace with hash 2018407090, now seen corresponding path program 19 times [2018-06-22 01:43:46,556 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:46,556 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:46,556 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:46,556 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:46,556 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:46,579 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:46,901 INFO ]: Checked inductivity of 831 backedges. 348 proven. 95 refuted. 0 times theorem prover too weak. 388 trivial. 0 not checked. [2018-06-22 01:43:46,901 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:46,901 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 01:43:46,907 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:47,007 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:47,013 INFO ]: Computing forward predicates... [2018-06-22 01:43:47,381 INFO ]: Checked inductivity of 831 backedges. 359 proven. 84 refuted. 0 times theorem prover too weak. 388 trivial. 0 not checked. [2018-06-22 01:43:47,400 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:47,400 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 31 [2018-06-22 01:43:47,400 INFO ]: Interpolant automaton has 31 states [2018-06-22 01:43:47,400 INFO ]: Constructing interpolant automaton starting with 31 interpolants. [2018-06-22 01:43:47,400 INFO ]: CoverageRelationStatistics Valid=149, Invalid=781, Unknown=0, NotChecked=0, Total=930 [2018-06-22 01:43:47,401 INFO ]: Start difference. First operand 166 states and 192 transitions. Second operand 31 states. [2018-06-22 01:43:48,038 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:48,038 INFO ]: Finished difference Result 169 states and 195 transitions. [2018-06-22 01:43:48,038 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-06-22 01:43:48,038 INFO ]: Start accepts. Automaton has 31 states. Word has length 99 [2018-06-22 01:43:48,039 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:48,039 INFO ]: With dead ends: 169 [2018-06-22 01:43:48,039 INFO ]: Without dead ends: 169 [2018-06-22 01:43:48,040 INFO ]: 0 DeclaredPredicates, 141 GetRequests, 89 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 506 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=536, Invalid=2326, Unknown=0, NotChecked=0, Total=2862 [2018-06-22 01:43:48,041 INFO ]: Start minimizeSevpa. Operand 169 states. [2018-06-22 01:43:48,048 INFO ]: Finished minimizeSevpa. Reduced states from 169 to 169. [2018-06-22 01:43:48,048 INFO ]: Start removeUnreachable. Operand 169 states. [2018-06-22 01:43:48,049 INFO ]: Finished removeUnreachable. Reduced from 169 states to 169 states and 195 transitions. [2018-06-22 01:43:48,049 INFO ]: Start accepts. Automaton has 169 states and 195 transitions. Word has length 99 [2018-06-22 01:43:48,049 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:48,049 INFO ]: Abstraction has 169 states and 195 transitions. [2018-06-22 01:43:48,049 INFO ]: Interpolant automaton has 31 states. [2018-06-22 01:43:48,049 INFO ]: Start isEmpty. Operand 169 states and 195 transitions. [2018-06-22 01:43:48,050 INFO ]: Finished isEmpty. Found accepting run of length 101 [2018-06-22 01:43:48,051 INFO ]: Found error trace [2018-06-22 01:43:48,051 INFO ]: trace histogram [28, 9, 9, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:48,051 INFO ]: === Iteration 30 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:48,051 INFO ]: Analyzing trace with hash -1853273348, now seen corresponding path program 20 times [2018-06-22 01:43:48,051 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:48,051 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:48,051 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:48,051 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:43:48,051 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:48,080 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:48,989 INFO ]: Checked inductivity of 866 backedges. 16 proven. 673 refuted. 0 times theorem prover too weak. 177 trivial. 0 not checked. [2018-06-22 01:43:48,989 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:48,989 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 01:43:48,995 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:43:49,075 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:43:49,138 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:49,143 INFO ]: Computing forward predicates... [2018-06-22 01:43:49,444 INFO ]: Checked inductivity of 866 backedges. 16 proven. 673 refuted. 0 times theorem prover too weak. 177 trivial. 0 not checked. [2018-06-22 01:43:49,463 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:49,463 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23] total 33 [2018-06-22 01:43:49,464 INFO ]: Interpolant automaton has 33 states [2018-06-22 01:43:49,464 INFO ]: Constructing interpolant automaton starting with 33 interpolants. [2018-06-22 01:43:49,464 INFO ]: CoverageRelationStatistics Valid=73, Invalid=983, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 01:43:49,464 INFO ]: Start difference. First operand 169 states and 195 transitions. Second operand 33 states. [2018-06-22 01:43:50,517 WARN ]: Spent 179.00 ms on a formula simplification that was a NOOP. DAG size: 43 [2018-06-22 01:43:51,446 WARN ]: Spent 254.00 ms on a formula simplification that was a NOOP. DAG size: 41 [2018-06-22 01:43:51,860 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:51,860 INFO ]: Finished difference Result 197 states and 225 transitions. [2018-06-22 01:43:51,863 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2018-06-22 01:43:51,863 INFO ]: Start accepts. Automaton has 33 states. Word has length 100 [2018-06-22 01:43:51,863 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:51,864 INFO ]: With dead ends: 197 [2018-06-22 01:43:51,864 INFO ]: Without dead ends: 197 [2018-06-22 01:43:51,867 INFO ]: 0 DeclaredPredicates, 182 GetRequests, 96 SyntacticMatches, 8 SemanticMatches, 78 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1475 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=423, Invalid=5897, Unknown=0, NotChecked=0, Total=6320 [2018-06-22 01:43:51,867 INFO ]: Start minimizeSevpa. Operand 197 states. [2018-06-22 01:43:51,874 INFO ]: Finished minimizeSevpa. Reduced states from 197 to 183. [2018-06-22 01:43:51,874 INFO ]: Start removeUnreachable. Operand 183 states. [2018-06-22 01:43:51,875 INFO ]: Finished removeUnreachable. Reduced from 183 states to 183 states and 211 transitions. [2018-06-22 01:43:51,875 INFO ]: Start accepts. Automaton has 183 states and 211 transitions. Word has length 100 [2018-06-22 01:43:51,875 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:51,875 INFO ]: Abstraction has 183 states and 211 transitions. [2018-06-22 01:43:51,875 INFO ]: Interpolant automaton has 33 states. [2018-06-22 01:43:51,875 INFO ]: Start isEmpty. Operand 183 states and 211 transitions. [2018-06-22 01:43:51,876 INFO ]: Finished isEmpty. Found accepting run of length 102 [2018-06-22 01:43:51,876 INFO ]: Found error trace [2018-06-22 01:43:51,876 INFO ]: trace histogram [29, 9, 9, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:51,876 INFO ]: === Iteration 31 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:51,876 INFO ]: Analyzing trace with hash -1616282638, now seen corresponding path program 21 times [2018-06-22 01:43:51,877 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:51,877 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:51,877 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:51,877 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:51,877 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:51,899 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:52,246 INFO ]: Checked inductivity of 902 backedges. 401 proven. 113 refuted. 0 times theorem prover too weak. 388 trivial. 0 not checked. [2018-06-22 01:43:52,247 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:52,247 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 01:43:52,255 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:43:52,332 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2018-06-22 01:43:52,332 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:52,336 INFO ]: Computing forward predicates... [2018-06-22 01:43:52,709 INFO ]: Checked inductivity of 902 backedges. 416 proven. 98 refuted. 0 times theorem prover too weak. 388 trivial. 0 not checked. [2018-06-22 01:43:52,730 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:52,730 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 33 [2018-06-22 01:43:52,730 INFO ]: Interpolant automaton has 33 states [2018-06-22 01:43:52,730 INFO ]: Constructing interpolant automaton starting with 33 interpolants. [2018-06-22 01:43:52,730 INFO ]: CoverageRelationStatistics Valid=181, Invalid=875, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 01:43:52,730 INFO ]: Start difference. First operand 183 states and 211 transitions. Second operand 33 states. [2018-06-22 01:43:53,603 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:53,603 INFO ]: Finished difference Result 270 states and 304 transitions. [2018-06-22 01:43:53,603 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 50 states. [2018-06-22 01:43:53,603 INFO ]: Start accepts. Automaton has 33 states. Word has length 101 [2018-06-22 01:43:53,604 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:53,605 INFO ]: With dead ends: 270 [2018-06-22 01:43:53,605 INFO ]: Without dead ends: 249 [2018-06-22 01:43:53,606 INFO ]: 0 DeclaredPredicates, 158 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1211 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=901, Invalid=3791, Unknown=0, NotChecked=0, Total=4692 [2018-06-22 01:43:53,606 INFO ]: Start minimizeSevpa. Operand 249 states. [2018-06-22 01:43:53,614 INFO ]: Finished minimizeSevpa. Reduced states from 249 to 195. [2018-06-22 01:43:53,614 INFO ]: Start removeUnreachable. Operand 195 states. [2018-06-22 01:43:53,615 INFO ]: Finished removeUnreachable. Reduced from 195 states to 195 states and 224 transitions. [2018-06-22 01:43:53,615 INFO ]: Start accepts. Automaton has 195 states and 224 transitions. Word has length 101 [2018-06-22 01:43:53,615 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:53,615 INFO ]: Abstraction has 195 states and 224 transitions. [2018-06-22 01:43:53,615 INFO ]: Interpolant automaton has 33 states. [2018-06-22 01:43:53,615 INFO ]: Start isEmpty. Operand 195 states and 224 transitions. [2018-06-22 01:43:53,618 INFO ]: Finished isEmpty. Found accepting run of length 116 [2018-06-22 01:43:53,618 INFO ]: Found error trace [2018-06-22 01:43:53,618 INFO ]: trace histogram [35, 10, 10, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:53,619 INFO ]: === Iteration 32 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:53,619 INFO ]: Analyzing trace with hash -1020992956, now seen corresponding path program 22 times [2018-06-22 01:43:53,619 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:53,619 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:53,619 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:53,619 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:53,619 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:53,644 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:54,214 INFO ]: Checked inductivity of 1243 backedges. 513 proven. 121 refuted. 0 times theorem prover too weak. 609 trivial. 0 not checked. [2018-06-22 01:43:54,215 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:54,215 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 01:43:54,221 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:43:54,315 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:43:54,315 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:54,320 INFO ]: Computing forward predicates... [2018-06-22 01:43:55,204 INFO ]: Checked inductivity of 1243 backedges. 526 proven. 108 refuted. 0 times theorem prover too weak. 609 trivial. 0 not checked. [2018-06-22 01:43:55,224 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:55,224 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 34 [2018-06-22 01:43:55,224 INFO ]: Interpolant automaton has 34 states [2018-06-22 01:43:55,224 INFO ]: Constructing interpolant automaton starting with 34 interpolants. [2018-06-22 01:43:55,225 INFO ]: CoverageRelationStatistics Valid=183, Invalid=939, Unknown=0, NotChecked=0, Total=1122 [2018-06-22 01:43:55,225 INFO ]: Start difference. First operand 195 states and 224 transitions. Second operand 34 states. [2018-06-22 01:43:55,786 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:55,786 INFO ]: Finished difference Result 198 states and 227 transitions. [2018-06-22 01:43:55,786 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2018-06-22 01:43:55,786 INFO ]: Start accepts. Automaton has 34 states. Word has length 115 [2018-06-22 01:43:55,786 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:55,787 INFO ]: With dead ends: 198 [2018-06-22 01:43:55,787 INFO ]: Without dead ends: 198 [2018-06-22 01:43:55,788 INFO ]: 0 DeclaredPredicates, 162 GetRequests, 104 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 640 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=670, Invalid=2870, Unknown=0, NotChecked=0, Total=3540 [2018-06-22 01:43:55,788 INFO ]: Start minimizeSevpa. Operand 198 states. [2018-06-22 01:43:55,793 INFO ]: Finished minimizeSevpa. Reduced states from 198 to 198. [2018-06-22 01:43:55,794 INFO ]: Start removeUnreachable. Operand 198 states. [2018-06-22 01:43:55,796 INFO ]: Finished removeUnreachable. Reduced from 198 states to 198 states and 227 transitions. [2018-06-22 01:43:55,796 INFO ]: Start accepts. Automaton has 198 states and 227 transitions. Word has length 115 [2018-06-22 01:43:55,796 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:55,796 INFO ]: Abstraction has 198 states and 227 transitions. [2018-06-22 01:43:55,796 INFO ]: Interpolant automaton has 34 states. [2018-06-22 01:43:55,796 INFO ]: Start isEmpty. Operand 198 states and 227 transitions. [2018-06-22 01:43:55,798 INFO ]: Finished isEmpty. Found accepting run of length 117 [2018-06-22 01:43:55,798 INFO ]: Found error trace [2018-06-22 01:43:55,798 INFO ]: trace histogram [36, 10, 10, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:55,798 INFO ]: === Iteration 33 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:55,798 INFO ]: Analyzing trace with hash -1585394262, now seen corresponding path program 23 times [2018-06-22 01:43:55,798 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:55,798 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:55,799 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:55,799 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:55,799 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:55,828 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:56,579 INFO ]: Checked inductivity of 1287 backedges. 18 proven. 1031 refuted. 0 times theorem prover too weak. 238 trivial. 0 not checked. [2018-06-22 01:43:56,579 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:43:56,579 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 01:43:56,585 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:43:56,690 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2018-06-22 01:43:56,690 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:43:56,695 INFO ]: Computing forward predicates... [2018-06-22 01:43:57,217 INFO ]: Checked inductivity of 1287 backedges. 18 proven. 1031 refuted. 0 times theorem prover too weak. 238 trivial. 0 not checked. [2018-06-22 01:43:57,245 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:43:57,246 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 36 [2018-06-22 01:43:57,246 INFO ]: Interpolant automaton has 36 states [2018-06-22 01:43:57,246 INFO ]: Constructing interpolant automaton starting with 36 interpolants. [2018-06-22 01:43:57,246 INFO ]: CoverageRelationStatistics Valid=80, Invalid=1180, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 01:43:57,246 INFO ]: Start difference. First operand 198 states and 227 transitions. Second operand 36 states. [2018-06-22 01:43:58,440 WARN ]: Spent 124.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 01:43:59,881 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:43:59,881 INFO ]: Finished difference Result 229 states and 260 transitions. [2018-06-22 01:43:59,881 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-06-22 01:43:59,881 INFO ]: Start accepts. Automaton has 36 states. Word has length 116 [2018-06-22 01:43:59,881 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:43:59,882 INFO ]: With dead ends: 229 [2018-06-22 01:43:59,882 INFO ]: Without dead ends: 229 [2018-06-22 01:43:59,883 INFO ]: 0 DeclaredPredicates, 207 GetRequests, 112 SyntacticMatches, 9 SemanticMatches, 86 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1809 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=478, Invalid=7178, Unknown=0, NotChecked=0, Total=7656 [2018-06-22 01:43:59,883 INFO ]: Start minimizeSevpa. Operand 229 states. [2018-06-22 01:43:59,889 INFO ]: Finished minimizeSevpa. Reduced states from 229 to 213. [2018-06-22 01:43:59,889 INFO ]: Start removeUnreachable. Operand 213 states. [2018-06-22 01:43:59,891 INFO ]: Finished removeUnreachable. Reduced from 213 states to 213 states and 244 transitions. [2018-06-22 01:43:59,891 INFO ]: Start accepts. Automaton has 213 states and 244 transitions. Word has length 116 [2018-06-22 01:43:59,891 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:43:59,891 INFO ]: Abstraction has 213 states and 244 transitions. [2018-06-22 01:43:59,891 INFO ]: Interpolant automaton has 36 states. [2018-06-22 01:43:59,891 INFO ]: Start isEmpty. Operand 213 states and 244 transitions. [2018-06-22 01:43:59,892 INFO ]: Finished isEmpty. Found accepting run of length 118 [2018-06-22 01:43:59,892 INFO ]: Found error trace [2018-06-22 01:43:59,892 INFO ]: trace histogram [37, 10, 10, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1] [2018-06-22 01:43:59,892 INFO ]: === Iteration 34 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:43:59,893 INFO ]: Analyzing trace with hash -1901965564, now seen corresponding path program 24 times [2018-06-22 01:43:59,893 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:43:59,893 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:43:59,893 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:59,893 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:43:59,893 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:43:59,923 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:44:00,803 INFO ]: Checked inductivity of 1332 backedges. 582 proven. 141 refuted. 0 times theorem prover too weak. 609 trivial. 0 not checked. [2018-06-22 01:44:00,803 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:44:00,803 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 01:44:00,809 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:44:00,915 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 12 check-sat command(s) [2018-06-22 01:44:00,915 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:44:00,920 INFO ]: Computing forward predicates... [2018-06-22 01:44:01,248 INFO ]: Checked inductivity of 1332 backedges. 599 proven. 124 refuted. 0 times theorem prover too weak. 609 trivial. 0 not checked. [2018-06-22 01:44:01,269 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:44:01,286 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 36 [2018-06-22 01:44:01,286 INFO ]: Interpolant automaton has 36 states [2018-06-22 01:44:01,286 INFO ]: Constructing interpolant automaton starting with 36 interpolants. [2018-06-22 01:44:01,286 INFO ]: CoverageRelationStatistics Valid=219, Invalid=1041, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 01:44:01,287 INFO ]: Start difference. First operand 213 states and 244 transitions. Second operand 36 states. [2018-06-22 01:44:02,426 WARN ]: Spent 147.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-22 01:44:03,033 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:44:03,033 INFO ]: Finished difference Result 319 states and 356 transitions. [2018-06-22 01:44:03,033 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2018-06-22 01:44:03,033 INFO ]: Start accepts. Automaton has 36 states. Word has length 117 [2018-06-22 01:44:03,033 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:44:03,035 INFO ]: With dead ends: 319 [2018-06-22 01:44:03,035 INFO ]: Without dead ends: 296 [2018-06-22 01:44:03,035 INFO ]: 0 DeclaredPredicates, 180 GetRequests, 106 SyntacticMatches, 0 SemanticMatches, 74 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1512 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=1106, Invalid=4594, Unknown=0, NotChecked=0, Total=5700 [2018-06-22 01:44:03,036 INFO ]: Start minimizeSevpa. Operand 296 states. [2018-06-22 01:44:03,047 INFO ]: Finished minimizeSevpa. Reduced states from 296 to 226. [2018-06-22 01:44:03,047 INFO ]: Start removeUnreachable. Operand 226 states. [2018-06-22 01:44:03,048 INFO ]: Finished removeUnreachable. Reduced from 226 states to 226 states and 258 transitions. [2018-06-22 01:44:03,048 INFO ]: Start accepts. Automaton has 226 states and 258 transitions. Word has length 117 [2018-06-22 01:44:03,048 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:44:03,048 INFO ]: Abstraction has 226 states and 258 transitions. [2018-06-22 01:44:03,048 INFO ]: Interpolant automaton has 36 states. [2018-06-22 01:44:03,048 INFO ]: Start isEmpty. Operand 226 states and 258 transitions. [2018-06-22 01:44:03,049 INFO ]: Finished isEmpty. Found accepting run of length 133 [2018-06-22 01:44:03,049 INFO ]: Found error trace [2018-06-22 01:44:03,050 INFO ]: trace histogram [44, 11, 11, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1] [2018-06-22 01:44:03,050 INFO ]: === Iteration 35 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:44:03,050 INFO ]: Analyzing trace with hash -432758952, now seen corresponding path program 25 times [2018-06-22 01:44:03,050 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:44:03,050 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:44:03,050 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:44:03,050 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:44:03,050 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:44:03,083 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:44:03,482 INFO ]: Checked inductivity of 1796 backedges. 725 proven. 150 refuted. 0 times theorem prover too weak. 921 trivial. 0 not checked. [2018-06-22 01:44:03,482 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:44:03,482 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 01:44:03,488 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:44:03,602 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:44:03,608 INFO ]: Computing forward predicates... [2018-06-22 01:44:05,050 INFO ]: Checked inductivity of 1796 backedges. 740 proven. 135 refuted. 0 times theorem prover too weak. 921 trivial. 0 not checked. [2018-06-22 01:44:05,069 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:44:05,069 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 37 [2018-06-22 01:44:05,069 INFO ]: Interpolant automaton has 37 states [2018-06-22 01:44:05,069 INFO ]: Constructing interpolant automaton starting with 37 interpolants. [2018-06-22 01:44:05,069 INFO ]: CoverageRelationStatistics Valid=221, Invalid=1111, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 01:44:05,069 INFO ]: Start difference. First operand 226 states and 258 transitions. Second operand 37 states. [2018-06-22 01:44:05,814 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:44:05,814 INFO ]: Finished difference Result 229 states and 261 transitions. [2018-06-22 01:44:05,814 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2018-06-22 01:44:05,814 INFO ]: Start accepts. Automaton has 37 states. Word has length 132 [2018-06-22 01:44:05,815 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:44:05,816 INFO ]: With dead ends: 229 [2018-06-22 01:44:05,816 INFO ]: Without dead ends: 229 [2018-06-22 01:44:05,816 INFO ]: 0 DeclaredPredicates, 184 GetRequests, 120 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 789 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=820, Invalid=3470, Unknown=0, NotChecked=0, Total=4290 [2018-06-22 01:44:05,816 INFO ]: Start minimizeSevpa. Operand 229 states. [2018-06-22 01:44:05,823 INFO ]: Finished minimizeSevpa. Reduced states from 229 to 229. [2018-06-22 01:44:05,823 INFO ]: Start removeUnreachable. Operand 229 states. [2018-06-22 01:44:05,824 INFO ]: Finished removeUnreachable. Reduced from 229 states to 229 states and 261 transitions. [2018-06-22 01:44:05,824 INFO ]: Start accepts. Automaton has 229 states and 261 transitions. Word has length 132 [2018-06-22 01:44:05,825 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:44:05,825 INFO ]: Abstraction has 229 states and 261 transitions. [2018-06-22 01:44:05,825 INFO ]: Interpolant automaton has 37 states. [2018-06-22 01:44:05,825 INFO ]: Start isEmpty. Operand 229 states and 261 transitions. [2018-06-22 01:44:05,826 INFO ]: Finished isEmpty. Found accepting run of length 134 [2018-06-22 01:44:05,826 INFO ]: Found error trace [2018-06-22 01:44:05,826 INFO ]: trace histogram [45, 11, 11, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1] [2018-06-22 01:44:05,826 INFO ]: === Iteration 36 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:44:05,826 INFO ]: Analyzing trace with hash -530009322, now seen corresponding path program 26 times [2018-06-22 01:44:05,826 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:44:05,826 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:44:05,826 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:44:05,826 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:44:05,826 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:44:05,860 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:44:06,559 INFO ]: Checked inductivity of 1850 backedges. 20 proven. 1519 refuted. 0 times theorem prover too weak. 311 trivial. 0 not checked. [2018-06-22 01:44:06,560 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:44:06,560 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 01:44:06,565 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:44:06,684 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:44:06,684 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:44:06,691 INFO ]: Computing forward predicates... [2018-06-22 01:44:07,813 INFO ]: Checked inductivity of 1850 backedges. 20 proven. 1519 refuted. 0 times theorem prover too weak. 311 trivial. 0 not checked. [2018-06-22 01:44:07,834 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:44:07,834 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 27] total 39 [2018-06-22 01:44:07,835 INFO ]: Interpolant automaton has 39 states [2018-06-22 01:44:07,835 INFO ]: Constructing interpolant automaton starting with 39 interpolants. [2018-06-22 01:44:07,835 INFO ]: CoverageRelationStatistics Valid=87, Invalid=1395, Unknown=0, NotChecked=0, Total=1482 [2018-06-22 01:44:07,835 INFO ]: Start difference. First operand 229 states and 261 transitions. Second operand 39 states. [2018-06-22 01:44:10,171 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:44:10,171 INFO ]: Finished difference Result 263 states and 297 transitions. [2018-06-22 01:44:10,171 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 62 states. [2018-06-22 01:44:10,171 INFO ]: Start accepts. Automaton has 39 states. Word has length 133 [2018-06-22 01:44:10,171 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:44:10,172 INFO ]: With dead ends: 263 [2018-06-22 01:44:10,172 INFO ]: Without dead ends: 263 [2018-06-22 01:44:10,173 INFO ]: 0 DeclaredPredicates, 233 GetRequests, 129 SyntacticMatches, 10 SemanticMatches, 94 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2177 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=535, Invalid=8585, Unknown=0, NotChecked=0, Total=9120 [2018-06-22 01:44:10,173 INFO ]: Start minimizeSevpa. Operand 263 states. [2018-06-22 01:44:10,179 INFO ]: Finished minimizeSevpa. Reduced states from 263 to 245. [2018-06-22 01:44:10,180 INFO ]: Start removeUnreachable. Operand 245 states. [2018-06-22 01:44:10,181 INFO ]: Finished removeUnreachable. Reduced from 245 states to 245 states and 279 transitions. [2018-06-22 01:44:10,181 INFO ]: Start accepts. Automaton has 245 states and 279 transitions. Word has length 133 [2018-06-22 01:44:10,181 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:44:10,181 INFO ]: Abstraction has 245 states and 279 transitions. [2018-06-22 01:44:10,181 INFO ]: Interpolant automaton has 39 states. [2018-06-22 01:44:10,181 INFO ]: Start isEmpty. Operand 245 states and 279 transitions. [2018-06-22 01:44:10,182 INFO ]: Finished isEmpty. Found accepting run of length 135 [2018-06-22 01:44:10,182 INFO ]: Found error trace [2018-06-22 01:44:10,182 INFO ]: trace histogram [46, 11, 11, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1] [2018-06-22 01:44:10,182 INFO ]: === Iteration 37 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:44:10,182 INFO ]: Analyzing trace with hash 750196504, now seen corresponding path program 27 times [2018-06-22 01:44:10,182 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:44:10,182 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:44:10,183 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:44:10,183 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:44:10,183 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:44:10,208 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:44:10,937 INFO ]: Checked inductivity of 1905 backedges. 812 proven. 172 refuted. 0 times theorem prover too weak. 921 trivial. 0 not checked. [2018-06-22 01:44:10,937 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:44:10,937 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 01:44:10,942 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:44:11,031 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2018-06-22 01:44:11,031 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:44:11,035 INFO ]: Computing forward predicates... [2018-06-22 01:44:11,263 INFO ]: Checked inductivity of 1905 backedges. 831 proven. 153 refuted. 0 times theorem prover too weak. 921 trivial. 0 not checked. [2018-06-22 01:44:11,285 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:44:11,285 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 26] total 39 [2018-06-22 01:44:11,285 INFO ]: Interpolant automaton has 39 states [2018-06-22 01:44:11,286 INFO ]: Constructing interpolant automaton starting with 39 interpolants. [2018-06-22 01:44:11,286 INFO ]: CoverageRelationStatistics Valid=261, Invalid=1221, Unknown=0, NotChecked=0, Total=1482 [2018-06-22 01:44:11,286 INFO ]: Start difference. First operand 245 states and 279 transitions. Second operand 39 states. Received shutdown request... [2018-06-22 01:44:12,318 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-06-22 01:44:12,319 WARN ]: Verification canceled [2018-06-22 01:44:12,325 WARN ]: Timeout [2018-06-22 01:44:12,326 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 01:44:12 BoogieIcfgContainer [2018-06-22 01:44:12,326 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 01:44:12,327 INFO ]: Toolchain (without parser) took 59506.01 ms. Allocated memory was 302.5 MB in the beginning and 849.9 MB in the end (delta: 547.4 MB). Free memory was 258.9 MB in the beginning and 290.7 MB in the end (delta: -31.8 MB). Peak memory consumption was 515.6 MB. Max. memory is 3.6 GB. [2018-06-22 01:44:12,327 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 302.5 MB. Free memory is still 268.0 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 01:44:12,327 INFO ]: ChcToBoogie took 92.09 ms. Allocated memory is still 302.5 MB. Free memory was 257.9 MB in the beginning and 255.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:44:12,328 INFO ]: Boogie Preprocessor took 37.78 ms. Allocated memory is still 302.5 MB. Free memory was 255.9 MB in the beginning and 254.9 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-22 01:44:12,328 INFO ]: RCFGBuilder took 428.18 ms. Allocated memory is still 302.5 MB. Free memory was 254.9 MB in the beginning and 245.9 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:44:12,328 INFO ]: TraceAbstraction took 58935.87 ms. Allocated memory was 302.5 MB in the beginning and 849.9 MB in the end (delta: 547.4 MB). Free memory was 244.9 MB in the beginning and 290.7 MB in the end (delta: -45.8 MB). Peak memory consumption was 501.6 MB. Max. memory is 3.6 GB. [2018-06-22 01:44:12,330 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 302.5 MB. Free memory is still 268.0 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 92.09 ms. Allocated memory is still 302.5 MB. Free memory was 257.9 MB in the beginning and 255.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 37.78 ms. Allocated memory is still 302.5 MB. Free memory was 255.9 MB in the beginning and 254.9 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 428.18 ms. Allocated memory is still 302.5 MB. Free memory was 254.9 MB in the beginning and 245.9 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 58935.87 ms. Allocated memory was 302.5 MB in the beginning and 849.9 MB in the end (delta: 547.4 MB). Free memory was 244.9 MB in the beginning and 290.7 MB in the end (delta: -45.8 MB). Peak memory consumption was 501.6 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was constructing difference of abstraction (245states) and interpolant automaton (currently 60 states, 39 states before enhancement), while ReachableStatesComputation was computing reachable states (358 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 16 locations, 1 error locations. TIMEOUT Result, 58.8s OverallTime, 37 OverallIterations, 46 TraceHistogramMax, 29.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 783 SDtfs, 2319 SDslu, 7135 SDs, 0 SdLazy, 16133 SolverSat, 1838 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 10.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 3565 GetRequests, 1953 SyntacticMatches, 55 SemanticMatches, 1557 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20349 ImplicationChecksByTransitivity, 37.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=245occurred in iteration=36, 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.3s AutomataMinimizationTime, 36 MinimizatonAttempts, 400 StatesRemovedByMinimization, 26 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.4s SsaConstructionTime, 2.2s SatisfiabilityAnalysisTime, 24.2s InterpolantComputationTime, 4321 NumberOfCodeBlocks, 4260 NumberOfCodeBlocksAsserted, 160 NumberOfCheckSat, 4252 ConstructedInterpolants, 0 QuantifiedInterpolants, 1193800 SizeOfPredicates, 271 NumberOfNonLiveVariables, 13653 ConjunctsInSsa, 1477 ConjunctsInUnsatCore, 69 InterpolantComputations, 6 PerfectInterpolantSequences, 21336/31945 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/enc-rev_append.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_01-44-12-343.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/enc-rev_append.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_01-44-12-343.csv Completed graceful shutdown