is_deterministic.hxx

00001 // is_deterministic.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
00016 //
00017 #ifndef VCSN_ALGORITHMS_IS_DETERMINISTIC_HXX
00018 # define VCSN_ALGORITHMS_IS_DETERMINISTIC_HXX
00019 
00020 # include <vaucanson/algorithms/is_deterministic.hh>
00021 # include <set>
00022 # include <vaucanson/misc/usual_macros.hh>
00023 # include <vaucanson/automata/concept/automata_base.hh>
00024 
00025 namespace vcsn {
00026 
00027   /*-------------------------.
00028   | is_state_deterministic.  |
00029   `-------------------------*/
00030 
00031   template <typename input_t>
00032   static bool
00033   is_state_deterministic (input_t& input,
00034                           typename input_t::state_iterator& current_state,
00035                           typename input_t::series_set_elt_t::semiring_elt_t&
00036                                                                  zero_semiring)
00037   {
00038     AUTOMATON_TYPES(input_t);
00039 
00040     typedef typename series_set_elt_t::support_t        support_t;
00041     typedef typename std::set<htransition_t>            delta_ret_t;
00042     delta_ret_t delta_ret;
00043 
00044     input.deltac(delta_ret, *current_state, delta_kind::transitions());
00045     // FIXME : O(n^2) => O(nlog(n)) There is maybe an algorithm in O(nlog(n))
00046     for_all_const_(delta_ret_t, j, delta_ret)
00047     {
00048       series_set_elt_t s = input.series_of(*j);
00049       typename delta_ret_t::const_iterator k = j;
00050       ++k;
00051       for (; k != delta_ret.end(); ++k)
00052       {
00053         series_set_elt_t s_ = input.series_of(*k);
00054         for_all_(support_t, supp, s.supp())
00055           if (s_.get(*supp) != zero_semiring)
00056             return false;
00057       }
00058     }
00059     return true;
00060   }
00061 
00062 
00063 
00064 
00065   /*-------------------.
00066   | is_deterministic.  |
00067   `-------------------*/
00068   template <typename A, typename input_t>
00069   bool
00070   do_is_deterministic(const AutomataBase<A>&    ,
00071                       const input_t&            input)
00072   {
00073     AUTOMATON_TYPES(input_t);
00074     semiring_elt_t                zero_semiring
00075       = input.structure().series().semiring()
00076       .zero(SELECT(typename semiring_elt_t::value_t));
00077 
00078     // Empty automaton is not deterministic
00079     if (input.states().size() == 0)
00080       return false;
00081 
00082     if (input.initial().size() != 1)
00083       return false;
00084 
00085     for_all_states(i, input)
00086       if (not is_state_deterministic (input, i, zero_semiring))
00087         return false;
00088     return true;
00089   }
00090 
00091 
00092   template<typename A, typename T>
00093   bool
00094   is_deterministic(const Element<A, T>& a)
00095   {
00096     TIMER_SCOPED("is_deterministic");
00097     return do_is_deterministic(a.structure(), a);
00098   }
00099 
00100 } // vcsn
00101 
00102 #endif // ! VCSN_ALGORITHMS_IS_DETERMINISTIC_HXX

Generated on Wed Jun 13 17:00:22 2007 for Vaucanson by  doxygen 1.5.1