let run ?(trace=false) machine u =
      let m = String.length u in
      let apply qs c =
        try
          let t = Hashtbl.find machine.mc_power_table c in
          ISM.find qs t
        with
        | Not_found ->
            let qs' =
              IS.fold
                begin fun q qs' ->
                  List.fold_left
                    begin fun qs' (cl,qs'') ->
                      if match_character_class cl c then
                        IS.union qs' qs''
                      else
                        qs'
                    end
                    qs'
                    machine.mc_table.(q)
                end
                qs
                IS.empty
            in
            let t =
              try
                Hashtbl.find machine.mc_power_table c
              with
              | Not_found -> ISM.empty
            in
            Hashtbl.replace machine.mc_power_table c (ISM.add qs qs' t);
            qs'
      in
      let rec loop qs i =
        if IS.is_empty qs then
          false
        else
          begin
            if i = m then
              IS.mem machine.mc_qf qs
            else
              begin
                let c = u.[i] in
                if trace then
                  begin
                    Printf.printf "%d %C {" i c;
                    IS.iter (fun q -> Printf.printf " %d" q) qs;
                    Printf.printf " }\n%!"
                  end;
                let qs' = apply qs c in
                loop qs' (i + 1)
              end
          end
      in
      loop machine.mc_qi 0