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/MADWiFi-encode_ie_ok.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:12:29,363 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:12:29,365 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:12:29,379 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:12:29,379 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:12:29,380 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:12:29,381 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:12:29,383 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:12:29,385 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:12:29,385 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:12:29,386 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:12:29,387 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:12:29,387 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:12:29,388 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:12:29,389 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:12:29,390 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:12:29,391 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:12:29,393 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:12:29,395 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:12:29,402 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:12:29,403 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:12:29,407 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:12:29,408 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:12:29,408 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:12:29,409 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:12:29,410 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:12:29,410 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:12:29,411 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:12:29,412 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:12:29,412 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:12:29,412 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:12:29,413 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:12:29,413 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:12:29,414 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:12:29,414 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:12:29,415 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:12:29,427 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:12:29,428 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:12:29,428 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:12:29,428 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:12:29,429 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:12:29,429 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:12:29,429 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:12:29,430 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:12:29,430 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:12:29,430 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:12:29,430 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:12:29,430 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:12:29,431 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:12:29,431 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:12:29,431 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:12:29,431 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:12:29,431 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:12:29,431 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:12:29,432 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:12:29,433 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:12:29,433 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:12:29,484 INFO ]: Repository-Root is: /tmp [2018-06-22 15:12:29,500 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:12:29,507 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:12:29,508 INFO ]: Initializing SmtParser... [2018-06-22 15:12:29,509 INFO ]: SmtParser initialized [2018-06-22 15:12:29,509 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/MADWiFi-encode_ie_ok.c.smt2 [2018-06-22 15:12:29,511 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:12:29,596 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/MADWiFi-encode_ie_ok.c.smt2 unknown [2018-06-22 15:12:29,918 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/MADWiFi-encode_ie_ok.c.smt2 [2018-06-22 15:12:29,925 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:12:29,933 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:12:29,934 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:12:29,934 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:12:29,934 INFO ]: ChcToBoogie initialized [2018-06-22 15:12:29,937 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:12:29" (1/1) ... [2018-06-22 15:12:29,987 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:29 Unit [2018-06-22 15:12:29,987 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:12:29,988 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:12:29,988 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:12:29,988 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:12:30,008 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:29" (1/1) ... [2018-06-22 15:12:30,008 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:29" (1/1) ... [2018-06-22 15:12:30,019 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:29" (1/1) ... [2018-06-22 15:12:30,019 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:29" (1/1) ... [2018-06-22 15:12:30,036 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:29" (1/1) ... [2018-06-22 15:12:30,037 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:29" (1/1) ... [2018-06-22 15:12:30,038 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:29" (1/1) ... [2018-06-22 15:12:30,049 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:12:30,050 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:12:30,050 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:12:30,050 INFO ]: RCFGBuilder initialized [2018-06-22 15:12:30,051 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:29" (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:12:30,060 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:12:30,060 INFO ]: Found specification of procedure False [2018-06-22 15:12:30,060 INFO ]: Found implementation of procedure False [2018-06-22 15:12:30,060 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:12:30,060 INFO ]: Found specification of procedure state [2018-06-22 15:12:30,060 INFO ]: Found implementation of procedure state [2018-06-22 15:12:30,060 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:12:30,060 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:12:30,060 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:12:30,307 INFO ]: Using library mode [2018-06-22 15:12:30,308 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:12:30 BoogieIcfgContainer [2018-06-22 15:12:30,308 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:12:30,309 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:12:30,309 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:12:30,312 INFO ]: TraceAbstraction initialized [2018-06-22 15:12:30,312 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:12:29" (1/3) ... [2018-06-22 15:12:30,313 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@e49b9ca and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:12:30, skipping insertion in model container [2018-06-22 15:12:30,313 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:29" (2/3) ... [2018-06-22 15:12:30,314 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@e49b9ca and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:12:30, skipping insertion in model container [2018-06-22 15:12:30,314 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:12:30" (3/3) ... [2018-06-22 15:12:30,315 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:12:30,324 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:12:30,332 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:12:30,374 INFO ]: Using default assertion order modulation [2018-06-22 15:12:30,375 INFO ]: Interprodecural is true [2018-06-22 15:12:30,375 INFO ]: Hoare is false [2018-06-22 15:12:30,375 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:12:30,375 INFO ]: Backedges is TWOTRACK [2018-06-22 15:12:30,375 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:12:30,375 INFO ]: Difference is false [2018-06-22 15:12:30,375 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:12:30,375 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:12:30,388 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:12:30,398 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:12:30,398 INFO ]: Found error trace [2018-06-22 15:12:30,399 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:30,399 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:30,407 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 15:12:30,409 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:30,409 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:30,449 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:30,449 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:12:30,449 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:30,481 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:30,594 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:12:30,595 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:12:30,595 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:12:30,597 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:12:30,609 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:12:30,609 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:12:30,611 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:12:30,728 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:12:30,728 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:12:30,730 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:12:30,731 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:12:30,731 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:12:30,740 INFO ]: With dead ends: 13 [2018-06-22 15:12:30,740 INFO ]: Without dead ends: 13 [2018-06-22 15:12:30,742 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:12:30,756 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:12:30,776 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:12:30,777 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:12:30,778 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:12:30,779 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:12:30,779 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:12:30,779 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:12:30,779 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:12:30,779 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:12:30,780 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:12:30,780 INFO ]: Found error trace [2018-06-22 15:12:30,780 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:30,780 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:30,781 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 15:12:30,781 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:30,781 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:30,782 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:30,782 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:12:30,782 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:30,832 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:31,125 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:12:31,125 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:12:31,125 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) [2018-06-22 15:12:31,138 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:12:31,181 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:31,188 INFO ]: Computing forward predicates... [2018-06-22 15:12:31,764 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:12:31,784 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:12:31,784 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 15:12:31,785 INFO ]: Interpolant automaton has 9 states [2018-06-22 15:12:31,785 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 15:12:31,785 INFO ]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-06-22 15:12:31,785 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 15:12:31,930 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 7 [2018-06-22 15:12:32,326 WARN ]: Spent 245.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 12 [2018-06-22 15:12:32,587 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:12:32,587 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:12:32,588 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:12:32,588 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 15:12:32,588 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:12:32,588 INFO ]: With dead ends: 15 [2018-06-22 15:12:32,588 INFO ]: Without dead ends: 15 [2018-06-22 15:12:32,590 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:12:32,590 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:12:32,593 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:12:32,593 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:12:32,593 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:12:32,594 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:12:32,594 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:12:32,594 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:12:32,594 INFO ]: Interpolant automaton has 9 states. [2018-06-22 15:12:32,594 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:12:32,594 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:12:32,594 INFO ]: Found error trace [2018-06-22 15:12:32,594 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:32,595 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:32,595 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 15:12:32,595 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:32,595 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:32,596 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:32,596 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:12:32,596 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:32,652 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:32,862 WARN ]: Spent 108.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 15:12:33,183 WARN ]: Spent 252.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2018-06-22 15:12:33,501 WARN ]: Spent 204.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-22 15:12:33,518 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:12:33,518 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:12:33,518 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:12:33,530 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:12:33,601 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:12:33,601 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:33,604 INFO ]: Computing forward predicates... [2018-06-22 15:12:34,287 WARN ]: Spent 377.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 22 [2018-06-22 15:12:34,431 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:12:34,455 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:12:34,455 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:12:34,456 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:12:34,456 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:12:34,456 INFO ]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:12:34,456 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:12:34,747 WARN ]: Spent 181.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 36 [2018-06-22 15:12:34,981 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:12:34,981 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:12:34,982 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:12:34,982 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:12:34,982 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:12:34,984 INFO ]: With dead ends: 17 [2018-06-22 15:12:34,984 INFO ]: Without dead ends: 17 [2018-06-22 15:12:34,984 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:12:34,984 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:12:34,987 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:12:34,987 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:12:34,988 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:12:34,988 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:12:34,988 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:12:34,988 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:12:34,988 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:12:34,988 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:12:34,989 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:12:34,989 INFO ]: Found error trace [2018-06-22 15:12:34,989 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:34,989 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:34,989 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 15:12:34,989 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:34,989 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:34,990 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:34,990 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:12:34,990 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:35,041 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:35,327 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:12:35,327 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:12:35,328 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:12:35,344 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:12:35,402 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:12:35,402 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:35,405 INFO ]: Computing forward predicates... [2018-06-22 15:12:35,885 WARN ]: Spent 351.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 29 [2018-06-22 15:12:36,189 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:12:36,211 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:12:36,211 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 13 [2018-06-22 15:12:36,211 INFO ]: Interpolant automaton has 13 states [2018-06-22 15:12:36,211 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 15:12:36,211 INFO ]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2018-06-22 15:12:36,211 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 13 states. [2018-06-22 15:12:36,630 WARN ]: Spent 383.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 54 [2018-06-22 15:12:36,793 WARN ]: Spent 134.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 30 [2018-06-22 15:12:37,048 WARN ]: Spent 238.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 41 [2018-06-22 15:12:37,323 WARN ]: Spent 257.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 47 [2018-06-22 15:12:37,360 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:12:37,360 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:12:37,361 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:12:37,361 INFO ]: Start accepts. Automaton has 13 states. Word has length 21 [2018-06-22 15:12:37,361 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:12:37,362 INFO ]: With dead ends: 19 [2018-06-22 15:12:37,362 INFO ]: Without dead ends: 19 [2018-06-22 15:12:37,362 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 17 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=63, Invalid=243, Unknown=0, NotChecked=0, Total=306 [2018-06-22 15:12:37,362 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:12:37,365 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:12:37,365 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:12:37,365 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:12:37,365 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:12:37,366 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:12:37,366 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:12:37,366 INFO ]: Interpolant automaton has 13 states. [2018-06-22 15:12:37,366 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:12:37,366 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:12:37,366 INFO ]: Found error trace [2018-06-22 15:12:37,366 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:37,367 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:37,367 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 15:12:37,367 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:37,367 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:37,367 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:37,367 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:12:37,367 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:37,415 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:37,662 WARN ]: Spent 144.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 8 [2018-06-22 15:12:38,081 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:12:38,081 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:12:38,081 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:12:38,087 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:12:38,149 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:12:38,149 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:38,154 INFO ]: Computing forward predicates... [2018-06-22 15:12:39,389 WARN ]: Spent 829.00 ms on a formula simplification. DAG size of input: 169 DAG size of output: 37 [2018-06-22 15:12:42,075 WARN ]: Spent 2.38 s on a formula simplification. DAG size of input: 45 DAG size of output: 33 [2018-06-22 15:12:42,458 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:12:42,477 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:12:42,477 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 16 [2018-06-22 15:12:42,477 INFO ]: Interpolant automaton has 16 states [2018-06-22 15:12:42,477 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 15:12:42,477 INFO ]: CoverageRelationStatistics Valid=34, Invalid=206, Unknown=0, NotChecked=0, Total=240 [2018-06-22 15:12:42,477 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 16 states. [2018-06-22 15:12:43,047 WARN ]: Spent 519.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 67 [2018-06-22 15:12:43,412 WARN ]: Spent 336.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 40 [2018-06-22 15:12:43,624 WARN ]: Spent 191.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 49 [2018-06-22 15:12:43,964 WARN ]: Spent 316.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 50 [2018-06-22 15:12:44,407 WARN ]: Spent 417.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 63 [2018-06-22 15:12:44,447 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:12:44,448 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:12:44,453 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:12:44,453 INFO ]: Start accepts. Automaton has 16 states. Word has length 25 [2018-06-22 15:12:44,453 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:12:44,454 INFO ]: With dead ends: 21 [2018-06-22 15:12:44,454 INFO ]: Without dead ends: 21 [2018-06-22 15:12:44,454 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 20 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 6.2s TimeCoverageRelationStatistics Valid=87, Invalid=375, Unknown=0, NotChecked=0, Total=462 [2018-06-22 15:12:44,454 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:12:44,459 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:12:44,459 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:12:44,459 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:12:44,459 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:12:44,460 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:12:44,460 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:12:44,460 INFO ]: Interpolant automaton has 16 states. [2018-06-22 15:12:44,460 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:12:44,460 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:12:44,460 INFO ]: Found error trace [2018-06-22 15:12:44,460 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:44,461 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:44,461 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 15:12:44,461 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:44,461 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:44,461 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:44,461 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:12:44,461 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:44,565 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:44,904 WARN ]: Spent 174.00 ms on a formula simplification. DAG size of input: 6 DAG size of output: 4 [2018-06-22 15:12:45,758 WARN ]: Spent 809.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 21 [2018-06-22 15:12:46,021 WARN ]: Spent 188.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 26 [2018-06-22 15:12:46,393 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:12:46,393 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:12:46,393 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:12:46,400 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:12:46,509 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:12:46,509 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:46,520 INFO ]: Computing forward predicates... [2018-06-22 15:12:46,690 WARN ]: Spent 123.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 25 [2018-06-22 15:12:47,105 WARN ]: Spent 278.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 30 [2018-06-22 15:12:47,366 WARN ]: Spent 220.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 33 [2018-06-22 15:12:47,738 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:12:47,758 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:12:47,758 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 20 [2018-06-22 15:12:47,758 INFO ]: Interpolant automaton has 20 states [2018-06-22 15:12:47,758 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 15:12:47,758 INFO ]: CoverageRelationStatistics Valid=48, Invalid=332, Unknown=0, NotChecked=0, Total=380 [2018-06-22 15:12:47,758 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 20 states. [2018-06-22 15:12:48,251 WARN ]: Spent 436.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 61 [2018-06-22 15:12:48,522 WARN ]: Spent 239.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 32 [2018-06-22 15:12:48,894 WARN ]: Spent 344.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 39 [2018-06-22 15:12:49,199 WARN ]: Spent 278.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 42 [2018-06-22 15:12:49,643 WARN ]: Spent 364.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 43 [2018-06-22 15:12:50,205 WARN ]: Spent 538.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 47 [2018-06-22 15:12:50,260 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:12:50,260 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:12:50,263 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:12:50,263 INFO ]: Start accepts. Automaton has 20 states. Word has length 29 [2018-06-22 15:12:50,263 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:12:50,264 INFO ]: With dead ends: 23 [2018-06-22 15:12:50,264 INFO ]: Without dead ends: 23 [2018-06-22 15:12:50,264 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 22 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 69 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=128, Invalid=574, Unknown=0, NotChecked=0, Total=702 [2018-06-22 15:12:50,264 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:12:50,277 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:12:50,277 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:12:50,278 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:12:50,278 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:12:50,278 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:12:50,278 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:12:50,278 INFO ]: Interpolant automaton has 20 states. [2018-06-22 15:12:50,278 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:12:50,279 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:12:50,279 INFO ]: Found error trace [2018-06-22 15:12:50,279 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:50,279 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:50,279 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-22 15:12:50,279 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:50,279 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:50,280 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:50,280 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:12:50,280 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:50,413 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:51,120 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:12:51,120 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:12:51,120 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:12:51,126 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:12:51,192 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:12:51,192 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:51,197 INFO ]: Computing forward predicates... [2018-06-22 15:12:51,474 WARN ]: Spent 148.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 28 [2018-06-22 15:12:51,800 WARN ]: Spent 278.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 30 [2018-06-22 15:12:52,021 WARN ]: Spent 179.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 33 [2018-06-22 15:12:52,182 WARN ]: Spent 110.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 26 [2018-06-22 15:12:52,431 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:12:52,463 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:12:52,463 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 23 [2018-06-22 15:12:52,464 INFO ]: Interpolant automaton has 23 states [2018-06-22 15:12:52,464 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 15:12:52,464 INFO ]: CoverageRelationStatistics Valid=49, Invalid=457, Unknown=0, NotChecked=0, Total=506 [2018-06-22 15:12:52,464 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 23 states. [2018-06-22 15:12:53,114 WARN ]: Spent 592.00 ms on a formula simplification. DAG size of input: 102 DAG size of output: 79 [2018-06-22 15:12:53,426 WARN ]: Spent 267.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 33 [2018-06-22 15:12:53,802 WARN ]: Spent 337.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 41 [2018-06-22 15:12:54,193 WARN ]: Spent 352.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 52 [2018-06-22 15:12:54,570 WARN ]: Spent 338.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 47 [2018-06-22 15:12:54,910 WARN ]: Spent 297.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 44 [2018-06-22 15:12:55,299 WARN ]: Spent 359.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 37 [2018-06-22 15:12:55,440 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:12:55,440 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:12:55,440 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:12:55,440 INFO ]: Start accepts. Automaton has 23 states. Word has length 33 [2018-06-22 15:12:55,441 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:12:55,441 INFO ]: With dead ends: 25 [2018-06-22 15:12:55,441 INFO ]: Without dead ends: 25 [2018-06-22 15:12:55,442 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 23 SyntacticMatches, 4 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 68 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=158, Invalid=772, Unknown=0, NotChecked=0, Total=930 [2018-06-22 15:12:55,442 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:12:55,446 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:12:55,447 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:12:55,447 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:12:55,447 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:12:55,447 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:12:55,447 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:12:55,448 INFO ]: Interpolant automaton has 23 states. [2018-06-22 15:12:55,448 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:12:55,448 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:12:55,448 INFO ]: Found error trace [2018-06-22 15:12:55,448 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:55,449 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:55,449 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-22 15:12:55,449 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:55,449 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:55,449 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:55,449 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:12:55,449 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:55,521 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:55,837 WARN ]: Spent 179.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 15:12:56,220 WARN ]: Spent 121.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 29 [2018-06-22 15:12:56,352 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 32 [2018-06-22 15:12:56,497 WARN ]: Spent 124.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 29 [2018-06-22 15:12:56,872 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:12:56,872 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:12:56,872 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:12:56,879 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:12:56,943 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:56,950 INFO ]: Computing forward predicates... [2018-06-22 15:12:57,324 WARN ]: Spent 165.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 28 [2018-06-22 15:12:57,658 WARN ]: Spent 276.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 30 [2018-06-22 15:13:01,488 WARN ]: Spent 3.35 s on a formula simplification. DAG size of input: 323 DAG size of output: 91 [2018-06-22 15:13:01,640 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 26 [2018-06-22 15:13:04,107 INFO ]: Checked inductivity of 105 backedges. 3 proven. 74 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:13:04,127 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:13:04,127 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 25 [2018-06-22 15:13:04,127 INFO ]: Interpolant automaton has 25 states [2018-06-22 15:13:04,127 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-22 15:13:04,127 INFO ]: CoverageRelationStatistics Valid=61, Invalid=539, Unknown=0, NotChecked=0, Total=600 [2018-06-22 15:13:04,128 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 25 states. [2018-06-22 15:13:05,217 WARN ]: Spent 1.01 s on a formula simplification. DAG size of input: 110 DAG size of output: 102 [2018-06-22 15:13:05,992 WARN ]: Spent 717.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 41 [2018-06-22 15:13:06,781 WARN ]: Spent 755.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 60 [2018-06-22 15:13:07,606 WARN ]: Spent 750.00 ms on a formula simplification. DAG size of input: 114 DAG size of output: 60 [2018-06-22 15:13:08,466 WARN ]: Spent 826.00 ms on a formula simplification. DAG size of input: 115 DAG size of output: 79 [2018-06-22 15:13:09,174 WARN ]: Spent 673.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 51 [2018-06-22 15:13:10,017 WARN ]: Spent 809.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 55 [2018-06-22 15:13:10,698 WARN ]: Spent 646.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 63 [2018-06-22 15:13:10,761 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:13:10,761 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 15:13:10,761 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 15:13:10,761 INFO ]: Start accepts. Automaton has 25 states. Word has length 37 [2018-06-22 15:13:10,761 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:13:10,762 INFO ]: With dead ends: 27 [2018-06-22 15:13:10,762 INFO ]: Without dead ends: 27 [2018-06-22 15:13:10,763 INFO ]: 0 DeclaredPredicates, 63 GetRequests, 27 SyntacticMatches, 4 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 81 ImplicationChecksByTransitivity, 12.7s TimeCoverageRelationStatistics Valid=196, Invalid=926, Unknown=0, NotChecked=0, Total=1122 [2018-06-22 15:13:10,763 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 15:13:10,766 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 15:13:10,766 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 15:13:10,767 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 15:13:10,767 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 15:13:10,767 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:13:10,767 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 15:13:10,767 INFO ]: Interpolant automaton has 25 states. [2018-06-22 15:13:10,767 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 15:13:10,768 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 15:13:10,768 INFO ]: Found error trace [2018-06-22 15:13:10,768 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:13:10,768 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:13:10,769 INFO ]: Analyzing trace with hash 1618126293, now seen corresponding path program 8 times [2018-06-22 15:13:10,769 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:13:10,769 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:13:10,769 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:13:10,769 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:13:10,769 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:13:10,840 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:13:11,081 WARN ]: Spent 112.00 ms on a formula simplification. DAG size of input: 4 DAG size of output: 1 [2018-06-22 15:13:11,325 WARN ]: Spent 195.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-22 15:13:11,986 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:13:11,986 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:13:11,986 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:13:11,992 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:13:12,070 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:13:12,070 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:13:12,085 INFO ]: Computing forward predicates... [2018-06-22 15:13:12,349 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 28 [2018-06-22 15:13:12,602 WARN ]: Spent 191.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 33 [2018-06-22 15:13:12,746 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 26 [2018-06-22 15:13:13,264 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:13:13,283 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:13:13,283 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 26 [2018-06-22 15:13:13,284 INFO ]: Interpolant automaton has 26 states [2018-06-22 15:13:13,284 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-22 15:13:13,284 INFO ]: CoverageRelationStatistics Valid=66, Invalid=584, Unknown=0, NotChecked=0, Total=650 [2018-06-22 15:13:13,284 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 26 states. [2018-06-22 15:13:13,939 WARN ]: Spent 581.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 60 [2018-06-22 15:13:14,226 WARN ]: Spent 247.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 32 [2018-06-22 15:13:14,509 WARN ]: Spent 251.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 42 [2018-06-22 15:13:14,840 WARN ]: Spent 299.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 42 [2018-06-22 15:13:15,237 WARN ]: Spent 321.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 37 [2018-06-22 15:13:15,515 WARN ]: Spent 249.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 41 [2018-06-22 15:13:15,749 WARN ]: Spent 207.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 33 [2018-06-22 15:13:16,009 WARN ]: Spent 218.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 36 [2018-06-22 15:13:16,277 WARN ]: Spent 220.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 37 [2018-06-22 15:13:16,309 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:13:16,310 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 15:13:16,310 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 15:13:16,310 INFO ]: Start accepts. Automaton has 26 states. Word has length 41 [2018-06-22 15:13:16,310 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:13:16,311 INFO ]: With dead ends: 29 [2018-06-22 15:13:16,311 INFO ]: Without dead ends: 29 [2018-06-22 15:13:16,311 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 32 SyntacticMatches, 4 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 118 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=220, Invalid=1040, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 15:13:16,311 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 15:13:16,316 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 15:13:16,316 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 15:13:16,317 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 15:13:16,317 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 15:13:16,317 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:13:16,317 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 15:13:16,317 INFO ]: Interpolant automaton has 26 states. [2018-06-22 15:13:16,317 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 15:13:16,318 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 15:13:16,318 INFO ]: Found error trace [2018-06-22 15:13:16,318 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:13:16,318 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:13:16,318 INFO ]: Analyzing trace with hash 996918775, now seen corresponding path program 9 times [2018-06-22 15:13:16,318 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:13:16,318 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:13:16,319 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:13:16,319 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:13:16,319 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:13:16,387 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:13:16,651 WARN ]: Spent 129.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 15:13:17,219 WARN ]: Spent 520.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-22 15:13:17,415 WARN ]: Spent 121.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2018-06-22 15:13:17,991 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:13:17,991 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:13:17,991 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:13:17,998 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:13:18,101 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 15:13:18,101 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:13:18,110 INFO ]: Computing forward predicates... [2018-06-22 15:13:18,320 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 22 [2018-06-22 15:13:18,570 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 28 [2018-06-22 15:13:18,902 WARN ]: Spent 278.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 30 [2018-06-22 15:13:19,126 WARN ]: Spent 174.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 33 [2018-06-22 15:13:19,464 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:13:19,484 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:13:19,484 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 28 [2018-06-22 15:13:19,485 INFO ]: Interpolant automaton has 28 states [2018-06-22 15:13:19,485 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-22 15:13:19,485 INFO ]: CoverageRelationStatistics Valid=66, Invalid=690, Unknown=0, NotChecked=0, Total=756 [2018-06-22 15:13:19,485 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 28 states. [2018-06-22 15:13:20,261 WARN ]: Spent 694.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 66 [2018-06-22 15:13:20,529 WARN ]: Spent 221.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 26 [2018-06-22 15:13:20,859 WARN ]: Spent 296.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 41 [2018-06-22 15:13:21,214 WARN ]: Spent 321.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 41 [2018-06-22 15:13:21,525 WARN ]: Spent 277.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 37 [2018-06-22 15:13:21,896 WARN ]: Spent 330.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 34 [2018-06-22 15:13:22,280 WARN ]: Spent 332.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 31 [2018-06-22 15:13:22,556 WARN ]: Spent 225.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 33 [2018-06-22 15:13:22,817 WARN ]: Spent 229.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 33 [2018-06-22 15:13:23,363 WARN ]: Spent 507.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 48 [2018-06-22 15:13:23,399 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:13:23,399 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 15:13:23,399 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 15:13:23,399 INFO ]: Start accepts. Automaton has 28 states. Word has length 45 [2018-06-22 15:13:23,399 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:13:23,400 INFO ]: With dead ends: 31 [2018-06-22 15:13:23,400 INFO ]: Without dead ends: 31 [2018-06-22 15:13:23,400 INFO ]: 0 DeclaredPredicates, 77 GetRequests, 34 SyntacticMatches, 6 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 90 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=249, Invalid=1233, Unknown=0, NotChecked=0, Total=1482 [2018-06-22 15:13:23,400 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 15:13:23,404 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 15:13:23,404 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 15:13:23,404 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 15:13:23,404 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 15:13:23,405 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:13:23,405 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 15:13:23,405 INFO ]: Interpolant automaton has 28 states. [2018-06-22 15:13:23,405 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 15:13:23,406 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 15:13:23,406 INFO ]: Found error trace [2018-06-22 15:13:23,406 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:13:23,406 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:13:23,406 INFO ]: Analyzing trace with hash -570306151, now seen corresponding path program 10 times [2018-06-22 15:13:23,406 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:13:23,406 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:13:23,407 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:13:23,407 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:13:23,407 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:13:23,530 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:13:23,960 WARN ]: Spent 199.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 25 [2018-06-22 15:13:24,283 WARN ]: Spent 307.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 59 [2018-06-22 15:13:24,663 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 35 [2018-06-22 15:13:24,784 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 32 [2018-06-22 15:13:24,965 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 34 [2018-06-22 15:13:25,559 WARN ]: Spent 151.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 22 [2018-06-22 15:13:25,588 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:13:25,588 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:13:25,588 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:13:25,594 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:13:25,702 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:13:25,702 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:13:25,714 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 15:13:31,284 WARN ]: Removed 24 from assertion stack [2018-06-22 15:13:31,284 INFO ]: Timeout while computing interpolants [2018-06-22 15:13:31,485 WARN ]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:13:31,485 WARN ]: Verification canceled [2018-06-22 15:13:31,489 WARN ]: Timeout [2018-06-22 15:13:31,489 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:13:31 BoogieIcfgContainer [2018-06-22 15:13:31,489 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:13:31,490 INFO ]: Toolchain (without parser) took 61564.55 ms. Allocated memory was 309.3 MB in the beginning and 793.8 MB in the end (delta: 484.4 MB). Free memory was 259.7 MB in the beginning and 178.9 MB in the end (delta: 80.8 MB). Peak memory consumption was 570.5 MB. Max. memory is 3.6 GB. [2018-06-22 15:13:31,491 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 309.3 MB. Free memory is still 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:13:31,491 INFO ]: ChcToBoogie took 53.92 ms. Allocated memory is still 309.3 MB. Free memory was 259.7 MB in the beginning and 257.8 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:13:31,491 INFO ]: Boogie Preprocessor took 61.38 ms. Allocated memory is still 309.3 MB. Free memory was 257.8 MB in the beginning and 255.7 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:13:31,492 INFO ]: RCFGBuilder took 258.15 ms. Allocated memory is still 309.3 MB. Free memory was 255.7 MB in the beginning and 244.8 MB in the end (delta: 11.0 MB). Peak memory consumption was 11.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:13:31,492 INFO ]: TraceAbstraction took 61179.71 ms. Allocated memory was 309.3 MB in the beginning and 793.8 MB in the end (delta: 484.4 MB). Free memory was 244.8 MB in the beginning and 178.9 MB in the end (delta: 65.8 MB). Peak memory consumption was 555.6 MB. Max. memory is 3.6 GB. [2018-06-22 15:13:31,495 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.06 ms. Allocated memory is still 309.3 MB. Free memory is still 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 53.92 ms. Allocated memory is still 309.3 MB. Free memory was 259.7 MB in the beginning and 257.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 61.38 ms. Allocated memory is still 309.3 MB. Free memory was 257.8 MB in the beginning and 255.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 258.15 ms. Allocated memory is still 309.3 MB. Free memory was 255.7 MB in the beginning and 244.8 MB in the end (delta: 11.0 MB). Peak memory consumption was 11.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61179.71 ms. Allocated memory was 309.3 MB in the beginning and 793.8 MB in the end (delta: 484.4 MB). Free memory was 244.8 MB in the beginning and 178.9 MB in the end (delta: 65.8 MB). Peak memory consumption was 555.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 analyzing trace of length 50 with TraceHistMax 11, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 1568. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 61.1s OverallTime, 11 OverallIterations, 11 TraceHistogramMax, 23.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 143 SDtfs, 433 SDslu, 1119 SDs, 0 SdLazy, 977 SolverSat, 523 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 445 GetRequests, 202 SyntacticMatches, 25 SemanticMatches, 218 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 517 ImplicationChecksByTransitivity, 43.3s 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.1s SsaConstructionTime, 1.1s SatisfiabilityAnalysisTime, 27.5s InterpolantComputationTime, 531 NumberOfCodeBlocks, 531 NumberOfCodeBlocksAsserted, 44 NumberOfCheckSat, 512 ConstructedInterpolants, 0 QuantifiedInterpolants, 22090916 SizeOfPredicates, 831 NumberOfNonLiveVariables, 2835 ConjunctsInSsa, 442 ConjunctsInUnsatCore, 19 InterpolantComputations, 1 PerfectInterpolantSequences, 333/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/MADWiFi-encode_ie_ok.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-13-31-511.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/MADWiFi-encode_ie_ok.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-13-31-511.csv Completed graceful shutdown