java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/simple_nest.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:36:40,183 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:36:40,187 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:36:40,199 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:36:40,199 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:36:40,201 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:36:40,202 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:36:40,207 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:36:40,209 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:36:40,210 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:36:40,213 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:36:40,213 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:36:40,214 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:36:40,215 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:36:40,218 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:36:40,219 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:36:40,223 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:36:40,225 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:36:40,226 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:36:40,227 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:36:40,228 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:36:40,230 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:36:40,231 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:36:40,231 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:36:40,232 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:36:40,233 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:36:40,233 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:36:40,234 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:36:40,235 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:36:40,235 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:36:40,236 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:36:40,237 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:36:40,237 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:36:40,238 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:36:40,238 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:36:40,239 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 15:36:40,251 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:36:40,252 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:36:40,252 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:36:40,252 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:36:40,253 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:36:40,253 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:36:40,254 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:36:40,254 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:36:40,254 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:36:40,254 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:36:40,254 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:36:40,254 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:36:40,255 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:36:40,255 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:36:40,255 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:36:40,255 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:36:40,255 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:36:40,256 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:36:40,256 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:36:40,257 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:36:40,257 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:36:40,305 INFO ]: Repository-Root is: /tmp [2018-06-22 15:36:40,321 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:36:40,325 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:36:40,327 INFO ]: Initializing SmtParser... [2018-06-22 15:36:40,327 INFO ]: SmtParser initialized [2018-06-22 15:36:40,328 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/simple_nest.c.smt2 [2018-06-22 15:36:40,329 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 15:36:40,418 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/simple_nest.c.smt2 unknown [2018-06-22 15:36:40,683 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/simple_nest.c.smt2 [2018-06-22 15:36:40,688 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:36:40,694 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:36:40,694 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:36:40,694 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:36:40,695 INFO ]: ChcToBoogie initialized [2018-06-22 15:36:40,701 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:36:40" (1/1) ... [2018-06-22 15:36:40,743 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:36:40 Unit [2018-06-22 15:36:40,743 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:36:40,744 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:36:40,744 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:36:40,744 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:36:40,765 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:36:40" (1/1) ... [2018-06-22 15:36:40,765 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:36:40" (1/1) ... [2018-06-22 15:36:40,770 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:36:40" (1/1) ... [2018-06-22 15:36:40,770 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:36:40" (1/1) ... [2018-06-22 15:36:40,773 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:36:40" (1/1) ... [2018-06-22 15:36:40,774 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:36:40" (1/1) ... [2018-06-22 15:36:40,775 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:36:40" (1/1) ... [2018-06-22 15:36:40,776 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:36:40,777 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:36:40,777 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:36:40,777 INFO ]: RCFGBuilder initialized [2018-06-22 15:36:40,778 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:36:40" (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 15:36:40,800 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:36:40,800 INFO ]: Found specification of procedure False [2018-06-22 15:36:40,800 INFO ]: Found implementation of procedure False [2018-06-22 15:36:40,800 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:36:40,800 INFO ]: Found specification of procedure state [2018-06-22 15:36:40,800 INFO ]: Found implementation of procedure state [2018-06-22 15:36:40,800 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:36:40,800 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:36:40,801 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 15:36:41,031 INFO ]: Using library mode [2018-06-22 15:36:41,031 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:36:41 BoogieIcfgContainer [2018-06-22 15:36:41,031 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:36:41,032 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:36:41,032 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:36:41,042 INFO ]: TraceAbstraction initialized [2018-06-22 15:36:41,042 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:36:40" (1/3) ... [2018-06-22 15:36:41,043 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@49dd3c07 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:36:41, skipping insertion in model container [2018-06-22 15:36:41,043 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:36:40" (2/3) ... [2018-06-22 15:36:41,043 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@49dd3c07 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:36:41, skipping insertion in model container [2018-06-22 15:36:41,043 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:36:41" (3/3) ... [2018-06-22 15:36:41,045 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:36:41,056 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:36:41,066 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:36:41,099 INFO ]: Using default assertion order modulation [2018-06-22 15:36:41,100 INFO ]: Interprodecural is true [2018-06-22 15:36:41,100 INFO ]: Hoare is false [2018-06-22 15:36:41,100 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:36:41,100 INFO ]: Backedges is TWOTRACK [2018-06-22 15:36:41,100 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:36:41,100 INFO ]: Difference is false [2018-06-22 15:36:41,100 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:36:41,100 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:36:41,115 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:36:41,127 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:36:41,127 INFO ]: Found error trace [2018-06-22 15:36:41,128 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:36:41,128 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:36:41,134 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 15:36:41,136 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:36:41,136 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:36:41,176 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:36:41,176 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:36:41,176 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:36:41,209 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:36:41,290 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:36:41,292 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:36:41,293 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:36:41,294 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:36:41,310 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:36:41,311 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:36:41,313 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:36:41,401 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:36:41,401 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:36:41,402 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:36:41,403 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:36:41,404 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:36:41,413 INFO ]: With dead ends: 13 [2018-06-22 15:36:41,413 INFO ]: Without dead ends: 13 [2018-06-22 15:36:41,415 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:36:41,427 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:36:41,448 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:36:41,449 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:36:41,449 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:36:41,451 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:36:41,451 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:36:41,451 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:36:41,451 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:36:41,451 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:36:41,452 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:36:41,452 INFO ]: Found error trace [2018-06-22 15:36:41,452 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:36:41,452 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:36:41,453 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 15:36:41,453 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:36:41,453 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:36:41,453 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:36:41,454 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:36:41,454 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:36:41,484 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:36:41,678 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:36:41,679 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:36:41,679 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 15:36:41,688 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:36:41,720 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:36:41,726 INFO ]: Computing forward predicates... [2018-06-22 15:36:42,468 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:36:42,502 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:36:42,502 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 15:36:42,503 INFO ]: Interpolant automaton has 9 states [2018-06-22 15:36:42,503 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 15:36:42,503 INFO ]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-22 15:36:42,503 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 15:36:42,852 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:36:42,852 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:36:42,853 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:36:42,853 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 15:36:42,853 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:36:42,854 INFO ]: With dead ends: 15 [2018-06-22 15:36:42,854 INFO ]: Without dead ends: 15 [2018-06-22 15:36:42,855 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:36:42,855 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:36:42,859 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:36:42,859 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:36:42,860 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:36:42,860 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:36:42,860 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:36:42,860 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:36:42,860 INFO ]: Interpolant automaton has 9 states. [2018-06-22 15:36:42,860 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:36:42,860 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:36:42,860 INFO ]: Found error trace [2018-06-22 15:36:42,860 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:36:42,861 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:36:42,861 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 15:36:42,861 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:36:42,861 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:36:42,862 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:36:42,862 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:36:42,862 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:36:42,917 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:36:43,225 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:36:43,225 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:36:43,225 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 15:36:43,234 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:36:43,275 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:36:43,275 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:36:43,278 INFO ]: Computing forward predicates... [2018-06-22 15:36:43,686 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:36:43,745 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:36:43,745 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:36:43,745 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:36:43,745 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:36:43,745 INFO ]: CoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:36:43,746 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:36:44,291 WARN ]: Spent 261.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-06-22 15:36:44,556 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 15 [2018-06-22 15:36:44,581 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:36:44,581 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:36:44,581 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:36:44,581 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:36:44,582 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:36:44,582 INFO ]: With dead ends: 17 [2018-06-22 15:36:44,582 INFO ]: Without dead ends: 17 [2018-06-22 15:36:44,583 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=49, Invalid=133, Unknown=0, NotChecked=0, Total=182 [2018-06-22 15:36:44,583 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:36:44,586 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:36:44,586 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:36:44,587 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:36:44,587 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:36:44,587 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:36:44,587 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:36:44,587 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:36:44,587 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:36:44,588 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:36:44,588 INFO ]: Found error trace [2018-06-22 15:36:44,588 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:36:44,588 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:36:44,588 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 15:36:44,588 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:36:44,588 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:36:44,589 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:36:44,589 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:36:44,589 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:36:44,614 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:36:44,895 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:36:44,895 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:36:44,895 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 15:36:44,903 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:36:44,960 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:36:44,960 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:36:44,964 INFO ]: Computing forward predicates... [2018-06-22 15:36:45,199 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:36:45,231 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:36:45,231 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 12 [2018-06-22 15:36:45,231 INFO ]: Interpolant automaton has 12 states [2018-06-22 15:36:45,231 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 15:36:45,231 INFO ]: CoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:36:45,232 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 12 states. [2018-06-22 15:36:45,511 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:36:45,511 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:36:45,512 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:36:45,512 INFO ]: Start accepts. Automaton has 12 states. Word has length 21 [2018-06-22 15:36:45,512 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:36:45,513 INFO ]: With dead ends: 19 [2018-06-22 15:36:45,513 INFO ]: Without dead ends: 19 [2018-06-22 15:36:45,513 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=67, Invalid=173, Unknown=0, NotChecked=0, Total=240 [2018-06-22 15:36:45,513 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:36:45,516 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:36:45,516 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:36:45,517 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:36:45,517 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:36:45,517 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:36:45,517 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:36:45,517 INFO ]: Interpolant automaton has 12 states. [2018-06-22 15:36:45,517 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:36:45,517 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:36:45,518 INFO ]: Found error trace [2018-06-22 15:36:45,518 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:36:45,518 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:36:45,518 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 15:36:45,518 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:36:45,518 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:36:45,519 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:36:45,519 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:36:45,519 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:36:45,559 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:36:45,909 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:36:45,909 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:36:45,909 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 15:36:45,916 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:36:45,939 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:36:45,939 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:36:45,943 INFO ]: Computing forward predicates... [2018-06-22 15:36:46,675 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:36:46,695 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:36:46,695 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 18 [2018-06-22 15:36:46,696 INFO ]: Interpolant automaton has 18 states [2018-06-22 15:36:46,696 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-22 15:36:46,696 INFO ]: CoverageRelationStatistics Valid=48, Invalid=258, Unknown=0, NotChecked=0, Total=306 [2018-06-22 15:36:46,696 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 18 states. [2018-06-22 15:36:47,219 WARN ]: Spent 483.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 47 [2018-06-22 15:36:47,431 WARN ]: Spent 181.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 29 [2018-06-22 15:36:47,560 WARN ]: Spent 108.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 31 [2018-06-22 15:36:47,884 WARN ]: Spent 286.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 38 [2018-06-22 15:36:48,174 WARN ]: Spent 216.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 36 [2018-06-22 15:36:48,229 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:36:48,229 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:36:48,231 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:36:48,231 INFO ]: Start accepts. Automaton has 18 states. Word has length 25 [2018-06-22 15:36:48,231 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:36:48,232 INFO ]: With dead ends: 21 [2018-06-22 15:36:48,232 INFO ]: Without dead ends: 21 [2018-06-22 15:36:48,232 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=109, Invalid=397, Unknown=0, NotChecked=0, Total=506 [2018-06-22 15:36:48,232 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:36:48,235 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:36:48,235 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:36:48,236 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:36:48,236 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:36:48,236 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:36:48,236 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:36:48,236 INFO ]: Interpolant automaton has 18 states. [2018-06-22 15:36:48,236 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:36:48,237 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:36:48,237 INFO ]: Found error trace [2018-06-22 15:36:48,237 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:36:48,237 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:36:48,237 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 15:36:48,237 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:36:48,237 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:36:48,238 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:36:48,238 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:36:48,238 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:36:48,291 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:36:48,712 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:36:48,712 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:36:48,712 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 15:36:48,718 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:36:48,810 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:36:48,845 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:36:48,850 INFO ]: Computing forward predicates... [2018-06-22 15:36:54,384 WARN ]: Spent 4.84 s on a formula simplification. DAG size of input: 420 DAG size of output: 68 [2018-06-22 15:36:54,601 WARN ]: Spent 165.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 34 [2018-06-22 15:36:55,472 WARN ]: Spent 280.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-22 15:36:57,535 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:36:57,565 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:36:57,574 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 21 [2018-06-22 15:36:57,575 INFO ]: Interpolant automaton has 21 states [2018-06-22 15:36:57,575 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 15:36:57,575 INFO ]: CoverageRelationStatistics Valid=55, Invalid=365, Unknown=0, NotChecked=0, Total=420 [2018-06-22 15:36:57,575 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 21 states. [2018-06-22 15:37:00,849 WARN ]: Spent 2.69 s on a formula simplification. DAG size of input: 108 DAG size of output: 93 [2018-06-22 15:37:01,404 WARN ]: Spent 512.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 34 [2018-06-22 15:37:02,005 WARN ]: Spent 534.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 36 [2018-06-22 15:37:02,617 WARN ]: Spent 568.00 ms on a formula simplification. DAG size of input: 114 DAG size of output: 65 [2018-06-22 15:37:03,312 WARN ]: Spent 663.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 59 [2018-06-22 15:37:04,680 WARN ]: Spent 1.24 s on a formula simplification. DAG size of input: 109 DAG size of output: 92 [2018-06-22 15:37:04,765 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:04,765 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:37:04,769 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:37:04,769 INFO ]: Start accepts. Automaton has 21 states. Word has length 29 [2018-06-22 15:37:04,770 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:04,770 INFO ]: With dead ends: 23 [2018-06-22 15:37:04,770 INFO ]: Without dead ends: 23 [2018-06-22 15:37:04,771 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 22 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 66 ImplicationChecksByTransitivity, 13.4s TimeCoverageRelationStatistics Valid=142, Invalid=560, Unknown=0, NotChecked=0, Total=702 [2018-06-22 15:37:04,771 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:37:04,775 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:37:04,775 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:37:04,776 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:37:04,776 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:37:04,776 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:04,776 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:37:04,776 INFO ]: Interpolant automaton has 21 states. [2018-06-22 15:37:04,776 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:37:04,777 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:37:04,777 INFO ]: Found error trace [2018-06-22 15:37:04,777 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:04,777 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:04,777 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-22 15:37:04,777 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:04,777 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:04,778 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:04,778 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:37:04,778 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:04,831 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:05,239 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:37:05,239 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:05,239 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 15:37:05,246 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:37:05,333 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:37:05,333 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:05,338 INFO ]: Computing forward predicates... [2018-06-22 15:37:06,124 WARN ]: Spent 471.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 46 [2018-06-22 15:37:06,671 WARN ]: Spent 182.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 41 [2018-06-22 15:37:08,620 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:37:08,652 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:08,652 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 24 [2018-06-22 15:37:08,652 INFO ]: Interpolant automaton has 24 states [2018-06-22 15:37:08,653 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 15:37:08,653 INFO ]: CoverageRelationStatistics Valid=63, Invalid=489, Unknown=0, NotChecked=0, Total=552 [2018-06-22 15:37:08,653 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 24 states. [2018-06-22 15:37:09,444 WARN ]: Spent 750.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 90 [2018-06-22 15:37:09,846 WARN ]: Spent 349.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 23 [2018-06-22 15:37:10,472 WARN ]: Spent 601.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 52 [2018-06-22 15:37:10,912 WARN ]: Spent 403.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 37 [2018-06-22 15:37:11,682 WARN ]: Spent 743.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 60 [2018-06-22 15:37:12,463 WARN ]: Spent 749.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 39 [2018-06-22 15:37:13,605 WARN ]: Spent 1.11 s on a formula simplification. DAG size of input: 95 DAG size of output: 59 [2018-06-22 15:37:13,657 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:13,657 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:37:13,657 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:37:13,657 INFO ]: Start accepts. Automaton has 24 states. Word has length 33 [2018-06-22 15:37:13,658 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:13,658 INFO ]: With dead ends: 25 [2018-06-22 15:37:13,658 INFO ]: Without dead ends: 25 [2018-06-22 15:37:13,659 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 116 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=172, Invalid=758, Unknown=0, NotChecked=0, Total=930 [2018-06-22 15:37:13,659 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:37:13,662 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:37:13,662 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:37:13,663 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:37:13,663 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:37:13,663 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:13,663 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:37:13,663 INFO ]: Interpolant automaton has 24 states. [2018-06-22 15:37:13,663 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:37:13,664 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:37:13,664 INFO ]: Found error trace [2018-06-22 15:37:13,664 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:13,664 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:13,664 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-22 15:37:13,664 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:13,664 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:13,665 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:13,665 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:37:13,665 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:13,721 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:14,340 WARN ]: Spent 427.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 15:37:15,160 WARN ]: Spent 739.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2018-06-22 15:37:15,462 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:37:15,463 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:15,463 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 15:37:15,470 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:37:15,524 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:15,530 INFO ]: Computing forward predicates... [2018-06-22 15:37:17,179 WARN ]: Spent 1.42 s on a formula simplification. DAG size of input: 256 DAG size of output: 36 [2018-06-22 15:37:17,743 WARN ]: Spent 376.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 37 [2018-06-22 15:37:18,014 WARN ]: Spent 220.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 41 [2018-06-22 15:37:18,717 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:37:18,737 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:18,737 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 27 [2018-06-22 15:37:18,738 INFO ]: Interpolant automaton has 27 states [2018-06-22 15:37:18,738 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-22 15:37:18,738 INFO ]: CoverageRelationStatistics Valid=72, Invalid=630, Unknown=0, NotChecked=0, Total=702 [2018-06-22 15:37:18,738 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 27 states. [2018-06-22 15:37:19,279 WARN ]: Spent 505.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 95 [2018-06-22 15:37:19,798 WARN ]: Spent 482.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 46 [2018-06-22 15:37:20,190 WARN ]: Spent 360.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 44 [2018-06-22 15:37:21,010 WARN ]: Spent 785.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 38 [2018-06-22 15:37:21,656 WARN ]: Spent 614.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 44 [2018-06-22 15:37:22,158 WARN ]: Spent 443.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 29 [2018-06-22 15:37:22,846 WARN ]: Spent 648.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 54 [2018-06-22 15:37:23,970 WARN ]: Spent 1.07 s on a formula simplification. DAG size of input: 108 DAG size of output: 67 [2018-06-22 15:37:24,017 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:24,017 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 15:37:24,018 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 15:37:24,018 INFO ]: Start accepts. Automaton has 27 states. Word has length 37 [2018-06-22 15:37:24,018 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:24,019 INFO ]: With dead ends: 27 [2018-06-22 15:37:24,019 INFO ]: Without dead ends: 27 [2018-06-22 15:37:24,020 INFO ]: 0 DeclaredPredicates, 62 GetRequests, 28 SyntacticMatches, 1 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 147 ImplicationChecksByTransitivity, 9.3s TimeCoverageRelationStatistics Valid=214, Invalid=976, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 15:37:24,020 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 15:37:24,023 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 15:37:24,023 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 15:37:24,024 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 15:37:24,024 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 15:37:24,024 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:24,024 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 15:37:24,024 INFO ]: Interpolant automaton has 27 states. [2018-06-22 15:37:24,024 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 15:37:24,025 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 15:37:24,025 INFO ]: Found error trace [2018-06-22 15:37:24,025 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:24,025 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:24,025 INFO ]: Analyzing trace with hash 1618126293, now seen corresponding path program 8 times [2018-06-22 15:37:24,025 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:24,025 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:24,026 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:24,026 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:37:24,026 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:24,089 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:24,710 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 15:37:24,710 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:24,710 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 15:37:24,716 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:37:24,770 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:37:24,770 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:24,775 INFO ]: Computing forward predicates... [2018-06-22 15:37:26,296 WARN ]: Spent 1.31 s on a formula simplification. DAG size of input: 256 DAG size of output: 36 [2018-06-22 15:37:27,985 WARN ]: Spent 1.03 s on a formula simplification. DAG size of input: 32 DAG size of output: 28 [2018-06-22 15:37:28,201 WARN ]: Spent 180.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 32 [2018-06-22 15:37:28,508 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 15:37:28,528 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:28,528 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 27 [2018-06-22 15:37:28,529 INFO ]: Interpolant automaton has 27 states [2018-06-22 15:37:28,529 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-22 15:37:28,529 INFO ]: CoverageRelationStatistics Valid=75, Invalid=627, Unknown=0, NotChecked=0, Total=702 [2018-06-22 15:37:28,529 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 27 states. [2018-06-22 15:37:29,289 WARN ]: Spent 710.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 79 [2018-06-22 15:37:29,523 WARN ]: Spent 197.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 25 [2018-06-22 15:37:29,763 WARN ]: Spent 214.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 30 [2018-06-22 15:37:30,017 WARN ]: Spent 218.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 40 [2018-06-22 15:37:30,320 WARN ]: Spent 257.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 42 [2018-06-22 15:37:30,622 WARN ]: Spent 274.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 47 [2018-06-22 15:37:30,919 WARN ]: Spent 230.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 34 [2018-06-22 15:37:31,242 WARN ]: Spent 295.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 37 [2018-06-22 15:37:31,973 WARN ]: Spent 693.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 79 [2018-06-22 15:37:32,012 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:32,012 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 15:37:32,012 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 15:37:32,012 INFO ]: Start accepts. Automaton has 27 states. Word has length 41 [2018-06-22 15:37:32,012 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:32,013 INFO ]: With dead ends: 29 [2018-06-22 15:37:32,013 INFO ]: Without dead ends: 29 [2018-06-22 15:37:32,013 INFO ]: 0 DeclaredPredicates, 69 GetRequests, 32 SyntacticMatches, 3 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 143 ImplicationChecksByTransitivity, 7.2s TimeCoverageRelationStatistics Valid=242, Invalid=1018, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 15:37:32,013 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 15:37:32,018 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 15:37:32,019 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 15:37:32,019 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 15:37:32,019 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 15:37:32,020 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:32,020 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 15:37:32,020 INFO ]: Interpolant automaton has 27 states. [2018-06-22 15:37:32,020 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 15:37:32,021 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 15:37:32,021 INFO ]: Found error trace [2018-06-22 15:37:32,021 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:32,021 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:32,021 INFO ]: Analyzing trace with hash 996918775, now seen corresponding path program 9 times [2018-06-22 15:37:32,021 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:32,021 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:32,022 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:32,022 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:37:32,022 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:32,094 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:33,105 WARN ]: Spent 795.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 12 [2018-06-22 15:37:33,714 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 15:37:33,715 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:33,715 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 15:37:33,720 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:37:33,770 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 15:37:33,770 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:33,776 INFO ]: Computing forward predicates... [2018-06-22 15:37:34,291 WARN ]: Spent 334.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 36 [2018-06-22 15:37:34,686 WARN ]: Spent 229.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 41 [2018-06-22 15:37:35,899 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 15:37:35,920 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:35,920 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 29 [2018-06-22 15:37:35,920 INFO ]: Interpolant automaton has 29 states [2018-06-22 15:37:35,920 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-22 15:37:35,921 INFO ]: CoverageRelationStatistics Valid=76, Invalid=736, Unknown=0, NotChecked=0, Total=812 [2018-06-22 15:37:35,921 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 29 states. [2018-06-22 15:37:36,551 WARN ]: Spent 585.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 76 [2018-06-22 15:37:36,736 WARN ]: Spent 140.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 23 [2018-06-22 15:37:36,941 WARN ]: Spent 150.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 28 [2018-06-22 15:37:37,232 WARN ]: Spent 258.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 34 [2018-06-22 15:37:37,759 WARN ]: Spent 496.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 32 [2018-06-22 15:37:38,049 WARN ]: Spent 246.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 23 [2018-06-22 15:37:38,427 WARN ]: Spent 304.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 37 [2018-06-22 15:37:38,737 WARN ]: Spent 276.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 32 [2018-06-22 15:37:39,196 WARN ]: Spent 428.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 45 [2018-06-22 15:37:39,904 WARN ]: Spent 670.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 62 [2018-06-22 15:37:39,935 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:39,935 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 15:37:39,936 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 15:37:39,936 INFO ]: Start accepts. Automaton has 29 states. Word has length 45 [2018-06-22 15:37:39,936 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:39,937 INFO ]: With dead ends: 31 [2018-06-22 15:37:39,937 INFO ]: Without dead ends: 31 [2018-06-22 15:37:39,937 INFO ]: 0 DeclaredPredicates, 76 GetRequests, 34 SyntacticMatches, 5 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 182 ImplicationChecksByTransitivity, 6.3s TimeCoverageRelationStatistics Valid=254, Invalid=1228, Unknown=0, NotChecked=0, Total=1482 [2018-06-22 15:37:39,937 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 15:37:39,942 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 15:37:39,942 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 15:37:39,943 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 15:37:39,943 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 15:37:39,943 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:39,943 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 15:37:39,943 INFO ]: Interpolant automaton has 29 states. [2018-06-22 15:37:39,943 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 15:37:39,944 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 15:37:39,944 INFO ]: Found error trace [2018-06-22 15:37:39,944 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:39,944 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:39,944 INFO ]: Analyzing trace with hash -570306151, now seen corresponding path program 10 times [2018-06-22 15:37:39,944 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:39,944 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:39,947 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:39,947 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:37:39,947 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:39,993 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:40,409 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 31 [2018-06-22 15:37:41,514 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 15:37:41,514 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:41,515 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 15:37:41,521 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:37:41,570 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:37:41,570 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:41,576 INFO ]: Computing forward predicates... [2018-06-22 15:37:41,918 WARN ]: Spent 265.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 30 Received shutdown request... [2018-06-22 15:37:41,956 INFO ]: Timeout while computing interpolants [2018-06-22 15:37:42,156 WARN ]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:37:42,156 WARN ]: Verification canceled [2018-06-22 15:37:42,160 WARN ]: Timeout [2018-06-22 15:37:42,160 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:37:42 BoogieIcfgContainer [2018-06-22 15:37:42,160 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:37:42,161 INFO ]: Toolchain (without parser) took 61472.53 ms. Allocated memory was 306.7 MB in the beginning and 753.4 MB in the end (delta: 446.7 MB). Free memory was 261.1 MB in the beginning and 640.8 MB in the end (delta: -379.7 MB). Peak memory consumption was 67.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:37:42,162 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 306.7 MB. Free memory is still 271.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:37:42,162 INFO ]: ChcToBoogie took 49.29 ms. Allocated memory is still 306.7 MB. Free memory was 261.1 MB in the beginning and 259.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:37:42,162 INFO ]: Boogie Preprocessor took 32.50 ms. Allocated memory is still 306.7 MB. Free memory was 259.1 MB in the beginning and 257.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:37:42,163 INFO ]: RCFGBuilder took 254.03 ms. Allocated memory is still 306.7 MB. Free memory was 257.1 MB in the beginning and 249.1 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:37:42,163 INFO ]: TraceAbstraction took 61127.90 ms. Allocated memory was 306.7 MB in the beginning and 753.4 MB in the end (delta: 446.7 MB). Free memory was 249.1 MB in the beginning and 640.8 MB in the end (delta: -391.7 MB). Peak memory consumption was 55.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:37:42,166 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 306.7 MB. Free memory is still 271.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 49.29 ms. Allocated memory is still 306.7 MB. Free memory was 261.1 MB in the beginning and 259.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 32.50 ms. Allocated memory is still 306.7 MB. Free memory was 259.1 MB in the beginning and 257.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 254.03 ms. Allocated memory is still 306.7 MB. Free memory was 257.1 MB in the beginning and 249.1 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61127.90 ms. Allocated memory was 306.7 MB in the beginning and 753.4 MB in the end (delta: 446.7 MB). Free memory was 249.1 MB in the beginning and 640.8 MB in the end (delta: -391.7 MB). Peak memory consumption was 55.0 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 50 with TraceHistMax 11, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 25 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 61.0s OverallTime, 11 OverallIterations, 11 TraceHistogramMax, 28.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 138 SDtfs, 476 SDslu, 918 SDs, 0 SdLazy, 831 SolverSat, 569 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.8s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 437 GetRequests, 209 SyntacticMatches, 11 SemanticMatches, 217 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 739 ImplicationChecksByTransitivity, 47.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=31occurred in iteration=10, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 10 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.8s SatisfiabilityAnalysisTime, 29.1s InterpolantComputationTime, 531 NumberOfCodeBlocks, 531 NumberOfCodeBlocksAsserted, 44 NumberOfCheckSat, 512 ConstructedInterpolants, 0 QuantifiedInterpolants, 7059076 SizeOfPredicates, 443 NumberOfNonLiveVariables, 1620 ConjunctsInSsa, 406 ConjunctsInUnsatCore, 19 InterpolantComputations, 1 PerfectInterpolantSequences, 330/1230 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/simple_nest.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-37-42-176.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/simple_nest.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-37-42-176.csv Completed graceful shutdown