Home

Vaucanson 1.4 TAF-Kit Documentation - LRDE

1. mm Minden eene 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 1 71 27ms 71 29ms 2 9 1 CMD O determiniz 84 62ms 6 88ms 1 6 88ms 84 62ms 2 65 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 S8 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 rational 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 erpressions together with the usual and necessary convention and simplification also conceal difficulties that have to be circ
2. jesse ee Meis 2 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 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 T AF Krr 1 4 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 This has to be corrected in the forthcoming versions of VAUCANSON VaucANSON 1 4 TAF KiT Documentation 9T September 28 2011 vcsn int b a 0 1 2 cat E 10 12421 1480 1 2 2 1 vcsn int b a 0 1 12 22 cat E 10 12 122 vcsn int b Lexer error unrecognized characters
3. B 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 Vaucanson 1 4 TAF KiT Documentation 105 September 28 2011 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 D Fig S d or gives jute eg B 1 after the elimination of the state q B 1 4 1 The naive heuristics a Make real the initial and final subliminal states 7 and t From i to every initial state p there is thus 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 i and t com
4. Tf 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 101 If s is a series in K M we denote by c s its constant term that is the coefficient of 1m 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 1j 8p Under a natural and not restrictive hypothesis on K cf 16 17 the following property holds Property 1 A series s in IK 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 IK 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 1m only We then have Property 2 The behaviour of A is defined if and only if the behaviour of An is 3 Let A IL E T and Ap I Eg T be their respective matrix description We write E for the proper matrix such that E Ep Eo Property 3 If the behaviour of A is defined we have lA I E Er ET It is important to note that it is not true that A is necessarily defined when Eo and thus I Eo Ep
5. vcsn char b aab cat E a b ab atb atb ab atb vcsn char b aab cat E atb ab a b atb ab atb 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 bai or a b 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 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 vcsn char b aabc cat E atbtc a tb c VAUCANSON 1 4 TAF KIT Documentation 32 September 28 2011 thomp abc left x
6. 2 2 eval S lt aut gt lt word gt 3 From expressions to automata 3 1 standard lt exp gt 3 2 thompson lt exp gt 3 3 star alphabet lt ezp gt 4 Operations on automata quotient lt aut gt product auti lt aut2 gt power aut n shuffle auti lt aut2 gt infiltration auti 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 zml an equivalent 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 TAF KiT Documentation 58 September 28 2011 3 2 1 1 transpose vcsn transpose a xml gt b xml Computes the transposition of the automaton a zmi 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 ex
7. 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 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 5In TAF KiT 1 4 the functions which parse with rational expressions over a product of free monoids are not implemented cf Section 3 5 VaucANSON 1 4 TAF KiT
8. Eg T are defined cf 16 17 for more details and example The algorithm whose implementation depends indeed on K has the double goal of de ciding if the behaviour of Ap is defined and of computing Eo Ep and Eg T It will be described in 14 B 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 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 multiplicity semiring ii For every initial state i of A with initial function i add a transition from s to i with label i and set I i to Ox the zero of the multiplicity semiring which is equivalent to say that i is not initial anymore iii Suppress by a backward closure every spontaneous transition that has been created in ii VAUCANSON 1 4 TAF KiT Documentation 102 September 28 2011 By convention we consider that a transition from s
9. VAUCANSON 1 4 TAF K1tT 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 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 Krr and will serve as a user s manual for it TAF KIT will be the only documented part of VAUCANSON 1 4 A second phase of the project officially starting March 1st 2011 is now engaged with the same partners together 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 2 y hopefully as soon as possible and fully documented J S October 2011 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 Alexandre Duret Lutz 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 ACKNOWLEDGEMENTS Since March Ist 2011 the work on the VAUCANSON platform is supported by the Agence Nationale de la Recherche with th
10. 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 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 cf HL vcsn int fmp b a0 1 2 40 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 for the fmp instances cf Section 3 5 Unix usage The command line is first interpreted by the shell which makes the characters t UU 09 9 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 protected by or VAUCANSON 1 4 TAF KiT Documentation 23 September 28 2011 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 char 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 78
11. 3 cut up 0 15ms 0O 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 D and X options have the same behaviour as T but output 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 3The 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 TAF KIT Documentation 28 September 28 2011 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 ldbi0det xml 2 1db10 bench txt cat 1db10 bench txt Re SUMMARY
12. 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 ti xml for Ti a 1 b 1 lly Il Figure A 14 The fmp transducer Ti over a b x x yV cf Section B 5 2 2 A 5 1 2 rout ml for ii A 5 2 Factory The following program is in the data automata char fmp b directory VAUCANSON 1 4 TAF KiT Documentation 99 September 28 2011 Figure A 15 The fmp transducer Ut over x y x u v cf Section B 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 computes 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 an
13. 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 Am automaton A is ambiguous if and only if the trim part of the product Ax A contains a state outside of the diagonal 3 2 1 4 partial identity PER Tm Transforms the automaton a zml over A into an automaton vcsn partiai identi a xm Xm j e p d 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 zml 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 cipi xml vcsn char fmp z display cipi xml i OED 1 1 Cr edo a d v clpi xml 2 states 5 transitions 1 1 T 1 Figure 3 8 A weighted partial identity VAUCANSON 1 4 TAF KiT Documentation 60 September 28 2011 Caveat i The partial identity function is implemented for the TAF KIT instances vcsn char b vcsn int b vcsn char z et vcsn int z only so that the type of the resu
14. gt double 6 1 3 4 5 xml NAM transitions a counter clockwise ring of tran sitions labelled by a and a clockwise ring of transitions labelled by b Specification VAUCANSON 1 4 TAF KiT Documentation 95 September 28 2011 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 Sch tzen berger used them to give the first example of automata over a 2 letter alphabet that have arbitrary large loop complexity 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 16 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 8 Program ladybird sanan m Acadia ota Generates an n state automaton over the alphabet a b c a ir a ira o xm i GE EENS 7 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 aut
15. 34 36 X 28 Xerces 7 xml see format z 36 ZERO see token 93 September 28 2011 Appendix A Automata repository and factory The VAUCANSON 1 4 distribution contains a folder data automata where a number of au tomata and of VAUCANSON programs which build automata are ready for use by the T AF KrT 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 ml for Aj Figure A 1 The Boolean automaton An over a b cf Figure 1 2 A 1 1 2 b1 xml for B Figure A 2 The Boolean automaton B over a b 94 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 a b A 1 2 Factory The following programs are in the data automata char b directory A 1 2 1 Program divkbaseb Se eee Generates an automaton over the digit alphabet 0 b 1 AUT undi ee that recognises the writing in base 5 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
16. 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 commands of TAF Kirr all other commands are presented in the next chapter 1 1 First contact Let us first suppose that VAUCANSON is fully installed as explain
17. Documentation 109 September 28 2011 a 1 Figure B 2 A composition that preserves multiplicity VAUCANSON 1 4 TAF KiT Documentation 110 September 28 2011 Index 20 36 37 27 e 36 z 36 A 21 a 21 40 accessible 47 alphabet 21 31 40 alphabeti 21 alphabet2 21 are equivalent 69 75 are equivalent E 69 argument see convention aut to exp 12 55 62 aut to exp DM 55 aut to exp SD 55 automata repository 39 automaton accessible part of an 47 64 deterministic 72 Glushkov 63 position 63 proper 49 standard 63 Thompson 32 trim 72 unambiguous 60 universal 75 B 28 b composition 85 bench 28 bench plot output 28 binom 67 binomial coefficient 67 Boost 7 cat 39 cat E 31 40 80 chain 53 characteristic 61 coaccessible 47 complement 72 complete 71 is complete 70 composition 85 composition R 87 CONCAT see token 37 concatenate 52 condition scalar end function 43 59 61 82 convention two argument 51 CPAR see token CWEIGHT see token D 28 data 39 derived term 78 is deterministic 72 determinize 72 display 40 divkbaseb char b 18 domain 84 w domain 85 dot see format 26 dotty 26 e 36 edit 20 40 82 enumerate 74 epsilon see transition eval 12 62 87 eval S 62 evaluation 87 exp see format 111 exp to aut 20 23 56 80 expand 35 42 56 66 67 export time
18. Documentation 34 September 28 2011 vcsn char b aab1 cat E 0 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 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 ei 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
19. 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 TAF KIT is run it breaks its command line into command names and arguments vcsn char b determinize al xml minimize data LLLA LV OS W TAF KiT instance name arg name arg name arg 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 KrrT will 1 parse the options 2 parse all expected arguments using indications that may have been given by options 3 execute the algorithm 4 print the result in
20. TAF KiT Documentation 18 September 28 2011 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 aml denote the same language Precondition no precondition Specification are equivalent E e xml f xml are equivalent standard e xm1 standard f xml Caveat The specifications for the input format of rational expressions apply for this function Vaucanson 1 4 TAF KiT Documentation 19 September 28 2011 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 Sch tzenberger theorem These would be called rw transducers in VAUCANSON rw stands for rational weights They are not implemented in TAF Kir 1 4 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 KIT 1 4 they are both alphabets of
21. a mt and b aml 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 xm1 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 TAF KiT Documentation 54 September 28 2011 3 1 4 3 star S vcsn star a xml gt b xml Build a standard 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 vcsn oxml aut to exp SO a xml gt e xml behaviour of a zml and writes the result mb aml Precondition No precondition Specification star S a xml star standardize a xm1l 3 1 5 Automata and expressions operations on expressions 3 1 5 1 aut to exp aut to exp DM aut aut to exp S0 aut 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 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
22. a traversal of the under lying graph of a aml 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 vcsn v is trim a xml luput is not trin Tells whether or not the automaton a zml is trim Specification is trim a xml is accessible a xml is coaccessible a xml 3 As the functions of this section are valid for all instances of TAF KIT 1 4 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 TAF K1T Documentation 47 September 28 2011 3 1 1 3 is empty vcsn v is empty a xml l put de aot epe 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 a sequence of co t
23. 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 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 oxml cat E atb a b a b gt exp xml vcsn char b ixml cat E exp xml a b a b a b VAUCANSON 1 4 TAF KiT Documentation 26 September 28 2011 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 T AF Krr 1 4 handles them as objects of different and uninterchangeable types 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
24. 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 L 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 T space 69 om e DE eL Ga A 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 TAF KiT Documentation 21 September 28 2011 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 1 0 1 gt dec bin xml vcsn char b quotient dec bin xml VI display dec bin xml 4 states 9 transitions 1 1 T 1 Figure 2 2 Result of the command vcsn char b quotient dec 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 au
25. and b azml 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 Krr 1 4 VAUCANSON 1 4 TAF KiT Documentation 65 September 28 2011 Specification The shuffle of a aml and b aml is by definition cf 16 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 defined by alk alk VpqcA VvreB p q r p q p r ANB q r Vpc A Vr sc B a jm p s r s r S T p VT m P T p and the initial and final functions by Vpc A Vre B 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 16 Exer ITI 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
26. and b zml are standard for the sum operation is defined only on standard automata and obey the two argument convention Specification cf Section B 1 3 2 VAUCANSON 1 4 TAF KiT Documentation l September 28 2011 3 1 3 3 concatenate Pod e e Jj Build the automaton that is the concatena i Xm c xm A a EE QUSE tion of a xml and b zml and writes the result in c zml Precondition o zl and pb emt are standard for the concatenation operation is defined only on standard automata and obey the two argument convention Specification cf Section B 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 zml Precondition a zml is standard for the star operation is defined only on standard au tomata Specification cf Section B 1 3 4 3 1 3 5 left mult vcsn left mult a xml k gt b xml Build the automaton that is obtained by multiplication on the left of a zmi by k and writes the result mb emt Precondition a zml is standar
27. b xml Computes the minimized automaton of a zml and writes the result in b aml Precondition o ml 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 minimize a xm1 is the minimal automaton of the language accepted by a zml ii TAF KIT 1 4 the quotient algorithm is specialised to Boolean automata and implements the Hopcroft algorithm alcmp xml 4 states 8 transitions 1 1 T 2 almin xml 3 states 6 transitions 1 1 YT 1 Figure 3 16 The complement of aildet xm1 and its minimisation 3 4 1 5 prefix suffix factor Vas profit ciami o put 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 zmi prefix a xml is an automaton which accepts all prefixes of words in the language accepted by a aml vcsn suffix a xml gt b xml Makes every state of o zm initial and writes the result in b aml Precondition a zml is realtime and trim Comments Thanks to the preconditions b zmi suffix a xml is an automaton which accepts all suffixes of words in the language accepted by a aml VaucANSON 1 4 TAF KiT Documentation 73 September 28 2011 vcsn factor a xml gt b xml Makes every state of a aml initial and final and writes the result in b zml Precondition
28. char z product ci xml ustar xml gt clu xml vcsn char z display ciu xml SEN pe Ee 2 0 2 1 Er 2 1 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 VaucANSON 1 4 TAF KiT Documentation 64 September 28 2011 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 em Precondition i o zl is 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 Krr 1 4 Specification vcsn power a xml O 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 vcsn char z power cci xml 2 gt cc2 xml vcsn char z quotient cc2 xml 2 gt cc2q xml CDa aa b l v ccl xml 2 states 3 transitions 1 1 8T 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 vcsn shuffle a xml b xml gt c xml Computes the shuffle of a aml and b aml and writes the result in c zml Precondition i o zl
29. command For Boolean automata or transducers setting 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 cl ml Your choice 1 11 7 For state O 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 The repetition of the menu after each command may seem heavy But it proves to be very convenient VAUCANSON 1 4 TAF KiT Documentation 41 September 28 2011 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 O Initial states O W 1 Final states O W 2 Transitions 1 From 0 to O labeled by a 2 From 0 to 0 labeled by 1 a 2 aba 3 ababa As it can be observed on the above screen capture the expression that labels the transi
30. 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 where x 5 XML The XML I O system is based on the use of the Apache Xerces C library version 2 7 http apache org xerces c On Ubuntu Debian install the following packages libxerces27 and libxerces28 dev or libxerces28 and libxerces28 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 gt 1 34 It shall be noted that with Boost 1 44 a special flag must be given to the compiler through the configure file CPPFLAGS DBOOST SPIRIT USE OLD NAMESPACE Ncurses needed for building TAF Krr 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 provided in both INSTALL and doc README txt files The following installation commands will install VAUCANSON in usr local cd vaucanson 1 4 configure make sudo make install Depending on your architecture both Boost and Xerces might be
31. 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 TAF KiT Documentation 24 September 28 2011 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 How XML FsM XML fsm fsm OPENFST X dot dot v 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 b xml 0 a k k kk CO o o o OO OO OO CH 0 0 0 0 1 1 1 vcsn char z ofsm cat bi xml ifsm eval bab 2 Caveat The fsm format is not really implemented in TAF KrT 1 4 It has been added in a way which is more a feasibility proof There are indeed two reasons for the limitat
32. located in non standard directories If you are unsure of the location of your libraries you may type in your shell whereis boost These commands will return the paths to Boost headers You can then specify this directories to the configure file through the use of two environment variables CPPFLAGS for the header files and LDFLAGS for the library files For instance if your 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 lib you will use the following configure line 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 simply compiled it the TAF KIT binaries are to be found in the directory vaucanson 1 4 taf kit tests This directory contains wrappers around the real T AF KrT programs from vaucanson 1 4 taf kit src that enable them to run locally 0 5 MacOSX specifics The installation process of VAUCANSON and its dependencies on MacOS X is less straightfor ward than onto other Linux systems First the MacOS X system should be up to date before going through the rest of the installation process Second the macports software will be 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 o
33. mk Ae ge quedes 23 4 edisSptay ssis gaiari u T deae a a e he a A 2 3 5 36d Eb 8 up ku ao Ae ke add ede es Abdo Be eed 3 Specification of functions on automata and rational expressions 3 1 General automata and rational expressions JLL Graph functions scr eta ete Sse Bede a et els RR date Bs 3 1 2 Transformations of automata ses 00 00 1 NNN 11 11 14 14 15 16 17 18 19 19 19 20 24 27 29 29 31 34 39 39 39 39 40 40 40 VAUCANSON 1 4 TAF KiT Documentation 2 September 28 2011 3 2 3 3 3 4 3 5 3 6 3 1 8 Operations on automata 3 1 4 Operations on behaviour of automata 3 1 5 Automata and expressions operations on expressions Weighted automata and expressions over free monoids 3 2 1 Properties and transformations of automata 3 2 2 Behaviour of automata 3 2 3 From expressions to automata 3 2 4 Operations on automata Automata and rational expressions on free monoids with weights in a field 3 3 1 3 3 2 Operations on expressions Operations on automata Boolean automata and rational expressions on free monoids 3 4 1 Operations on automata 3 4 2 Operations on the behaviour of automata 3 4 3 Operations on expressions Weighted automata over a product of two free monoids 3 5 1 3 5 2 Operations on transducers Transformations of transducers 3 5 8 Operations on behaviours of transducers Weighted automata on free monoi
34. of the components of the product contain 1 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 vcsn char char b a a 0 b 1 exp to aut a 0 b 1 gt ex pairi xml vcsn char char b aut to exp ex pair1 xml b 1 a 0 a 0 b 1 a 0 a 0 b 12 b 102 a 0 3 0 1 a 0 vcsn char char b second projection ex pairi xml vcsn char b aut to exp 1 40 0 1 0 0 1 1 0 0 e 0 0 e vcsn char char b pair to fmp ex pairi xml gt ex fmpi xml vcsn char fmp b aut to exp ex fmp1 xml 5 1 a 0 a 0 b 102 a 0 a 0 b 1 b 122 a 0 a 0 1 a 0 vcsn char fmp b image ex fmpi xml vcsn char b aut to exp 1 40 0 1 0 0 1 1 0 0 e 0 0 e VAUCANSON 1 4 TAF KiT Documentation 35 September 28 2011 a 0 1 a 0 1 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 Zz vcsn int z a 2 3 expand 2 1 2 e 2 2 3 2 Explicit parametrization the pa
35. one path labeled aa y in 7 and one path labeled y u in U1 and there are two paths labeled aa u in Ti U1 Hence 7 Ga U does not realize the composition of the weighted relations realized by 7 and U Preparation of transducers for the composition In order to have 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 4 can be described as follows a Split the states of 7 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 1x C 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 pau d Delete the black black states every state in 7 ra U is a pair of states e Trim and eliminate the transitions with label 1 1 by classical closure Figure B 2 shows the construction applied to J and U4 VAUCANSON 1 4 TAF KiT
36. spontaneous transitions such that one gets a valid automaton the behaviour of prp tst1 xm1 itself is defined if and only if k lt i and this is to be detected by the algorithm 5Often called also e transitions VaucANSON 1 4 TAF KiT Documentation 49 September 28 2011 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 I Tells whether or not the automaton a zml is standard nput 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 ami 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 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 de
37. states 6 transitions I 1 T 1 Figure 1 2 Result of the command vcsn char b display al ml The command aut to exp outputs a rational expression which denotes the language accepted by An 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 ZU the GraphViz package is installed see Section 0 3 VAUCANSON 1 4 TAF KiT Documentation 12 September 28 2011 vcsn char b aut to exp al ml atb a b atb vcsn char b eval ai ml 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 ml gt aldet xml vcsn char b data aidet xml States 4 Transitions 8 Initial states 1 Final states 2 vcsn char b display aidet xml aldet xml 4 states 8 transitions I 1 T 22 Figure 1 3 The determinisation of al ml The file aldet xm1 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 d
38. 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 characteristic property which makes a necessary i The result depends indeed only on a zml itself not on its type ii The empty automaton Y is deterministic vcsn determinize a xml gt b xml Computes the determinisation of a zml and writes the result in b aml 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 Y W cf Figure 1 3 for the determinisation of al ml 3 4 1 3 complement vcsn complement a xml gt b xml Computes the complement automaton of o zm and writes the result in 5 zml Precondition o 20 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 TAF KiT Documentation 72 September 28 2011 3 4 1 4 minimize vcsn minimize a xml gt
39. to i is spontaneous if is scalar that is if the support of 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 Comments a 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 TU 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 B 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 B 1 3 1 union Just the union of the two automata It is a graph function indeed B 1 3 2 sum Precondition a zml and b aml are standard for the sum operation is defined only on standard automata Specification e The standard automaton A B QU R j 4 G i V gt is defined as VAUCANSON 1 4 TAF KiT Documentation 10
40. will serve as a landmark for both functionalities and performance of the first phase of VAUCANSON It will be coined VAUCANSON 1 4 Moreover there will be a TAF Krr 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 TAF Kir 1 4 will be the only documented part of VAUCANSON 1 4 A beta version of VAUCANSON 1 4 has been presented at the FSMNLP 2011 Conference held in Blois France from July 12 to July 15 2011 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 until the release of VAUCANSON 2 0 VaucANSON 1 4 TAF KiT Documentation 6 September 28 2011 Chapter 0 Administrativia 0 1 Getting Vaucanson 1 4 The version 1 4 of the VAUCANSON platform can be downloaded from http www lrde epita fr cgi bin twiki view Vaucanson Vaucanson1 A Other previous versions of the VAUCANSON platform can be downloaded from http vaucanson lrde epita fr Please note this manual is not meant to be backward compatible with VAUCANSON versions prior to 1 4 0 2 Licensing VAUCANSON 1 4 is a free software released under the GNU General Public Licence version 2 If you are unfamiliar with this license please refer to http www gnu org licenses gpl 2 0 txt a copy of this license is included in each
41. xml ba xml aut to exp a btb a b ata b a b b atb a a b vcsn char z shuffle ab xml ba xml aut to exp M expand abab 2 abba 2 baab baba VAUCANSON 1 4 TAF KiT Documentation 66 September 28 2011 3 2 4 5 infiltration vcsn infiltration a xml b xml gt c xml Computes the infiltration of a zml and b aml and writes the result in e emt Precondition i o zl and b azml are realtime automata and obey the two argument convention ii This operation requires to be meaningful that the weight semiring be commutative Specification The infiltration of a amt and b zml is by definition cf 16 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 vcsn char z infiltration ab xml ab xml aut to exp M expand 2 aab 4 aabb ab 2 ababt 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 15 Chap 6 More precisely if H denotes the number of subwords of f equal to g and f fg the polynomial obtained by the infiltration of
42. 19 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 DELGADO 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 Jyr 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 89 13 S LOMBARDY J SAKAROVITCH The Universal Automaton in Logic and Automata History and Perspectives J Flum E Gradel Th W
43. 2 vcsn int b a 0 1 12 22 cat E 10 12 1 22 140 1241422 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 is a letter of the alphabet as in the Morse alphabet considered in the example above Caveat TAF Krr 1 4 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 CUNCAT cat E ab a ba b a b a b a b vcsn char b aab parser CONCAT SPACE cat E a b a bXasb a b a b a b 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 automat
44. 3 September 28 2011 Vp q EQU R j Eng if pqeQ Fag if pqcR Fiq if p iandqER Ox otherwise Vp EQU RN j Ti 8 U if psi Vp 4 Tp if peQ i Up if pER Gp q B 1 3 3 concatenate Precondition a zml and b aml 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 g EQU R j Vp EQ U RV j Eng if pqeQ Tg if pqcR U if nech Gy T F Vp pHing if pcQandqcR Tp Uj if pEQ OK otherwise B 1 3 4 star Precondition a zml is standard for the star operation is defined only on standard au tomata Specification VAUCANSON 1 4 TAF KIT Documentation 104 September 28 2011 e The standard automaton Ar lt Q A Eil i T gt is Vp q EQ EO 2 Jl Pia pape TE ToT Eiq Ep otherwise Vp Q T9 ih i pest R Ty1 otherwise B 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 EV i T2 is defined by Vp qeQ 9 re WU pen ia Eng otherwise weQ Tah SC F T otherwise B 1 3 6 right mult Precondition 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 i TC is defined by vpeQ Ti Tpk
45. 9 where a comma must be used as thousand separator d 0 1 2 3 4 5 6 7 8 9 vcsn char b exp to aut a 0123456789 d d d d d d d d d gt numbers xml vcsn char b eval numbers xml 1 234 987 vcsn char b eval numbers xml 1 24 987 O ep tz 99 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 0123456789 d d d d d d d d d gt numbers xml Lexer error unrecognized characters dt 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 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
46. UCANSON 1 4 TAF KiT Documentation 61 September 28 2011 cispp xml 2 states 5 transitions l 1 T 1 Figure 3 10 The support of C4 3 2 2 Behaviour of automata The function aut to exp and its variant 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 by a aml Precondition i a aml is realtime ii word is a sequence of letters in the input alphabet of a ml the generators of A Example vcsn char z power ci xml 10 gt c10 xml vcsn 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 vcsn char z eval c iO xml 1 0 FATAL Cannot parse 1 0 Comments cf Section B 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 by a aml Precondition i No condition on a ami ii As for eval word is a sequence of letters in the input alphabet of a mi Specification eval S a xml uord eval realtime a xml uword Tef Section 3 2 4 3 VAUCANSON 1 4 TAF KiT Documentation 62 September 28 2011 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 zm and writes the result in a zml Specification We call standard
47. a format that can be controlled using options When commands are chained internally using NI and the printing step of the com mand before the and the parsing step of the command after the are of course omitted VaucANSON 1 4 TAF KiT Documentation 17 September 28 2011 1 2 5 Automata repository and factory Most of TAF Kirr 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 5 Other features of TAF Kirr 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 KIT 1 4 their list is available via the option list automata vcsn char b list automata The following automata are predefined ai xml bi xml div3base2 xml double 3 1 xml ladybird 6 xml For every TAF KIT instance vcsn xxx 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
48. a zml is realtime and trim Comments Thanks to the preconditions b zmi 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 these automata accept all words the example shows how the construction works 3 states 6 transitions l 1 T 3 3 states 6 transitions 1 3 T 1 3 states 6 transitions l 3 T 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 xm1 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 TAF K1T Documentation 14 September 28 2011 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 zml Precondition a zml is realtime Specification If is useless a xm1 the shortest function exits with a
49. acters pairs of character and integer pairs of integers pairs of characters pairs of integers characters characters integers integers weight semiring function sections B V A B V Z x Z x Z max Z min D RE x Q x F2 X B V B V B V Z x Z x B V A Z x B V A Z x 1 2 4 4 ee ee ki Fi Fil ki CO CO CO OTIN N NN NIN N b2 MIb Dawe SF BPW ww DDD Table 3 1 The TAF KIT instances in VAUCANSON 1 4 and their commands VAUCANSON 1 4 TAF KiT Documentation S45 September 28 2011 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 accessible lt aut gt coaccessible lt aut gt 2 trim lt aut gt is trim lt aut gt 3 is empty lt aut gt 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 auti lt aut2 gt sum cauti lt aut2 g
50. alled reduced expression which is obviously equivalent to the original expression 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 is rewritten as indicated on the right These rewriting rules mean that it is impossible for VAUCANSON to output a rational expression such as 3 0 ab 4 This expression is by construction equal to 4 1 as it can be verified with the following command vcsn char z aab cat E 3 O0 ab 4 4 1 VAUCANSON 1 4 TAF KiT Documentation 30 September 28 2011 E00 0E 0 E 0 gt E 0 ESE ELSE 1EsE Or 1 T Je HE 0 El et 0 k 0 0 O kR 20 k JE2E E Ik gt E Tx k RFE khjE E k h E kh ASE h k E h Uk II E k 1 gt E k k 1 E gt k E Ux Uk TEL z k kim Table 2 5 The trivial identities 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 actually implemented in VAUCANSON 1 4 and is somehow a mistake A more na
51. 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 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 VAUCANSON 1 4 TAF KiT Documentation 31 September 28 2011 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 6 Rational operators 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 a b ab a b VAUCANSON outputs it by making the product between non atomic subexpressions explicit
52. and writes the result in the transducer wu zml Comments inverse t xml is kind of pivotal function and will have an influence 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 aml and writes the result in the transducer wu sml 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 16 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 l 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 Hin 16 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 TAF KiT Documentation 81 September 28 2011 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 l pr
53. 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 divbbase3 xml States 3 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 DU VAUCANSON is only compiled without being installed one should first go to the vaucanson 1 4 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 TAF KiT Documentation 18 September 28 2011 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 the 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 parametriz
54. ata on either files using the same syntax because T AF KrT 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 ml vcsn char b data States 4 Transitions 8 Initial states 1 Final states 2 VAUCANSON 1 4 TAF KiT Documentation 13 September 28 2011 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 ai ml 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 the 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 compilat
55. ation 77 September 28 2011 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 aml Precondition no precondition Specification The definition of the derived term automaton of an expression in the Boolean case is due to Antimirov 4 and can be found in other references 1 1 12 16 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 cf 16 Exer I 5 5 vcsn char b aut to exp SO div3base2 xml O 1 1 0 1 0 0 1 0 1 041 0 1 0 1 1 0 0 1 1 0 1 1 0 0 vcsn char b aut to exp S0 div3base2 xml derived term 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 implements the ideas introduced in 6 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 but will be in subsequent versions of VAUCANSON iii The derived term function is sensitive to the bracketting of the expression cf 1 VaucANSON 1 4
56. ation 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 19 long option short purpose of the option help Give the help list usage Give a short usage message version V Print program version list commands T 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 alp
57. 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 universal lt aut gt 3 Operations on expressions 3 1 derived term ezp 3 2 are equivalent E lt exp1 gt lt exp2 gt Comments For clarifying specifications we make use of some specific automata e Y is the empty automaton no state e 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 aml over the alphabet A is complete if a it has at least one initial state Vaucanson 1 4 TAF KiT Documentation 70 September 28 2011 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 o ml 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 wh
58. 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 Comments In TAF KIT 1 4 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 1 5 2 3 2 3 2 thompson vcsn thompson e xml gt a xml Computes the Thompson automaton of e zm and writes the vcsn alphabet alpha star alphabet gt a xml vcsn quotient a xml gt b xml result in a mi 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 3 2 3 3 star alphabet Creates the automaton a zmi whose be haviour is the characteristic series of the free monoid generated by alpha Specification The automaton a zml has one state both initial and final and a transition for every letter in alpha 3 2 4 Operations on automata 3 2 4 1 quotient Computes the quotient of a mt and writes t
59. characters or both alphabets of integers and the weight semiring numerical and commutative by K in TAF Kir 1 4 B or Z We denote the transducers by tdc rather than by aut As automata over A x B fmp transducers are eligible to functions listed in Section 3 1 and that apply to all automata For technical reasons functions which involve reading rational expressions cat E exp to aut are not implemented in TAF Krr 1 4 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 1tl tdc 1 5 ltl to pair lt tdc gt 2 Operations on transducers domain lt tdc gt image idc w domain dc w image lt tdc gt composition lt tdc1 gt lt tdc2 gt evaluation lt tdc gt lt aut gt 2 1 2 2 2 3 2 4 eval tdc word 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 a ml realizes what is called the inverse relation of the relation realized by t zml VAUCANSON 1 4 TAF KiT Documentation 80 September 28 2011 Precondition no precondition Specification Swaps the first for the second component in the labels of the transitions of the transducer t aml
60. csn 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 ja 05 0ja 1 6 COD Figure A 10 The Zmin automaton minab xml over a 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 lja O a m O a 0 b 0 b 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 bab 0 a ue O a 0 0 b 0 b Figure A 12 The Zmin automaton sag xml over a b VAUCANSON 1 4 TAF KiT Documentation 98 September 28 2011 A A 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 maa 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 lla 0 p 0 016 O b 0 b 0 b Figure A 13 The Zmin automaton maxblocka xml over a b Ah B fmp transducers
61. d 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 TAF KiT Documentation 100 September 28 2011 Appendix B Algorithm specification description and discussion B 1 General automata and rational expressions functions B 1 1 Graph functions B 1 1 0 reverse This is a hidden and ancillary graph function not accessible to the user through TAF Krr 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 B 1 1 1 accessible coaccessible trim Graph traversal Implemented by breadth first search B 1 2 Transformations of automata B 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 T is a semiring and t is in T by definition t 2 t ncN 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 starO with obvious meaning and result
62. d for the left exterior multiplication operation is defined only on standard automata Specification cf Section B 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 m VAUCANSON 1 4 TAF KiT Documentation 52 September 28 2011 3 1 3 6 right mult 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 aml Precondition a zml is standard for the right exterior multiplication operation is defined only on standard automata Specification cf Section B 1 3 6 Example Figure 3 4 shows the effect of a left and a right exterior multiplication on the standardization of the Z automaton c1 xml vcsn char z standardize ci xml left mult 3 display vcsn char z standardize ci xml right mult 5 display Lr 2 0 2 D 5 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 3 1 3 7 chain vcsn chain a xml n gt b xml Build the concatenation of n copies of a zm 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 i
63. dot 28 export time xml 28 expression reduced 30 40 factor 74 field 68 first projection 88 format dot 24 exp 24 fpexp 24 32 fsm 24 40 xml 24 40 fpexp see format fsm see format Graphviz 40 Graphviz 8 26 help 20 27 i 25 40 87 image 84 w image 85 infiltration see product infiltration 67 input 25 internal see pipe intersection 75 inverse 80 is empty 27 48 is unambiguous 60 is useless 48 L 20 1 20 left mult 52 letter to letter seetransducer83 letterize 58 list all commands 20 list automata 18 20 list commands 20 is 1tl 83 ltl to pair 83 minimize 73 VAUCANSON 1 4 TAF KiT Documentation Ncurses 7 0 28 o 25 40 87 ONE see token OPAR see token OPENFST 25 OpenFST 24 output 25 OWEIGHT see token P 36 p 36 pair to fmp 88 parser 36 parser1 36 parser2 36 partial identity 60 pipe internal 14 17 61 shell 13 PLUS see token power 62 65 predefined alphabets 21 prefix 73 product Cauchy 52 54 Hadamard 52 infiltration 67 shuffle 65 product 52 64 product S 54 is proper 48 proper 49 63 Q 36 quotient 22 63 radix ordering 74 rational expression 29 operator 29 realtime 62 64 65 is realtime 59 realtime 59 reduce 68 reduced expression see expression report time 28 112 September 28 2011 repository see automata right mult 53 seco
64. ds over alphabets of pairs 3 6 1 Transformations of automata Bibilography Index A Automata repository and factory A 1 A 2 A 3 A 4 A 5 VAUCANSON 1 4 TAF KiT Documentation automata A 1 1 Repository A 1 2 Factory Z automata A 2 1 Repository Zmin automata A 3 1 Repository Zmax automata A 4 1 Repository fmp transducers A 5 1 Repository A 5 2 Factory 51 54 55 58 58 62 63 63 68 68 69 70 70 74 78 80 80 84 87 88 88 89 91 94 94 94 95 96 96 98 98 99 99 99 99 99 September 28 2011 B Algorithm specification description and discussion 101 B 1 General automata and rational expressions functions 101 B 1 1 Graph functions 101 B 1 2 Transformations of automata le 101 B 1 3 Operations on automata ooa 103 B 1 4 From automata to expressions ees 105 B 2 Weighted automata and rational expressions over free monoids 106 B 2 2 Behaviour of automata 22e n 106 B 3 Automata and rational expressions on free monoids with weights in a field 107 B 3 1 Operations on automata llle 107 B 5 Weighted automata over a product of two free monoids 108 B 5 2 Operations on transducers sooo a 108 VaucANSON 1 4 TAF KiT Documentation 4 September 28 2011 Introduction VAUCANSON is a free software platform dedicated to the manipulation of finite state automata Here finite sta
65. due to Delgado Morais 9 or simply the order of the state identifiers Build a rational expression which denotes the behaviour of o ml and writes the result in e ml Precondition No precondition Specification cf Section B 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 cca a cta bec cta 1 vcsn char b aut to exp DM ladybird 3 xml a b c c a b c a b c cta 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 a c atbtc ct1 On this 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 vcsn char z aut to exp cl ml 0 1 1 2 0 2 1 vcsn char fmp b aut to exp EI ml a 1 1 y 1 x b 1 a 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 12 1 VAUCANSON 1 4 TAF KiT Documentation 55 September 28 2011 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
66. dure eliminates the spontaneous transitions of the automaton The result may not be defined for some automata of certain type We follow the definition taken in 16 17 and consider that the result is defined 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 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 IF is treated separately Altogether the algorithm is valid for all instances of TAF Krr 1 4 It is will be indeed documented in 14 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 i in the illustration below vcsn char q aa edit prp tsti xml Automaton description States 0 1 2 3 Initial states O W 1 Final states 2 W 1 Transitions 1 From 0 to 0 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 Although there exists always an order to eliminating the
67. e entries are linear combination with coefficients in K of letters in A One can then write E 3 aua acA where every aj is a square matrix of dimension Q with entries in K These matices define a morphism jp from A into KH 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 u 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 Theorem 1 Sch tzenberger 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 automaton 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 J u T of dimension Q being given the algorithm that underlies the theorem amounts to find a maximal prefix closed subset P of A such that the vectors I pu are independent in PH Such set of vectors allows in turn to compute a new and equivalent repre
68. e expressions exp and fzp have 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 iei ec ost tf SA S Computes a transducer that realizes the com vcsn composition XIn u xm v xm a Fi R position of the relations realized by aml and a ml and writes the result in v zml Precondition t zmli and u zml have matching monoids output of t zml input of a ml and the same weight semiring Specification composition R t xml u aml composition subnormalize t xml subnormalize u xm1 VaucANSON 1 4 TAF KiT Documentation 87 September 28 2011 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 b in B and c in C A is thus a subset of Bx C BxC 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 Kirr 1 4 there are not many functions special to automata over such alphabets There will be more in subsequent versions At this stage what is mo
69. e project ANR 10 INTB 0203 VaucANSON 1 4 TAF KiT Documentation 1 September 28 2011 Table of contents Introduction 0 Administrativia 0 1 Getting VAUCANSON 14 pe 22k nun R9 LORS BUR eee ee a 0 2 Licensing 2 508 3e 9 9 3 PLA A OE SIR RO Re a HDD A Ss 0 3 Prerequisites i zo dc vee segs Rasse V eu Rob Ed RN N HORE Rods 0 4 Building VAUCANSON 24s sho 0 5 MacOS X specifies dnte du eerte eget re CR eR RD ee Edd 1 Presentation of TAF Kit Ladle First contact edee t aM gage aot db ee oc eee eo he egere deoa fes S and 1 2 STA Kip oreanisation ere ee CX A Robles a alee EOD 12 1 Automata types 4 i49 wx C XU xS RR UE d WR EA 1 2 2 PAF KIT instances uem date ics Up RS GERE PR PRIN d 1 2 8 Command options ee 1 24 TAF Krr smodusoperandi 2 222222 lle 1 2 5 Automata repository and factory 2 Specification of options and IO functions 2 1 Simple options 28 ux ted Uu SLE EE at EE i Ca eei CR Ra 2 1 1 Information options eh 2 1 2 Alphabet specification 2 1 3 Input and output formats e 2 1 4 Benchmarking options 2 2 The writing of rational expressions 2 241 The definition of expressions 2 2 2 Parsing strings into expressions 000004 2 2 8 Parser parametrization e 2 3 TAF KiT IO functions 0 0 sss 2 3 0 Data file location 2 2 ss 2 9 lI 3data voix lt 3 v etr oec bk Bde et dec es beds E E EE 2 9 9 CAES eee sade See seu
70. ed in Section 0 4 Any of the following commands could be typed and their results observed We describe now some of the functions of the instance of TAF Krr 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 lf VAUCANSON is only compiled without being installed one should first go to the vaucanson 1 4 taf kit tests directory by a cd command and type vcsn char b instead of vcsn char b for each of the following commands 11 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 An over a b The first command data will just make sure that TAF KrT knows about this automaton It will display the number of states transitions initial states and final states of An vcsn char b data ai mi States 3 Transitions 6 Initial states 1 Final states 1 This automaton a1 xml can also be displayed with the command display vcsn char b display ai ml 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
71. edefined alphabets 21 prefix 73 product Cauchy 52 54 Hadamard 52 infiltration 67 shuffle 65 product 52 64 product S 54 is proper 48 proper 49 63 Q 36 quotient 22 63 radix ordering 74 rational expression 29 operator 29 realtime 62 64 65 is realtime 59 realtime 59 reduce 68 reduced expression see expression report time 28 92 September 28 2011 repository see automata right mult 53 second projection 88 shortest 75 shuffle see product shuffle 65 SPACE see token 38 spontaneous see transition is standard 50 standard 63 standardize 50 STAR see token star 52 star alphabet 63 64 star S 55 state elimination method 55 105 subnormalize 82 subnormalized seetransducer82 is subnormalized 82 subword 67 suffix 73 sum 51 sum S 54 support 61 T 28 terminal state 72 Thompson see automaton thompson 32 63 TIMES see token 37 token CONCAT 36 CPAR 36 CWEIGHT 36 ONE 36 OPAR 36 OWEIGHT 36 PLUS 36 SPACE 36 STAR 36 TIMES 36 ZERO 36 transducer 80 letter to letter 83 subnormalized 82 85 transition VAUCANSON 1 4 TAF KiT Documentation epsilon 49 spontaneous 49 transpose 59 is trim 47 trim 47 trivial identities 30 union 51 universal seeautomaton75 universal 75 usage 20 V 20 v 25 27 verbose 25 27 VERBOSE DEGREE 28 version 20 Var 40 writing data
72. erminal 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 I 1 T 1 Figure 3 1 The Z automaton us1l 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 Specification VaucANSON 1 4 TAF KiT Documentation 48 September 28 2011 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 o mt and writes the result in b aml Specification i This procedure can be called for automata of any type ii The proce
73. ers 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 only 18 combinations are instanciated Table 1 3 shows these instances their names that is how they should be called from the she11 and the type of automata they allow to work with Vaucanson 1 4 TAF KiT Documentation 15 September 28 2011 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 vcsn char z automata characters Z x vcsn int z automata integers Z x vcsn char char z automata pairs of characters Z x vcsn int int z automata pairs of integers Z x vcsn char zmax automata characters Z max vcsn char zmin automata characters Z min 4 vcsn char r automata characters R x vcsn char q automata characters Q x vcsn char f2 automata characters F2 x vcsn char fmp b transducers characters B V vcsn char fmp z transducers characters Z x vcsn int fmp b transducers integers B V A vcsn int fm
74. f and g it holds lt f T9 9 gt g It is then easy to write a script that computes write the following lines bin sh vcsn char z a 1 exp to aut 2 gt tmp tmpi xml vcsn char z a 1 exp to aut 3 tmp tmp2 xml vcsn char z infiltration tmp tmpi 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 binom ab aabb ab 4 VAUCANSON 1 4 TAF KiT Documentation 67 September 28 2011 3 3 Automata and rational expressions on free monoids with weights in a field Three instances of T AF KrT 1 4 implement a weight semiring which is a field vcsn char q vcsn 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 auti 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 Compu
75. ge inverse t xml fx1 dom xml 2 states 4 transitions 1 1 T 1 fx1 im xml 2 states 4 transitions l 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 Krr 1 4 they are automata with the same weight semiring as the operand VaucANSON 1 4 TAF KiT Documentation 84 September 28 2011 e Forgets the second component of the label and keeps the weight i i of the transitions of the transducer zml and writes the result in the automaton a zml on A Precondition no precondition ncn vice E Forgets the first component of the label and keeps the weight Eom i of the transitions of the transducer t zml and writes the result in the automaton b zml on B Precondition no precondition fx1 wdom xml 2 states 4 transitions Zl 1 T 1 fx1 wim xml 2 states 4 transitions 4l 1 T 1 Figure 3 25 The weighted domain and image of fx1 xml 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 s
76. habet 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 Krr But VAUCANSON and the TAF Kirr 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 at ml in Section 1 1 and determinized this automaton we did not have to tell TAF Krr that the alphabet was A a b On the contrary when the automaton or the expression does not exist prior to the T AF KIT function then specifying an alphabet is mandatory For instance the following commands end in error vcsn 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 defined 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 rationa
77. he result in b mt 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 For an example cf Figure 3 12 VAUCANSON 1 4 TAF KiT Documentation 63 September 28 2011 3 2 4 2 product vcsn product a xml b xml gt c xml Computes the product of a aml and b zml and writes the result in c aml Precondition i a zml and b azml 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 KirT 1 4 Specification The product of a emt and b zml 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 Vp qcA Vvr scB p4 and rs pr E as and the initial and final functions by YVpE A VreB I pr l p r and T p r T p T r Comments i The result c zml 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 16 Sect III 3 2 Example Together with the command star alphabet product allows the projection over a subalphabet of an automaton vcsn char z a1 star alphabet gt ustar xml vcsn
78. hich contains the automaton or the expression so there is no need to specify them again when working from a file This is a questionable feature of both VAUCANSON 1 4 and the corresponding version of FsM XML but it is so VAUCANSON 1 4 TAF KiT Documentation 936 September 28 2011 vcsn char b a parser OPAR CPAR exp to aut O 2 gt par xml vcsn char b aut to exp par xml GICOSIGODEE T TEC EC EC 245 ert Caveat lt is the responsability of the user to define the tokens in such a way there is no collision 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 abei cat E _e0 e_e_ e ete e vcsn char z a aez01 cat E z a0 a zO a z 0 a z eO z a0 a zO a z 0 a zO 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 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 b a a b b a vcsn char b a parser TIMES x PLUS cat E
79. hted 4 eliminate the spontaneous transitions with a backward procedure Comments The subnormalize function 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 fxi xml cannot be built nor edited with the edit function Caveat The subnormalize function requires that the transducer meets the scalar end function condition VAUCANSON 1 4 TAF KiT Documentation 82 September 28 2011 2 a b Nb b 2 abb ba ba baa 0I b b Gsm b b fx1 xml 2 states 3 transitions l 1 T 2 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 ltl to pair vcsn ltl to pair t xml gt a xml Transforms 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 E mt becomes a letter in the alphabet Ax B 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 the
80. ich a azml 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 Y is not complete iii Once the definition is written down it appears that it could be taken for automata over a free monoid 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 zml is realtime Specification If a zml is not complete a add a new state z to a aml 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 ai xml display 4 states 9 transitions 1 1 T 1 Figure 3 15 The completion of A VaucANSON 1 4 TAF KiT Documentation 71 September 28 2011 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 aml over
81. ilke eds Amsterdam Univ Press 2007 457 504 14 S LOMBARDY J SAKAROVITCH On the weighted closure problem in preparation 15 M LoTHAIRE Combinatorics on Words Addison Wesley 1983 Reprint Cambridge University Press 1997 16 J SAKAROVITCH l ments de th orie des automates Vuibert 2003 English corrected edition Elements of Automata Theory Cambridge University Press 2009 17 J SAKAROVITCH Rational and recognisable power series In Handbook of Weighted Automata M Droste W Kuich and H Vogler eds Springer 2009 105 174 VAUCANSON 1 4 TAF KiT Documentation 90 September 28 2011 Index 20 36 37 27 e 36 z 36 A 21 a 21 40 accessible 47 alphabet 21 31 40 alphabeti 21 alphabet2 21 are equivalent 69 75 are equivalent E 69 argument see convention aut to exp 12 55 62 aut to exp DM 55 aut to exp SD 55 automata repository 39 automaton accessible part of an 47 64 deterministic 72 Glushkov 63 position 63 proper 49 standard 63 Thompson 32 trim 72 unambiguous 60 universal 75 B 28 b composition 85 bench 28 bench plot output 28 binom 67 binomial coefficient 67 Boost 7 cat 39 cat E 31 40 80 chain 53 characteristic 61 coaccessible 47 complement 72 complete 71 is complete 70 composition 85 composition R 87 CONCAT see token 37 concatenate 52 condition scalar end funct
82. impler but in which the number of paths is not preserved vcsn composition t xml u xml gt v xml Realizes the composition algorithm on t aml and u zml and writes the result in v zml Precondition t zmli 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 TAF KIT is described at Section B 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 e 3 Realizes the Boolean composition algorithm vcsn composition Xm u xm v xm P on t zml and u gml and writes the result in v aml VAUCANSON 1 4 TAF KiT Documentation 85 September 28 2011 Precondition t zmli and u zml are subnormalized with matching monoids output of t zml input of u ml and Boolean weight semiring Specification The Boolean composition algorithm is described at Section B 5 2 2 and goes roughly as follows 1 performing the product of t aml and vu zm 2 make the result proper Example Figure 3 26 shows the b composition and the composition of the fmp transducers ti xml and ui xml that are taken as examples at Section B 5 2 2 cf Figure B 1 and Fig ure B 2 vcsn char fmp b b composition ti ml ui xml display vcsn char fmp b composition t1 xml ui xml display Note that the b compos
83. ion 43 59 61 82 convention two argument 51 CPAR see token CWEIGHT see token D 28 data 39 derived term 78 is deterministic 72 determinize 72 display 40 divkbaseb char b 18 domain 84 w domain 85 dot see format 26 dotty 26 e 36 edit 20 40 82 enumerate 74 epsilon see transition eval 12 62 87 eval S 62 evaluation 87 exp see format exp to aut 20 23 56 80 expand 35 42 56 66 67 export time dot 28 export time xml 28 expression reduced 30 40 factor 74 field 68 first projection 88 format dot 24 exp 24 fpexp 24 32 fsm 24 40 xml 24 40 fpexp see format fsm see format Graphviz 40 Graphviz 8 26 help 20 27 i 25 40 87 image 84 w image 85 infiltration see product infiltration 67 input 25 internal see pipe intersection 75 inverse 80 is empty 27 48 is unambiguous 60 is useless 48 L 20 1 20 left mult 52 letter to letter seetransducer83 letterize 58 list all commands 20 list automata 18 20 list commands 20 is 1tl 83 ltl to pair 83 minimize 73 VAUCANSON 1 4 TAF KiT Documentation Ncurses 7 0 28 o 25 40 87 ONE see token OPAR see token OPENFST 25 OpenFST 24 output 25 OWEIGHT see token P 36 p 36 pair to fmp 88 parser 36 parser1 36 parser2 36 partial identity 60 pipe internal 14 17 61 shell 13 PLUS see token power 62 65 pr
84. ion 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 by the specification of IK and of the type of M 1 2 1 1 Semirings The semirings that are instanciated in TAF KriT 1 4 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 are the free monoids and the direct products of two free monoids A free monoid is completely determined by the set of generators called We add this precision as in the next version VAUCANSON 2 the kind of labels will also be a criterion in the definition of the programming type of an automaton VaAUCANSON 1 4 TAF KiT Documentation 14 September 28 2011 semiring mathematical symbol
85. ions 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 It is thus inadequate to try to use the fsm format for another automata than letterized Boolean automata with a unique initial state vcsn char z ofsm cat cl ml 011 O0 00041 O0 VAUCANSON 1 4 TAF KiT Documentation 25 September 28 2011 1 1 2 0 2 1 0O 1 0 vcsn char z ofsm cat c1 xml vcsn char z ifsm ofsm cat 01e O0 000 0 1 0 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 bi xml gt bi dot dotty bi dot vcsn char b display bi xml 2 1 3 2 Rational expression formats 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 Krr in this file vcsn char b aab cat E atb a b a b atb a b a b vcsn char b aab cat E atb a b a b gt exp txt cat exp txt a tb a b a b vcsn char b
86. ition is not trim 6 states 10 transitions 1 2 T 2 7 states 10 transitions 1 3 T 4 Figure 3 26 b composition and composition of ti xml and u1 xml Caveat In TAF KiT 1 4 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 TAF KiT Documentation 86 September 28 2011 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 aml 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 aml t zml and a aml have the same weight semiring Specification evaluation t xml a xml W image composition partial identity a xml t xml 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 ezp by the relation fxp realized by t aml 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 Kir 1 4 th
87. l 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 vcsn char b alphabet ab edit aut xml vcsn char b aab exp to aut abata gt aut xml The function edit is described at Section 2 3 5 exp to aut which takes a rational expression and converts it into an automaton at Section 3 1 5 2 VAUCANSON 1 4 TAF KiT Documentation 20 September 28 2011 vcsn char b display aut xml aut xml 5 states 4 transitions 1 1 4T 22 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 alphabeti a specify the first or input alphabet of transducers fmp alphabet2 A specify the second or output alphabet of transducers fmp 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
88. l1xC The proof of the Composition Theorem is equivalent to the construction of the transducer T xU Qx R A xC G IxJ TXxU by the following rules i If p a 1 q E then foral r 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 z q E and r x 1 s F then p r 1 1 4 5 G A next possible step is to eliminate the transitions with label 1 1 by means of a clas sical closure algorithm Figure B 1 shows an example of such product before and after the elimination of spontaneous transitions l v l u t Ti Pa Ut zl ali Figure B 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 Ax 1 1 where A AU 1 It amounts to replace iii by VAUCANSON 1 4 TAF KiT Documentation 108 September 28 2011 ii If p a z q E witha A and r a u s F with uw e then p r a u q 5 G 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 construction 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
89. 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 aml 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 B 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 ii The actual implementation of exp to aut carries 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 3 2 3 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 weigted automata as shown at Figure 3 7 result of the following command cf 16 Exer III 2 24 vcsn char q aab exp to aut 1 6a 1 3b 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 aml Specification VAUCANSON 1 4 TAF KiT Documentation 56 September 28 2011 3 states 6 transitions I 1 T 3 Figure 3 7 A standard Q automaton built by ex
90. le 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 and 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 5By the team of National Taiwan University VaucANSON 1 4 TAF KiT Documentation 40 September 28 2011 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 vcsn char z edit ci mi Automaton description States 0 1 Initial states O W 1 Final states 1 W 1 Transitions 1 From O 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 co 4 Delete a transition Your choice 1 11 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 KIT instance which calls the edit
91. lt 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 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 aictchr xml vcsn char zmin display aictchr xml atct xml 2 states 4 transitions 1 1 T 1 adctchr 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 3 2 1 6 support Transforms the automaton a ml whose weight semir vcsn xxx k support a xml gt b xml ing 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 ci xml gt cispp xml vcsn char b display cispp xml VA
92. m afterwards We do not fully document these options as they are anyway not yet finalized VAUCANSON 1 4 TAF KiT Documentation 27 September 28 2011 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 UTPUT 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 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 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 ldbi0det xml 2 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 25 7 determinize 65 57ms 65 54ms 1 65 54ms 65 57ms 4 24 1 CMD O determiniz 80 51ms 9 11ms 1 9 11ms 80 51ms 2 55 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
93. ml 10 states 11 transitions 1 1 T 1 thomp abc right xml 10 states 11 transitions 1 1 YT 1 Figure 2 5 The operator is not associative vcsn char b aabc cat E at btc atbtc vcsn char b aabc ofpexp cat E atbtc a b c vcsn char b aabc ofpexp cat E at btc at b c 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 bi 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 bis vcsn char z display cl ml Eventhough all semirings which are instantiated in TAF KrT 1 4 are commutative this is not an assumption which is made in VAUCANSON in general In any case the weight semiring This is not so good and will hopefully be corrected in further versions of VAUCANSON VAUCANSON 1 4 TAF KiT Documentation 33 September 28 2011 a b 2a 2b Ops Daron cl xml 2 states 3 transitions I 1 T 1 Figure 2 6 The Z automaton C and its display by Graphviz 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
94. nd projection 88 shortest 75 shuffle see product shuffle 65 SPACE see token 38 spontaneous see transition is standard 50 standard 63 standardize 50 STAR see token star 52 star alphabet 63 64 star S 55 state elimination method 55 105 subnormalize 82 subnormalized seetransducer82 is subnormalized 82 subword 67 suffix 73 sum 51 sum S 54 support 61 T 28 terminal state 72 Thompson see automaton thompson 32 63 TIMES see token 37 token CONCAT 36 CPAR 36 CWEIGHT 36 ONE 36 OPAR 36 OWEIGHT 36 PLUS 36 SPACE 36 STAR 36 TIMES 36 ZERO 36 transducer 80 letter to letter 83 subnormalized 82 85 transition VAUCANSON 1 4 TAF KiT Documentation epsilon 49 spontaneous 49 transpose 59 is trim 47 trim 47 trivial identities 30 union 51 universal seeautomaton75 universal 75 usage 20 V 20 v 25 27 verbose 25 27 VERBOSE DEGREE 28 version 20 Var 40 writing data 34 36 X 28 Xerces 7 xml see format z 36 ZERO see token 113 September 28 2011
95. nitial 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 a1 xml VAUCANSON 1 4 TAF KiT Documentation 53 September 28 2011 1 4T 1 10 states 24 transitions 1 Figure 3 5 Concatenation of 3 copies of the standardization of al ml vcsn char z standardize al ml M 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 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 a S Build standard automaton whose behaviour is the sum of a xm XIn c xm 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 TRUE Build a standard automaton whose behaviour is the Cauchy V D i v product of the behaviours of
96. non zero exit code 3 4 2 3 intersection Computes from a zml and b aml an automa vcsn intersection a xml b xm gt c xml ton which accepts the intersection of the lan guages accepted by a aml and b aml and writes the result in c ml Precondition no precondition Specification 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 xm1 Tells whether or not the automata a aml and b aml 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 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 zml Precondition no precondition Specification With every language is canonically associated an automaton called the universal automaton of the language in 16 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 TAF KiT Documentation 75 Septembe
97. omaton 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 vcsn char z cat VAUCANSON 1 4 TAF KiT Documentation 96 September 28 2011 Oo b c EK Figure A 7 The ladybird g A 2 1 1 pi ml The chacteristic automaton of the automaton B cf Figure A 2 The different outcomes of functions such as power n bi xml quotient on the automaton bi ml illustrate well the influence of the weights A 2 1 2 c1 xml for Cj Comments The series realised by C 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 8 d1 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 Jo bk VaucANSON 1 4 TAF KiT Documentation 97 September 28 2011 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 v
98. on 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 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 vcsn char b ixml cat E p xml C EC vcsn char b parser OPAR lt CPAR gt ixml cat E p xml VAUCANSON 1 4 TAF KiT Documentation 38 September 28 2011 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 vcsn char b ixml cat E pp xml CC CC e a 2 3 TAF Kit IO functions We end this chapter with the description of the input and output commands available within TAF Krir The other commands that perform computations on the automata and expressions are described in the next chapter 1 data aut 2 cat aut 3 cat E emp 4 display aut 5 edit aut 2 3 0 Data file location TAF Krr works or a user works with TAF KIT in a current directory called working direc tory On the o
99. on no precondition Specification are equivalent a xml b xml is empty reduce sum standardize realtime a xm1 left mult standardize realtime b xm1 1 3 3 2 Operations on expressions 3 3 2 1 are equivalent E vcsn v ixml are equivalent E e xml f xml Tells whether or not the expressions e aml Expressions are equivalent and f zml denote the same language Specification are equivalent E e xml f xml are equivalent standard e xm1 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 These data depend heavily on the examples and also on the machine on which the examples are run VAUCANSON 1 4 TAF KiT Documentation 69 September 28 2011 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
100. oper 2 weakly letterized in the sense that the labels of transitions are either in Ax 1p or in 14 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 Ax1p or in 14 x B 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 zml a subnormalized transducer and writes the result in a aml 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 k5 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 weig
101. p 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 acatacct tbacatbacc b acatacct bacatbacc acatacctbacatbacc vcsn char z aabc expand a b cta c b ac 1 b b 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 TAF KiT Documentation 57 September 28 2011 3 2 Weighted automata and expressions over free monoids The following functions concern automata over a free monoid as opposed to automata over a direct product of free monoids A priori there is no assumption on the multiplicity semiring However in VAUCANSON 1 4 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 IR 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 1 2 3 4 partial identity lt aut gt 5 characteristic lt aut gt 6 support lt aut gt 2 Behaviour of automata 2 1 eval lt aut gt lt word gt
102. p z transducers integers Z x Table 1 3 The TAF Krr instances in VAUCANSON 1 4 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 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 KrT command is executed some more informations or data have to be known by or given to the command They roughly fall into three different classes This name or precision comes from the fact that a transducer can be considered as well a
103. phviz by TAF Krr is not well tuned and that the output is rather poor It is not too difficult however for Mac users to get a rendering of automata of much better quality cf Figure 1 This can be done in three steps First download the Graphviz application for Mac from www pixelglow com graphviz Although already old and outdated by the 2 xx versions the 1 13 v16 version is rec ommended 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 SI bin sh if x 1 x then cat tmp tmpdotty dot open W a Graphviz tmp tmpdotty dot rm f tmp tmpdotty dot else open W a Graphviz 1 fi VaucANSON 1 4 TAF KiT Documentation 9 September 28 2011 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 6000 X DOTTY al xml 3 states 6 transitions f 1 fT 1 Oz CH al xml 3 states 6 transitions I 1 T 1 Figure 1 Two versions of the Graphviz application VAUCANSON 1 4 TAF KIT Documentation 10 September 28 2011 Chapter 1 Presentation of TAF Kit TAF KiIT stands for Typed Automata Function Kit it is a command line interface to VAU CANSON
104. plicitely 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 followng example cf Figure 2 6 for the automaton c1 xm1 vcsn char z v is realtime c1 xml Input is realtime T Pages far Computes from a zml an automaton by eliminating the spon vcsn rea ime a xm XIn zs n S taneous transitions from the letterized version of o zm 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 Kir 1 4 scalar end function condition VAUCANSON 1 4 TAF KiT Documentation 59 September 28 2011 3 2 1 3 is unambiguous vcsn v is unambiguous a xml e s S si Tells whether or not the automaton a zmli is unambiguous Input is unambiguous Precondition a zml is a realtime automaton Specification
105. pute a two component index in k p l p 1 if p is the origin of a loop l p 0 otherwise k p i p 1 o p 1 where i p is the in degree of p and o p its out degree Lexicographically order the states by their index c While there remains states choose the state q with smallest index remove it and replace the incoming and outgoing transitions according to B 1 recompute the index for those states that were adjacent to q d Return the label of the transition from i to t B 2 Weighted automata and rational expressions over free monoids B 2 2 Behaviour of automata B 2 2 1 eval As the automaton A implemented by a xml is supposed to be realtime it is described by a representation A jj v The coefficient of a word w in the series A realised by Ais A u w v cf 16 Sect IIL 3 The vector A u w is computed by induction on w the length of w The overall complexity of the algorithm is O Zd where d is the dimension of A VAUCANSON 1 4 TAF KiT Documentation 106 September 28 2011 B 3 Automata and rational expressions on free monoids with weights in a field B 3 1 Operations on automata B 3 1 1 Reduction of representations over a field Automata and representation Any finite automaton over A with multiplicity in K is equivalent to a realtime automa ton A with set of states Q A I E T where I and T are vectors in K and E is a square matrix of dimension Q whos
106. r 28 2011 Example vcsn char b universal a1 xml display 3 states 14 transitions 1 1 T 1 Figure 3 18 The universal automaton of ai ml of L A1 indeed Comments The universal automaton contains many interesting informations on the lan guage In particular 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 Hg is accepted by the automaton h6 xm1 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 16 Sec II 8 VaucANSON 1 4 TAF KiT Documentation 76 September 28 2011 b and a more structured view Figure 3 19 The universal automaton of Hg f a b fla flp 1 3 4 or 5 mod 6 VAUCANSON 1 4 TAF KIT Document
107. re important is the mere existence of this type of automata whithin TAF Krr 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 fmp transducer over B x C every letter b c 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 TAF KiT Documentation 88 September 28 2011 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 3
108. 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 cl ml 101101 45 The way they are input as strings as well as part of a rational expression is described in the next section 2 1 3 5 Boolean result formats Some TAF Krr 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 0 for true and any 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 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 the
109. rg 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 VaucANSON 1 4 TAF KiT Documentation 8 September 28 2011 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 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 lib The installation is then to be completed by the classical two lines make sudo make install The Graphviz application which is used to displaying automata while looking for a ded icated graphic interface is normally launched in an X11 window It is to be acknowledged that the call of Gra
110. rser 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 long option short purpose of the option parser p fix the value of the tokens parser P fix the value of the tokens concerning input alphabet parser2 Q fix the value of the tokens concerning output alphabet token meaning default value s ZERO constant 0 and the null series Qi tg hg ONE constant 1 and the identity of the monoid 4 fe Le STAR Kleene star k PLUS sum TIMES product ES CONCAT concatenation product within the monoid ake OPAR group start MC CPAR group end p OWEIGHT weight start 5 CWEIGHT weight end Sa SPACE space character to be ignored as Table 2 7 Tokens of the parser option the writing data 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 vcsn char b a parser OPAR CPAR cat E Q IC O 2 The values of the writing data are stored in the XML file w
111. s 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 VAUCANSON 1 4 TAF KiT Documentation 16 September 28 2011 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 are 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
112. scription of the algorithm at Section B 1 2 2 Example Figure 3 3 shows a transducer tt1 xml built for the sake of the example and the result of the command vcsn char fmp b standardize tt1 xml display VAUCANSON 1 4 TAF KiT Documentation 50 September 28 2011 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 Kir 1 4 the alphabet s of the output is the alphabet s of the first input argu ment 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 zml and writes 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 aml Precondition a zml
113. se 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 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 G 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 c
114. sentation 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 these systems are solved by an iterative method of Gaussian elimination VAUCANSON 1 4 TAF KiT Documentation 107 September 28 2011 B 5 Weighted automata over a product of two free monoids B 5 2 Operations on transducers B 5 2 2 composition b composition The Composition Theorem due to Elgot and Mezei cf 16 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 proper normalized transducers T Q A xB E 1 T and U R B xC F IU that is the transitions of 7 are labelled in Ax1 or in 1 x B and those of U are labelled in Bxlorin
115. so contains programs called automata factory which create parametrized families of au tomata It is coupled with some other modules An XML format for automata and expressions called FSM XML This format aims at be ing an interchange format for automata and thus at making possible and hopefully easy the communication between various programs that input or output automata So far this format is used as the normal and default input and output format for TAF Krr A graphic user interface called VGI especially dedicated to VAUCANSON is under devel opment at the EE Department of the National Taiwan University in Taipeh It will allow to describe automata and to visualize the result of operation on automata in a graphical way All functions defined in TAF Krr will be called via the menu of 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 After several years of hard and complex developments the evolution and progress of the VAUCANSON platform are now stuck and we have reached the conclusion that we have to undertake a thorough revision of the VAUCANSON library that will most probably change its interface and the one of the associated API These new developments will give rise to a new series of versions of VAUCANSON coined VAUCANSON 2 x However we want to have a version of the platform that
116. suffix in TAF KIT Boolean semiring B V ii cd ring of integers Z Z cx z field of reals R x teet field of rationals Q Q 4 x qg two element field F 0 1 x with 1 1 0 f2 min tropical semiring Zmin Z min zmin max tropical semiring Zmax Z max zmax Table 1 1 The semirings implemented in VAUCANSON TAF Kirr 1 4 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 Kirr 1 4 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 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 2 2 TAF Kit instances As the consequence of the preceding subsection the type of an automaton is determined 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 lett
117. t 1 General automata and rational 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 but it is out of the scope of this user s manual 44 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 char
118. t concatenate auti lt aut2 gt left mult lt aut gt lt k gt 3 1 3 2 3 3 3 4 star lt aut gt 3 5 3 6 right mult lt aut gt lt k gt 3 7 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 auti lt aut2 gt 4 3 star S lt aut gt 5 Automata and expressions operations on expressions 5 1 5 2 expand lt exp gt 5 3 Allowing some exceptions mentioned when describing the functions aut to exp aut aut to exp DM aut aut to exp S0 lt aut gt exp to aut emzp VaucANSON 1 4 TAF KiT Documentation 46 September 28 2011 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 IM e a cml as well as exchanges the initial and final edges and write the result mb aml 3 1 4 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 vcsn accessible a xml gt b xml Computes the accessible part of the automaton a aml and writes the result in b aml Specification The description of the function is the specification It is realised by
119. te 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 The platform consists in a few 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 generic in the sense that it makes it possible to write an algorithm once and apply it to different types of automata However this genericity is achieved in a way that should not cause any slowdown at runtime because the type of the automaton manipulated is known at compile time compiling an algorithm will generate code that is almost as efficient as an algorithm written specifically for this type of automaton TAF Kit is a command line interface to the library that allows user to execute VAUCAN SON s algorithms without any knowledge of C Because the VAUCANSON library needs to know the type of automata at compile time the TAF KIT interface has been instantiated for a predefined set of common automaton types TAF KiT does not allow to write new algorithms nor to manipulate new types of automata but it makes it possible to combine without efforts a large set of algorithms on common automata types A repository of automata that shows examples of automata of various types and al
120. tes from a zml an equivalent automaton of minimal dimension and writes the result in 5 zml Precondition a zml is realtime Comments Implements Sch tzenberger algorithm for reduction of representations cf Sec tion B 3 Caveat i The reduction algorithm may 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 xm1 and its reduction VAUCANSON 1 4 TAF KiT Documentation 68 September 28 2011 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 dans R ou 1024 dans Q the number of states should be 6 in the first case 11 in the second vcsn char r power c1 xml 5 reduce VI data States 10 Transitions 88 Initial states 1 Final states 1 vcsn char q power ci xml 10 reduce VI 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 zmLl realize Automata are not equivalent the same series Preconditi
121. ther hand every instance vcsn xxx y of TAF Krr 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 Every TAF KrT command writes in the working directory 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 Final states 1 2 3 2 cat vcsn cat a xml gt b xml Prints some characteristic data on the automaton a ml cf Section 1 1 Reads the automaton a zml and writes it in the file b emt VAUCANSON 1 4 TAF KIT Documentation 39 September 28 2011 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 outp
122. tion 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 polynomial 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 O First component labeled by the word ab Second component labeled by the word ba With weight 1 Automaton description States O Initial states O W 1 The automaton test xml is supposed to have been created with one state both initial anf final VAUCANSON 1 4 TAF KiT Documentation 42 September 28 2011 Final states O W 2 Transitions 1 From 0 to 0 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 initail 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 f
123. tomaton that reads any sequence of coins of 1 2 5 10 20 or 50 cents as long as the values are increasing vcsn 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 ki Zo OO So n PH 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 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 TAF KiT Documentation 22 September 28 2011 vcsn 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 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
124. tural definition would be m k gt k m with m any element of the monoid This may be corrected in forthcoming revisions of VAUCANSON 1 4 but should anyway be reevaluated in connection with the definition of the function derived term for the weighthed automata 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 use 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 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
125. umvented by any software that deals with expressions 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 VAUCANSON 1 4 TAF KiT Documentation 29 September 28 2011 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 multiplica 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 16 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 who
126. unctions 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 But it turned out that not all functions in TAF Krr 1 4 would behave correctly in presence of such general initial or final functions This is the reason why we have left the restriction in the edit function and we make the assumption that all automata that are dealt with by TAF KIT 1 4 meet this restriction which we call the scalar end function condition The transducer test fmp xml is supposed to have been created with one state both initial anf final VaucANSON 1 4 TAF KiT Documentation 43 September 28 2011 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 Krr 1 4 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 Krr 1 4 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 argumen
127. ut 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 3 3 cat E vcsn char b aab cat E exp Read the expression ezp given as a string lt red exp gt stores it in the memory and writes it back vcsn char b oxml cat E exp 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 SE EEN an XML file vcsn display a xml vcsn edit a xml Comments The different behaviours of the cat E function according to the possible formats have been described at Section 2 1 3 2 A rational espression output by cat E is in reduced form cf Section 2 2 1 2 2 3 4 display Display the automaton a aml 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 fi
128. y are drawn by the display function But they are very different with respect to the functions which can be applied to them vcsn char fmp b display trx xml vcsn char fmp b 1tl to pair trx xml gt trx pair xml vcsn char char b complete trx pair xml complement gt trx pair cmp xml vcsn char fmp b complete trx xml complement gt trx cmp xml vcsn char fmp b command complete doesn t exist AAA CO VAUCANSON 1 4 TAF KiT Documentation 83 September 28 2011 trx xml 2 states 4 transitions l 1 T 2 trx pair xml 2 states 4 transitions l 1 T 2 trx pair cmp xml 3 states 12 transitions l 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 Fr PES 4 Forgets the second component of the label and the weight of vcsn omain XIn a xm ele a the transitions of the transducer t zml and writes the result in the characteristic automaton a zml on A Precondition no precondition Forgets the first component of the label and the weight of the vcsn image Xm Xm aiii 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 ima

Vaucanson 1.4 TAF-Kit Documentation - LRDE

Contents

Download Pdf Manuals

Related Search

Related Contents