(Back to Top)

NAME

Gfsm::Automaton - object-oriented interface to libgfsm finite-state automata

(Back to Top)

SYNOPSIS

 use Gfsm;

 ##------------------------------------------------------------
 ## Constructors, etc.
 
 $fsm = Gfsm::Automaton->new();
 $fsm = Gfsm::Automaton->new($is_transducer,$srtype,$n_preallocated_states);
 
 $fsm2 = $fsm->clone();     # copy constructor
 $fsm2 = $fsm->shadow();    # copy non-structural elements
 $fsm2->assign($fsm1);      # assigns $fsm1 to $fsm2
 
 $fsm->clear();             # clear automaton structure

 ##------------------------------------------------------------
 ## Accessors/Manipulators: Properties
 
 $bool = $fsm->is_transducer();           # get 'is_transducer' flag
 $bool = $fsm->is_transducer($bool);      # ... or set it
 
 $bool = $fsm->is_weighted(?$bool);       # get/set 'is_weighted' flag
 $mode = $fsm->sort_mode(?$mode);         # get/set sort-mode flag (dangerous)
 $bool = $fsm->is_deterministic(?$bool);  # get/set 'is_deterministic' flag (dangerous)
 $srtype = $fsm->semiring_type(?$srtype); # get/set semiring type
 
 $n = $fsm->n_states();                   # get number of states
 $n = $fsm->n_final_states();             # get number of final states
 $n = $fsm->n_arcs();                     # get number of arcs
 
 $id = $fsm->root(?$id);                  # get/set id of initial state
 
 $bool = $fsm->has_state($id);            # check whether a state exists
 $bool = $fsm->is_cyclic();               # check for cyclicity

 ##------------------------------------------------------------
 ## Accessors/Manipulators: States
 $id = $fsm->add_state();                 # add a new state
 $id = $fsm->ensure_state($id);           # ensure that a state exists
 
 $fsm->remove_state($id);                 # remove a state from an FSM
 
 $bool = $fsm->is_final($id,?$bool);      # get/set final-flag for state $id
 
 $deg  = $fsm->out_degree($id);           # get number of outgoing arcs for state $id
 
 $w    = $fsm->final_weight($id,?$w);     # get/set final weight for state $id
 
 $fsm->renumber_states();                 # close gaps in stateid numbering
 $fsm->statesort_aff();                   # ... same thing
 $fsm->statesort_dfs();                   # depth-first state sort
 $fsm->statesort_bfs();                   # breadth-first state sort

 ##------------------------------------------------------------
 ## Accessors/Manipulators: Arcs
 
 $fsm->add_arc($fsm,$id_from,$id_to,$lab_lo,$lab_hi,$weight); # add an arc
 $fsm->arcsort($fsm,$mode);                                   # sort automaton arcs
 
 $ai = Gfsm::ArcIter->new();              # create new arc-iterator
 $ai = Gfsm::ArcIter->new($fsm,$stateid); # create & open
 
 $ai->open($fsm,$stateid);                # open outgoing arcs from $stateid in $fsm
 $ai->reset();                            # reset to 1st outgoing arc
 $ai->close();                            # close an arc iterator
 
 $bool = $ai->ok();                       # check iterator validity
 $ai->remove();                           # remove current arc from the automaton
 
 $stateid = $ai->target(?$stateid);       # get/set current arc target StateId
 $lab     = $ai->lower(?$lab);            # get/set current arc lower label
 $lab     = $ai->upper(?$lab);            # get/set current arc upper label
 $weight  = $ai->weight(?$weight);        # get/set current arc weight
 
 $ai->next();                             # increment to next outgoing arc
 $ai->seek_lower($lab);                   # (inclusive) seek next arc with lower label $lab
 $ai->seek_upper($lab);                   # (inclusive) seek next arc with upper label $lab
 $ai->seek_both($lo,$hi);                 # (inclusive) seek next arc with labels $lo,$hi

 ##--------------------------------------------------------------
 ## I/O
 
 $fsm_or_undef = $fsm->load($filename_or_handle);   # load binary file (class method ok)
 $fsm_or_undef = $fsm->save($filename_or_handle);   # save binary file
 
 $fsm_or_undef = $fsm->load_string($buffer);        # load from in-memory buffer $string (class method ok)
 $fsm_or_undef = $fsm->save_string($buffer);        # save to in-memory buffer $string
 
 $fsm_or_undef = $fsm->compile($filename_or_handle, %options);
         # compile AT&T-style text format file (transducer format only; class method ok)
 
 $fsm_or_undef = $fsm->print_att($filename_or_handle, %options);
         # save AT&T-style text format file (transducer format only)
 
 $fsm_or_undef = $fsm->compile_string($string, ?$abet_lo, ?$abet_hi, ?$abet_states);
         # compile AT&T-style text format $string (class method ok)
 
 $fsm_or_undef = $fsm->print_att_string($string, ?$abet_lo, ?$abet_hi, ?$abet_states);
         # save AT&T-style text format $string
 
 $bool = $fsm->draw_vcg($filename_or_handle,%options);  # save in VCG format
 $bool = $fsm->draw_dot($filename_or_handle,%options);  # save in DOT format
 
 $bool = $fsm->viewps(%options);                        # for debugging

 ##--------------------------------------------------------------
 ## Algebra (constructive)
 
 $fsm = $fsm1->optional();    # set optional
 $fsm = $fsm1->closure();     # reflexive + transitive closure
 $fsm = $fsm1->closure(1);    # transitive closure
 $fsm = $fsm1->n_closure($n); # n-ary closure
 
 $fsm = $fsm1->compact($rmeps);   # heuristic compaction (encoded minimization)
 
 $fsm = $fsm1->complement();      # lower complement wrt. internal alphabet
 $fsm = $fsm1->complement($abet); # lower complement wrt. alphabet $abet
 
 $sinkid = $fsm->complete($abet); # complete lower wrt. $abet, returns sink-state Id
 
 $fsm = $fsm1->compose($fsm2);    # transducer composition
 
 $fsm = $fsm1->concat($fsm2);     # concatenate automata
 
 $fsm = $fsm1->connect();         # remove non co-accessible states
 
 $fsm = $fsm1->determinize();     # acceptor determinization
 
 $fsm = $fsm1->difference($fsm2); # lower difference
 
 ($fsm,$key) = $fsm1->encode($key,$encode_labels,$encode_weights); # encode labels and/or weights
 $fsm        = $fsm1->decode($key,$decode_labels,$decode_weights); # ... or decode them
 
 $fsm = $fsm1->insert_automaton($qfrom,$qto,$fsm2,$w); # insert a whole automaton
 
 $fsm = $fsm1->intersect($fsm2);  # lower acceptor intersection
 
 $fsm = $fsm1->invert();          # invert transdcuer sides
 
 $fsm = $fsm1->minimize($rmeps);  # acceptor minimization
 
 $fsm = $fsm1->product($fsm2);    # compute Cartesian product of acceptors
 
 $fsm = $fsm1->project($side);    # project 1 side of a transducer
 
 $fsm = $fsm1->replace($lo,$hi,$fsm2);  # replace arcs over ($lo:$hi) with $fsm2 in $fsm1
 
 $fsm = $fsm1->rmepsilon();       # remove epsilon-arcs
 
 $fsm = $fsm1->union($fsm2);      # compute automaton union

 ##--------------------------------------------------------------
 ## Algebra ((pseudo-)destructive)
 
 $fsm->_closure();                # destructive closure
 #... etc.

 ##--------------------------------------------------------------
 ## Composition (low-level)
 
 $fsmout = $fsm1->compose_full($fsm2,$fsmout); # mid-level composition

 ##--------------------------------------------------------------
 ## Lookup
 
 $fsm = $fst->lookup($labs);                   # string+fst composition: $fsm=compose(id($labs),$fst)
 $fsm = $fst->lookup($labs,$fsm);              # ... specifying result fsm
 $fsm = $fst->lookup($labs,$fsm,$maxq);        # ... specifying result and result size limit
 
 ($fsm,$map) = $fst->lookup_full($labs);             # ... returning state-id map
 ($fsm,$map) = $fst->lookup_full($labs,$fsm);        # ... specifying result
 ($fsm,$map) = $fst->lookup_full($labs,$fsm,$maxq);  # ... specifying result and size limit
 $map        = $fst->lookup_full($labs,$fsm,$maxq);  # ... in scalar context returns only map.
 
 $trellis = $fst->lookup_viterbi($labs);  # Viterbi trellis construction

 ##--------------------------------------------------------------
 ## Serialization
 
 $paths = $fsm->paths();                        # enumerate paths (non-cyclic $fsm only!)
 
 $paths = $trellis->viterbi_trellis_paths();    # enumerate Viterbi trellis paths
 $best  = $trellis->viterbi_trellis_bestpath(); # get best Viterbi trellis path
 
 $arcpaths = $fsm->arcpaths();                  # enumerate alignments (packed)
 @arcs = Gfsm::unpack_arcpath($arcpath);        # ... get all arcs in an arc-path
 ($q,$r,$lo,$hi,$w) = Gfsm::unpack_arc($arc);   # ... unpack a single arc

 ##--------------------------------------------------------------
 ## Tries
 
 $trie = Gfsm::Automaton->newTrie;
 
 $qid = $trie->add_path(\@lo,\@hi);
 $qid = $trie->add_path(\@lo,\@hi, $w);
 $qid = $trie->add_path(\@lo,\@hi, $w, $add_to_arcs, $add_to_state_final, $add_to_path_final);
 
 ($qid, $lo_i,$hi_i,$w_last) = $trie->find_prefix(\@lo,\@hi);
 
 $qids = $trie->add_path_states(\@lo,\@hi);
 $qids = $trie->add_path_states(\@lo,\@hi, $w);
 $qids = $trie->add_path_states(\@lo,\@hi, $w, $add_to_arcs, $add_to_state_final, $add_to_path_final);
 
 ($qids,$lo_i,$hi_i,$w_last) = $trie->find_prefix_states(\@lo,\@hi);
 
 $qid_to = $trie->find_arc_lower($qid_from, $lab_lo);  ##-- target state or Gfsm::noState()
 $qid_to = $trie->find_arc_upper($qid_from, $lab_hi);  ##-- target state or Gfsm::noState()
 
 $qid_to = $trie->get_arc_lower($qid_from, $lab_lo);   ##-- find or insert arc
 $qid_to = $trie->get_arc_upper($qid_from, $lab_hi);   ##-- find or insert arc

(Back to Top)

DESCRIPTION

Not yet written.

(Back to Top)

BUGS AND LIMITATIONS

Probably many.

(Back to Top)

SEE ALSO

Gfsm(3perl), gfsmutils(1).

(Back to Top)

AUTHOR

Bryan Jurish <moocow@cpan.org>

(Back to Top)

COPYRIGHT AND LICENSE

Copyright (C) 2005-2014 by Bryan Jurish

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.14.2 or, at your option, any later version of Perl 5 you may have available.

(Back to Top)