Home

Vaucanson 1.4.1 TAF

1. VAUCANSON 1 4 1 TAF KiT Documentation 34 July 14 2012 Associativity Sum and product of languages or series are associative but it is not the case of the corresponding rational operators as we have recalled above The construction of the Thompson automaton of an expression makes it clear Figure 2 5 displays the result of the following commands vcsn char b aabc thompson a b c display vcsn char b aabc thompson at btc display thomp abc left xml 10 states 11 transitions 1 1 T 1 thomp abc right xml 10 states 11 transitions 1 1 T 1 Figure 2 5 The operator is not associative The default bracketing is on the left that is a b c is the same as a b c a b c is the same as a b c For the output the default format for expressions as text strings called exp represents the sum and concatenation as associative operators The fpexp format yields the full paranthesized writing vesn char b aabc cat E atbtc atb c vcesn char b aabc cat E a btc atb c vcsn char b aabc ofpexp cat E at btc atb c vcsn char b aabc ofpexp cat E a b c a b c Vaucanson 1 4 1 TAF KiT Documentation 35 July 14 2012 2 2 2 2 The weights Weights are written in braces as in 3 When the expression is output by VAUCANSON weights are also followed by a blank space vcsn char z aab cat E 2 a 2 b
2. 0 b Figure A 12 The Zmin automaton sag xml over a b VAUCANSON 1 4 1 TAF KiT Documentation 96 July 14 2012 A 4 Zmax automata A 4 1 Repository The following automata files are stored data automata char zmax directory and acces sible by the command vcsn char zmax cat A 4 1 1 maxab Comments The series realised by this automaton associates every word w of a b with max number of a number of b cf Figure A 10 A 4 1 2 maxblocka xml Comments The series realised by this automaton associates every word w of a b with the length of the greatest block of a la 0 m 0 a 0 b 0 b 0 b O b Figure A 13 The Zmin automaton maxblocka xml over a b A 5 B fmp transducers A 5 1 Repository The following automata files are stored data automata char fmp b directory and acces sible by the command vcsn char fmp b cat A 5 1 1 t1 xm1 for 7 al b 1 lly lx Figure A 14 The fmp transducer Ti over a b x x y cf Section C 5 2 2 A 5 1 2 u1l xml1 for 14 A 5 2 Factory The following program is in the data automata char fmp b directory VAUCANSON 1 4 1 TAF KiT Documentation 97 July 14 2012 Figure A 15 The fmp transducer U over x y x u v cf Section C 5 2 2 A 5 2 1 Program quotkbaseb Generates an fmp transducer over the digit alphabets quotkbaseb 3 2 gt quot3base2 xml 0 b 1 that compute
3. Figure 2 3 Result of the command vcsn char int b display misc xml Alphabets for transducers The products of two free monoids have two alphabets one for each monoid The instances of TAF KIT that handle transducers consequently support two options alphabet1 and alphabet2 that can be abbreviated to a and A respectively Table 1 3 gives the two possible choices for these alphabets in TAF Krr 1 4 1 both character or both integer alphabets The following command calls for the interactive construction of the right normaliser for numbers written in base 2 which is then shown below ter 11 vecsn int fmp b a0 1 2 A0 1 edit norm2 xml norm2 xml 2 states 6 transitions 1 1 T 1 Figure 2 4 The normaliser in base 2 Caveat The function exp to aut is not implemented in TAF KiT 1 4 1 for the fmp in stances cf Section 3 5 Unix usage The command line is first interpreted by the she11 which makes the characters 2 27 e 0 etc being given their meaning for the shell In order to give them their meaning in the current alphabet and in the writing of rational expressions they have to be cm protected by or Vaucanson 1 4 1 TAF KiT Documentation 25 July 14 2012 vcsn char b aab cat E aab aab vcsn char b aab cat E aa b zsh unknown file attribute vcsn char b aab cat E aa b aa b vcsn char b aab cat E aab zsh no matches found aab vcsn cha
4. Specification cf Section C 1 3 4 3 1 3 5 left mult right mult vcsn left mult a xml k gt b xml Build the automaton that is obtained by multiplication on the left of a zml by k and writes the result in b zaml vcsn right mult a xml k gt b xml Build the automaton that is obtained by multiplication on the right of a zml by k and writes the result in b zml Precondition a zml is standard for the left and right exterior multiplication operations are defined only on standard automata Specification cf Section C 1 3 5 Comments Beware that although the multiplication is on the left the operand k is the second argument and thus written on the right of a xml Example Figure 3 4 shows the effect of a left and a right exterior multiplication on the standardization of the Z automaton c1 xml VAUCANSON 1 4 1 TAF KiT Documentation 54 July 14 2012 2 0 2 1 3 states 5 transitions I 1 T 1 3 states 5 transitions I 1 T 1 Figure 3 4 Left and right multiplication on a standard Z automaton vcsn char z standardize c1 xml Y left mult 3 Al display vcsn char z standardize c1 xml right mult 5 display Caveat The second argument of these two functions is a weight and still is given as a character chain In the case of Z Q and R as weight semirings and for negative k the that gives the sign is indeed interpreted as announcing an option on the co
5. Vaucanson 1 4 1 TAF KiT Documentation 68 July 14 2012 The shuffle of a zml and b zml is by definition cf 17 Sect 111 3 2 6 the accessible part of the automaton whose set of states is the cartesian product of the sets of states of the two automata and whose transitions are defined by alk alk Vo q EA VreB gt oe e Gg p q r p 4 p r de q r VpE A Yr s EB pieg as s Fj r s Y x p a ne and the initial and final functions by VpE A VreB I p r I p I r and T p r T p T r hadam3 xml 4 states 8 transitions I 1 T 1 hadam1 xml 1 states 0 transitions I 1 T 1 Figure 3 13 Two shuffle products of Z automata Example i Figure 3 13 shows the shuffle products of the Z automata that realize the series ab and ab on the left and the series a and a on the right cf 17 Exer 111 3 3 15 ii The shuffle product of two words yields the set of words obtained by intertwining their letters The function expand is well suited for the presentation of the result of such shuffle products vcsn char z aab exp to aut ab gt ab xml vcsn char z aab exp to aut ba gt ba xml vcsn char z shuffle ab xml ba xml aut to exp a b b a b ata b ta b b atb a a b vcsn char z shuffle ab xml ba xml aut to exp Al expand abab 2 abba 2 baab baba vcsn infiltration a xml b xml gt c xml Computes the infiltration of a zml and b aml
6. cat E Q C O x The values of the writing data are stored in the XML file which contains the automaton or the expression so there is no need to specify them again when working from a file vesn char b a parser OPAR CPAR exp to aut gt par A vesn char b aut to exp par xml CEC Te oN TIO IC ea dad This is a questionable feature of both VAUCANSON 1 4 1 and the corresponding version of Fsm XML but it is so Vaucanson 1 4 1 TAF KiT Documentation 38 July 14 2012 a 0 1 a 0 1 xml long option parser parserl parser2 token ZERO ONE STAR PLUS TIMES CONCAT OPAR CPAR OWEIGHT CWEIGHT SPACE short Pp P constant 0 constant 1 Kleene star sum product purpose of the option fix the value of the tokens fix the value of the tokens concerning input alphabet fix the value of the tokens concerning output alphabet meaning and the null series and the identity of the monoid concatenation product within the monoid group start group end weight start weight end space character to be ignored default value s CN be 0 2 z 649 6 9 1 e e Table 2 7 Tokens of the parser option the writing data gt gt Caveat It is the responsability of the user to define the tokens in such a way there is no colli
7. o 2 1 4 Benchmarking options o 2 2 The writing of rational expressions 0 0 e 2 2 1 The definition of expressions e 2 2 2 Parsing strings into expressions e 2 2 3 Parser parametrization e 2 3 TAF KITIO functions saor o eaea a a a o OR 23 02 Data fle location 2 00 a a a A eo i an a a Za datad ek hte bot es Heh Mae Bes a ik qed ae hee BAG oe Ae a les Dede CAC he Bt Boke ee aaa mA Be ee ec te ew ea A Bhs A NCATE cheek etc ie Ws aaa tes e a hl tal obec he WR A gh A eats ole 23A E A Ce des ers a ee ee ae eo LS ae OR Saas 2 08 NA 2 23 06 COUT ekki Rte a Ala GPM ate Pa Moen eA eles Goethe VAUCANSON 1 4 1 000 10 10 12 12 15 15 16 17 18 19 TAF KIT Documentation 2 July 14 2012 3 Specification of functions on automata and rational expressions 46 3 1 General automata and rational expressions 000 48 3 1 1 Graph functions 204 2 is 2G be eee eM Re we ae 49 3 1 2 Transformations of automata 2 0 0 00000002 eee 50 3 1 3 Operations on automatas 53 3 1 4 Operations on behaviour of automata soo soa a 56 3 1 5 Automata and expressions operations on expressions 57 3 2 Weighted automata and expressions over free monoids 60 3 2 1 Properties and transformations of automata 60 3 2 2 Behaviour of automata ee 64 3 2 3 From expressio
8. 2 a 2 b As another example the automaton C of Figure 2 6 is described in the file c1 xml and gives rise to the following command and output vcsn char z aut to exp c1 xml atb b 2 a 2 b vesn char z display c1 xml a b 2a 2b OD cl xml 2 states 3 transitions tl 1 T 1 Figure 2 6 The Z automaton C and its display by Graphviz Eventhough all semirings which are instantiated in TAF KtT 1 4 1 are commutative this is not an assumption which is made in VAUCANSON in general In any case the weight semiring be commutative or not the left and right exterior multiplications yield distinct expressions from which distinct automata are built vcsn char z aab cat E 2 ab 3 2 ab 3 vcsn char z aab cat E 2 3 ab 6 ab 2 2 3 Parser parametrization As there is a priori no restriction on the alphabet the representation of the rational operators called token may collide with the one of elements of the monoid VAUCANSON actually allows every operator to be represented by an arbitrary string The set of these representations is called the writing data It is a feature of VAUCANSON that some different default values are prepared for the constants so that TAF KIT may try to choose a representation which does not collide with the words For the same purpose the other tokens have to be given explicitely This is not so good and will hopefully be corrected in further versions o
9. Rational expressions are given either as character strings default format or XML files xml format By default rational expressions are read as strings given on the command line and output as strings on the standard output Both can be diverted in the Unix way but a string written in a file cannot be read by TAF KtT directly in this file cf Section 2 3 3 vcsn char b aab cat E atb a b a b a b a b a b vcsn char b aab cat E atb a b a b gt exp txt cat exp txt a b a b a b vcsn char b aab cat E exp txt Lexer error unrecognized characters exp txt cat exp txt vcsn char b aab cat E a b a b a b There are indeed two string formats for expressions exp and fpexp when they are made explicit The first one stands for expression and is the default format the second one for fully parenthesized expression They have both the same behaviour for the input For the output the exp format gives an expression with as few parentheses as possible the fpexp format gives the expression with all parentheses made explicit vcsn char b oexp aab cat E a b a a b a vcsn char b ofpexp aab cat E a b a a b a VAUCANSON 1 4 1 TAF KiT Documentation 28 July 14 2012 Alternatively rational expressions can be read from an FSM XML file whose filename is given on the command line and output as an FSM XML file as well vcsn char b aab o
10. Table 2 2 Alphabet options Character alphabets For characters alphabets as with the char TAF KIT instances used in the above examples the letters of the alphabets can be arbitrary ASCII characters and need just to be listed after the alphabet or a option Some character alphabets are predefined These are letters for the lower case letters a b z alpha for the upper and lower case letters a b 2z A B Z digits for all digits 0 1 9 For instance aletters is an abbreviation for aabcdefghijklmnopqrstuvwxyz The above list of predefined alphabets is obtained by typing vcsn char b help When specifying characters alphabets the following characters have to be escaped with a backslash y space 69 om EC DN gt ea D and in this case the list of characters has to be put within quotes The same characters are then used normally without being escaped in the expression For instance the following Vaucanson 1 4 1 TAF KIT Documentation 23 July 14 2012 commands will create an automaton that recognize all decimal numbers written in base 2 and then display the quotient vcsn char b a 01 exp to aut 1 0 1 1 0 1 0 0 1 0 1 x gt dec bin xml vcsn char b quotient dec bin xml Y display dec bin xml 5 states 11 transitions 1 1 T 1 Figure 2 2 Result of the command vcsn char b quotient d
11. VAUCANSON 1 4 1 TAF K1T Documentation ABOUT THIS DOCUMENT The VAUCANSON platform is an on going project of a free software platform dedicated to the manipulation of finite state automata which started about ten years ago already It is conducted at LTCI Telecom ParisTech IGM University Paris Est and LRDE EPITA in Paris The last version of the platform coined VAUCANSON 1 4 1 is meant to be the last one of a first phase of this project This document describes a part of this version only the TAF KIT and will serve as a user s manual for it TAF KIT will be the only documented part of VAUCANSON 1 4 1 A second phase of the project officially starting March 1st 2011 is now engaged with the same partners together with the team of Prof Hsu Chun Yen at the EE Department of the National Taiwan University in Taipeh It will give rise to versions VAUCANSON 2 12 y hopefully as soon as possible and fully documented July 2012 AUTHORING The authors of the VAUCANSON platform are jointly represented as the VAUCANSON GROUP The permanents of this group are Alexandre Duret Lutz LRDE EPITA Paris adl lrde epita fr Sylvain Lombardy IGM Universit Paris Est Marne la Vall e lombardy univ mlv fr Jacques Sakarovitch LTCI CNRS Telecom ParisTech Paris sakarovitch enst fr The authors of the VGI Graphical User Interface are represented by Hsu Chun Yen EE Dept National Taiwan University Taipeh yen cc ee ntu edu tw ACKNOW
12. z vcsn char z aaz01 expand at 1 a Z Caveat i If the alphabet contains the three characters 1 e and _ the default representation of the constant 1 is still e and another less ambiguous representation has to be chosen explicitely cf below The same is true for the default representation of the constant 0 if the alphabet contains the three characters 0 z and _ vcsn char b a_abel cat E 0 e vcsn char z a_az01 expand at 1 a Z ii The identity of free monoid over an alphabet of pairs or of a product of free monoids whose generators are characters is always 1 by default even if the alphabets of the components of the pairs or of the components of the product contain 1 5In TAF Kir 1 4 1 the functions which parse with rational expressions over a product of free monoids are not implemented cf Section 3 5 VAUCANSON 1 4 1 TAF KiT Documentation 37 July 14 2012 In the results of the following commands note how the coding of the identity element of the monoid underlined for helping the reader changes from 1 to e when one goes from the automaton over the pairs resp from the transducer to the projection on the second component resp to the image vcesn char char b a a 0 b 1 exp to aut a 0 b 1 gt ex pair1 xml vecsn char char b aut to exp ex pair1 xml b 1 a 0 a 0 b 1 a 0 a 0 x b 1 b 1 x a 0 a
13. 1 1 b 0 1 0 Caveat The fsm format is not really implemented in TAF KiT 1 4 1 It has been added in a way which is more a feasibility proof There are indeed two reasons for the limitations of the fsm format within VAUCANSON First the automata than can be described with the fsm format must meet several con ditions one initial state only labels are letters or integers that refer to a symbol table Second VAUCANSON does not code the weights correctly for OPENFST It is thus inade quate to try to use the fsm format for another automata than letterized Boolean automata with a unique initial state The following two examples of commands use the fsm format for Z automata The first one gives a correct answer as the weights are all equal to 1 the second one demonstrates that VAUCANSON is not even able to read correctly the fsm file it has written vcsn char z ofsm cat b1 xml ifsm eval bab 2 VAUCANSON 1 4 1 TAF K1T Documentation 27 July 14 2012 vesn char z ofsm cat c1 xml 11 0 O 0 1 0 1 2 0 2 1 0 0 vesn char z ofsm cat c1 xml vcsn char z ifsm ofsm cat le 0 00 0 0 O GOGG HEH OO amp The dot format produces dot files that can be processed and visualized using the GraphViz package The first two comand lines below are equivalent to the third one vcsn char b odot cat b1 xml gt b1 dot dotty b1 dot vcsn char b display b1 xml 2 1 3 2 Rational expression formats
14. 1i The procedure eliminates the spontaneous transitions of the automaton The result may not be defined for some automata of certain type For the consistency of the definitions in full generality we had to depart from the definition taken in 17 18 and consider a very restricted definition of validity of an automaton 14 15 For the weight semirings that are implemented in TAF Krr 1 4 1 however the new definition of validity amounts to the old one and an automaton is valid if and only if the family of weights of computations labelled by the identity is summable iii The spontaneous transition elimination algorithm implemented in VAUCANSON 1 4 1 is novel It is valid for automata whose weight semiring is positive such as K B Z min Z max or ordered with a positive part which is a subsemiring and a negative part which is the opposite of tbe positive part such as K Z Q R Finally the case of K F is treated separately Altogether the algorithm is valid for all instances of TAF KiT 1 4 1 It is documented in 14 15 Example We test the algorithme proper with the automaton prp tst1 xml described below and represented at Figure 3 2 We run indeed the test with a varying weight k for the spontaneous transition 3 from state 1 to state 2 k gt in the illustration below vcsn char q aa edit prp tst1 xml Automaton description States 0 1 2 3 Initial states 0 W 1 Final states 2 W 1
15. 66 July 14 2012 3 2 4 2 product vcsn product a xml b xml gt c xml Computes the product of a zml and b zml and writes the result in c zml Precondition i a zml and b zml are realtime automata and obey the two argument convention cf Section 3 1 3 ii This operation requires to be meaningful that the weight semiring be commutative and this is the case for all the instances implemented in TAF KtrT 1 4 1 Specification The product of a zml and b aml is by definition the accessible part of the automaton whose set of states is the cartesian product of the sets of states of the two automata and whose transitions are defined by k h kh YVp q EA Yr s B p4 and ros gt mr 255 as and the initial and final functions by VpE A VreB I p r I p I r and T p r T p T r Comments i The result c ml is a realtime automaton ii In terms of representations the representation of the product is the tensor product of the representations of the operands cf 17 Sect 111 3 2 Example Together with the command star alphabet product allows the projection over a subalphabet of an automaton vcsn char z al star alphabet gt ustar xml vcsn char z product c1 xml ustar xml gt clu xml vcesn char z display clu xml On pe ai 2 0 2 1 1 1211 cl xml 2 states 3 transitions I 1 T 1 clu xml 2 states 3 transitions 1 1 T 1 Figure 3 11 Projection of C over 1 VA
16. The following functions concern automata over a free monoid as opposed to automata over a direct product of free monoids Their behaviours are series over A that is weighted subsets of A A priori there is no assumption on the multiplicity or weight semiring However in VAUCANSON 1 4 1 TAF KIT gives access to automata with weight in numerical commutative semirings only The next two sections Section 3 3 and Section 3 4 will describe functions that are special to automata with multiplicity in a field R Q and F2 and in B respectively 1 Properties and transformations of automata transpose lt aut gt is realtime lt aut gt realtime lt aut gt is unambiguous lt aut gt partial identity lt aut gt partial erase lt aut gt characteristic lt aut gt support lt aut gt 2 Behaviour of automata 2 1 eval lt aut gt lt word gt 2 2 eval S lt aut gt lt word gt 3 From expressions to automata 3 1 standard lt ezp gt 3 2 thompson lt ezp gt 3 3 alphabet star alphabet 4 Operations on automata 1 quotient lt aut gt coquotient lt aut gt 2 product lt aut1 gt lt aut2 gt 3 power lt aut gt lt n gt 4 shuffle lt auti gt lt aut2 gt infiltration lt aut1 gt lt aut2 gt 3 2 1 Properties and transformations of automata The following function is not implemented It is just convenient to describe the specification of realtime Computes from a z ml an equiva
17. Transitions 1 From 0 to O labeled by 1 2 1 2 From 0 to 1 labeled by a 3 From 1 to 2 labeled by 1 2 1 4 From 2 to 1 labeled by 1 5 From 2 to 3 labeled by 1 6 From 3 to 1 labeled by 1 1 5 Often called also e transitions Vaucanson 1 4 1 TAF KiT Documentation 51 July 14 2012 Although there exists always an order to eliminating the spontaneous transitions such that one gets a valid automaton the behaviour of prp tst1 xml itself is defined if and only if k lt gt and this is to be detected by the algorithm prp tstl xml 4 states 6 transitions 1 1 T 1 Figure 3 2 A test for the algorithm proper 3 1 2 2 is standard standardize vcsn v is standard a xml Input is standard Tells whether or not the automaton a zml is standard Specification An automaton is said to be standard if it has a unique initial state which is the destination of no transition and whose initial multiplicity is equal to the unit of the multiplicity semiring vcsn standardize a xml gt b xml Transforms a zml into a standard automaton and writes the result in b aml Specification i If a zml is standard b aml a aml ii As a standard automaton is not necessarily proper nor accessible and the initial func tion of a state may a priori be any polynomial standardize is not completely specified by the definition of standard automaton and i above iii Roughly the procedure amounts to make real
18. k 1 E gt k E Ux Uk gt k 1 afk gt ke Table 2 5 The trivial identities These rewriting rules mean that it is impossible for VAUCANSON to output a rational expression such as 3 O0 ab 4 This expression is by construction equal to 4 1 as it can be verified with the following command vesn char z aab cat E 3 0 ab 4 4 1 This command cat E does not apply any algorithm to the rational expression Its only purpose is to read and write the rational expression using any I O option supplied on the command line The trivial identities are performed while reading the expression Caveat The definition of the identity Cat corresponds to what is implemented in VAUCAN SON 1 4 1 and is somehow a mistake A more natural definition would be m k gt k m with m any element of the monoid It may be corrected in forthcoming revisions of VAUCAN SON 1 4 1 if any Note that this identity raises a problem anyway It is consistent with common usage in the computation with series but not with the definition of operations on standard automata cf Section C 1 3 5 2 2 2 Parsing strings into expressions As we wrote above there are several classical ways of faithfully representing an expression by a string of symbols We are nevertheless faced with two and even three problems First we want to avoid the blotted form of marking languages and even of fully parenthe sised forms and to be able to u
19. or in any directory which is assigned by the usual Unix file path scheme As we mentioned in Section 1 1 every TAF KIT command first reads in the working directory and if the automaton is not found there it then reads from the data directory 2 3 1 data vcsn data a xml States 3 Transitions 6 Initial states 1 Prints some characteristic data on the automaton a zml cf Section 1 1 Final states 1 vcsn cat a xml gt b xml 2 3 2 cat Reads the automaton a zml and writes it in the file b zml Comments The cat function of VAUCANSON works very much in the same way as the Unix cat command and allows in the same way to write a file on the standard output or in another file The main difference is the behaviour described above the cat command first reads from the working directory and then from the data directory and thus allows to load predefined automata from the data directory to the working one The next difference is that the format of both the input and output may be controlled via the i and o options as described at Section 2 1 3 1 The cat function thus allows to convert a representation in one format into a representation in another one cf Section 2 1 3 1 for the shorcomings of the conversion between the xml and the fsm formats 2 33 cat E vcsn char b aab cat E emp Read the expression exp given as a string lt red ezp gt stores it in the memory and writes it back vcsn
20. 2 states 4 transitions 1 1 T 1 fx1 im xml 2 states 4 transitions 1 1 T 1 Figure 3 24 The domain and image of fx1 xml Caveat The results of domain and image could or should have been Boolean automata In TAF KirT 1 4 1 they are automata with the same weight semiring as the operand VAUCANSON 1 4 1 TAF KiT Documentation 87 July 14 2012 gee iano Beal a da Forgets the second component of the label and keeps the weight i i of the transitions of the transducer t sml and writes the result in the automaton a zml on A Precondition no precondition EPERE EE ee Forgets the first component of the label and keeps the weight Sa i of the transitions of the transducer t z ml and writes the result in the automaton b zml on B Precondition no precondition fx1 wdom xml 2 states 4 transitions 1 1 T 1 fx1 wim xml 2 states 4 transitions 1 1 T 1 Figure 3 25 The weighted domain and image of fx1 xm1 3 5 2 2 composition b composition As we shall see the composition algorithms of fmp transducers are defined on subnormalized ones only There are two distinct functions for the composition The first one composition yields a fmp transducer in which the number of paths is preserved It is the only one which makes sense for weighted fmp transducer The second one b composition is reserved for Boolean fmp transducers and yields a fmp transducer which is simpler but in which the number
21. 6 Rational operators VAUCANSON distinguishes indeed between two concatenation operators the classical con catenation of expressions as described in the above table and concatenation of letters or generators which form elements of the monoid and which remains implicit most of the time The default explicit notation for it is cf Table 2 7 Operators precedence The classical precedence relation between operators which allows to spare grouping symbols is extended in order to include the exterior multiplications and the concatenation of letters gt x gt k gt k gt gt For instance the rational expression which denotes the language that consists of all words that contain ab as a factor can be written by a user as atb ab at b VAUCANSON outputs it by making the product between non atomic subexpressions explicit vcsn char b aab cat E a tb rab a tb x a b ab a b vcsn char b aab cat E a b ab a b a b ab a b An atom which is enclosed in grouping symbols is not an atom anymore vcsn char b aab cat E a b a b Caveat because VAUCANSON builds rational expressions on top of words the Kleene star operator and the weights see below apply to words and not to letters as it is usually the case in other applications For instance ab is the same rational expression as ab for VAUCANSON but it is different from a b or a b
22. 97 ADe Repository ias ale eee a at e A i lea a als 97 ALO Lio SHACtOLY e e het toes oe Ged SL A eh E a E AA a ai 97 VAUCANSON 1 4 1 TAF K T Documentation 3 July 14 2012 B Vaucanson Graphical Interface VGI Belt sOverview ss ce ead esse sh og a ae Aine e la fe ay tt we B 2 Installation Latas ado eee Sd hein aoe ee Go bos p Eee do Bd B 2 1 ARequirements os acp rota ata hoe Qe hia A Al ee ei B 2 2 Installation and Start up 00000202 eee B 2 3 Getting and Compiling the Source Code B3 Using VG ereot ede ee A a doe ee ee Syd ad ade B 3 1 Create a New Automaton 002 200000002 B 3 2 Running Algorithms Provided by Vaucanson B33 LAYOUT A A oA a a Re a ie a C Algorithm specification description and discussion C 1 General automata and rational expressions functions Cael Graph functions mira A a hs tt ARA Ti C 1 2 Transformations of automata 2 2 0 00000002 eee C 1 3 Operations on automata osoa oa e a C 1 4 From automata to expressions 0 0 020500 C 2 Weighted automata and rational expressions over free monoids C 2 2 Behaviour of automata 1 C 3 Automata and rational expressions on free monoids with weights in a field C 3 1 Operations on automata e C 5 Weighted automata over a product of two free monoids C 5 2 Operations on transducers 2 2 e a Bibilography Index 99 99 99 99 10
23. It is realised by a traversal of the under lying graph of a zml It may imply a renumbering of the states vcsn coaccessible a xml gt b xml Computes the co accessible part of the automaton a zml and writes the result in b aml Specification coaccessible a xml reverse accessible reverse a xml 3 1 1 2 trim is trim vcsn trim a xml gt b xml Computes the trim part of the automaton a zml and writes the result in b aml Specification trim a xml coaccessible accessible a xml vesn v is trim a xml Taput is not trin Tells whether or not the automaton a zml is trim Specification is trim a xml is accessible a xml A is coaccessible a xml 3 As the functions of this section are valid for all instances of TAF KtT 1 4 1 the instance in the description is shown under the generic name vcsn Even if the functions is accessible and is coaccessible are not implemented the specification is clear VAUCANSON 1 4 1 TAF KiT Documentation 49 July 14 2012 3 1 1 3 is empty vcsn v is empty a xml Tague de nos 6npiy Tells whether or not the automaton a zml is empty 3 1 1 4 is useless vcsn v is useless a xml Tells whether or not the automaton a zml has successful com Input is has successful computations putations Specification is useless a xml is empty trim a xml Comments is useless is a graph function and tests whether there are successful computa tions in the automaton that is
24. a sequence of co terminal transitions the first one beginning in an initial state the last one ending in a final state By definition or by the way automata are specified in VAUCANSON each of these transitions have a non zero label This does not imply that the label of the computation itself is different from zero nor that the behaviour of the automaton is different from zero For instance the behaviour of the Z automaton usl xml of Figure 3 1 is the null series Nevertheles one has vcsn char z v is useless usl xml Input has a successful computation usl xml 2 states 2 transitions 1 1 T 1 Figure 3 1 The Z automaton usl xml 3 1 2 Transformations of automata 3 1 2 1 is proper proper vcsn v is proper a xml Tells whether or not the automaton a zml is proper Input is not proper Vaucanson 1 4 1 TAF KiT Documentation 90 July 14 2012 Specification An automaton is proper if it has no spontaneous transitions that is no transition labelled by the identity of the monoid empty word for free monoids the pair of empty words for product of free monoids If a transition is labelled by a polynomial and not by a monomial this means that the support of the polynomial does not contain the identity vcsn proper a xml gt b xml Computes a proper automaton equivalent to a zml and writes the result in b zml Specification i This procedure can be called for automata of any type
25. and writes the result in c aml Precondition i a zml and b zml are realtime automata and obey the two argument convention Vaucanson 1 4 1 TAF KiT Documentation 69 July 14 2012 ii This operation requires to be meaningful that the weight semiring be commutative Specification The infiltration of a zml and b zml is by definition cf 17 Sect III 3 2 6 the accessible part of the automaton whose set of states is the cartesian product of the sets of states of the two automata and whose transitions are those of the product and of the shuffle Example As for the shuffle the function expand is well suited for the presentation of the result the infiltration of words vesn char z infiltration ab xml ab xml Y aut to exp expand 2 aab 4 aabb ab 2 abab 2 abb Comments The infiltration product has been introduced under the name shuffle by Chen Fox and Lyndon in the study of the free group 7 It appears in identities between generalised binomial coefficients that is when counting the subwords cf 16 Chap 6 More precisely if E denotes the number of subwords of f equal to g and f tg the polynomial obtained by the infiltration of f and g it holds lt f T9 9 gt 7 g It is then easy to write a script that computes 2 write the following lines bin sh vesn char z a 1 exp to aut 2 gt tmp tmp1 xml vesn char z a 1 exp to aut 3 gt tmp tmp2 xml vesn char z infiltratio
26. are very different with respect to the functions which can be applied to them vesn char fmp b display trx xml vesn char fmp b 1tl to pair trx xml gt trx pair xml vcsn char char b complete trx pair xml Y complement gt trx pair cmp xml vesn char fmp b complete trx xml Y complement gt trx cmp xml vcsn char fmp b command complete doesn t exist AAA SH VAUCANSON 1 4 1 TAF KiT Documentation 86 July 14 2012 trx xml 2 states 4 transitions l 1 T 2 trx pair xml 2 states 4 transitions 1 1 T 2 trx pair cmp xml 3 states 12 transitions 1 1 T 1 Figure 3 23 A letter to letter transducer its pair of characters version and the complement 3 5 2 Operations on transducers 3 5 2 1 domain image w domain w image P Pn E E 3 Forgets the second component of the label and the weight of vcsn omain XM a xm DI 4 the transitions of the transducer t zml and writes the result in the characteristic automaton a zml on A Precondition no precondition de iis bii Forgets the first component of the label and the weight of the vcsn image XM XM aisle A 7 transitions of the transducer t zml and writes the result in the characteristic automaton b zml on B Precondition no precondition Comments The specification for image is taken so that the following identities hold image t xml domain inverse t xml and domain t xml image inverse t xml fx1 dom xml
27. b display c1spp xml cispp xml 2 states 5 transitions 1 1 T 1 Figure 3 10 The support of C 3 2 2 Behaviour of automata The function aut to exp and its variants cf Section 3 1 5 1 apply to these automata 3 2 2 1 eval vcsn eval a xml word Computes the coefficient of the word word in the series realized lt value gt by a zml Precondition i a zmlis realtime ii word is a sequence of letters in the input alphabet of a zml the generators of A Example vesn char z power c1 xml 10 gt c10 xml vesn char z eval c10 xml 10 1024 Caveat The parameter word must be a sequence of letters and not an expression which denotes a word cf Section 2 1 3 3 Tef Section 3 2 4 3 VAUCANSON 1 4 1 TAF KiT Documentation 64 July 14 2012 vcsn char z eval c10 xml 1 0 FATAL Cannot parse 1 0 Comments cf Section C 2 2 1 for the description of the algorithm 3 2 2 2 eval S vcsn eval S a xml word Computes the coefficient of the word word in the series realized lt value gt by a aml Precondition i No condition on a zml ii As for eval word is a sequence of letters in the input alphabet of a zml Specification eval S a xml word eval realtime a xml word 3 2 3 From expressions to automata 3 2 3 1 standard vcsn standard e xml gt a xml Computes the standard automaton of e zml and writes the result in a zml Specification We call
28. can then be used to modify the way the object will be output vcsn char b a parser OPAR CPAR oxml cat E gt p xml vecsn char b ixml cat E p xml C Soe oe vcsn char b parser OPAR lt CPAR gt ixml cat E p xml lt lt gt gt x If we edit the file p xml and suppress the writing data in it and write the result in the file pp xm1 we then get the output with the default values for the tokens vesn char b ixml cat E pp xml CC EC 2 2 3 TAF Kit IO functions We end this chapter with the description of the input and output commands available within TAF KiIT The other commands that perform computations on the automata and expressions are described in the next chapter 1 data lt aut gt 2 cat lt aut gt 3 cat E lt ezp gt 4 display lt aut gt 5 edit lt aut gt 6 gui lt aut gt 2 3 0 Data file location TAF KTIT works or a user works with TAF KIT in a current directory called working direc tory On the other hand every instance vcsn xxx y of TAF KIT knows a directory called data directory located at vaucanson 1 4 data automata xxx y and where automata pre defined by VAUCANSON are stored The latter form the automata repository of the instance cf Section 1 2 5 See Appendix A for the list of automata in each repository VAUCANSON 1 4 1 TAF KIT Documentation 41 July 14 2012 Every TAF KtT command writes in the working directory
29. char b oxml cat E ezp gt e xml as a string by default vcsn char b ixml cat E e xml It can also read and write the expression as lt red ezp gt an XML file Comments The different behaviours of the cat E function according to the possible formats have been described at Section 2 1 3 2 Note that the shell syntax may be combined with the TAF KIT options for format For instance the following command will read a string from the file lt file gt vcsn char b aab cat E cat lt file gt A rational expression output by cat E is in reduced form cf Section 2 2 1 2 VAUCANSON 1 4 1 TAF KIT Documentation 42 July 14 2012 vcsn display a xml vcsn edit a xml 2 3 4 display Display the automaton a zml via Graphviz Comments The same functionality may be achieved by outputting the automaton a aml in the dot format and then calling dotty directly cf Section 2 1 3 1 The possibility of using VGI a graphic interface written within the VAUCANSON project will be given as soon as possible 2 3 5 edit Create and edit the automaton a azml via keyboard interface Comments This command edit provides a textual interface to define automata interac tively It takes as argument the filename of the automaton to be defined or modified If the file does not yet exist the alphabet of the automaton should be specified on the command line using the alphabet or a option as with any other command a
30. characters Z x vcsn int fmp b transducers integers B V A vcsn int fmp z transducers integers Z x Table 1 3 The TAF KIT instances in VAUCANSON 1 4 1 is how they should be called from the she11 and the type of automata they allow to work with The first part of the table shows Boolean automata The first instance where the letters are characters corresponds to classical automata and has been used in the First contact section The next instance handles Boolean automata whose letters are integers the three others support alphabets of pairs All of these are called Boolean automata because each word is associated with a Boolean weight either the word is accepted and its weight is true or it is not and its weight is false The instances for weighted automata are listed in the second part of Table 1 3 The first four instances work with automata with weights in the ring of integers and over free monoids with different types of generators the next five work with automata over a free monoid of characters and with weights in different semirings The third part shows the transducers instanciated in VAUCANSON 1 4 1 they are called fmp transducers where fmp stands for free monoid products 4 1 2 3 Command options Every TAF KIT instance determines the weight semiring and the type of letters in the alpha bet s This is sufficient at compile time but when a TAF KIT command is executed some This name or precision
31. commands of TAF Krr all other commands are presented in the next chapter 1 1 First contact Let us first suppose that VAUCANSON is fully installed as explained in Section 0 4 1 Any of the following commands could be typed and their results observed We describe now some of the functions of the instance of TAF KiT which deals with classical automata that is Boolean automata over a free monoid whose generators are characters These functions are called by the vcsn char b command To begin with we have to deal with an automaton of the correct type There are several means to build or define such an automaton but the most direct way is to use one of those If VAUCANSON is only compiled without being installed one should first go to the vaucanson 1 4 1 taf kit tests directory by a cd command and type vcsn char b instead of vesn char b for each of the following commands 12 whose definition comes with TAF Krr We choose the automaton A shown at Figure 1 2 and whose description is contained in the XML file a1 xml Figure 1 1 The Boolean automaton A over a b The first command data will just make sure that TAF KIT knows about this automaton It will display the number of states transitions initial states and final states of A1 vcsn char b data al xml States 3 Transitions 6 Initial states 1 Final states 1 This automaton a1 xml can also be displayed with the command di
32. equivalent or not For several reasons we distinguish indeed between expressions that are obviouly equiva lent such as E F and F E or E F 6G and E F G There are however expressions which can be constructed by the above rules such as E 0 or 1 E and which we do not want to exist Such convention are not only useful for simplifying expressions they are also necessary to make some computation processes such as derivation finite Everytime a rational expression is constructed inside VAUCANSON either as the result of a computation or as the mere consequence of the reading of a string of symbols that represents it the following rewriting rules called trivial identities and listed in Table 2 5 are automatically applied giving rise to a so called reduced expression which is obviously equivalent to the original expression Vaucanson 1 4 1 TAF KiT Documentation 32 July 14 2012 In this table E stands for any rational expression x is any monoid generator that is a letter or a pair of two letters or a pair of a letter and 1 k and h are weights while 0x and 1g designate the zero and unit of the weight semiring Any subexpression of a form listed to the left of a gt is rewritten as indicated on the right E0 0 0 E gt 0 E 40 gt E 0 E gt E ESE 1EsE 0 1 T 0K E 0 E 0g gt 0 k 0 0 O k 0 Ik ES gt E Eflx gt E Tk k AFE kh E E k A E kh k E h k E h E k 1 gt E k
33. exe cution of the function it is called with and outputs it on the standard error output It is recommanded to divert it with the 2 gt redirection to a file which will be exploited afterwards The example below shows only some lines the most important ones of this file vcsn char b T1 determinize ladybird 10 xml gt 1db10det xml 2 gt 1db10 time txt cat 1db10 time txt Taf kit command bench Charge id lt name gt total self calls self avg total avg 100 0 0 _program 216 89ms 216 89ms 1 0 22s 0 22s 62 8 9 automaton output 136 23ms 136 23ms 1 136 23ms 136 23ms 30 2 7 determinize 65 57ms 65 54ms 1 65 54ms 65 57ms 4 2 1 CMD O determiniz 80 51ms 9 11ms 1 9 11ms 80 51ms 2 5 2 automaton input 5 50ms 5 50ms 1 5 50ms 5 50ms 0 1 4 eps_removal 0 16ms 0 16ms 1 0 16ms 0 16ms 0 1 3 cut_up 0 l5ms 0 15ms 1 0 15ms 0 15ms 0 0 8 is_realtime autom 0 03ms 0 03ms 1 0 03ms 0 03ms 0 0 5 accessible_states 0 02ms 0 02ms 1 0 02ms 0 02ms 0 0 6 sub_automaton 0 00ms 0 00ms 1 0 00ms 0 00ms The content of the time statistics output is controlled by an integer called VERBOSE_DEGREE and which can take the values 1 2 or 3 Default value is 2 The automaton ladybird 10 xml has been built beforehand by the factory ladybird char b The com putation has been done on a MacBook Pro with a 2 GHz Intel Core i7 processor Vaucanson 1 4 1 TAF KiT Documentation 30 July 14 2012 The D and X options have the same behaviour as T but o
34. fa bY 92 A 1 1 3 evena xml Figure A 3 The Boolean automaton evena xml over a b A 1 1 4 oddb xml Figure A 4 The Boolean automaton oddb xml over fa b A 1 2 Factory The following programs are in the data automata char b directory A 1 2 1 Program divkbaseb E er aes eee Generates an automaton over the digit alphabet 0 b 1 AS A that recognises the writing in base b of the numbers divisible by the integer k Comments The divisor div3base2 xml Figure A 5 is already in the repository Figure A 5 The divisor div3base2 xml over 0 1 A 1 2 2 Program double_ring Generates an n state automaton over the al phabet a b that consists in a double ring of double_ring 6 1 3 4 5 gt double 6 1 3 4 5 xml A transitions a counter clockwise ring of tran sitions labelled by a and a clockwise ring of transitions labelled by b Specification VAUCANSON 1 4 1 TAF KiT Documentation 93 July 14 2012 The states are labelled from 0 to n 1 State O is initial The number of states n is the first parameter and the next parameters give the list of final states Figure A 6 shows the automaton built by the above command Comments The double ring automata are closely related to the star height problem Schiitzen berger used them to give the first example of automata over a 2 letter alphabet that have arbitrary large loop co
35. list commands 1 List usual commands list all commands L List all commands including debug commands list automata List predefined automata Table 2 1 Information options 2 1 2 Alphabet specification The necessity of alphabet specification As we have seen Section 1 2 2 every TAF KIT instance determines or one could say is determined by the type of the letters that generate the free monoid s over which the automata or the rational expressions are built And this is sufficient at compile time that is in order to generate TAF KIT But VAUCANSON and the TAF Krr functions are designed in such a way that they need to know the complete type of an automaton or an expression in order to handle it that is not only the type of weights and of letters but also the set of letters that constitute the alphabet s The XML files which describe automata or expressions contain this information and are so to say self contained For instance when we read a1 xml in Section 1 1 and determinized this automaton we did not have to tell TAF KtT that the alphabet was A a b On the contrary when the automaton or the expression does not exist prior to the TAF KIT function then specifying an alphabet is mandatory For instance the following commands end in error vesn char b edit aut xml Error alphabet should be explicitly defined using alphabet vcsn char b exp to aut abata Error alphabet should be explicitly define
36. long execution time 3 1 4 Operations on behaviour of automata These functions implement somehow one direction of Kleene s theorem by building standard automata which realize the rational operations on the behaviour of the parameters the S stands for series as the behaviour is a series in general 3 1 4 1 sum S g Timis a Build a standard automaton whose behaviour is the sum of a xm XM c xm m n r repa aee the behaviours of a zml and b zml and writes the result in c xml Precondition No precondition besides the two argument convention Specification sum S a xml b xml sum standardize a xml standardize b xml 3 1 4 2 cauchy S ee eee eee ee Build a standard automaton whose behaviour is the Cauchy Vv v product of the behaviours of a zml and b zml and writes the result in c aml Precondition No precondition besides the two argument convention Specification cauchy S a xml b xml concatenate standardize a xml standardize b xml Comments The terminology used here is meant to recall that the product of behaviours of automata seen as series is the Cauchy product and corresponds to the concatenation of automata when they are standard automata and not to their product The latter is defined for realtime automata over a free monoid only cf Section 3 2 4 2 Vaucanson 1 4 1 TAF KiT Documentation 56 July 14 2012 3 1 4 3 star S vcsn star a xml gt b xml Build a sta
37. of paths is not preserved vcsn composition t xml u xml gt v xml Realizes the composition algorithm on t aml and u 2ml and writes the result in v ml Precondition t zml and u zml are subnormalized with matching monoids output of t zml input of u zml and same weight semirings Specification The composition algorithm used in T AF KTT is described at Section C 5 2 2 Comments When the weight semiring is not complete it may be the case that the compo sition is not defined in which case the call to composition will produce an error r o 3 i Realizes the Boolean composition algorithm vcsn composition xm u xm V Xm P P on t zml and u zml and writes the result in v aml Vaucanson 1 4 1 TAF KiT Documentation 88 July 14 2012 Precondition t zml and u zml are subnormalized with matching monoids output of t zml input of u zml and Boolean weight semiring Specification The Boolean composition algorithm is described at Section C 5 2 2 and goes roughly as follows 1 performing the product of t zml and u aml 2 make the result proper Example Figure 3 26 shows the b composition and the composition of the fmp transducers t1 xml and ul xml that are taken as examples at Section C 5 2 2 cf Figure C 1 and Fig ure C 2 vcsn char fmp b b composition t1 xml u1 xml Y display vcsn char fmp b composition t1 xml u1 xml Y display Note that the b composition is not trim 6
38. of this type of automata whithin TAF KIT which already allows to demonstrate the usefulness of going forth and back between the class of transducers and the one of automata cf Figure 3 23 1 Transformations of automata 1 1 first projection lt aut gt second projection lt aut gt 1 2 pair to fmp lt aut gt 3 6 1 Transformations of automata 3 6 1 1 first projection second projection vcsn first projection a xml gt b xml Yields an automaton over B resp C by keeping the first resp second component of every letter 3 6 1 2 pair to fmp vcsn pair to fmp a xml gt t xml yields a fmp transducer over B xC every letter b c being mapped to the corresponding element of B xC Specification A transition labelled by a x b x a y becomes a transition labelled by aba zzy VAUCANSON 1 4 1 TAF KiT Documentation 91 July 14 2012 Appendix A Automata repository and factory The VAUCANSON 1 4 1 distribution contains a folder data automata where a number of automata and of VAUCANSON programs which build automata are ready for use by the TAF KIT commands A 1 B automata A 1 1 Repository The following automata files are stored data automata char b directory and accessible by the command vcsn char b cat A 1 1 1 ai xml for A Figure A 1 The Boolean automaton A over a b cf Figure 1 2 A 1 1 2 b1 xml for B Figure A 2 The Boolean automaton B over
39. other value for false The shell makes this value available in the variable The TAF KIT option verbose or v can be used to request an explicit output of this value vcsn int b is empty coins xml echo 1 vcsn int b v is empty coins xml Input is not empty VAUCANSON 1 4 1 TAF KiT Documentation 29 July 14 2012 2 1 4 Benchmarking options The functions in VAUCANSON library are interspersed with instructions which trigger time measurement in case some dedicated variables are set up in a certain way This feature is primarily intended to the adjustment and improvement of the programming of the library rather than to the benefit of TAF KIT users It can nevertheless be activated through TAF KIT by instantiating some options As they appear when the help option is called we list them in Table 2 4 and briefly present them afterwards We do not fully document these options as they are anyway not yet finalized long option short purpose of the option report time VERBOSE_DEGREE T Report time statistics export time dot VERBOSE_DEGREE D Export time statistics in DOT format export time xml VERBOSE_DEGREE X Export time statistics in XML format bench NB_ITERATIONS B Bench bench plot output OUTPUT FILENAME 0 Bench output filename Table 2 4 Benchmarking options and formats 2 1 4 1 Time statistics The report time option T for short builds a file with some time statistics for the
40. quickly define a Boolean automaton with symbols a and b in the alphabet 4 A majority of VGI s functions are available in the context pop up menu after clicking the right mouse button on an object Try clicking the right mouse button anywhere in the empty space in the newly created untitled window and the Add State option will appear Vaucanson 1 4 1 TAF K1T Documentation 101 July 14 2012 5 Click the right mouse button on the newly added state s0 and different options appear Select the Add Transition From option 6 Click the right mouse button on the state s0 again and select the Add Transition To option 7 A loop transition is added to the state s0 VAUCANSON 1 4 1 TAF K1T Documentation 102 July 14 2012 8 Add another state s1 and add a transition from s0 to sl 9 Double click on the transition from s0 to sl and the Weighted Regular Expression Editor appears 10 Click on the Alphabet Symbol drop down menu and select b Then click on the OK button VAUCANSON 1 4 1 TAF K1T Documentation 103 July 14 2012 B Weighted Regular Expression Editor Xx 11 11 Click on the state s0 and check the Initial State check box in the properties panel on the left hand side of the window to set s0 as an initial state 12 Continue editing the automaton until it appears as the screenshot below which contains a Bool
41. realtime ve Pages e Computes from a zml an automaton by eliminating the spon vcsn rea ime a xm XM Saat z taneous transitions from the letterized version of a zml and writes the result in b aml Specification realtime a xml proper letterize a xml Comments i The problem with realtime is the same as the one of proper and has been mentioned at Section 3 2 4 2 ii letterize proper a xm1 is another realtime automaton which has potentially many more states and transitions than realtime a xml Such automata cannot be built by the edit function and will not be considered within TAF KIT 1 4 1 scalar end function condition Vaucanson 1 4 1 TAF KiT Documentation 61 July 14 2012 3 2 1 3 is unambiguous vcsn v is unambiguous a xml E A E Tells whether or not the automaton a zml is unambiguous Input is unambiguous Precondition a zml is a realtime automaton Specification An automaton is unambiguous if every word accepted by the automaton is the label of only one successful computation Comments i Being ambiguous or unambiguous is classically a property of Boolean automata We have found interesting to extend the definition to any weighted automata ii The function implements the following characterization of unambiguous automata which yields an algorithm of polynomial complexity An automaton A is ambiguous if and only if the trim part of the product Ax A contains a state outside of the dia
42. script is bin sh f tmp pd png if test x 1 x then dot Tpdf gt f else dot Tpdf gt f fi xpdf f rm f f 0 7 VGI The availability of the Graphical User Interface VGI developped at NTU is one of the novelty of VAUCANSON 1 4 1 with respect to VAUCANSON 1 4 Every instance of TAF KIT has a function gui that launches VGI cf Section 2 3 For this function to work TAF KtrT needs to be specified where is VGI Download the vgi jar archive from http vaucanson project org resources vgi jar store it in a folder denoted by path to vgi folder in the following There is two methods to specify to VAUCANSON where this archive is stored either by setting the environment variable VGIJAR with the command VAUCANSON 1 4 1 TAF KiT Documentation 10 July 14 2012 000 Xx DOTTY O 1 O al xml 3 states 6 transitions 1 1 T 1 ja b D 1 1 v al xml 3 states 6 transitions I 1 T 1 Figure 1 Two versions of the Graphviz application export VGIJAR path to vgi folder vgi jar or by puting the following script named vgi in a directory of the path for instance usr local bin bin sh exec java jar path to vgi folder vgi jar 0 and making it executable A call to the gui function will then open a window such as the one shown at Figure 2 cf Appendix B Figure 2 The VGI window Vaucanson 1 4 1 TAF KIT Docum
43. the existence of this token is hardly noticeable when one uses alphabet of characters as its default value in this case is the empty string as well It is necessary to explicitely give it a non empty value in order to make it appear vcsn char b aab cat E aba bab aba bab vcsn char b aab parser CONCAT cat E aba bab a b a b a b This token is useful and necessary when the generators of the monoid that is the letters are not characters but written as sequences of symbols In TAF Krr 1 4 1 this happens for the instances in which the type of letters are integers In this case the default value of CONCAT is The token is necessary when the set of letters viewed as a set of words on the alphabet of digits is not a prefix code vesn int b a 0 1 2 cat E 10 12 21 x 140 1 2 2 1 vcsn int b a 0 1 12 22 cat E 10 12 122 vcsn int b Lexer error unrecognized characters 2 vesn int b a 0 1 12 22 cat E 10 12 1 22 1 0 12 1 22 One understands that the parser matches the longest prefix of the string it reads with the letters of the alphabet The token SPACE The token SPACE is meant to be a character or a string that is equivalent to the empty sequence and that makes the writing of expressions as strings more readable by the users Of course its default value is the space character and is likely to keep this value unless the space character itself i
44. the options 2 parse all expected arguments using indications that may have been given by options VAUCANSON 1 4 1 TAF KiT Documentation 18 July 14 2012 3 execute the algorithm 4 print the result in a format that can be controlled using options When commands are chained internally using and the printing step of the com mand before the and the parsing step of the command after the are of course omitted 1 2 5 Automata repository and factory Most of TAF KIT functions allow to build automata from other ones There are functions which take a rational expression and yield an automaton that accepts the language denoted by the expression and a function edit that allows to define or to transform an automaton element by element cf Section 2 3 6 Other features of TAF KIT for the definition of automata are the automata repository and the automata factory 1 2 5 1 Automata repository With our first example cf Section 1 1 we mentioned that an automaton a1 xml is ready and available to the functions of the instance vcsn char b There exist some other automata for the same purpose and such automata also exist for other instances of TAF KtT 1 4 1 their list is available via the option list automata vcsn char b list automata The following automata are predefined al xml b1 xml div3base2 xml double 3 1 xml ladybird 6 xml For every TAF KIT instance vcsn xxx
45. they are read from a file whose filename is specified on the com mand line and the file is output on the standard output or can be diverted to a named file in the Unix way VAUCANSON can read automata in two formats FsM XML the default format or in a textual format called fsm and which is close to the one used in OPENFST It can write automata in these two formats as well as in the dot format that can then be used for graphical output afterwards VAUCANSON 1 4 1 TAF KiT Documentation 26 July 14 2012 long option short purpose of the option input i select input format for automata and rational expressions output o select output format for automata and rational expressions verbose v select verbose option for Boolean results i values o values format for automata format for rational expressions none none Fsm XML text string xml xml Fsm XML Fsm XML fsm fsm OPENF ST dot dot exp exp text string fpexp fpexp text string Table 2 3 Input and output options and formats The xml format is the default format for input and output automata to and from VAU CANSON It is defined by the Fsm XML format whose complete description will be given in a forthcoming technical report cf also 10 The fsm format has been defined within the AT amp T FSM Library Finite State Machine Library 2 and used in the OPENFST library 3 vcsn char b ofsm cat b1 xml 0 0 a 0 0 0 b 0 0 1 b 0 1 1 a O
46. to be under the string format the i and o options have no effect on this function 3 5 3 Operations on behaviours of transducers 3 5 3 1 composition R tea ds 1 Computes a transducer that realizes the com vcsn composition Xm u xm vV xm ANA x y R position of the relations realized by t zml and u zml and writes the result in v xml Precondition t zml and u zml have matching monoids output of t zml input of u zml and the same weight semiring Specification composition R t xml u aml composition subnormalize t xml subnormalize u xml VAUCANSON 1 4 1 TAF KiT Documentation 90 July 14 2012 3 6 Weighted automata on free monoids over alphabets of pairs An alphabet of pairs A is defined by a pair of alphabets B and C and letters in A are pairs b c with bin B and cin C The alphabet A is thus a subset of B xC Bx C is easily identified with a subset of B x C and in this way some functions apply to automata over A that correspond to functions on automata over B x C The alphabets of pairs are the key to several constructions on automata and transducers One example is when letters within an expression or an automaton are indexed another one is the treatment of letter to letter transducers as automata on a free monoid In TAF Krr 1 4 1 there are not many functions special to automata over such alphabets There will be more in subsequent versions At this stage what is more important is the mere existence
47. used to get all the prerequisites and should be installed first on the computer see http www macports org A complete guide to its installation is available from http guide macports org If macports is already installed it should be made up to date by synchronising the local port tree with the global macports ports by the following command sudo port selfupdate Three libraries are to be installed in order to build VAUCANSON see Prerequisite for details Boost Xerces and Ncurses sudo port install ncurses sudo port install boost sudo port install xercesc Note that executing each of these commands may take a while especially when installing Boost By default macports will install each of these three libraries in the opt local directory which is not standard with respect to the Unix organisation In order to build VAUCANSON this directory is therefore to be specified to the configure command by the following options configure CPPFLAGS I opt local include LDFLAGS L opt local lib g P P Moreover if the installed version of Boost is greater than or equal to 1 44 it is necessary to add another option to the configure command configure CPPFLAGS I opt local include DBOOST_SPIRIT_USE_OLD_NAMESPACE LDFLAGS L opt local 1lib The installation is then to be completed by the usual two commands make sudo make install 0 6 Improving the display quality As long as a dedic
48. well produce an automaton which will look more complicated than the original one especially when the latter is already of minimal dimension Figure 3 14 shows such an example cc2q xml 3 states 6 transitions 1 1 T 1 cc2r xml 3 states 12 transitions 1 1 T 1 Figure 3 14 The quotient of cc2 xml and its reduction VAUCANSON 1 4 1 TAF KiT Documentation 71 July 14 2012 ii The computation of reduced representations implies the exact resolution of linear sys tems of equations which becomes problematic when the dimension of the systems grows The following example shows an error occurs when dealing with systems of dimension 32 in R ou 1024 in Q the number of states should be 6 in the first case 11 in the second vcsn char r power c1 xml 5 reduce Al data States 10 Transitions 88 Initial states 1 Final states 1 vcsn char q power c1 xml 10 Y reduce NYl data States 25 Transitions 444 Initial states 1 Final states 1 3 3 1 2 are equivalent vcsn v are equivalent a xml b xm Tells whether or not the automata a zml and b zml realize Automata are not equivalent the same series Precondition no precondition Specification are equivalent a xml b xml is empty reduce sum standardize realtime a xml left mult standardize realtime b xml1 1 3 3 2 Operations on expressions 3 3 2 1 are equivalent E vcsn v ixml are equivalent E e xml
49. y the XML files for these automata are located at in a special directory vaucanson 1 4 data automata xxx y cf Section 2 3 0 More details on these automata are given at Appendix A 1 2 5 2 Automata factory In the same directory as the automata quoted above some programs have been compiled which generate new automata depending on parameters given to the program The name of the program is suffixed by the characteristic part of the name of the TAF KIT instance For instance the program divkbaseb char b generates the automaton that accepts the rep resentation in base b of numbers divisible by by k divkbaseb char b 5 3 gt divbbase3 xml vcsn char b data div5base3 xml States 3 5If VAUCANSON is only compiled without being installed one should first go to the vaucanson 1 4 1 data automata char b directory by a cd command and type divkbaseb char b instead of divkbaseb char b in the command of the example Vaucanson 1 4 1 TAF KiT Documentation 19 July 14 2012 Transitions 6 Initial states 1 Final states 1 We give another example of construction of an automaton with the factory at Section 2 1 4 The list of automata factories is also given at Appendix A Vaucanson 1 4 1 TAF KiT Documentation 20 July 14 2012 Chapter 2 Specification of options and IO functions The list of possible options of a TAF KIT command is obtained with the classical help option They fall in t
50. 0 100 100 100 105 106 108 108 108 108 110 113 114 114 114 114 115 115 118 120 VAUCANSON 1 4 1 TAF K1T Documentation 4 July 14 2012 Introduction VAUCANSON is a free software platform dedicated to the manipulation of finite state automata Here finite state automata is to be understood in the broadest sense VAUCANSON supports weighted automata over a free monoid and even weighted automata on some non free monoids currently only automata on products of two free monoids also known as transducers are supported From user s point of view the platform consists in two main components The VAUCANSON library is a C library that implements objects for automata rational expressions as well as algorithms on these objects This library is written under the static genericity paradigm TAF Kit is a command line interface to the library that allows user to execute VAUCAN SON s algorithms without any knowledge of C nor of VAUCANSON API This interface is instantiated for a predefined set of commonly used automaton types The platform is coupled with two other communication modules An XML format for automata and expressions called FSM XML aims at being a gen eral purpose interchange format for weighted automata and regular expressions It is used as the normal and default input and output format for TAF KIT and thus for the communication between TAF KIT and VGI A Graphical User Interface called
51. 0 x 1 a 0 vcsn char char b second projection ex pair1 xml vcsn char b aut to exp 1 0 0x 1 0 0 1 1 x 0 0x e 0 0x e vcsn char char b pair to fmp ex pair1 xml gt ex fmp1 xml vcsn char fmp b aut to exp ex fmp1 xml 6b 1 a 0 a 0 x b 1 a 0 a 0 x b 1 b 1 x a 0 a 0 x 1 a 0 vcsn char fmp b image ex fmp1 xml vcsn char b aut to exp 1 0 0x 1 0 0 1 1 x 0 0x e 0 0x e For integer alphabets the constant 1 and the empty word on one hand the constant 0 and the null series on the other are always that is even if the integers 1 or 0 are not in the alphabet written as e and z respectively vcsn int z a 2 3 expand 2 1 2 z vcsn int z a 2 3 expand 2 1 2 x e 2 2 3 2 Explicit parametrization the parser option Table 2 7 shows the tokens that are used in the writing of rational expressions within VAU CANSON together with their meaning and default values The parser option can be used to modify the values of these tokens Each of them must be defined as a non empty string This ability of the user to define the tokens at will allows to use characters of any kind as letters of the alphabet For instance one may define the language of well parenthetized words of nested depth at most 2 over the alphabet for which one should obviously rename the OPAR and CPAR tokens vesn char b a parser OPAR CPAR
52. Ep Eo T It is important to note that it is not true that A is necessarily defined when Eo and thus I Eo Ep Eo T are defined cf 17 18 for more details and example The algorithm whose implementation depends indeed on K has the double goal of deciding if the behaviour of Ay is defined and of computing Ep Ep and Ep T It will be described in 15 C 1 2 2 standardize An automaton is said to be standard if it has a unique initial state which is the destination of no transition and whose initial multiplicity is equal to the unit of the multiplicity semiring VAUCANSON 1 4 1 TAF KiT Documentation 109 July 14 2012 Not only every automaton is equivalent to a standard one but a simple procedure called standardization transforms every automaton A in an equivalent standard one The difficulty in specifying standardization comes from the fact that on the one hand side a standard automaton is not necessarily proper nor accessible and on the other the initial function of a state may a priori be any polynomial The procedure goes as follows i Add a new state s make it initial with initial multiplicity equal to the unit of the multi plicity semiring ii For every initial state i of A with initial function add a transition from s to i with label i and set i to Ox the zero of the multiplicity semiring which is equivalent to say that i is not initial anymore iii Supp
53. Function Kit In the static generic programming paradigm used in the VAUCANSON library the types of the automata that are treated have to be known at compile time The command line interface TAF KIT is a set of programs called from the she11 and used to chain operations on automata At the installation of VAUCANSON TAF KIT is therefore compiled for several predefined types of automata TAF KIT does not allow to write new algorithms nor to manipulate new types of au tomata but it makes it possible without efforts to use already programmed functions on automata of predefined types TAF KIT gives a restricted access to VAUCANSON functionali ties but it is a direct access without any need of programming skill A basic familiarity with Unix command syntax only is sufficient to make use of TAF KIT The type of an automaton is determined by a the fact it is an automaton over a free monoid or over a product of two free monoids b the type of the generators of the free monoid s c the weight semiring The weight semiring can be B Z Q R Fo Zmin or Zmax The generators may be characters integers or pairs of these At the installation of VAUCANSON TAF KIT is instanciated for 18 combinations of weights and generators types Besides basic editing commands most of classical operations on automata together with less classical ones are available in the TAF KIT instances from transformations of automata into expre
54. LEDGEMENTS Since March 1st 2011 the work on the VAUCANSON platform is supported by the Agence Nationale de la Recherche with the project ANR 10 INTB 0203 The work on the Graphical User Interface VGI is supported by the NSC 100 2923 E 002 001 MY3 project since January 1st 2011 Introduction Table of contents O Getting started Od Getting VAUCANSON LAL ci dc a Bae eo es nd Rk Me da 0 27 EI Cenin ee a e ea a a A AA A A ag ca 0 3 Prerequisites dto sii di ee A ia a ty BN dee a 0 4 Building VAUCANSON 0 0 0 000 ee ee 0 5 MacOSX specifics ee 0 6 Improving the display quality o o e e e 0 6 1 Graphviz for Mac easier echo oe a a A N a 0 6 2 Graphviz for Linux snk ee Ore Sok Gok tS ee BA ia 0 VGD oe Scaling to So ee a ee ed O aa ek GOR ood 1 Presentation of TAF Kit Del Pirstscontacts reia Sok Sa teas ete RIA AOE ee a See ent TAS 1 2 TAF KIT Organisation L21 Automata types enana a aa ee ae ala 1 2 2 TAP KIT instances s reaa o DoE E ai r iK A E a ea a i 1 2 3 Command options 2 3 2 0 26 a eee ena ad a a a 1 2 4 TAF KIT S modus operandi ooa a 0005 1 2 5 Automata repository and factory 2 000 2 Specification of options and IO functions 2 1 Simple options s lt a x wwe Oat ain Ses a Be ae Wh be Re ea 2 1 1 Information options 0 00000 eee eee 2 1 2 Alphabet specification o e 2 1 3 Input and output formats
55. LGADO J MORAIS Approximation to the smallest regular expression for a given regular language Proc CIAA 2004 LNCS 3317 Springer 2004 312 314 10 A DEMAILLE A DURET LUTZ F LESAINT S LOMBARDY J SAKAROVITCH AND F TERRONES An XML format proposal for the description of weighted automata trans ducers and regular expressions Post Proc FSMNLP 2008 J Pikorski B Watson A Yli Jyra eds IOS Press 2009 199 206 11 CH FROUGNY J SAKAROVITCH Number representation and finite automata in Combinatorics Automata and Number Theory V Berth M Rigo eds Cambridge University Press 2010 34 107 12 S LOMBARDY J SAKAROVITCH Derivatives of rational expressions with multiplicity Theoret Comput Sci 332 2005 141 177 118 13 S LOMBARDY J SAKAROVITCH The Universal Automaton in Logic and Automata History and Perspectives J Flum E Gradel Th Wilke eds Amsterdam Univ Press 2007 457 504 14 S LOMBARDY J SAKAROVITCH The Removal of Weighted e Transitions Proc CIAA 2012 LNCS 7381 Springer 2012 345 352 15 S LOMBARDY J SAKAROVITCH On the weighted closure problem in preparation 16 M LOTHAIRE Combinatorics on Words Addison Wesley 1983 Reprint Cambridge University Press 1997 17 J SAKAROVITCH l ments de th orie des automates Vuibert 2003 English corrected edition Elements of Automata Theory Cambridge University Press 2009 18 J SAKAROVITCH Ration
56. UCANSON 1 4 1 TAF KiT Documentation 67 July 14 2012 3 2 4 3 power vcsn power a xml n gt d xml Computes the product of a zml by itself n times and writes the result in d zml Precondition i a zmlis realtime ii This operation requires to be meaningful that the weight semiring be commutative and this is the case for all the instances implemented in the TAF KiIrT 1 4 1 Specification vcsn power a xml 0 gt ustar xml where ustar xml is the one state automaton initial and final with one transition for every letter of the alphabet of a xm1 which accepts the whole free monoid and which is the identity element for the power of automata Example vcesn char z power cc1 xml 2 gt cc2 xml vcsn char z quotient cc2 xml 2 gt cc2q xml CDa l v ccl xml 2 states 3 transitions 1 1 T 1 cc2 xml 4 states 9 transitions 1 1 T 1 cc2q xml 3 states 6 transitions 1 1 T 1 Figure 3 12 The Z automaton cc1 xml its square cc2 xml and the quotient of cc2 xm1 3 2 4 4 shuffle infiltration vcsn shuffle a xml b xml gt c xml Computes the shuffle of a aml and b zml and writes the result in c zml Precondition i a zml and b zml are realtime automata and obey the two argument convention ii This operation requires to be meaningful that the weight semiring be commutative and this is the case for all the instances implemented in the TAF KIT 1 4 1 Specification
57. VGI and especially dedicated to VAUCANSON allows to describe automata and to visualize the result of operations on automata in an interactive and graphical way All functions defined in TAF KtT can be called via the menu of Val The VAUCANSON platform is currently under a thorough revision and its core is rebuilt with a new design that changes the interface and the associated API The ultimate version of the first phase of the project coined VAUCANSON 1 4 has been eventually released in September 2011 The novelty of the VAUCANSON 1 4 1 version just released in July 2012 is the integration of the Graphical User Interface VGI Ideally a user s manual for VAUCANSON should document all of these components We decided not to do so not so much because it is a lot of work but also as this work would not be so useful since the new design is likely to make most of the description soon obsolete On the other hand we want to have a version of the platform that will serve as a landmark for both functionalities and performance of the first phase of VAUCANSON This version is coined VAUCANSON 1 4 1 and we consider it is accessible through the TAF KIT only There will be a TAF KTT for the future versions of VAUCANSON its functionalities will include all those of the present one and its interface will essentially be the same as the TAF KIT of VAUCANSON 1 4 1 TAF KIT will be the only documented part of VAUCANSON 1 4 1 TAF KIT stands for Typed Automata
58. a transition with label I p Dually from every final state r to t there is thus a transition with label T r b For every state p outside and t compute a two component index 1 p k p l p 1 if pis the origin of a loop l p 0 otherwise k p li p 1 o p 1 where p is the in degree of p and o p its out degree Lexicographically order the states by their index VAUCANSON 1 4 1 TAF KiT Documentation 113 July 14 2012 c While there remains states choose the state q with smallest index remove it and replace the incoming and outgoing transitions according to C 1 recompute the index for those states that were adjacent to q d Return the label of the transition from i to t C 2 Weighted automata and rational expressions over free monoids C 2 2 Behaviour of automata C 2 2 1 eval As the automaton A implemented by a xml is supposed to be realtime it is described by a representation A u v The coefficient of a word w in the series A realised by Ais u w v cf 17 Sect III 3 The vector A p w is computed by induction on w the length of w The overall complexity of the algorithm is O d where d is the dimension of A C 3 Automata and rational expressions on free monoids with weights in a field C 3 1 Operations on automata C 3 1 1 Reduction of representations over a field Automata and representation Any finite automaton over A with multiplicit
59. al lt aut gt 3 Operations on expressions 3 1 derived term lt ezp gt 3 2 are equivalent E lt exp1 gt lt exp2 gt Comments For clarifying specifications we make use of some specific automata V is the empty automaton no state W is the one state automaton where the unique state is initial but not final and is both the source and the target of a transition labeled by every letter of the alphabet 3 4 1 Operations on automata 3 4 1 1 is complete complete vcsn v is complete a xml Tells whether or not the automaton a zml is complete Input is complete Precondition a zml is realtime Specification A realtime automaton a zml over the alphabet A is complete if a it has at least one initial state VAUCANSON 1 4 1 TAF KiT Documentation 73 July 14 2012 b every state of a zml is the origin of at least one transition labelled by a for every a in A Comments As a consequence of the specifications every word of A is the label of at least one computation in a xml characteristic property which makes a necessary possibly a not successful one i The property thus depends not only on a zml itself but also on the alphabet on which a zml is constructed Or to tell it in another way not only on the value of the automaton but also on its type ii The empty automaton V is not complete iii Once the definition is written down it appears that it could be taken for automata over a free mono
60. al and recognisable power series In Handbook of Weighted Automata M Droste W Kuich and H Vogler eds Springer 2009 105 174 Vaucanson 1 4 1 TAF KiT Documentation 119 July 14 2012 Index 22 38 40 7 29 e 38 z 38 A 23 a 23 43 accessible 49 alphabet 23 33 43 alphabet 66 alphabet1 23 alphabet2 23 are equivalent 72 78 are equivalent E 72 argument see convention aut to exp 13 57 64 aut to exp DM 57 aut to exp SO 57 aut to expt 83 automata repository 41 automaton accessible part of an 49 67 deterministic 75 Glushkov 65 position 65 proper 51 standard 65 Thompson 35 trim 75 unambiguous 62 universal 78 B 30 31 b composition 88 bench 30 31 bench plot output 30 binom 70 binomial coefficient 70 bisimulation 66 Boost 8 cat 42 cat E 33 42 83 chain 55 characteristic 63 coaccessible 49 complement 75 complete 74 is complete 73 composition 88 composition R 90 CONCAT see token 40 concatenate 54 condition scalar end function 45 61 63 85 convention two argument 53 CPAR see token CWEIGHT see token D 30 31 data 42 derived term 81 is deterministic 75 determinize 75 display 43 divkbaseb char b 19 domain 87 w domain 88 dot see format 28 dotty 28 e 38 edit 22 43 85 enumerate 77 epsilon see transition eval 13 64 90 120 eval S 65 eva
61. aldet xml1 has been created into the current directory while a1 xml is a file that is predefined in VAUCANSON s predefined automata repository We can call the command data on either files using the same syntax because TAF KItT will look for automata in both places In the pure Unix tradition we can of course chain commands with pipes For instance the above two commands could be rewritten as vcsn char b determinize al xml vcsn char b data States 4 Transitions 8 Initial states 1 Final states 2 VAUCANSON 1 4 1 TAF K1T Documentation 14 July 14 2012 where stands for read from standard input TAF KIT actually supports a more efficient way of chaining commands the internal pipe It is called internal because the pipe logic is taken care of by TAF KIT itself and not using a Unix pipe at all the commands are simply serialized in the same process using the automata object created by the previous one It is more efficient because the automaton does not have to be converted into an XML file for output and then parsed back as input of the next command in the chain Here is how the above command would look using an internal pipe notice how the symbol is protected from its evaluation by the shell vcsn char b determinize al xml Y data States 4 Transitions 8 Initial states 1 Final states 2 In the above command does not designate the standard input it denotes the result of t
62. ated graphical interface is not fully operational displaying automata is processed by the Graphviz application which is normally launched in an X11 window It is to be acknowledged that the call to Graphviz by TAF KIT is not well tuned and that the output is rather poor It is not too difficult however to get a rendering of automata of much better quality cf Figure 1 This can be done in three steps and in a slightly different way for Mac and Linux users VAUCANSON 1 4 1 TAF KiT Documentation 9 July 14 2012 0 6 1 Graphviz for Mac First download the Graphviz application for Mac from www pixelglow com graphviz Al though already old and outdated by the 2 xx versions the 1 13 v16 version is recom mended as the settings is easier to handle in that version Complete the installation by putting the Graphviz app folder in the Applications folder Second write the following script in a file called dotty bin sh if x 1 x then cat gt tmp tmpdotty dot open W a Graphviz tmp tmpdotty dot rm f tmp tmpdotty dot else open W a Graphviz 1 fi Finally make this file executable store it in a folder and put the full name of this folder in the PATH variable before usr local bin and usr X11 bin The appearance of the automata will be determined by fixing the settings in the interface 0 6 2 Graphviz for Linux For Linux users the process is almost same except that the program required is xpdf and the dotty
63. atenate lt aut1 gt lt aut2 gt left mult lt aut gt lt k gt right mult lt aut gt lt k gt w w 0 A A w O oF wn e 3 1 3 2 3 3 3 4 star lt aut gt 3 5 3 6 chain lt aut gt lt n gt 4 Operations on behaviours of automata 4 1 sum S lt aut1 gt lt aut2 gt 4 2 cauchy S lt aut1 gt lt aut2 gt 4 3 star S lt aut gt 5 Automata and expressions operations on expressions 5 1 aut to exp lt aut gt aut to exp DM lt aut gt aut to exp SO lt aut gt 5 2 expand lt exp gt 5 3 exp to aut lt exp gt Allowing some exceptions mentioned when describing the functions VAUCANSON 1 4 1 TAF KiT Documentation 48 July 14 2012 The following function is not implemented It is just convenient to describe specification of dual functions in this section It differs from transpose as it has no effect on the labels Reverses every edge of the underlying graph of the automaton vcsn reverse a xml gt b xml a zml as well as exchanges the initial and final edges and write the result in b aml 3 1 1 Graph functions Automata are labelled graphs a number of functions on automata are indeed functions on the graph structure irrespective of the labels 3 1 1 1 accessible coaccessible vesn accessible a xml gt b xml Computes the accessible part of the automaton a zml and writes the result in b aml Specification The description of the function is the specification
64. automaton of an expression in the Boolean case is due to Antimirov 4 and can be found in other references 1 12 17 Caveat The specifications for the input format of rational expressions apply for this function Example As shown with the next commands and Figure 3 20 the automaton div3base2 xml yields again a good example where the derived term automaton is significatively smaller than the standard automaton of the same expression cf 17 Exer 1 5 5 vcsn char b aut to exp SO div3base2 xml 0x 1 1 0 1 0 0 1 0 1 0 1 0 1 0x 1 1 0 0 1 1 0x 1 1 0 0x vcsn char b aut to exp SO div3base2 xml derived term Al display 7 states 17 transitions l 1 T 2 Figure 3 20 The derived term automaton of an expression computed from div3base2 xml Comments i The computation of the derived terms of an expression in VAUCANSON 1 4 1 implements the ideas introduced in 6 Vaucanson 1 4 1 TAF KiT Documentation 8l July 14 2012 ii The derived term automaton of an expression can be defined for weighted expressions as well and not only for Boolean expressions cf 12 This is not implemented in VAUCANSON 1 4 1 but will be in subsequent versions of VAUCANSON iii The derived term function is sensitive to the bracketting of the expression cf 1 3 4 3 2 are equivalent E vcsn v ixml are equivalent E e xml f xm Tells whether or not the expressions e aml Expressions are equivalent and f z
65. by the following three data 1 the type of the weight semiring 2 the fact that the monoid is either a free monoid or a product of two free monoids 3 the type of the letters that generate the free monoid s Not all possible combinations derived from the types of semiring and free monoid listed above are instanciated it would amount to over 70 possibilities even if one restricts oneself to the same type for the input and output monoids in transducers In VAUCANSON 1 4 1 only 18 combinations are instanciated Table 1 3 shows these instances their names that VAUCANSON 1 4 1 TAF KiT Documentation 16 July 14 2012 program name automaton type alphabet type weight semiring vcsn char b automata characters B V A vcsn int b automata integers B V A vcsn char char b automata pairs of characters B V A vcsn char int b automata pairs of character and integer B V A vcsn int int b automata pairs of integers B V A vesn char z automata characters Z x vesn int z automata integers Z x vcsn char char z automata pairs of characters Z x vesn int int z automata pairs of integers Z xX vcsn char zmax automata characters Z max vesn char zmin automata characters Z min vesn char r automata characters R x vcsn char q automata characters Q x vesn char f2 automata characters Fa x vcsn char fmp b transducers characters B V A vcsn char fmp z transducers
66. ch as power n b1 xml quotient on the automaton b1 xml illustrate well the influence of the weights A 2 1 2 c1 xml for C Comments The series realised by C4 associates every word w of a b with its value in the binary notation when a is interpreted as 0 and b as 1 a 2a b 2b Figure A 8 The Z automaton C over a b A 2 1 3 di xml Comments The series realised by this automaton associates every word w of a b with its number of a minus its number of b Figure A 9 The Z automaton d1 xml over a b Vaucanson 1 4 1 TAF KiT Documentation 95 July 14 2012 A 3 Zmin automata A 3 1 Repository The following automata files are stored data automata char zmin directory and acces sible by the command vcsn char zmin cat A 3 1 1 minab xml Comments The series realised by this automaton associates every word w of a b with min number of a number of b fija 0 b 0 a 1 6 COD Figure A 10 The Zmin automaton minab xml over fa b A 3 1 2 minblocka xml Comments The series realised by this automaton associates every word w of a b with the length of the smallest block of a between two b s lla O a O a 1030 0 b O b Figure A 11 The Zmin automaton sag xml over a b A 3 1 3 slowgrow xml Comments The smallest word associated with the value n is abaab a Dha b fika ie 0 a i o b
67. comes from the fact that a transducer can be considered as well as an automaton over the input monoid with weights in the rational series over the output monoid In VAUCANSON such type of transducers is called rw transducers where rw stands for rational weights to distinguish them from the fmp transducers No rw transducers are instanciated in TAF KIT 1 4 1 VAUCANSON 1 4 1 TAF KIT Documentation 17 July 14 2012 more informations or data have to be known by or given to the command They roughly fall into three different classes 1 the letters in the alphabet s 2 the informations concerning the input and output formats which control the way the arguments will be read and the results output by the command 3 the data called writing data which control the way rational expressions are written or read as symbol sequences this is partly related with the letters in the alphabets The letters of the alphabets have to be given explicitely to the command In many cases however this is transparent to or unnoticeable by the user if a command calls an automaton or an expression as a parameter and if this parameter is an XML file under the the Fsm XML format which is read by VAUCANSON the letters are contained in the file and nothing is to be added In the other cases the letters have to be listed in an option Data of the two other classes are given default values They may be useful in order to get the desired result they a
68. cteristic property which makes a necessary i The result depends indeed only on a zml itself not on its type 1i The empty automaton V is deterministic vcsn determinize a xml gt b xml Computes the determinisation of a zml and writes the result in b zml Precondition a zml is realtime Specification Computes the accessible part of the subset automaton an algorithm sometimes refered to as the subset construction The result is thus accessible and complete Comments determinize V W cf Figure 1 3 for the determinisation of a1 xm1 3 4 1 3 complement vcsn complement a xml gt b xml Computes the complement automaton of a zml and writes the result in b zml Precondition a zml is complete thus realtime and deterministic Specification Swap terminal for non terminal states in a zml Comments Thanks to the preconditions the language accepted by complement a xm1 is the complement of the language accepted by a aml Caveat The complement automaton is not trim cf Figure 3 16 VAUCANSON 1 4 1 TAF KiT Documentation 75 July 14 2012 3 4 1 4 minimize vcsn minimize a xml gt b xml Computes the minimized automaton of a zml and writes the result in b aml Precondition a zml is complete thus realtime and deterministic Specification minimize a xml quotient a xml cf Figure 3 16 for an example Comments i Thanks to the preconditions m
69. ction which works perfectly well for Boolean transducers does not yields a transducer for the composition if the multiplicities are to be taken into account For instance there is one path labeled aa y in J and one path labeled y u in U1 and there are two paths labeled aa u in Ti gt U Hence T JU does not realize the composition of the weighted relations realized by T and U Vaucanson 1 4 1 TAF KiT Documentation 116 July 14 2012 Preparation of transducers for the composition In order to have a product of transducers that realises the weighted composition we performa preliminary operation on both operands that distinguishes between transitions and the take advantage of this supplementary information in order to supress some transitions in the product The construction on 7 and U can be described as follows a Split the states of T and their outgoing transitions in such a way they are labeled either in Ax1 black states or in Ax B or the state is final white states the incoming transitions are duplicated on split states This is transducer 7 b Split the states of U and their incoming transitions in such a way they are labeled either in 1xC black states or in BxC or the state is initial white states the outgoing transitions are duplicated on split states This is transducer U c Apply the preceeding algorithm steps i ii and iii to 7 and U in order to build T
70. d in both INSTALL and doc README txt files The following installation commands will install VAUCANSON in usr local cd vaucanson 1 4 1 configure make sudo make install Depending on the architecture both Boost and Xerces might be located in non standard directories The location of these libraries may known via the following command whereis boost This command returns the paths to Boost headers These directories are then specified to the configure file by means of two environment variables CPPFLAGS for the header files and LDFLAGS for the library files For instance if Boost headers are located in usr user_name home my_path_to_boost include and its library files in usr user_name home my_path_to_boost 1ib the following configure line should be in voked configure CPPFLAGS I usr user_name home my_path_to_boost include LDFLAGS usr user_name home my_path_to_boost lib If VAUCANSON is not installed but only compiled the TAF KIT binaries are to be found in the directory vaucanson 1 4 1 taf kit tests This directory contains wrappers around the real TAF KIT programs from vaucanson 1 4 1 taf kit src that enable them to run locally VAUCANSON 1 4 1 TAF KiT Documentation 8 July 14 2012 0 5 MacOSX specifics The installation process of VAUCANSON and its dependencies on MacOSX may be less straightforward than onto other Linux systems First the macports software will be
71. d using alphabet In the latter case moreover and as there is no a priori restriction on the characters that can be used as letters VAUCANSON needs to know the alphabet over which the expression is built in order to parse the rational expression there is no other way for guessing whether the alphabet is A a b and the is a rational operator or if the alphabet is B a b and the is just a letter Specifying the alphabet can be done by using alphabet ab or its short equivalent aab For instance the correct writing of the above command reads vcesn char b alphabet ab edit aut xml vcesn char b aab exp to aut abata gt aut xml The function edit is described at Section 2 3 6 exp to aut which takes a rational expression and converts it into an automaton at Section 3 2 3 VAUCANSON 1 4 1 TAF KIT Documentation 22 July 14 2012 vcsn char b display aut xml aut xml 5 states 4 transitions 1 1 T 2 Figure 2 1 Result of the command vcsn char b display aut xml Table 2 2 reviews the alphabet specification options The different possibilities characters integers and pairs need to be described with more details long option short purpose of the option alphabet a specify the alphabet of automata or rational expressions alphabet1 a specify the first or input alphabet of transducers fmp alphabet2 A specify the second or output alphabet of transducers fmp
72. ean classical finite state automaton that accepts the regular expression a ba 13 Selecting File gt Save to save the newly created automaton somewhere so it can be used for the next part VAUCANSON 1 4 1 TAF K1T Documentation 104 July 14 2012 B 3 2 Running Algorithms Provided by Vaucanson Requirement compiled TAF Kit 1 Open the automaton that accepts the regular expression a ba and select Algorithms gt Set TAF Kit path in the menu bar of the VGI window 2 Working TAF Kit scripts are usually available in the taf kit tests subdirectory under the vaucanson 1 4 directory took in G ih at e Y gt Makefile am vesn char char b completeness test gt Makefile in gt vesn char char b test 1 defs README vesn char char z 5 defs in 5 vesn char b gt vesn char char z test gt vesn char b test 5 vesn char f2 File Name Volumes 150GBPart vaucanson 1 4a taf kit tests Files of Type All Files 7 Open Cancel 3 Select Algorithms gt Operations on all automata and rational expressions gt aut to exp VAUCANSON 1 4 1 TAF K1T Documentation 105 July 14 2012 El Lar sft Merge Sitar Thansiions Accessible Losccessle Remove Epston Transtons End Seve soke Ange 00 tenghi 5000 H T i i 1 E 4 The result of converting this automaton to regular ex
73. ec bin xml display Integer alphabets The letters of an integer alphabet must be specified as signed integer they are represented by the C type int and should be separated by commas For instance the following command will construct an automaton that reads any sequence of coins of 1 2 5 10 20 or 50 cents as long as the values are increasing vesn int b a1 2 5 10 20 50 exp to aut 1 2 5 10 20 50 gt coins xml vcsn int b eval coins xml 1210 vcsn int b eval coins xml 12105 vcsn int b eval coins xml 121050 ROS Eee e Note that digits are characters and not integers even if they look like the latter for integers between 0 and 9 and if in VAUCANSON 1 4 1 no operations on integer letters are implemented that could differentiate them The only difference is thus the syntax when listing them in the option Pair alphabets Pair alphabets should be specified using parentheses and commas to form pairs with types of letter that match the TAF KIT instance of course as in the following example The function quotient is described at Section 3 2 4 1 dec bin xml is an automaton with 12 states and 27 transitions and diplaying it would have been messy VAUCANSON 1 4 1 TAF K1T Documentation 24 July 14 2012 vecsn char int b a a 1 a 1 b 2 exp to aut a 1 a 1 b 2 gt misc xml vcsn char int b display misc xml misc xml 4 states 4 transitions 1 1 T 1
74. entation 11 July 14 2012 Chapter 1 Presentation of TAF Kit TAF KiIT stands for Typed Automata Function Kit it is a command line interface to VAU CANSON As stated in the introduction the VAUCANSON platform is dedicated to the compu tation of and with finite automata where finite automata means weighted automata over a priori arbitrary monoids In the static generic programming paradigm used in the VAUCANSON library the types of the automata that are treated have to be known at compile time TAF KIT which is a set of programs that should be called from the shell and that can be used to chain operations on automata has therefore been compiled for several predefined types of automata It thus allows to use already programmed functions on automata of predefined types TAF KIT gives a restricted access to VAUCANSON functionalities but it is a direct access without any need of programming skill A basic familiarity with Unix command syntax only is sufficient to make use of TAF KIT In this chapter we first give a series of examples of commands in the case of classical automata We then present the overall organisation of TAF KIT with the list of possible instances and options The following section describes the syntax of options that help define the behaviour of the commands whereas the fourth section describes the syntax of rational that is regular expressions within VAUCANSON The final section lists the input output
75. f VAUCANSON Vaucanson 1 4 1 TAF KiT Documentation 36 July 14 2012 2 2 3 1 Implicit parametrization the constants The constants 0 and 1 are naturally written by default as O and 1 This is witnessed for instance in the following command call that instantiates the last of the trivial identities T cf Table 2 5 vcsn char b aab cat E 0 1 If 1 is a letter in the alphabet as a character digit the same symbol cannot be used for representing the constant 1 nor the identity of the monoid that is the empty word VAUCANSON chooses the first available representation of the identity from the following list of candidate symbols 1 e or _e which does not collide with any letter of the alphabet vcsn char b aab1 cat E 0x e vcsn char b aabel cat E 0 e Similarly if 0 is a letter in the alphabet as a character digit the same symbol cannot be used for representing the constant 0 nor the null series and VAUCANSON chooses the first available representation of the zero from the following list of candidate symbols 0 z or _z which does not collide with any letter of the alphabet Because of the trivial identities see Section 2 2 1 2 this is a much rarer situation The following calls to the expand function cf Section 3 1 5 3 yields 0 in a non trivial way vcsn char z aal expand at 1 a 0 vcsn char z aa01 expand at 1 a
76. f xml Tells whether or not the expressions e zml Expressions are equivalent and f zml denote the same language Specification are equivalent E e xml f xml are equivalent standard e xml standard f xml Caveat The specifications for the input format of rational expressions apply for this function For instance the alphabet must be specified if the expressions are given as strings Example vcsn char q aab v are equivalent E b 2 a b 2 a b 2 a Expressions are equivalent SThese data depend heavily on the examples and also on the machine on which the examples are run VAUCANSON 1 4 1 TAF K1IT Documentation 72 July 14 2012 3 4 Boolean automata and rational expressions on free monoids The classical theory of automata has been developed for automata with no weight that is with weight taken in the Boolean semiring All functions of Section 3 1 and Section 3 2 obviously apply But a number of other functions very important ones indeed are specific to Boolean automata 1 Operations on automata is complete lt aut gt complete lt aut gt is deterministic lt aut gt determinize lt aut gt 1 2 3 complement lt aut gt 4 minimize lt aut gt 5 prefix lt aut gt suffix lt aut gt factor lt aut gt enumerate lt aut gt shortest lt aut gt 2 1 2 2 2 3 intersection lt aut1 gt lt aut2 gt 2 4 are equivalent lt aut1 gt lt aut2 gt 2 5 univers
77. gonal 3 2 1 4 partial identity partial erase eee eee ed Transforms the automaton a zml over A into an automaton vcsn partial 1dentl a xm Xm a j E p over A x A a fmp transducer which realises the identity on the behaviour of a zml and writes the result in t aml Precondition no precondition Specification Every transition of t zml is obtained from a transition of a aml by keeping the same weight and by replacing the label f by the pair f f Example vcsn char z partial identity c1 xml gt c1pi xml vcsn char fmp z display c1pi xml l OED 1 1 C2 See oder 1 v clpi xml 2 states 5 transitions I 1 T 1 Figure 3 8 A weighted partial identity Vaucanson 1 4 1 TAF KIT Documentation 62 July 14 2012 vcsn partial erase a xml gt t xml Caveat i The partial identity function is implemented for the TAF KIT instances vcesn char b vcsn int b vcsn char z et vcsn int z only so that the type of the result matches an implemented instance for fmp ii As the type of the result is different from the type defined by the calling instance of TAF KIT it is not possible to use the internal pipe to chain the functions iii The partial identity function requires the automaton to meet the scalar end function condition in order to behave correctly Transforms the automaton a zml over A into an automaton over A xA a fmp transducer which projects the behaviour of a zml o
78. he previous command 1 2 TAF Kit organisation TAF KIT is indeed one program and this same program is compiled for different types of automata The result of each compilation yields a command with a distinct name which can be called from the shell As we have seen in the preceding examples every such command essentially takes two arguments the first one determines a function and the second one an automaton which is the operand for the function 1 2 1 Automata types A finite automaton is a finite directed graph labelled by polynomials in K M that is by finite linear combinations of elements of a monoid M with coefficients in a semiring K The type of an automaton is thus entirely determined in VAUCANSON 1 4 1 by the specification of K and of the type of M 1 2 1 1 Semirings The semirings that are instanciated in TAF KtT 1 4 1 are shown in Table 1 1 All these semirings are numerical in the sense their elements are implemented as numbers but for the rationals float for R bool for B int for the others The rationals are pairs of integers and implemented as pairs of an int and an unsigned They all are commutative semirings 1 2 1 2 Monoids The monoids instanciated in TAF Krr 1 4 1 are the free monoids and the direct products of two free monoids A free monoid is completely determined by the set of generators called 3We add this precision as in the next version VAUCANSON 2 the kind of labels w
79. he following categories 1 options that give information on the instance 2 specifications of the alphabet s 3 determination of the input and output formats 4 activation of benchmarking options 5 and finally parametrization of the grammars for rational that is regular expressions The description of the options of the first four categories is given in the next section the one of options controlling the rational expressions called writing data is postponed to the following section 2 1 Simple options Along the Unix tradition the options are given long names called with the prefix together with short equivalent names prefixed with a simple which in practice will often be prefered 2 1 1 Information options They are listed in Table 2 1 Caveat The character being interpreted by the shell it should be protected in order to be given as an argument to a command Without such a protection the behaviour may depend on the shell and according to the files within the directory This option should probably be suppressed but it is necessary for the library argp which is used for reading the options in the command line and it does not seem easy to get around it In any case it should be avoided and the help option be used 21 long option short purpose of the option help Give the help list usage Give a short usage message version V Print program version
80. hese automata accept all words the example shows how the construction works 3 states 6 transitions 1 1 T 3 3 states 6 transitions 1 3 T 1 3 states 6 transitions l 3 FT 3 Figure 3 17 Automata for the prefixes suffixes and factors of div3base2 xml 3 4 2 Operations on the behaviour of automata 3 4 2 1 enumerate vcsn enumerate a xml n Computes the list of the words of length less than or equal to lt list of words gt n in the support of the series realized by a aml Precondition a zml is realtime Specification i The words are enumerated in the radix ordering and output as one word per line ii If is useless a xml then the list is empty Example The next command enumerates the words with an even number of a s vcsn enumerate apair xml 3 1 b aa bb aab aba baa bbb VAUCANSON 1 4 1 TAF K1T Documentation 77 July 14 2012 3 4 2 2 shortest vcsn shortest a xml Computes the shortest word in the support of the series real lt word gt ized by a aml Precondition a zml is realtime Specification If is useless a xm1 the shortest function exits with a non zero exit code 3 4 2 3 intersection Computes from a zml and b aml an automa vesn intersection a xml b xm gt c xml ton which accepts the intersection of the lan guages accepted by a zml and b zml and writes the result in c zml Precondition no precondition Specification
81. his example the DM heuristics seems to be better than the naive one They give indeed the same results in many cases eg for ladybird n xml for n gt 4 A thorough comparison between the two heuristics remains to be done The same functions apply of course to weighted automata and transducers as well vesn char z aut to exp c1 xml O 1 1 2 O 2 1 x vcesn char fmp b aut to exp t1 xml ta 1 1 y3 1 23 by 1 Clas 1 1 vcsn char fmp b aut to exp SO t1 xml a 1 1 y 1 x b 1 a 1 1 y 1 x b 1 a 1 1 y a 1 1 a 1 1 y a 1 1 VAUCANSON 1 4 1 TAF KiT Documentation 57 July 14 2012 vcsn ixml exp to aut e xml gt a xml ladybird 3 xml 3 states 9 transitions 1 1 T 1 Figure 3 6 The automaton ladybird 3 xml 3 1 5 2 exp to aut Build an automaton whose behaviour is de noted by the expression e aml and writes the result in a zml Precondition no precondition Specification The automaton a zml is the standard automaton of the expression e zml computed by the recursive use of the operations on automata as described at Section 3 1 3 and as specified at Section C 1 3 For the specification of the expression formats cf Section 2 1 3 2 Caveat i For technical reasons the exp to aut function is not implemented for the fmp instances that is for transducers in TAF KIT 1 4 1 ii The actual implementation of exp to aut carries
82. id in general and not only for Boolean automata It is the function complete which would be meaningless or at least artifical for a non Boolean automaton iv One must acknowledge that the definition is rather artifical also for automata which are not accessible vcsn complete a xml gt b xml Computes from a zml an equivalent complete automaton and writes the result in b aml Precondition a zmlis realtime Specification If a zml is not complete a add a new state z to a zml b for every state p of a zml including z and for every a in A if there exist no transi tion p a q in a zml add a transition p a z to a zml c if there exist no initial state in a zml make z initial Comments complete V W vcsn char b complete al xml display 4 states 9 transitions 1 1 T 1 Figure 3 15 The completion of A Vaucanson 1 4 1 TAF K1T Documentation 74 July 14 2012 3 4 1 2 is deterministic determinize vcsn is deterministic v a xml Input is not deterministic Tells whether or not the automaton a zml is deterministic Precondition a zml is realtime Specification A realtime automaton a zml over the alphabet A is deterministic if a it has at most one initial state b every state of a zml is the origin of at most one transition labelled by a for every a in A Comments As a consequence every word of A is the label of at most one computation in a zml chara
83. ill also be a criterion in the definition of the programming type of an automaton Vaucanson 1 4 1 TAF KiT Documentation 15 July 14 2012 semiring mathematical symbol suffix in TAF KtT Boolean semiring B V A p ring of integers Z Z x iz field of reals R x el field of rationals Q Q 4 x q two element field F 0 1 x with 1 1 0 2 min tropical semiring Zmin Z min zmin max tropical semiring Zmax Z max zmax Table 1 1 The semirings implemented in VAUCANSON TAF Krr 1 4 1 alphabet At compile time however it is not necessary to know the alphabet itself the type of its elements the letters will suffice Thus for TAF KIT the type of letters of one alphabet for a free monoid of two alphabets for a direct product of two free monoids has to be defined In TAF KtT 1 4 1 the following types of letters are considered 1 the simple letters which may be characters char or integers int 2 pairs of simple letters The combinations that are instanciated in TAF KIT 1 4 1 is shown in Table 1 2 letter types free monoids free monoid products characters char char fmp integers int int fmp pair of characters char char pair of integers int int pair of character and integer char int Table 1 2 The monoids implemented in VAUCANSON TAF Krr 1 4 1 1 2 2 TAF Kit instances As the consequence of the preceding subsection the type of an automaton is determined
84. inimize a xml is the minimal automaton of the language accepted by a aml ii TAF Kir 1 4 1 the quotient algorithm is specialised to Boolean automata and imple ments the Hopcroft algorithm alcmp xml 4 states 8 transitions I 1 T 2 almin xml 3 states 6 transitions 1 1 T 1 Figure 3 16 The complement and the minimisation of aldet xml 3 4 1 5 prefix suffix factor vaan profit ciami gt b m Makes every state of a zml final and writes the result in b aml Precondition a zml is realtime and trim Comments Thanks to the preconditions b zml prefix a xml is an automaton which accepts all prefixes of words in the language accepted by a aml vesn suffix a xml gt b xml Makes every state of a zml initial and writes the result in b aml Precondition a zml is realtime and trim Comments Thanks to the preconditions b zml suffix a xml is an automaton which accepts all suffixes of words in the language accepted by a aml VAUCANSON 1 4 1 TAF KiT Documentation 76 July 14 2012 vcsn factor a xml gt b xml Makes every state of a zml initial and final and writes the result in b aml Precondition a zml is realtime and trim Comments Thanks to the preconditions b zml factor a xml is an automaton which accepts all factors of words in the language accepted by a aml Example Figure 3 17 shows the automata for the prefixes suffixes and factors of div3base2 xml Of course t
85. integer pairs of integers pairs of characters pairs of integers characters characters integers integers weight semiring function sections B V A B V A Z x Z x Z max Z min gt e x Q x Fa X B V A B V A B V A Z x Z x B V A Z x B V A Z x 1 2 4 4 O O O ee NON O COINN DNyN DNDNNINN y DDNDN DyN Dawe SF BPW ww DDD Table 3 1 The TAF KIT instances in VAUCANSON 1 4 1 and their commands VAUCANSON 1 4 1 TAF KiT Documentation LAF July 14 2012 3 1 General automata and rational expressions Automata are labelled graphs and these labels are in full generality elements of a monoid associated with a multiplicity taken in a semiring or a finite sum of such weighted elements The commands considered in this section make assumption neither on the monoid nor on the weight semiring They are thus called by any instance of TAF KIT for automata of any type 1 Graph functions 1 1 accessible lt aut gt coaccessible lt aut gt 1 2 trim lt aut gt is trim lt aut gt 1 3 is empty lt aut gt 1 4 is useless lt aut gt 2 Transformations of automata 2 1 proper lt aut gt is proper lt aut gt 2 2 standardize lt aut gt is standard lt aut gt 3 Operations on automata union lt aut1 gt lt aut2 gt sum lt auti gt lt aut2 gt conc
86. intersection a xml b xml product realtime a xml1 realtime b xm1 3 4 2 4 are equivalent vcsn v are equivalent a xml b xml Tells whether or not the automata a zml and b zml accept Automata are not equivalent the same language Precondition no precondition Specification are equivalent a xml b xml is useless intersection a xml complement determinize realtime b xml A is useless intersection complement determinize realtime a xml b xm1 3 4 2 5 universal vcsn universal a xml gt b xml Computes the universal automaton of the language accepted by a zml and writes the result in b aml Precondition no precondition Specification With every language is canonically associated an automaton called the universal automaton of the language in 17 which is finite whenever the language is rational It has been first defined by J H Conway in 8 in order to solve two dual problems of approximation of languages A complete and systematic presentation of the universal automaton is given in 13 including the computation algorithm that is implemented in VAUCANSON VAUCANSON 1 4 1 TAF K1T Documentation 718 July 14 2012 Example vcsn char b universal al xml display 3 states 14 transitions 1 1 T 1 Figure 3 18 The universal automaton of a1 xml of L A indeed Comments The universal automaton contains many interesting informations on the lan guage In particular
87. is only a decomposition algorithm it does not attempt to make the automaton more compact this would be the task of other and more sophisticated algorithms Example Figure 3 22 shows a Z transducer and its subnormalization Note that the trans ducer fx1 xm1 cannot be built nor edited with the edit function as this function does not create nor handle labels of transition that are sums Caveat The subnormalize function requires that the transducer meets the scalar end function condition Vaucanson 1 4 1 TAF KiT Documentation 85 July 14 2012 2 a b b b 2 abb ba ba baa 0I b b Gsm b b fx1 xml 2 states 3 transitions l 1 T 1 fx1 sbn xml 6 states 8 transitions l 1 T 1 Figure 3 22 A Z transducer and its subnormalization 3 5 1 4 is ltl vcsn is ltl v t xml Tells whether or not the label of every transition of t zml is Input is letter to letter in Ax B 3 5 1 5 1tl to pair vcsn 1tl to pair t xml gt a xml Transforms t aml into an automaton over AxB with weight in K and writes the result in a zml Precondition t zml is letter to letter Specification The label of every transition of t xml becomes a letter in the alphabet AxB and the weight of the transition is kept unchanged Comments A letter to letter transducer and an automaton over the corresponding alphabet of pairs looks very much the same when they are drawn by the display function But they
88. it contains a copy of any minimal NFA which recognizes the language In the case of group langages and even reversible languages an automaton of minimal loop complexity is to be found within the universal automaton cf 13 The universal automaton however becomes soon very complex as witnessed in the figure below and a more structured view on it is necessary to discover the interesting properties The language He is accepted by the automaton h6 xml that is generated within VAUCANSON by a call to the factory doublering char b 6 1 3 4 5 gt h6 xml More details on the computation of the universal automaton of Hg and its relation with the star height of Hg are to be found in 13 or 17 Sec II 8 VAUCANSON 1 4 1 TAF KiT Documentation 79 July 14 2012 b and a more structured view Figure 3 19 The universal automaton of Hg f a b fla flo 1 3 4 or 5 mod 6 VAUCANSON 1 4 1 TAF K1T Documentation 80 July 14 2012 3 4 3 Operations on expressions 3 4 3 1 derived term vcsn derived term e xml gt a xml Computes the derived term automaton of e zml and writes the result in a sml Precondition no precondition Specification The definition of the derived term
89. lent automaton whose transi vcsn letterize a xml gt b xml tions are all labelled by letters or the empty word by cutting the label of every transition into letters and writes the result in b zml VAUCANSON 1 4 1 TAF K1T Documentation 60 July 14 2012 3 2 1 1 transpose vcsn transpose a xml gt b xml Computes the transposition of the automaton a zml and writes the result in b zml Specification Builds the transposition of the underlying graph and exchanges the initial and final functions that is realises the function reverse cf Section 3 1 Finally transposes the labels as well that is takes the mirror image of the words that label the transitions and in the initial and final functions Comments i The behaviour of At the tranpose of A is the transpose of the behaviour of A ii There exists a transpose function for transducers fmp as well that will be redefined explicitely for them cf Section 3 5 1 2 3 2 1 2 is realtime realtime vcsn is realtime v a xml Teste is realt ine Tells whether or not the automaton a zml is realtime Specification An automaton over a free monoid is realtime if it is both letterized and proper Caveat The label of a transition of a realtime automaton is not necessarily a weighted letter but may be a sum of weighted letters as shown on the following example cf Figure 2 6 for the automaton c1 xm1 vcsn char z v is realtime c1 xml Input is
90. luation 90 exp see format exp to aut 22 25 58 83 expand 37 45 58 69 70 83 export time dot 30 export time xml 30 expression reduced 32 42 factor 77 field 71 first projection 91 format dot 26 exp 26 fpexp 26 35 fsm 26 42 xml 26 42 fpexp see format fsm see format Graphviz 43 Graphviz 8 28 gui 45 help 22 30 i 27 42 90 image 87 w image 88 infiltration see product infiltration 69 input 27 internal see pipe intersection 78 inverse 83 is empty 29 50 is unambiguous 62 is useless 50 L 22 1 22 left mult 54 letter to letter seetransducer86 letterize 60 list all commands 22 list automata 19 22 VAUCANSON 1 4 1 TAF KiT Documentation list commands 22 is 1t1 86 1t1 to pair 86 minimize 76 Ncurses 8 0 30 o 27 42 90 ONE see token OPAR see token OPENFST 27 OpenFST 26 output 27 OWEIGHT see token P 39 p 39 pair to fmp 91 parser 38 39 parser1 39 parser2 39 partial erase 63 partial identity 62 pipe internal 15 18 63 shell 14 PLUS see token power 64 68 predefined alphabets 23 prefix 76 product Cauchy 54 56 Hadamard 54 infiltration 69 shuffle 68 product 54 67 product S 56 is proper 50 proper 51 65 Q 39 quotient 24 66 radix ordering 77 rational expression 31 121 July 14 2012 operator 32 realtime 64 67 68 is real
91. mial itself that is every monomial appears only once but not between the transitions that have the same origin and end The label that can be given to a transition in a transducer is more constraint it is a weighted element of the product monoid that is a weigted pair of words After the origin and end of the transition the user is asked for the first component of the pair then for the second component and finally for the weight vcsn char fmp z aab Aab edit test fmp xml 11 Your choice 1 11 3 Add a transition from state 0 To state 0 First component labeled by the word ab Second component labeled by the word ba With weight 1 Automaton description States 0 Initial states O W 1 Final states 0 W 2 Transitions 1 From O to O labeled by ab ba W 1 Caveat The automata created with the edit function have the property that the initial and final functions are scalar functions that is the labels of initial and final arrows are restricted to be weights This restriction does not come from a theoretical limitation One could imagine and even wish to work with automata in which the initial or final functions may take as a value a weighted expression like any other transition label To tell the truth this possibility is open in the library of VAUCANSON 1 4 1 But it turned out that not all functions in TAF KIT 1 4 1 would behave correctly in presence of such general initial or final functions This is the reaso
92. ml denote the same language Precondition no precondition Specification are equivalent E e xml f xml are equivalent standard e xml standard f xml Caveat The specifications for the input format of rational expressions apply for this function Vaucanson 1 4 1 TAF K1T Documentation 82 July 14 2012 3 5 Weighted automata over a product of two free monoids Automata over a product of two free monoids are called transducers in the literature and fmp transducers in VAUCANSON fmp stands for free monoid product Their behaviours are series over A x B that is weighted subsets of A x B or weighted relations from A input monoid to B output monoid but looked at symmetrically Transducers can also be considered as automata over the input alphabet with multiplicity in the semiring of rational series over the output alphabet the equivalence between the two points of view is asserted by the Kleene Schiitzenberger theorem These would be called rw transducers in VAUCANSON rw stands for rational weights They are not implemented in TAF Krr 1 4 1 cf Section 1 2 2 but will be in subsequent versions In the sequel we denote the input monoid by A the output monoid by B in TAF Krr 1 4 1 they are both alphabets of characters or both alphabets of integers and the weight semiring numerical and commutative by K in TAF kirT 1 4 1 B or Z We denote the transducers by tdc rather than by aut As automa
93. mmand line The solution is to use an argument after the function name in order to indicate that any following arguments should be treated as operands even if they begin with the character vesn char z standardize c1 xml gt cis xml vesn char z left mult cis xml 1 vesn char z invalid option 1 Try vcsn char z help or vcsn char z usage for more information vesn char z left mult cis xml 1 G GG YN Y 3 1 3 6 chain vcsn chain a xml n gt b xml Build the concatenation of n copies of a zml by and writes the result in b aml Precondition a zml is standard for the concatenation operation is defined only on stan dard automata Specification vcsn chain a xml O gt u xml where u xml is the one state automaton initial and final with no transitions which accepts the empty word and which is the identity element for the concatenation of automata Example Figure 3 5 shows the effect of a concatenation of 3 copies of the standardization of the B automaton al xml Vaucanson 1 4 1 TAF KiT Documentation 55 July 14 2012 1 4T 1 10 states 24 transitions 1 Figure 3 5 Concatenation of 3 copies of the standardization of a1 xml vcsn char z standardize al xml Y chain 3 display Comments This function compensates for the absence of exponents in the writing of rational expressions Note that it may easily yield large automata and entail
94. mplexity and McNaughton to give the simplest example of minimal automata which do not achieve the minimal loop complexity for the language the recognize This was then reinterpreted in terms of universal automata cf 17 Sec II 8 The automaton double 3 1 xml Figure A 6 is already in the repository Figure A 6 The double rings Hg and double 3 1 xm1 A 1 2 3 Program ladybird ya Ain Generates an n state automaton over the alphabet a b c a LI a 1rd 0 xm i ro sun AS 7 id whose equivalent minimal deterministic automaton has 2 states Specification The states are labelled from 0 to n 1 State O is initial and final The number of states n is the first parameter and the next parameters give the list of final states Figure A 6 shows the automaton built by the above command Comments The determinisation of ladybird n has 2 states and is minimal as it is co deterministic ladybird n is used in the benchmarking of VAUCANSON The automaton ladybird 6 xml Figure A 7 is already in the repository A 2 Z automata A 2 1 Repository The following automata files are stored data automata char z directory and accessible by the command vesn char z cat VAUCANSON 1 4 1 TAF KiT Documentation 94 July 14 2012 Figure A 7 The ladybird Le A 2 1 1 b1 xml The chacteristic automaton of the automaton B cf Figure A 2 The different outcomes of functions su
95. n tmp tmp1 xml tmp tmp2 xml eval 3 in a file called binom make this file executable and store it in a folder whose address appears in the PATH variable One then have a command with 3 arguments the first one is the alphabet the next two are words f and g over this alphabet the command outputs E i binom ab aabb ab 4 VAUCANSON 1 4 1 TAF K T Documentation 70 July 14 2012 3 3 Automata and rational expressions on free monoids with weights in a field Three instances of TAF KTtT 1 4 1 implement a weight semiring which is a field vcsn char q vesn char r and vcsn char f2 for which the weight semiring is Q R and Fy Z 2Z respectively cf Section 1 2 2 In addition to all the functions of the preceding section which obviously apply a function reduce is specific to those automata whose weight semiring is a field It then easily allows to test the equivalence of two automata or expressions 1 Operations on automata 1 1 reduce lt aut gt 1 2 are equivalent lt aut1 gt lt aut2 gt 2 Operations on expressions 2 1 are equivalent E lt exp1 gt lt exp2 gt 3 3 1 Operations on automata 3 3 1 1 reduce vcsn reduce a xml gt b xml Computes from a zml an equivalent automaton of minimal dimension and writes the result in b zml Precondition a zml is realtime Comments Implements Schtitzenberger algorithm for reduction of representations cf Sec tion C 3 Caveat i The reduction algorithm may
96. n why we have left the restriction in the edit function and we make the assumption that all automata that are dealt with by TAF Krr 1 4 1 meet this restriction which we call the scalar end function condition 2 3 6 gui vcsn edit a xml Create and edit the automaton a zml via the graphical user interface VGI Comments The graphical user interface VGI is described at Appendix B The automaton test xml is supposed to have been created with one state both initial anf final The transducer test fmp xml is supposed to have been created with one state both initial anf final VAUCANSON 1 4 1 TAF KiT Documentation 45 July 14 2012 Chapter 3 Specification of functions on automata and rational expressions Functions are classified according to the type of automata they are applied to They depend upon the type of the monoid free monoid or direct product of two free monoids at this stage for TAF KtT 1 4 1 and upon the type of the multiplicity semiring numerical semirings of different kinds Some functions are specialised to even more particular type of alphabets Note that TAF KtT 1 4 1 offers no instance where the multiplicity semiring is a semiring of series over a free monoid with multiplicity in a numerical semiring In this chapter we give the specifications of the functions that is the preconditions on their arguments and the description of the result and how it is related to the argument 1 General automata and ratio
97. nEN and as infinite sums are not always defined t is not always defined Hence a semiring should be equipped with two supplementary methods supplementary to the defining operations of the semiring is starable and star with obvious meaning and result If s is a series in K M we denote by c s its constant term that is the coefficient of 1w Thus a series s is proper if its constant term is nul c s Ox And the proper part of an arbitrary series s is the proper series sp such that s c s lm Sp Under a natural and not restrictive hypothesis on K cf 17 18 the following property holds Property 1 A series s in K M is starable if and only if c s is starable and it holds s c s sp c s As a conclusion to this paragraph we can say that star is not always defined in K and thus in K M 2 Let A be an automaton over M with multiplicityin K We say that the behaviour of A A is defined if and only if for every pair of states p and q in A the family of labels of computations from p to q is summable Let Ao be the automaton obtained from A by retaining the transitions labelled by 111 only We then have Property 2 The behaviour of A is defined if and only if the behaviour of Ao is 3 Let A 1 E T and Ay I1 Ey T be their respective matrix description We write Ep for the proper matrix such that E E Eo Property 3 If the behaviour of A is defined we have A I Eo
98. nal expressions The definition of rational or regular expressions is rather an easy and classical subject of any first year course in computer science at least for the Boolean case Reading and writing the same expressions prove to be a much more tricky matter for several reasons Some are specific to VAUCANSON to begin with no characters are reserved for the rational operators and the usual ones may appear as letters in the alphabet over which the expressions are built the writing of weights and the possibility of having integers as letters add to the problem The effective implementation of reading and writing strings that represent expressions together with the usual and necessary convention and simplification also conceal difficulties that have to be circumvented by any software that deals with expressions Vaucanson 1 4 1 TAF KiT Documentation 31 July 14 2012 2 2 1 The definition of expressions 2 2 1 1 Construction of expressions The general definition reads as follow A rational expression over a monoid M with weight in a semiring K is a well formed formula built from e the elements of M which are the atomic formulas e the following operators 1 two 0 ary operators or constants denoted by 0 and 1 2 one unary operator star denoted by x 3 two binary operators sum and product denoted by and 4 and for every k in K two unary operators the left and right exterior multi
99. nal expressions 2 Weighted automata and rational expressions over free monoids 3 Automata and rational expressions over free monoids with weights in a field 4 Boolean automata and rational expressions over free monoids 5 Weighted automata over product of two free monoids 6 Weighted automata over free monoids over alphabets of pairs This classification is used to organise the lists of commands Every instance of TAF KIT contains the commands of the first section and of one or several others as indicated in Table 3 1 below A command with input and output arguments with different types belongs to the instance corresponding to the input type Moreover such a command exists only if the type of the output argument is instanciated as well cf partial identity Section 3 2 1 4 Every section begins with the list of commands that are then described in the section Whereas this possibility is offered within the library VAUCANSON 1 4 1 but it is out of the scope of this user s manual 46 command name vcsn char b vcsn int b vcsn char z vcsn int z vcsn char zmax vcsn char zmin vcsn char r vcsn char q vcsn char f2 vcsn char char b vcsn char int b vcsn int int b vcsn char char z vcsn int int z vcsn char fmp b vcsn char fmp z vcsn int fmp b vcsn int fmp z alphabet type characters integers characters integers characters characters characters characters characters pairs of characters pairs of character and
100. nd the file will be created when the editor is exited if the file does exist the alphabet will be read from the file along with the automaton itself and the file will be overwritten upon exit The interface is based on a menu of choices After the edit command line and after every choice in the menu TAF KIT first outputs a description of the current state of the automaton and then the full menu vesn char z edit c1 xml Automaton description States O 1 Initial states 0 W 1 Final states 1 W 1 Transitions 1 From 0 to 1 labeled by 1 2 From 0 to O labeled by 0 1 3 From 1 to 1 labeled by 2 0 2 1 Please choose your action 1 Add states 5 Set initial 9 Display 2 Delete a state 6 Set not initial 10 Save and exit 3 Add a transition 7 Set final 11 Exit without saving Set not final 00 4 Delete a transition Your choice 1 11 SBy the team of National Taiwan University The repetition of the menu after each command may seem heavy But it proves to be very convenient VAUCANSON 1 4 1 TAF KiT Documentation 43 July 14 2012 Note that states are numbered from 0 but transitions numbers start at 1 The effect of the actions 1 2 4 6 8 and 9 to 11 is self evident The one of the others will depend upon the type of the automaton being edited and thus upon the TAF Krr instance which calls the edit command For Boolean automata or transducers se
101. ndard automaton whose behaviour is the star of the vcsn oxml aut to exp a xml gt e xml vcsn oxml aut to exp DM a xml gt e xml behaviour of a zml and writes the result in b aml Precondition No precondition Specification star S a xml star standardize a xml 3 1 5 Automata and expressions operations on expressions 3 1 5 1 aut to exp aut to exp DM aut to exp S0 In VAUCANSON expressions are computed from automata by the state elimination method The algorithm is then specified by the order in which the states are eliminated In TAF KIT 1 4 1 the order is either an order computed by a heuristics called the naive heuristics which is the default option or an order computed by a heuristics due to Delgado Morais 9 or simply the order of the state identifiers Build a rational expression which denotes the behaviour of a zml and writes the result in vcsn oxml aut to exp SO a xml gt e xml e zml Precondition No precondition Specification cf Section C 1 4 Example The three orders applied to the automaton ladybird 3 xm1 Figure 3 6 give the following results vcsn char b aut to exp ladybird 3 xml a c atbtcta btc cta a c a b c c a 1 vcsn char b aut to exp DM ladybird 3 xml a b c c a b c a b c c a vcsn char b aut to exp SO ladybird 3 xml a c atbtc a cta a c atbtc atbtc cta a c atbt c ctcta ta c atbtc ct1 On t
102. ndition a zml is standard for the right exterior multiplication operation is defined only on standard automata Specification e The standard automata Ak lt Q A E fi TCH gt is defined by vpeQ TMP T k C 1 4 From automata to expressions VAUCANSON implements the state elimination method for computing the rational expression that denotes the behaviour of an automaton The outcome of the algorithme depends upon the order in which the states are eliminated In VAUCANSON library this order of states is given to the fonction as a second parameter called chooser The chooser either runs over a list of states that is given explicitely or implements a heuristics that computes at each step the next state to be suppressed Two heuristics are implemented in the library the naive heuristics which is described below and a variant of it which takes into account not only the number of transitions incident to every given state but also the length of the expressions that label these transitions it is due to Delgado and Morais and described in 9 Note that in any case and for a precise specification in view of the derivation procedure in particular one should specify the bracketting F G H p Fog Eg Dr gives poe C 1 after the elimination of the state q C 1 4 1 The naive heuristics a Make real the initial and final subliminal states and t From 7 to every initial state p there is thus
103. ns to automata 2 eee ee ee 65 3 2 4 Operations on automatas 66 3 3 Automata and rational expressions on free monoids with weights in a field 71 3 3 1 Operations on automatas 71 3 3 2 Operations on expressions 1 ee a 72 3 4 Boolean automata and rational expressions on free monoids 73 3 4 1 Operations on automatas 73 3 4 2 Operations on the behaviour of automata 77 3 4 3 Operations on expressions so sooo o a a 81 3 5 Weighted automata over a product of two freemonoids 83 3 5 1 Transformations of transducers 0 0000 eee 83 3 5 2 Operations on transducers 1 ee 87 3 5 3 Operations on behaviours of transducers 2084 90 3 6 Weighted automata on free monoids over alphabets of pairs ee 91 3 6 1 Transformations of automata 0 0 a a eee 91 A Automata repository and factory 92 AL SBS AU TOMMO LAS he gs ot ke ce Ae Ne tes ale Shatin Det DB joel da rs hee GALS 92 ALL Repository tac a See bed ed aw Bd ee gO 92 AL Fact ry osa oe Mee Re RA ee ERAS Hae ee wes 93 AZ Lao ta eri a Bh es oe esas Sn O he So eg ea 94 A 2 1 Repository arco ea aoe a eS ee Ba Sa a a 94 AS Zmmin automatar e Fal Pole Oe he eta a ote ae hee eo 96 As34 Repository 22 aie be Ake See kee ke ee ea ee a 96 AA Zmax automata 2 ee 97 AGA Repository are fea RAR te A A A te oe ee 97 A 5 B fmp transducerS o Ce D sa a aA i Sea a i a
104. nto the empty word and writes the result in zml Precondition no precondition Specification Every transition of t zml is obtained from a transition of a zml by keeping the same weight and by replacing the label f by the pair f 14 The same restriction as for partial identity apply to partial erase 3 2 1 5 characteristic Transforms the Boolean automaton a zml into a char vcsn xxx k characteristic a xml gt b xml acteristic automaton whose weight semiring is deter mined by the calling instance of TAF KIT and writes the result in b aml Precondition no precondition Example vcsn char zmin characteristic alct xml gt alctchr xml vcsn char zmin display alctchr xml a1ct xml 2 states 4 transitions 1 1 T 1 a1ctchr xml 2 states 5 transitions l 1 T 1 Figure 3 9 A compact version of A and its characteristic automaton in Z min Comments Eventhough different from the type of the input the type of the result corre sponds to the calling instance of TAF KIT the internal pipe is thus usable Vaucanson 1 4 1 TAF KiT Documentation 63 July 14 2012 3 2 1 6 support Transforms the automaton a zml whose weight semi vcsn xxx k support a xml gt b xml ring is determined by the calling instance of TAF KIT into a Boolean automaton and writes the result in b aml Precondition no precondition Example vcsn char z support c1 xml gt cispp xml vcsn char
105. ommended that NetBeans be used to get and compile the source code The complete source code is available online in the Git repository https code google com p vgi and can be downloaded using NetBeans built in Git client by the following steps 1 In the menu bar of NetBeans select Team gt Git gt Clone 2 For the Remote Repository step enter https code google com p vgi for the Repository URL field leave the User and Password fields empty and click on the Next button Note The repository URL starts with https not http 3 For the Remote Branches step check the box beside the master branch and click on the Next button 4 For the Destination Directory step adjust the fields as desired or leave them as default and click on the Finish button Alternatively one can use the command line Git client to clone the VGI source code repository by the following command in a terminal window git clone https code google com p vgi With the source code downloaded and the project opened in NetBeans VGI can be readily compiled and run by selecting Run gt Run Project menu item in the menu bar B 3 Using VGI B 3 1 Create a New Automaton 1 Select File gt New in the menu bar of the VGI window Vaucanson 1 4 1 TAF KiT Documentation 100 July 14 2012 2 Select a semiring for the weight and edit the alphabet symbols to define basic information for a weighted automaton Alternatively click the Default button to
106. out first a letterization of the expres sion which is not necessary in principle As it is it is completely synonymous to the standard function cf Section This is one of the reasons for which it is not implemented for the fmp instances Example The exp to aut function is not implemented for transducers but is for weighted automata as shown at Figure 3 7 result of the following command cf 17 Exer III 2 24 vcsn char q aab exp to aut 1 6a 1 3b Y display 3 1 5 3 expand vcsn ixml oxml expand e xml gt f xml Expands the expression e zml and writes the result in a zml Specification Vaucanson 1 4 1 TAF KiT Documentation 58 July 14 2012 3 states 6 transitions I 1 T 3 Figure 3 7 A standard Q automaton built by exp to aut Distributes product over addition recursively under the starred subexpressions and groups the equal monomials For the specification of the expression formats cf Section 2 1 3 2 Example vcsn char b aabc expand atb 1 atba catcc a acatacctbacatbacc b acatacc bacatbacc acatacct bacatbacc vcsn char z aabc expand a b cta c b ac 1 b bx ab atc 2 ac b acb b Caveat Not implemented for the fmp instances that is for expressions over a direct product of free monoids Vaucanson 1 4 1 TAF KiT Documentation 59 July 14 2012 3 2 Weighted automata and expressions over free monoids
107. plica tions by k denoted by k and k This definition is the one taken by members of the VAUCANSON group in their writings about weighted rational expressions cf 17 12 It must be said that it is not the most common one In general if one may say so of the few publications that deal with weighted rational expressions the elements of K are atomic formulas and the left and right exterior multiplications are expressed with the product operator The VAUCANSON choice is more natural for the definition of the derivation of expressions even if it has the theoretical drawback of introducing an infinity of operators something that logicians do not like very much usually Being a formula an expression may be viewed as a finite tree whose inner nodes are labelled with operators and leaves by atoms The tree itself may be faithfully represented in different ways The Fsm XML format provides all necessary tags to describe such a tree 2 2 1 2 Reduction of expressions Like automata the rational expressions are a symbolic and finite representation of lan guages or series Natural valuation of the atoms and induction rules make every expression denotes a language or a series Two rational expressions are equivalent if they denote the same languages or series We want a priori to distinguish between two distinct equivalent expressions in particular since it is not always possible to decide whether two expressions are
108. pression is as expected B 3 3 Layout 1 Here is an example of an automaton laid out haphazardly 2 Select Layout gt feature in the menu bar of the VGI window and a more reasonable layout for the same automaton results VAUCANSON 1 4 1 TAF K1T Documentation 106 July 14 2012 Vaucanson 1 4 1 TAF K1T Documentation 107 July 14 2012 Appendix C Algorithm specification description and discussion C 1 General automata and rational expressions functions C 1 1 Graph functions C 1 1 0 reverse This is a hidden and ancillary graph function not accessible to the user through TAF KIT because it would be somewhat confusing with transpose It builds the transpose of the graph including the initial and final function that can be seen as labels of arcs from subliminal to real states but leaves the labels untouched C 1 1 1 accessible coaccessible trim Graph traversal Implemented by breadth first search C 1 2 Transformations of automata C 1 2 1 proper From a theoretical point of view the algorithm proper cannot be described nor understood before addressing the problem of the star in a semiring of series 1 If M is graded then K M equipped with the Cauchy product is a semiring as well If M is not graded this may not be the case anymore but is out of the scope of VAUCANSON for the time being and for certain while 108 If T is a semiring and t is in T by definition Harr
109. r b aab cat E aab aab The normal unix shell definition allocation and utilisation of variables may be mixed with the usage of TAF KIT command lines For instance the following command will create an automaton that recognize numbers of the form 12 456 789 where a comma must be used as thousand separator d 0 1 2 3 4 5 6 7 8 9 vesn char b exp to aut a 0123456789 d d d d d d d d d gt numbers xml vesn char b eval numbers xml 1 234 987 vesn char b eval numbers xml 1 24 987 OoFrRA HSH Note how the expression must be enclosed with rather than with in order to be correctly interpreted d 0 1 2 3 4 5 6 7 8 9 vcsn char b exp to aut a 01234567891 gt d d d d d d d d d gt numbers xml Lexer error unrecognized characters d d d d d d d d d 2 1 3 Input and output formats The TAF KIT commands are supposed to input and output objects of different sorts au tomata rational expressions words weights and Boolean results Their formats are controlled by the attributes of the input and output options As shown on Table 2 3 there is one default format when no format option is called These options are used not only to control and adequatly adjust the format of data handled by TAF KIT in order to process them but allow also to make TAF KIT a translator between different format for a given object 2 1 3 1 Automata formats Automata are always files
110. r normalized transducers T Q A x B E I T and uU R B xC F J U that is the transitions of T are labelled in 4x1 or in 1x B and those of U are labelled in Bxlorin 1xC VAUCANSON 1 4 1 TAF KiT Documentation 115 July 14 2012 The proof of the Composition Theorem is equivalent to the construction of the transducer T xU QxR A xC G IxJ TxU by the following rules i If p a 1 q E then for allr R p r a 1 q r G ii If r 1 u s F then for all ge Q q r 1 u q s EG iii If p 1 2 q E and r a 1 s F then p r 1 1 q s EG A next possible step is to eliminate the transitions with label 1 1 by means of a classi cal closure algorithm Figure C 1 shows an example of such product before and after the elimination of spontaneous transitions llv lju U Ti X U z 1 y 1 1 v Llu Figure C 1 Composition Theorem on Boolean transducers Product of subnormalized transducers This construction can easily be extended to subnormalized transducers which are such that transitions are labelled in AxB 1 1 where A AU 1 It amounts to replace iii by Gii If p a a q E with a A and r x u s F with u E then p r a u q s EG In this form it contains as a particular case the composition of letter to letter transducers Product of subnormalized transducers and composition It is known that this constru
111. raphically while the Vaucanson library provides computations and algorithms operating on automata B 2 Installation B 2 1 Requirements Minimum for Visualization and Graphical Editing Any operating system that supports Java Tested on Windows XP Windows 7 Ubuntu and Mac OS X Java SE 6 Runtime Environment JRE 6 For Running Algorithms Provided by Vaucanson Requires TAF Kit from the Vaucanson library which can be compiled from source on Unix like operating system Tested on Ubuntu and Mac OS X For Development and Modification of Source Code Any operating system that supports Java Tested on Windows XP Windows 7 Ubuntu and Mac OS X 99 Java SE 6 Development Kit JDK 6 NetBeans IDE 7 1 optional but highly recommended B 2 2 Installation and Start up As long as the minimum required operating system and Java runtime environments are avail able no installation is needed to use the visualization and graphical editing functions of VGI To run algorithms implemented in Vaucanson please compile the library to produce TAF Kit following the instructions for Vaucanson To start VGI simply double click on the vgi jar file in the downloaded package Alter natively one can start VGI from a terminal window by first navigating to the directory containing vgi jar and then typing the following command java jar vgi jar B 2 3 Getting and Compiling the Source Code Since VGI is developed using the NetBeans IDE it is highly rec
112. rd for the sum operation is defined only on standard automata Specification e The standard automaton A B lt Q U R j 4 G i V gt is defined as Vo q EQU R j Eng if paeQ Fy if pqER Fig if p iandqeR Ox otherwise Vp EQU R j 1 0 Uj if p i Vp Tp if pEeQ i Up if per Gp q C 1 3 3 concatenate Precondition a zml and b zml are standard for the concatenation operation is defined only on standard automata Specification e The standard automaton A B lt QU R j A G i V gt is Vp q EQU R j Vp EQ U R j Eng if PEER Fg if pqeRrR Up if peR Gp TF Vp A ee if peQandgeR Tp Uj if peQ OK otherwise VAUCANSON 1 4 1 TAF KIT Documentation 111 July 14 2012 C 1 3 4 star Precondition a zml is standard for the star operation is defined only on standard au tomata Specification e The standard automaton A lt Q A EW i T gt is Vp q EQ hs Esp E Tj Eiq if p i DT Eid Tp Eiq D Ep q otherwise Vp EQ po Ih A j TpT otherwise C 1 3 5 left mult Precondition a zml is standard for the left exterior multiplication operation is defined only on standard automata Specification e The standard automata kA lt Q A B i T gt is defined by kE if p 1 y qE pE Pq PIER Pa Eng otherwise weg Tah I p al Tp otherwise Vaucanson 1 4 1 TAF KIT Documentation 112 July 14 2012 C 1 3 6 right mult Preco
113. re sometimes necessary to read the parameters as files under a certain formats All these options are described with more details in the next chapter 1 2 4 TAF Kit s modus operandi Each instance of TAF KIT is a compiled program which offers a set of commands All TAF KIT instances work identically They differ on the type of automata they handle and may offer different commands because not every algorithms and thus commands work on any automata type cf Chapter 3 Any time an instance of TA F KTT is run it breaks its command line into command names and arguments vcsn char b determinize al xml minimize data ec Ne eee ee eee A Oe OOS TAF KIT instance name arg name arg name arg Eno pr OS command 1 command 2 command 3 The internal pipe is used to separate commands A command starts with a name it can be followed by several arguments although only one is used in the above example These arguments can be very different depending on the command So far we have used filenames as well as to designate either the standard input or the result of the previous command Some commands will also accept plain text representing for instance a word or a rational expression As explained in Section 1 2 3 the parameter s of a command may be completed and its behaviour may be controlled by some options We describe these options with more details in the next section For each command TAF KtT will 1 parse
114. ress by a backward closure every spontaneous transition that has been created in ii By convention we consider that a transition from s to is spontaneous if 1 is scalar that is if the support of 1 i seen as a polynomial over A is restricted to the identity 14 iv Remove the former initial states of A that are the destination of no incoming transition Commentfa Steps iii and iv are necessary to insure the following property The standardization of a standard automaton A is isomorphic to A b We say by convention in iii as we could have chosen different policies without loosing the above property which is in the specification of standardize A non proper polynomial 7 could give rise to a spontaneous transition labelled with its constant term We prefered not to do it in order to change as few things as possible We could have decided to perform no closure as soon as there exists at least one initial function which is not scalar We have prefered to have a choice which is more local to every intial state but this is certainly disputable C 1 3 Operations on automata A small sketch is worth a long speech Let A lt Q A E i T gt and B lt R A F j U gt be two standard automata C 1 3 1 union Just the union of the two automata It is a graph function indeed Vaucanson 1 4 1 TAF KiT Documentation 110 July 14 2012 C 1 3 2 sum Precondition a zml and b zml are standa
115. rsions prior to 1 4 1 which had never been really documented In one word no other version than VAUCANSON 1 4 1 or VAUCANSON 1 4 should be used 0 2 Licensing VAUCANSON 1 4 1 is a free software released under the GNU General Public Licence version 2 More information on this license is to be found at http www gnu org licenses gp1 2 0 txt a copy of this license is included in each copy of VAUCANSON in the file COPYING Beware that the license for the next versions of VAUCANSON will probably be different although VAUCANSON will stay an open and free software 0 3 Prerequisites C compiler G 4 x or later XML The XML I O system is based on the use of the Apache Xerces C library version 2 7 or later http apache org xerces c On Ubuntu Debian install packages with names similar to libxerces28 and libxerces28 dev or libxerces c3 1 and libxerces c dev Boost Boost provides free peer reviewed portable C source libraries On Ubuntu Debian install the following packages libboost dev libboost serialization dev libboost graph libboost graph dev VAUCANSON is compatible with Boost versions 1 34 or later Ncurses needed for building TAF KtT On Ubuntu Debian install the following packages libncurses5 libncurses dev Graphviz The display of automata is made using AT amp T GraphViz application On Ubuntu Debian install the following package graphviz 0 4 Building Vaucanson Detailed information is provide
116. s a letter of the alphabet as in the Morse alphabet considered in the example above Caveat TAF KtT 1 4 1 does not formally implement this specification When SPACE is used between letters of the alphabet it is replaced by TIMES instead of CONCAT as it should be if it were equivalent to the empty sequence One may argue however that the actual implementation is closer to the natural intuition vcsn char b aab cat E aba bab aba bab vcsn char b aab cat E a b a b a b a b a b a b vcsn char b aab parser CONCAT cat E aba bab a b a b a b vcsn char b aab parser CONCAT cat E a b a b a b a b a b a b vcsn char b aab parser CONCAT SPACE cat E a b a b a b a b a b a b VAUCANSON 1 4 1 TAF KiT Documentation 40 July 14 2012 2 2 3 3 Overwriting the writing data The writing data are used when parsing a string into a rational expression and when writing back a rational expression as a string or even when displaying an automaton A rational expression or an automaton themselves do not call on the writing data Nevertheless and as we said above the writing data are embarked in the XML file that contains an automaton or an expression cf Appendix It makes these objects fully self contained and allows for instance to convert them as a rational expression written as a string without giving additional information The parser option
117. s the integer quotient of the divi sion by the integer k first parameter of the numbers written in base b second parameter Comments The divisor quot3base2 xml cf Figure A 16 is already in the repository Figure A 16 The divisor quot3base2 xml over 0 1 2 A 5 2 2 Program ORR Generates two fmp transducers over the alphabets guessed from the two patterns first two parameters The first trans ducer is left sequential it realises the replacement of the first pattern by the second in a left to right reading of the input The second is right sequential it realises the replacement of the first pattern by the second in a right to left reading of the input The third parameter of the program completed by _left and right gives the name of the two transducers ORR abb baa fibred Comments The fmp transducers fibred_left xml and fibred_right xml are already in the repository Vaucanson 1 4 1 TAF KiT Documentation 98 July 14 2012 Appendix B Vaucanson Graphical Interface VGI Vaucanson Graphical Interface VGI Available at http code google com p vgi Date last updated July 11 2012 B 1 Overview Vaucanson Graphical Interface VGI is a graphical user interface GUI for the Vaucanson library a software platform dedicated to the manipulation of weighted finite state automata VGI provides the functionalities to visualize and edit finite state automata g
118. se the more natural and common way of writing expressions with implicit precedence of operators Another difficulty arises when the operators letters and weights share the same alphabet of characters for their represention Finally the possi bility of having integers as generators of a free monoid that is letters that are written as sequences of characters brings in another problem We treat these questions one after the other and begin with what can be considered as the default conventions We first suppose that the alphabet is an alphabet of characters letters and or digits for the time being and has been defined by means of the alphabet option According to VAUCANSON 1 4 1 TAF KiT Documentation 33 July 14 2012 the above definition we define in VAUCANSON rational expressions over A as opposed to rational expressions over A that is any word of A string of letters of A is seen as an atomic expression This feature may prove to be somewhat misleading see below 2 2 2 1 The rational operators The three rational operators sum product and Kleene star are represented by default as in the following Table 2 6 The representation of the left and right exterior multiplications that is the representation of weights is described at Section 2 2 2 2 Input Output Operator Ex Ex Kleene star EF or E F E F concatenation implicit or explicit E F E F disjunction E according to format grouping Table 2
119. sion between them nor with the elements of the monoid In case there exist such collisions the way the tokens are recognized in a string of letters may depend upon the token vcsn char b a_abel cat E _e0 e_e_ e ete_ e vcsn char z a_aez01 cat E z_a0 ta_z0 a _z 0 a_z_e0 z_a0 a_z0ta _z 0ta_z0 In the first line the string e has been recognized as the constant 1 in the second the string z has not been recognized as the constant 0 As a consequence it is not possible in VAUCANSON 1 4 1 to use the alphabet of all ASCII characters The token TIMES As noted at Table 2 6 the token TIMES is given a unique value for the output of strings by VAUCANSON but the empty string is always accepted as input for the representation of the same operator product vcsn char b aab cat E a b bta a b b a vcsn char b a x Sar parser TIMES x PLUS cat E This has to be corrected in the forthcoming versions of VAUCANSON VAUCANSON 1 4 1 TAF KiT Documentation 39 A es es July 14 2012 The token CONCAT The token CONCAT is used to represent the same operator product but between letters of the alphabet when such a sequence forms an element of the monoid As for TIMES CONCAT is given a unique value for the output of strings by VAUCANSON but the empty string is always accepted as input for the representation of the same operator Indeed
120. splay vcsn char b display al xml The displayed automaton won t have a layout as pretty as in Figure 1 2 but it represents the same automaton nonetheless al xml 3 states 6 transitions I 1 T 1 Figure 1 2 Result of the command vcsn char b display al xml The command aut to exp outputs a rational expression which denotes the language accepted by A The command eval tells whether a word belongs to that language answer with 1 yes or 0 no This is not to be confused with a function with a Boolean answer cf Section 2 1 3 5 21f the GraphViz package is installed see Section 0 3 VAUCANSON 1 4 1 TAF KiT Documentation 13 July 14 2012 vcsn char b aut to exp a1 xml atb a b atb vcsn char b eval al xml babab 1 The automaton A is not deterministic and the determinize command will compute its determinisation As most TAF KIT commands determinize produces its output an XML file representing the automaton on the standard output an event which would hardly be of interest The normal usage is to divert the output by means of a shell redirection to a file for subsequent computation with other commands vcsn char b determinize al xml gt aldet xml vcsn char b data aldet xml States 4 Transitions 8 Initial states 1 Final states 2 vcsn char b display aldet xml aldet xml 4 states 8 transitions I 1 T 2 Figure 1 3 The determinisation of a1 xm1 The file
121. ssions and back to operations such as quotient product and shuffle from operations for Boolean automata such as determinisation or computation of the universal automaton to operations on transducers such as composition or evaluation from reduction of automata with weights in a field to transformation of automata over pairs into transducers This version TAF Kit 1 4 1 has been presented at the CIAA 2012 conference held in Porto Portugal All users are encouraged to send us remarks comments and bug reports We shall make our possible to take them into account in the minor revisions that will be made to VAUCANSON 1 4 1 until the release of VAUCANSON 2 0 VAUCANSON 1 4 1 TAF KiT Documentation 6 July 14 2012 Chapter 0 Getting started The VAUCANSON PROJECT has a web site http www vaucanson project org where all information and documentation on the different components of the project including the present manual can easily be found and downloaded 0 1 Getting Vaucanson 1 4 1 Naturally the version 1 4 1 of the VAUCANSON platform can be downloaded from the VAu CANSON PROJECT site Alternatively it can also be found at http vaucanson lrde epita fr Vaucanson1 4 1 Other previous versions of the VAUCANSON platform can be downloaded from http vaucanson lrde epita fr Caveat This version 1 4 1 is not fully backward compatible with earlier versions and this manual is not meant to document the differences with VAUCANSON ve
122. standard automaton what is often called in the literature Glushov automaton or position automaton of the expression that is thus understood to be letterized even if it not necessarily so in VAUCANSON 1 4 1 Comments In TAF KtT 1 4 1 the standard function is synonymous to exp to aut or to be more precise the exp to aut function is synonymous to standard cf Section 3 2 3 3 2 3 2 thompson vcsn thompson e xml gt a xml Computes the Thompson automaton of e zml and writes the result in a zml Specification The precise specification of thompson is to be found elsewhere and probably to be written Comments i The following holds standard e xml proper thompson e xml with the specification that proper implements the backward elimination of spontaneous tran sitions ii The way automata are built and implemented in VAUCANSON makes that this construc tion has more a historical interest than an algorithmic one It is also useful to building tests because of the above equation VAUCANSON 1 4 1 TAF KiT Documentation 65 July 14 2012 3 2 3 3 alphabet star alphabet Creates the automaton a zml whose be haviour is the characteristic series of the al phabet alpha vcsn alphabet alpha alphabet gt a xml Specification The automaton a zml has two states one initial and one final and one transition from the initial state to the final state for every letter in alpha Creates the automaton a
123. states 10 transitions 1 2 T 2 7 states 10 transitions 1 3 T 4 Figure 3 26 b composition and composition of t1 xml and u1 xml Caveat In TAF KtT 1 4 1 b composition and composition do not test the precondition is subnormalized In the case where this precondition is not met the result is not correct This error will be corrected in subsequent versions VAUCANSON 1 4 1 TAF K1T Documentation 89 July 14 2012 3 5 2 3 evaluation Computes an automaton which realizes the vcsn evaluation t xml a xml gt b xml image of the series realized by a zml by the relation realized by t zml and writes the re sult in b aml Precondition t zml is subnormalized a zml is a realtime automaton over the input monoid of t zml t zml and a zml have the same weight semiring Specification evaluation t xml a xml W image composition partial identity a xml t xm1 Comments When the weight semiring is not complete it may be the case that the evaluation is not defined in which case the call to evaluation will produce an error 3 5 2 4 eval Computes an automaton which realizes the vcsn eval t xml exp image of the expression exp by the relation fxp realized by t zml and outputs the result as the expression fap Precondition t zml is subnormalized exp is an expression over the input monoid of t aml Comments Just a wrapper for evaluation Caveat In TAF Krr 1 4 1 the expressions exp and fzp have
124. ta over A x B fmp transducers are a priori eligible to functions listed in Section 3 1 and that apply to all automata However all functions which involve reading rational expressions cat E exp to aut expand are not implemented in TAF KtT 1 4 1 The function aut to expt is nevertheless implemented for transducers On the other hand a number of functions are specific to transducers and are described in this section 1 Transformations of transducers inverse lt tdc gt transpose lt tdc gt 1 1 1 2 1 3 is subnormalized lt tdc gt subnormalize lt tdc gt 1 4 is 1t1 lt tdc gt 1 5 ltl to pair lt tdc gt 2 Operations on transducers domain lt tdc gt image lt tdc gt w domain lt tdc gt w image lt tdc gt composition lt tdc1 gt lt tdc2 gt evaluation lt tdc gt lt aut gt eval lt tdc gt lt word gt 3 Operations on behaviours of transducers 3 1 composition R lt tdc1 gt lt tdc2 gt 3 5 1 Transformations of transducers 3 5 1 1 inverse vcsn inverse t xml gt u xml u zml realizes what is called the inverse relation of the relation realized by t aml VAUCANSON 1 4 1 TAF KiT Documentation 83 July 14 2012 Precondition no precondition Specification Swaps the first for the second component in the labels of the transitions of the transducer t zml and writes the result in the transducer wu zml Comments inverse t xm1 is kind of pivotal function and will have an infl
125. the result in c aml Precondition No precondition besides the two argument convention 3 1 3 2 sum vcsn sum a xml b xml gt c xml Build the automaton that is the sum of a zml and b zml and writes the result in c zml Precondition a zml and b zml are standard for the sum operation is defined only on standard automata and obey the two argument convention Specification cf Section C 1 3 2 Vaucanson 1 4 1 TAF KiT Documentation 53 July 14 2012 3 1 3 3 concatenate eer eee E Build the automaton that is the concatena POR EESO RET AA SAS ie tion of a zml and b zml and writes the result in c zml Precondition a zml and b zml are standard for the concatenation operation is defined only on standard automata and obey the two argument convention Specification cf Section C 1 3 3 Comments The concatenate function of two automata realises the Cauchy product of their behaviours We keep the word product for a product function which is based on the Cartesian product of the automata and which realises the intersection of the accepted languages in the case of Boolean automata and the Hadamard product of the behaviours in the general case of weigted automata cf Section 3 2 4 2 3 1 3 4 star vcsn star a xml gt b xml Build the automaton that is the star of a zml and writes the result in b aml Precondition a zml is standard for the star operation is defined only on standard au tomata
126. the subliminal initial state eliminate by a backward closure the spontaneous transitions thus created and suppress among the former initial states those ones that have become not accessible after the closure A more precise specification is given by the description of the algorithm at Section C 1 2 2 Example Figure 3 3 shows a transducer tt1 xm1 built for the sake of the example and the result of the command vcsn char fmp b standardize tt1 xml display Vaucanson 1 4 1 TAF KiT Documentation 52 July 14 2012 ttl xml 5 states 7 transitions I 2 T 2 5 states 7 transitions I 1 T 3 Figure 3 3 A transducer and its standardization 3 1 3 Operations on automata Caveat Five of the seven functions described in this subsection have two input arguments The question then arise of the determination of the alphabet s of the output Normally it should be the union of the alphabet s of the input arguments In TAF KtrT 1 4 1 the alphabet s of the output is the alphabet s of the first input argument And thus the letters that appear in the labels of the second input automaton must be contained in the alphabet of the first input automaton For further reference we call this assumption the two argument convention This error will be corrected in the subsequent versions of VAUCANSON 3 1 3 1 union vcsn union a xml b xml gt c xml Builds the automaton that is the union of a zml and b zaml and writes
127. time 61 realtime 61 reduce 71 reduced expression see expression report time 30 repository see automata right mult 54 second projection 91 shortest 78 shuffle see product shuffle 68 SPACE see token 40 spontaneous see transition is standard 52 standard 65 standardize 52 STAR see token star 54 star alphabet 66 67 star S 57 state elimination method 57 113 subnormalize 85 subnormalized seetransducer85 is subnormalized 85 subword 70 suffix 76 sum 53 sum S 56 support 64 T 30 31 terminal state 75 Thompson see automaton thompson 35 65 TIMES see token 39 token CONCAT 38 CPAR 38 CWEIGHT 38 ONE 38 OPAR 38 OWEIGHT 38 PLUS 38 SPACE 38 VAUCANSON 1 4 1 TAF KiT Documentation STAR 38 TIMES 38 ZERO 38 transducer 83 letter to letter 86 subnormalized 85 88 transition epsilon 51 spontaneous 51 transpose 61 is trim 49 trim 49 trivial identities 32 union 53 universal seeautomaton78 universal 78 usage 22 V 22 v 27 29 verbose 27 29 VERBOSE_DEGREE 30 version 22 Val 43 writing data 36 38 X 30 31 Xerces 8 xml see format z 38 ZERO see token 122 July 14 2012
128. tting a state initial or final requires the speci fication of a state only for weighted ones it requires the specification of a state and of a weight vcsn char fmp b edit t1 xml Your choice 1 10 5 For state 0 vcsn char z edit c1 xml Your choice 1 11 7 For state 0 With weight 2 The description of transitions will be the same for Boolean or weighted automata but different for automata and transducers When editing an automaton the user is first asked for the origin then for the end of the transition and finally for an expression that labels the transition This expression may be a simple letter from the alphabet but also any weighted rational expression without the star operator vcsn char z aab edit test xml 10 Your choice 1 11 3 Add a transition from state 0 To state O Labeled by the expression a Your choice 1 11 3 Add a transition from state O To state O Labeled by the expression 1 1 ab 1 a 1 3 ba Automaton description States 0 Initial states O W 1 Final states 0 W 2 Transitions 1 From 0 to O labeled by a 2 From 0 to 0 labeled by 1 a 2 aba 3 ababa VAUCANSON 1 4 1 TAF K1T Documentation 44 July 14 2012 As it can be observed on the above screen capture the expression that labels the transition has been transformed into a polynomial by the expand function cf Section 3 1 5 3 Note that all simplifications have been done within the polyno
129. uence on the specification of other functions 3 5 1 2 transpose vcsn transpose t xml gt u xml Computes the transposition of the transducer t zml and writes the result in the transducer wu uml Precondition no precondition Specification i Builds the transposition of the underlying graph ii Transposes the labels of the transitions thanks to the extension of the function transpose from words to pair of words transpose f g transpose f transpose g Example Figure 3 21 shows the left to right cautious Fibonacci transducer cf 17 Exam 9 ple V 1 4 its inverse and its transpose fib gd xml 5 states 8 transitions 1 1 T 3 fib gd inv xml 5 states 8 transitions I 1 T 3 fib gd trsp xml 5 states 8 transitions l 3 T 1 Figure 3 21 The left to right cautious Fibonacci transducer its inverse and its transpose Tn 17 transducers are allowed to have final functions that have non scalar values thus the examples there and here have a slightly different look VAUCANSON 1 4 1 TAF KiT Documentation 84 July 14 2012 3 5 1 3 is subnormalized subnormalize vcsn is subnormalized v t xml I Tells whether or not the transducer t zml is subnormalized nput is not subnormalized Specification A transducer is subnormalized if it is 1 proper 2 weakly letterized in the sense that the labels of transitions are either in A x 1p or in 14 gt
130. utput the file under another format The D option yields a dot file which can be displayed on the screen The X option yields an xml file which is ready for use by other programs 2 1 4 2 Benching The bench option B for short makes TAF KIT to repeat the functions that follow the option the number of times that is specified compulsory parameter with the option The data shown in the example above are stored in a result file for each of the execution and then a summary of these data is made which contains the mean the sum the minimum and the maximum This result file is output on the standard error output which can be diverted as usual vcsn char b B5 determinize ladybird 10 xml gt ldb10det xml 2 gt 1db10 bench txt cat ldb10 bench txt e SUMMARY 22 3 222222222235 ES Arithmetic mean Task list Charge id lt name gt total self calls self avg total avg 100 0 0 _program 233 22ms 233 22ms 1 0 23s 0 23s 63 7 9 automaton output 148 47ms 148 47ms 1 148 47ms 148 47ms 30 6 7 determinize 71 29ms 71 27ms T 71 27ms 71 29ms 2 9 1 CMD 0 determiniz 84 62ms 6 88ms 1 6 88ms 84 62ms 2 6 2 automaton input 6 12ms 6 12ms 1 6 12ms 6 12ms 0 1 4 eps_removal 0 16ms 0 16ms 1 0 16ms 0 16ms 0 1 3 cut_up 0 14ms 0 14ms 1 0 14ms 0 14ms 0 0 8 is_realtime autom 0 02ms 0 02ms 1 0 02ms 0 02ms 0 0 5 accessible_states 0 02ms 0 02ms 1 0 02ms 0 02ms 0 0 6 sub_automaton 0 00ms 0 00ms 1 0 00ms 0 00ms 2 2 The writing of ratio
131. ven the algorithm that underlies the theo rem amounts to find a maximal prefix closed subset P of A such that the vectors I pu are independent in F Such set of vectors allows in turn to compute a new and equivalent rep resentation of dimension P The substance of the theorem is that it is sufficient to perform this algorithm twice in a row on the given representation and then on its transpose in order to get the reduced representation The elementary step in this algorithm is thus to determine whether a given vector belongs to a subspace generated by a set of given independent vectors and in the positive case to compute its coordinates in this system that is to solve a system of linear equations In order to reach the optimal complexity and also to be able to treat the case of non commutative fields a case which does not appear in VAUCANSON 1 4 1 these systems are solved by an iterative method of Gaussian elimination C 5 Weighted automata over a product of two free monoids C 5 2 Operations on transducers C 5 2 2 composition b composition The Composition Theorem due to Elgot and Mezei cf 17 is one of the basic results on rational relations and finite transducers The composition algorithm described here has been presented in 5 We describe first the algorithm that realises the b composition and then the more sophisticated one that realises the composition Product of normalized transducers We first consider two prope
132. x B or in Ax B 3 initial and final functions are scalar that is take values in the weight semiring Comments The terminology subnormalized is new introduced in 5 and comes from normalized which means that the labels of transitions are either in 4x1g or in 14 xB The terminology normalized is not so good as it collides with the notion of normalized automata but is widely accepted and used Once normalized is accepted subnormalized is not so bad Other suggestions are still welcome no established terminology exists vcsn subnormalize t xml gt u xml Computes from t zml a subnormalized transducer and writes the result in u zml Precondition no precondition Specification 1 As for proper above one wants to letterize first and then eliminate the spontaneous transitions 2 We are to letterize monomials such as m k f g with f in A and g in B A monomial of the form k abc xy will be decomposed in the product of n sup f g generators in the following way k a x b y c 1 3 create n 1 states between the origin and the end of the transition labeled by the monomial and the n transitions such that each of them is labeled by one of the generators we have computed in the above decomposition the first one being possibly weighted 4 eliminate the spontaneous transitions with a backward procedure Comments The subnormalize function
133. xU d Delete the black black states every state in 7 x U is a pair of states e Trim and eliminate the transitions with label 1 1 by classical closure Figure C 2 shows the construction applied to J and Uy all Figure C 2 A composition that preserves multiplicity Vaucanson 1 4 1 TAF KiT Documentation 117 July 14 2012 Bibliography 1 P Y ANGRAND S LOMBARDY J SAKAROVITCH On the number of broken derived terms of a rational expression J Automata Languages and Combinatorics 15 2010 27 51 2 C ALLAUZEN M MOHRI F PEREIRA AND M D RILEY FSM Library Man pages http www2 research att com fsmtools fsm AT amp T 1998 2003 3 C ALLAUZEN AND M D RILEY OpenFst Library Wiki http www openfst org 2010 4 V ANTIMIROV Partial derivatives of regular expressions and finite automaton construc tions Theoret Comput Sci 155 1996 291 319 5 T CLAVEIROLE S LOMBARDY S O CONNOR L N POUCHET AND J SAKAROVITCH Inside Vaucanson Proc CIAA 2005 LNCS 3845 Springer 2005 117 128 6 J M CHAMPARNAUD D ZIADI Canonical derivatives partial derivatives and finite automaton constructions Theoret Comput Sci 289 2002 137 163 7 K T CHEN R H Fox AND R LYNDON Free differential calculus IV The quotient groups of the lower central series Ann Math 68 1958 81 95 8 J H Conway Regular Algebra and Finite Machines Chapman and Hall 1971 9 M DE
134. xml cat E atb a b a b gt exp xml vesn char b ixml cat E exp xml a b a b a b 2 1 3 3 Word formats Words are always strings of letters that are read on the command line and written on the standard output Caveat Although words are from a formal point of view a simple instance of a rational expression TAF KrrT 1 4 1 handles them as objects of different and uninterchangeable types cf Section 3 2 2 1 We come back to the subject in the next section 2 1 3 4 Weight formats Weights that is elements of the weight semiring and such as the result of the evaluation of a word in an automaton for instance are simply output as strings on the standard output vcsn char z eval c1 xml 101101 45 The way they are input as strings as well as part of a rational expression is described in the next section In one case in two similar cases indeed weights will be input as argument of a function and not as part of a rational expression They will be written as strings as well which will raise some problem cf Section 3 1 3 5 2 1 3 5 Boolean result formats Some TAF KIT functions such as which determines whether an automaton is empty or not yield Boolean results In the default format such results are returned using the status code of the TAF KIT instance so that the correponding commands can be used as conditions in shell scripts According to Unix convention the status code is O for true and any
135. y in K is equivalent to a realtime automaton A with set of states Q A 1 E T where I and T are vectors in K and E is a square matrix of dimension Q whose entries are linear combination with coefficients in K of letters in A One can then write E y aya acA where every ay is a square matrix of dimension Q with entries in K These matices define a morphism jp from A into K and for every w in A the coefficient of w in the series s realised by A is lt s w gt I wu T The tuple I 1 T is called a representation of dimension Q of s Rational series over a field If K is a field F for every F rational series s there exists an integer r called the rank of s which is the minimal dimension of any representation of s A representation of minimal dimension is said to be reduced Vaucanson 1 4 1 TAF KIT Documentation 114 July 14 2012 Theorem 1 Schiitzenberger A reduced representation of a F rational series s is effec tively computable from any representation of s A reduced representation of a rational series is an object comparable to the minimal au tomaton of a rational language to the extent it is not unique but defined up to a basis transformation within F The theorem implies two F automata which realize s and t are equivalent if and only if the reduced representation of the series s t is of dimension 0 and this is decidable The algorithm A representation I u T of dimension Q being gi
136. zml whose be haviour is the characteristic series of the free monoid generated by alpha vcsn alphabet alpha star alphabet gt a xml Specification The automaton a zml has one state both initial and final and a transition for every letter in alpha Comments These commands that build automata rather than transforming them are con venient for writing scripts cf Section 3 2 4 2 for instance 3 2 4 Operations on automata 3 2 4 1 quotient coquotient vcsn quotient a xml gt b xml Computes the quotient of a ml and writes the result in b zml Precondition a zml is a realtime automaton Comments The quotient function implements an iterative refinement of equivalences over states by a variant of Hopcroft s algorithm It is a weighted quotient what is called K quotient in 17 18 For an example cf Figure 3 12 For Boolean automata quotient computes what is sometimes called the smallest simu lation Two Boolean automata are in in bisimulation if they have the same isomorphic quotient vcsn coquotient a xml gt b xml Computes the coquotient of a zml and writes the result in b aml Precondition a zml is a realtime automaton Specification coquotient a xml transpose quotient transpose a xml Comments In contrast with morphisms of Boolean automata K quotients of weighted automata are directed hence the usefulness of a coquotient command VAUCANSON 1 4 1 TAF KiT Documentation

Vaucanson 1.4.1 TAF

Contents

Download Pdf Manuals

Related Search

Related Contents