Home

User manual - Web

1. Wes SynDic __ i This error is not fatal Choose one of the alternatives Process modify your input and try to submit it again ANLDE System ignore the error and continue your work menu at the left Set of ANLDE ignore the error and return to the start page Systems Process an ANLDE System Documentation ANLDE Theory User Guide Input a test ANLDE system a list of samples xi x5 2 x1 57x3 9 x4 x5 Send Notes x2 x1 x2 x3 x3 x4 Algorithms x3 x4 x6 5 x1 9 x3 8 x4 x6 configuration Log In Nickname admin P d pase icasi Save _ Store this ANLDE system in a text format Log in Register Caka gt E l Salve the naiven ANI DE sustem with Figure 9 Syntax error message 2 Set solver parameters using Algorithms configuration form see section 3 2 You may also use default values 3 Select alternative solver if needed and push button Solve see Figure 10 Al solving queries are put into the Solver Spooler queue The Web SynDic displays the number of tasks in the Solver Spooler queue see section 3 5 2 During solving time the Web Syndic system shows the processing form see Figure 6 After processing the Web SynDic system displays Solution Report form see Figure 11 The Solution Report form contains the following information e Test ANLDE system in traditional mathematical style and number of solutions Current version of the Web Syndic system obtai
2. Nickname admin compare the solvers The field Solving result contains solved if the system is solved successfully Otherwise Password p Generate Gauss Generate automatically a new ANLDE y system by the selected generator error message 1S displayed Login Register Generator Parameters you may also continue Parameter Current value Max value e Solving machine characteristics like processor core memory operating system Java ver user but your profile and aber equation aL i sion Tomcat version and Solver process nice value if they are available limits information will not system 3 100 gt p y be saved Number of unknowns in ANLDE system le 150 Server Lond i e Solutions of the test ANLDE system if the system is solved successfully Max values of coefficients for 1 active users ANLDE system fio 1000 O registered users Max values of components for si e Note on solution You can simply press Agree with the result button or send more detailed message see section 3 8 Figure 10 Alternative solvers E Web SynDic Solution Report Mozilla j JE a x File Edit View Go Bookmarks Tools Window Help The Web SynDic system may display the following errors while solving given ANLDE sys mi tem e Failed to solve the problem Solver process is abnormally terminated for example the gt X gt v 3 amp http zeta cs prv 8480 Web SynDic process serviet 3Bjsessionid D4EC
3. MN ee nes eae isa eee bottom of the current Generate a New Set form see Figure 16 You may also use default queue The Web SynDic displays the number of tasks in the Solver Spooler queue see caine section 3 5 2 During solving time the Web Syndic system shows the processing form see Figure 6 If Solver Spooler queue is full then the Web SynDic system prints error message Unable to process your request Buffer is full Task rejected You may try to reload this page later and the generated system set will be put into solver spooler queue if it has available space Choose desired generator and press Save a set button All generation queries are put into the Generator Spooler queue The Web SynDic displays the number of tasks in the Generator Spooler queue see section 3 5 2 During generation time the Web Syndic system shows the processing form see Figure 6 Student Software Engineering Project Web SynDic 27 3 After processing the Web SynDic system opens new browser window containing the ANLDE system set see Figure 17 y http zeta 8480 Web SynDic save jsp displaykid bc47d66a Microsoft Internet Explorer Marin Mpaska Bua MabpaHHoe Cepmmc Cnpaska Ei 9 OO Dd Oa g S oa 0 l http zeta 3480 Web SynDic save jsp display8id bc47d66a AApec To save the ANLDE Systems use your browser s save function for this page choose plain text file format You may proces
4. te E e Limit exceeded maximum memory for solving Try to increase memory limit Figure 11 Solution report for one ANLDE system e Limit exceeded maximum values of coefficients for basis solutions Try to increase maximum values of coefficients for basis solution Student Software Engineering Project Web SynDic 21 e Limit exceeded maximum number of unknowns The solver returns more unknowns tion 3 8 containing the ANLDE system and the list of solvers in this case than given ANLDE system contains We will be pleased if you will send note see sec e Limit exceeded maximum number of solutions Try to increase maximum number of basis solutions for ANLDE system 3 3 3 Saving ANLDE system The Web SynDic has a feature which allows user to save ANLDE system in a file The saving process consists of the following steps L Alternatively you can generate it automatically see section 3 3 1 new browser window containing the ANLDE system see Figure 12 EE Web SynDic Process an ANLDE System Mozilla al x sl Eile Edit View Go Bookmarks Tools Window Help 2 Back Forward Reload Stop PETROZAVODSK STATE UNIVERSITY http zeta 8480 Web SynDic save jsp page process Department of Computer Science Wes SynDic Process an ANLDE EE Mozilla i BA iol xi j File Edit Yiew Go Bookmarks Tools Window Help a z 3 5 Back Forward Reloa
5. 1 2 2 3 5 is not in form 5 because 3 J U I2 1 2 U 4 Adding z3 to the second equation we get the same ANLDE system as in Table 1 The following theorem shows the relation between derivations in a CF grammar and solu tions of the ANLDE system Theorem 1 Let v gt w be a derivation in CF grammar G x is the number of applications of rule r in this derivation i 1 2 m Then x 11 12 Tm is a solution of ANLDE system S G v w Therefore for the ANLDE system form Table 1 each succesfull derivation B gt aaAaaa corresponds to a solution Consider such a derivation B gt AAAaB AAAa gt aBBaAAa S aaAAa gt aaAaB Baa aaAaaa Student Software Engineering Project Web SynDic 10 Rule r is not applied so x 0 rule ra is applied two times so 12 2 rule r3 is applied one time 13 1 rule r4 is applied five times x4 5 Thus we get a solution x 0 2 1 5 Definition of ANLDE system does not take into account the order of symbols in strings v w right hand sides of rules r Let us define a as a multiset of all symbols of a the number of occurances is taken into account For example abaaabA A a a a a b b A at b Using this notation a 8 means that the strings a and differ in order of symbols only Binary operation A is a symmetric difference of two multisets Theorem 2 Let G and G are CF grammars with the same alphabet N U X v
6. 6 w Dmitry G Korzun Solution for one class of a linear diophantine equations by methods of the formal languages theory Transactions of the Petrozavodsk State University issue on Applied Mathematics and Computer Science vol 7 Petrozavodsk 1998 pp 93 116 In Russian Reshenie odnogo klassa lineynih diophantovih uravneniy v neotricatel nih ce lyh chislah metodami teorii formal nih yazykov Trudy Petrozavodskogo gosudarstvennogo universiteta Ser Prikladnaya matematika i informatika Vyp 7 cS Dmitry G Korzun On the existance of a generating CF grammar for arbitrary linear dio phantine system Transactions of the Petrozavodsk State University issue on Mathemat Student Software Engineering Project Web SynDic 43 ES 10 11 ics vol 6 Petrozavodsk 1999 pp 34 40 In Russian O sushchestvovanii porozhdayushchey KS grammatiki dlya proizvol noy lineynoy diophantovoy sistemy Trudy Petrozavodskogo gosudarstvennogo universiteta Ser Matematika Vyp 6 Dmitry G Korzun On a relation between formal grammars and systems of linear diophan tine equations Bulletin of young scientists Issue on Applied Mathematics and Mechanics No 3 2000 pp 34 40 In Russian Ob odnoy vazaimosvyazi formal nyh grammatik i sistem lineynih diophantovih uravneniy Vestnik molodyh uchenyh Ser Prikladnaya matematika i mehanika 2000 N3 Dmitry G Korzun Syntactic Algorithms for Solving Nonnegative Lin
7. This link opens Process a set of ANLDE Systems form This form has 3 sections Load amp Solve Generate amp Solve and Generate amp Save Press button Solve a set in Generate amp Solve section The Solution Report containing solved system resource usage and solutions will be loaded More detailed information on generating and solving ANLDE system sets can be found in section 3 4 3 Reference manual 3 1 ANLDE system 3 1 1 ANLDE system theory Nonnegative Linear Diophantine Equations Let Z 0 1 2 be a set of integers Z 0 1 2 be a set of nonnegative integers A system of nonnegative linear Diophantine equations NLDE for short is a linear system Ag b ASS Wee lig Bie Tae 1 Student Software Engineering Project Web SynDic 6 where n is number of equations m is number of unknowns Therefore the solutions of a NLDE system are m vectors with nonnegative integer components For example consider the NLDE system with n 2 equations and m 4 unknowns Li La 323 l 2 21 2 4 1 This system has infinitely many solutions in Z4 Among them for instance solutions 7 02 4 05 and 0d MY NLDE system 1 is homogenous if b is null vector O Z Any homogenous NLDE system has the trivial solution x O Z f For any NLDE system a corresponding homogenous system can be constructed replacing right hand side b by O For example the corresponding homogenous NLDE system for 2
8. Web SynDic works with a special class of homogeneous NLDE systems that are Associated with context free grammars ANLDE systems for short 2 1 Solving a test ANLDE system For solving one ANLDE system use ANLDE system link in the left side part of the main form This link opens Process an ANLDE System form Input ANLDE system into the corresponding text area see Figure 1 or press button Generate to generate ANLDE system automatically see section 2 2 and press button Solve The Solution Report page containing solved system EE Web SynDic Process an ANLDE System Mozilla j FE a xj E File Edit View Go Bookmarks Tools Window Help es Be E 2 X gt r 3 de amp http zeta cs prv 8480 Web SynDic process servlet id fb2285bbt generatetraccepted stop El Back Forward Reload ms ___PETROZAVODSK STATE UNIVERSITY es karelia ru Department of Computer Science Wes SynDic Process an ANLDE System Process Input a test ANLDE system a list of samples ANLDE System x1 x1 8 x3 8 x6 Set of ANLDE x2 x4 x6 x2 x3 x4 7 x6 Systems x3 xS 6 x3 xS 5 x6 Documentation ANLDE Theory User Guide Send Notes Algorithms Save Store this ANLDE system in a text format heya Salve lt none gt Solve the given ANLDE system with Log In the syntactic algorithm You may select one alternative solver to Nickname compare the solvers Password Generate Gauss Generate aut
9. able solutions of the corresponding homogenous system Sets M and H are always finite They describe the set of all solutions of 1 Namely any solution x can be computed as q pao E ash for some x N and a Z4 4 s 1 Student Software Engineering Project Web SynDic ff where p and q are the numbers of solutions in the basis M fa emer an i MO Oy For example all solutions of NLDE system 2 are described by the formula 1 0 0 2 a 1 1 0 3 6 0 3 1 6 ioe for V a 8 E Z 0 2 1 5 a 1 1 0 3 T 8 0 3 1 6 T N where the left square bracket means alternation Pp qd N 320 1 0 0 2 4 0 2 15 HA 10 37 H4 0 3 1 0 e Taking a 0 2 1 5 a 2 8 0 we get the solution x 2 4 1 11 This is very simular to the theory of linear equations general solution is a sum of a particular solution and a linear combination of homogenous ones However the NLDE case has its own specifics one particular solution is not enough to describe all solutions there must be a set but finite of particular solutions For the above example at least two particular solutions are required See monograph 9 and papers 10 11 as classic introduction to the area Complexity problems for NLDE systems The basic computation problems for a given NLDE system are listed below 1 Is the NLDE system solvable in nonnegative integers for the homogeneous case only nontrivial solvability is considered 2 S
10. allows a user to generate and solve a set of ANLDE systems at once The form for generating and solving a set of ANLDE systems is shown in Figure 16 After processing the Web SynDic system displays Solution Report see Figure 15 The The generating and solving process consists of the following steps Solution report contains the information described in section 3 4 1 and additional field Wait time Generator spooler buffer which contains waiting time in Generator Spooler buffer 1 Set generator parameters using Algorithms configuration form see section 3 2 or in the The list of possible generator and solver errors is presented in sections 3 3 1 and 3 3 2 bottom of the current Generate a New Set form see Figure 16 You may also use default values 3 4 3 Generating and saving ANLDE system set 2 Choose desired generator and press Solve a set button All generation queries are put The Web SynDic system allows a user to generate and save a set of ANLDE systems The form into the Generator Spooler queue The Web SynDic displays the number of tasks in the for generating and saving a set of ANLDE systems is shown in Figure 16 Generator Spooler queue see section 3 5 2 During generation time the Web Syndic The generating and saving process consists of the following steps system shows the processing form see Figure 6 A Ad l Jas AE l l bee ete 1 Set generator parameters using Algorithms configuration form see section 3 2 or in the
11. amp http izeta 8480 Web SynDic main jsp page process Back Forward Reload Stop Wes SynDic Process ANLDE System Set of ANLDE Systems Documentation ANLDE Theory User Guide Send Notes Algorithms configuration Input a test ANLDE system a list of samples RI F K6 xl 9x4 x6 x2 x2 5 x4 x3 x4 x5 x3 2 x4 x5 Save Store this ANLDE system in a text format Solve lt none gt Solve the given ANLDE system with the syntactic algorithm You may select one alternative solver to compare the solvers Generate Gauss Generate automatically a new ANLDE system by the selected generator Log In Nickname Password Log in Register you may also continue working as anonymous user but your profile and limits information will not Generator Parameters Parameter Current value Max value Number of equations in ANLDE system E 100 i EE web SynDic Process an ANLDE System Mozilla File Edit View Go Bookmarks Tools Window Help 4 2 3 2 T X v amp http zeta 8480 Web SynDic process servlet om HLL Reload puy Back Forward Stop PETROZAVODSK STATE UNIVERSITY al ba Department of Computer Science Wes SynDic uations and unknowns ae equ nS This error is not fatal Choose one of the alternatives Process modify your input and try to submit it again Se ignore the error and continue your
12. and log in During this guest session you can change the algorithms configuration but the changes are lost whenever your session is over The lifetime of your session is not limited however the session is terminated after idle period of 15 min The explanation of the name Web SynDic can be found here A Petrozavodsk State University Department of Computer Science W3C WSC cseh Web SynDic Team 2 E Figure 18 Server load information nickname and password afterward some additional Web SynDic features may be used Web SynDic allows a registered user to edit and store personal profile with user limits independently on session lifetime The registration is initialized with the Register button in the Log In form Afterward the web system returns the form shown in Fig 19 The user feeds the fields of the form with information he she wishes to provide about himself herself and clicks on the Register button to complete registration The required fields for filling are marked with sign A nickname may contain only latin letters numbers and underscores also a nickname contains at least 2 and no more than 32 characters A password may contain at least 4 and no more than 32 characters If there is an error in filled fields then Web SynDic responds with a corresponding error message it includes a reason of the error When the registration has been completed the user may log in the Web SynDic system To do this h
13. case when the same computational problems are NP complete or even overNP 9 A user just sends a test ANLDE system to Web SynDic the latter responds with the solution and some characteristics of the computation This allows to present the key features of the syntactic algorithms test them estimate the efficiency etc A user is assumed to be a researcher in Diophantine analysis formal grammars integer programming and related fields She He has an access to the Internet via a standard browser Note that the web system does not allow a user to have a direct access to the demon strated amp tested algorithms but shows only the outcome of their work Detailed information about the syntactic algorithms and ANLDE theory can be found in 1 2 6 7 1 2 Conventions In this document the following conventions for fonts are used Typewriter font URL addresses names of programs and utilities input text for web forms Bold font Names of buttons available in Web SynDic pages important notes on using Web SynDic Student Software Engineering Project Web SynDic 4 San serif font Names of forms and text areas available in Web SynDic pages Underlined text Names of links available in Web SynDic pages 2 Getting Started Web SynDic is a web system for demonstrating and testing novel syntactic method for searching nonnegative integer solutions of Linear Diophantine Equations LDE in nonnegative integers or Nonnegative LDE or NLDE for short
14. for some parameters needed by a solver or generator Generator External algorithm used for ANLDE systems and system sets generation depending on given generation parameters Hilbert basis A set of all indecomposable minimal solutions of a homogeneous NLDE system IL Integer linear programming Indecomposable A particular solution that is not a sum of two particular solutions lp_solve The non commercial linear programming code written in ANSI C by Michel Berkelaar Also it supports ILP problems Available on a http www cs sunysb edu algorith implement lpsolve implement shtm NLDE Nonnegative linear Diophantine equations i e their solutions are in nonneg nel ative integers and coefficients are integer See for example 9 10 11 Particular Any non trivial solution of a homogenous NLDE system solution PetrSU Petrozavodsk State University http petrsu karelia ru Registered user A user who has complete the registration at Web SynDic and got a user profile nickname and password Regular user Any user of the Web SynDic system She He is identified by user ID Session Web SynDic logical session for continuous time period of user working with Slopes Algorithm of M Filgueiras and A P Tomas for searching Hilbert basis of a Solver External algorithm used for solving ANLDE systems and system sets Syntactic The algorithms that solve ANLDE system by constructing some derivations Algorithms in the corres
15. generation user can modify produced ANLDE system Student Software Engineering Project Web SynDic 14 EF Web SynDic Process an ANLDE System Mozilla C 16 x lr E File Edit View Go Bookmarks Tools Window Help 2 El Back Forward Reload ms PETROZAVODSK STATE UNIVERSITY es karelia ru KE E de amp http zeta 8480 Web SynDic main jsp page process Department of Computer Science Were SynDic Process an ANLDE System Process Input a test ANLDE system a list of samples ANLDE System Set of ANLDE Systems Documentation ANLDE Theory User Guide Send Notes Algorithms Save Store this ANLDE system in a text format ogy en Solve lt none gt Solve the given ANLDE system with Log In the syntactic algorithm You may select one alternative solver to Nickname compare the solvers Password Generate Gauss Generate automatically a new ANLDE system by the selected generator Logi Regist Login Register Generator Parameters y Figure 4 Process ANLDE System The generation process consists of the following steps 1 Set generator parameters using Algorithms configuration form see section 3 2 or in the bottom of the current Process an ANLDE system form see Figure 5 2 Choose desired generator and press Generate button All generation queries are put into the Generator Spooler queue The Web SynDic displays the number of tasks in the Generator Spooler
16. is 11 T2 3L3 0 l 3 11 2 z4 0 If x is a solution of 1 and h is a solution of the corresponding homogeneous system then xz x ah is also a solution of 1 for any nonnegative integer a Nontrivial solution A of homogenous NLDE system is indecomposable if it is not a sum of two nontrivial solutions of the same homogenous system Solution x of NLDE system 1 is indecomposable if it is not a sum of another solution x and a nontrivial solution h of the corresponding homogenous system For instance the solution x 2 4 1 11 0 2 1 5 2 2 0 6 of NLDE system 2 is decomposable The solution h 2 2 0 6 1 1 0 3 1 1 0 3 of the homogenous system 3 is decomposable The solutions x 0 2 1 5 and h 1 1 0 3 of NLDE systems 2 and 3 respectively are indecomposable The notion a indecomposable solution for NLDE systems is equivalent to a minimal so lution where the minimality is considered with respect to standard component wise ordering For example x 0 2 1 5 is minimal for system 2 and therefore there is no another solution x such that x2 lt x h 1 1 0 3 is minimal for system 3 and therefore there is no another nontrivial solution h such that h lt h Hilbert basis of NLDE system 1 is a pair M H where N C Z is the set of all minimal indecomposable solutions of the NLDE system and H is the set of all minimal indecompos
17. queue see section 3 5 2 During generation time the Web Syndic system shows the processing form see Figure 6 3 In the case of successful generation produced ANLDE system will be placed in the text area of Process an ANLDE system form see Figure 7 4 If generator is unable to produce an ANLDE system for example if numbers of equations and unknowns are equal see Figure 8 you may change generator or generator parameters and try again In some cases you may try again without changing any parameters Generated or manually inserted ANLDE system is stored by the Web SynDic system as long as you work with it The Web SynDic system may display the following generation errors EE web SynDic Process an ANLDE System Mozilla Student Software Engineering Project Web SynDic 15 File Edit View Go Bookmarks Tools Window Help User Guide Send Notes Algorithms configuration Log In Nickname Password Login Register you may also continue working as anonymous user but your profile and limits information will not be saved Server Load 1 active users O registered users O solver tasks O generator tasks EE Web SynDic Processing Mozilla 2 X gt v 3 q amp http izeta 8480 Web SynDic main jsp page process Back Forward Reload Stop Save Store this ANLDE system in a text format Solve lt none gt Solve the given ANLDE s
18. the file containing the set of ANLDE systems The ANLDE system set should be in ANLDE system set format see section 3 1 If ANLDE Student Software Engineering Project Web SynDic 23 system set is invalid or text area is empty then the Web SynDic system prints error message see Figure 14 EZ Web SynDic Process a Set of ANLDE Systems Mozilla AE o Eile Edit View Go Bookmarks Tools Window Help 2 X gt 3 amp http zeta 8480 Web SynDic process servlet fal Back Forward Reload Stop PETROZAVODSK STATE UNIVERSITY Department of Computer Science Wes SynDic This error is not fatal Choose one of the alternatives Process e modify your input and try to submit it again ANLDE System ignore the error and continue your work menu at the left Set of ANLDE ignore the error and return to the start page Systems Documentation ET nene ANLDE Theory User Guide Load a Set from a Text File Send Notes re Browse Algorithms configuration For comparison of the syntactic algorithm with another solver select one alternative solver lt none gt y Log In Nickname 7 Solve a set Start processing your set load amp solve Password _Login _Register Generate a New Set xl Figure 14 Syntax error message 3 Select alternative solver if needed and push button Solve a set All solving queries are put into the Solver Spooler queue The Web SynDic displays the number of tasks in th
19. value is not available for example Maximum process virtual size is not available Parameter Current value Max value egin Register Number of equations in ANLDE when algorithm executes too fast then N A is displayed in the corresponding field e EST 100 working as anonymous Number of unknowns in ANLDE The field Solving result contains solved if the system is solved successfully Otherwise user but your profile and system fe 150 a E E il ic winot Number of ANLDE systems inset B 20 8 payen Max values of coefficients for Server Load ANLDE system fio 1000 j j icti j i Max values of components for O Solving machine characteristics like processor core memory operating system Java ver 1 ace a badr w aoda sion Tomcat version and Solver process nice value if they are available O solver tasks Max number of basis solutions for O generator tasks ANLDE system fioo 100 e Note on solution You can simply press Agree with the result button or send more For comparison of the A ee with another solver select one alternative solver lt none gt detailed message see section 3 8 l Solve a set Start processing your set generate amp solve Save a set Store the set in a text format without The list of possible solver errors is presented in section 3 3 2 solving generate amp save 3 4 2 Generating and solving ANLDE system set Figure 16 Generation form for set of ANLDE systems The Web SynDic system
20. 3CF211EE4713F9E Y Back Forward Reload Stop Wers SynDic Solution Report process is killed We will be pleased if you will send note see section 3 8 containing the Process 1 Test ANLDE system ANLDE system and the list of solvers in this case ANLDE System x1 41 x1 56 x5 90 x6 x5 x2 x4 68 x1 53 x5 23 x6 x2 x4 A 3 e A po x6 x3 17 x1 OS xS 57 x6 x3 e Limit exceeded maximum CPU time for solving Try to increase maximum CPU time Documentation Number of solutions 3 for solving parameter Y ore ees 2 Waiting time User Luide A a A 3 Sees o Solver spooler buffer OO min 00 sec e Algorithm failed The solver produces invalid solution for example the solver prints _ 3 Performance metrics of the algorithms ce Algorithms pcia error message We will be pleased if you will send note see section 3 8 containing the configuration E Maximum Algorithm Summary Summary process Solving ANLDE system and the list of solvers in this case CPU work real work Log In name time sec time sec virtual result Mkea AAA e Internal solver error or memory limit exceeded Try to increase memory limit Paseword 7 Syntactic lt 0 001 0 125 1396 solved y B y E EE Slopes 0010 0190 1704 solved e CPU time limit exceeded Try to increase maximum CPU time for solving ou may also contras 4 Solving machine characteristics Done Ep
21. 80 Web SynDic main jsp page notes amp on_solution PETROZAVODSK STATE UNIVERSITY al EN Department of Computer Science WebB SynDic Send Notes on Solution Process Dear guest e ANLDE System ra 3 e Set of ANLDE Write any opinion about the last ANLDE processing case For instance Systems e what do you think about this ANLDE system or its solution Documentation e what is your opinion about efficiency of the syntactic algorithm e ANLDE Theory e what does the comparison with another solver show e User Guide You can either agree or disagree with the solution We are glad to meet any Send Notes disagreement expecially when the solution is incorrect in any way you mean Algorithms configuration Log In Nickname Password Login Register Agree with solution l attach the processed system or set Disagree the system will be attached automatically you may also continue working as anonymous _Send notes user but your profile and Be Done Figure 22 Note on solution 32 Student Software Engineering Project Web SynDic 33 e Disagreement with the result of solving In this case the processed ANLDE system s will always be attached to the note auto matically Both features are used for backward opinions of Web SynDic users but the latter is also intended for testing the syntactic algorithms If a user just presses Agree with the result button directly in the report on solution page a stand
22. A A 3 5 2 Server load information ae e E E a AA 3 6 Registration and LogIn ee d 3 7 User Profile Configuration 24222 dia da Ae e a Oe WV CaO VM DIC DOES A oe Beg ee hoe ie bo ae amp BRE Soe Sysadmin Manual 4 1 Logging in as an administrator sans ako be ob ee we Se De eS AD Uger Wa Ve COTE Aa a ae ee A do Giangio cons tramita gt Bact Wig Ba ele e ee Swe OS o Se eee S AA Niewinne ACtlVitySCACISUICS s mame ee Hh doe ES Be we WR Rok ir AA 6 10 11 11 12 12 13 13 17 ZA 22 22 25 26 2 21 28 28 30 31 Student Software Engineering Project Web SynDic 3 5 Installation and Configuration Instructions 38 6 Frequently Asked Questions 39 7 Glossary 41 References 42 1 Introduction 1 1 Overview Web SynDic stands for web based demonstration and test of the syntactic algorithms for solving linear Diophantine equations in nonnegative integers T hese algorithms developed at CS Department of PetrSU are a novel type of algorithms for efficient solving some classes of nonnegative linear Diophantine equations NLDE or LDE in nonnegative integers by syntactic parsing methods These syntactic algorithms seem to be promising tool for solving some classes of NLDE sys tem more exactly a class of NLDE system associated with formal grammars ANLDE systems For this class the syntactic algorithms allow efficient polynomial and pseudo polynomial com putations comparing with the general NLDE
23. NLDE Password 7 system 6 150 7 Number of ANLDE systems in set f 20 Y E al Figure 3 Algorithms Configuration User is unable to set restrictions for ANLDE systems such us maximum number of equations in ANLDE system The Web SynDic system uses maximum values for these restrictions which are described in section 3 2 3 3 2 2 Generator Limits User can set the following generator limits Max CPU time for generation maximum CPU time for ANLDE system generation If CPU work time is greater than the restriction then the generation process is interrupted with corresponding error message Max memory for generation maximum virtual memory for each generation process If amount of memory exceeds the limit then the generation process is interrupted with corresponding error message 3 2 3 Generator Parameters User can set various parameters for generation process but in some cases for example if number of unknowns is much greater than the number of equations and number of solutions is rather small generator is unable to generate an ANLDE system Student Software Engineering Project Web SynDic 13 The generator has the following parameters Number of equations in ANLDE system number of equations in each generated ANLDE system The number of equations should be less than the number of unknowns Number of unknowns in ANLDE system number of unknowns in each generated ANLDE system The number of unknowns
24. Petrozavodsk State University Department of Computer Science THE WEB SYNDIC SYSTEM USER MANUAL Student Software Engineering Project Web SynDic Contents 1 Introduction ed Serve E oe ee Oe Maa ae dc A Be 1 2 Conventions oe 2m 8 bebe Se nk Be ee et ot Se Ele He A See Be Getting Started 2 1 Solving a test ANLDE system ee 2 2 Generating a test ANLDE system 0 0 0 0 e e 2 3 Generating and solving a set of ANLDE systems Reference manual ool ANLDE System ors a a wot st A E Se Ss Pee d 3 1 1 ANLDE systemi theory 20 24 2 a aca bag A Se AOS a Syl ANIL DE system Oria cin a der Kt deo eea ke Ok Gk a RAS de 3 2 Algorithms Configuration as aes a Roe Sw He hae e Bee By EERE Gd DOVER YE ore EE ore OR oe ek Cee e oo Generator Limits 2 sera eget Boe e be eee BEES os 3 2 3 Generator Parameters fe a ed Hed ed et ed YS 3 3 Processing a test ANLDE system a km Soe we hea a Ge ee Bes 3 3 1 Creating ANLDE system ue ode whe De eee daa ss 3 3 2 Solving ANLDE system og Sie a be BS eed BS Se ee eee Oooo Day ANLDE syst sane 4 8 tna e Sat ee ood eet on ae A 3 4 Processing a set of ANLDE systems 0 000000 eee eee 3 4 1 Loading and solving ANLDE system set 0 0 3 4 2 Generating and solving ANLDE system set 3 4 3 Generating and saving ANLDE system set 2 Oso CRC NOAM a s abe re pte sash ELN de Bg we rn a
25. amp metrics 9 amp display v Go PETROZAVODSK STATE UNIVERSITY E war archive into the Tomcat s webapps directory Also you may use the Tomcat Web Department of Computer Science Application Manager included with the Jakarta Tomcat to install Web SynDic into the Were GunDic Statistics Report running server For more details see the Jakarta Tomcat documentation Process Generated at Mon Sep 13 15 58 21 MSD 2004 Conk aration e ANLDE System IP address host Sum session time dd hh mm ss 8 sehen I hehe rh cl Hime dd hhimmiss Systems A MO 4 APRA Web SynDic supports the following context parameters Documentation 193 e ANLDE Theory 194 85 f e User Guide Po solver_spooler path generator_spooler path path to the external programs direc a ee User Profile tories Algorithms abstr ial datastore path path to the data store directory where user accounts and limits are Constraints t d Activity Statistics stored You have logged in eona as admin log out admin_email administrator s email for user notes and bug reports Server Load server cpu server ram server os server nice server java server information to 1 active users Done be displayed in the report pages Figure 27 Example of activity statistics report You may define the context parameters in the WEB INF web xml file in the following format lt context param gt lt param name gt parameter name lt param name gt lt param value gt paramet
26. ard message about solution agreement is send to the Web SynDic system for statistics 4 Sysadmin Manual System administrator is a privileged user she he manages and controls the web system This includes maintainance of the data store activity statistics usage and management of users and user limits 4 1 Logging in as an administrator To access the administrator privileges you need to log in the Web SynDic system as adminis trator There is predefined nickname admin for privileged user in the web system but you can change it or add a new user with administrator s privileges Logging in is quite typical see also section 3 6 you enter the nickname and password in the corresponding form and press Log in button If the password is correct and the user with entered nickname has administra tor privileges you will see administrator greeting and some options which are inaccessible to regular user see Fig 23 If you want to finish your current administrator session and become an anonymous user just follow log out link It is dangerous to leave administrator session opened after you have been finished your work so don t forget to log out if you have been logged in as administrator 4 2 User management One of the specific administrator options is ability to manage other users The user management means viewing and changing any existing user information and removing user accounts Follow Manage Users link to get User Management for
27. ary bees Login _ Register Algorithm CPI I wnrk real wnrk a Sa Solving 4 Figure 15 Solution report for the set of ANLDE systems average unknowns maximum unknowns maximum coefficients minimum number of solutions average number of solutions maximum number of solutions The solution characteristics are obtained from the default solver Therefore if the default solver fails then the characteristics are set to N A e Waiting time in Solver Spooler buffer If buffer is empty then Solver Spooler executes new task immediately and waiting time equals to zero e Performance metrics of the algorithms algorithm name summary CPU work time in seconds summary real work time in seconds Student Software Engineering Project Web SynDic 25 Student Software Engineering Project Web SynDic 26 A a A Hi Web ic f D Mozill maximum process virtual size in kilobytes a a File Edit View Go Bookmarks Tools Window Help solving result E 2 x 2 y 3 amp http fzeta 8480 Web SynDic main jsp page processset I Back Forward Reload Stop configuration Generate a New Set At the present the time unit for CPU work time is 0 001 second If Solver uses CPU work ar sak i a P ogan Select a generator Gauss y time which is less than 0 001 second then lt 0 001 is printed in the report page Nickname 7 Generator Parameters i E Password If the
28. ator main window Ol Web SynDte User Management x File Edit View Go Bookmarks Tabs Help lt gt Q amp Q Back Forward Stop Reload Home History Bookmarks Find http zeta cs karelia ru 8480 Web SynDic main jsp page users PETROZAVODSK STATE UNIVERSITY es karelia ru De artment of Com uter Science p p WEB SyNDIC Manage Users Process Use this form to view and change user s profiles Available only for the e ANLDE System administrator e Set of ANLDE z Systems Nickname anonymug Documentation _Get Profile e ANLDE Theory e User Guide Send Notes User Profile Algorithms configuration Manage Users Constraints Activity Statistics You have logged in as admin log out Server Load 1 active users Done 1 Bw Figure 24 User management 34 Student Software Engineering Project Web SynDic 35 Be careful while changing password and especially removing accounts you may easily remove even administrator account 4 3 Changing constraints Administrator has ability to change the constraints Constraints are the upper limits for some parameters needed by a solver or generator e g number of ANLDE systems in a set maximum time for solving etc A regular user can not set her his user limits for generation and solving section 3 2 to values greater than the constraints To change constraints follow Constraints link If you have administrator privileges you will s
29. ctic algorithm is its polynomial complexity This makes the algorithm to be more efficient than universal Algorithms solvers of arbitrary NLDE systems the syntactic solver can be used even for large configuration systems For instance the algorithm was tested on ANLDE systems with dimensions En up to 1000 equations 1200 unknowns and coefficients in range 0 500 Less than minute was spent by the syntactic solver to find Hilbert basis for any of these Nickname systems For comparison standard integer programming solvers might spend several Password hours or even days to find only one solution not the whole basis moreover they were failed to solve in reasonable time some of these ANLDE systems More details tog in _Resister about the ANLDE theory can be found here you may also continue abans Using Web SynDic you can test our syntactic algorithm look at its efficiency user but your profile and compare it with alternative algorithms Use the menu on the left of this page to limits information will not access these features be saved The basic Web SynDic feature is processing a single ANLDE system or a set of Server Load ANLDE systems Limits of this processing are controlled with algorithms 3 active users configuration Your opinion about Web SynDic can be given with send notes feature 2 registered users 1 solver tasks 0 generator tasks Now you are working as a guest To access more function you should register
30. d Stop To save the ANLDE Systems use your browser s save function for this page choose plain text file format You may process this set of systems with Web SynDic later x1 4 x1 4 x5 4 x6 x5 x6 x2 2 x1 6 x5 S x6 x2 x3 x4 6 xL S x5 6 x6 x3 x4 xt format thm You may compare the solvers Password Generate Gauss Generate automatically a new ANLDE system by the selected generator Logi Register _togin _Resister Generator Parameters y Figure 12 Save ANLDE system Insert valid ANLDE system into the text area of the Process an ANLDE system form Press Save button to save the ANLDE system in a file The Web SynDic system opens 3 Using standard browser functions you can save the system in a file The Web SynDic support pop up windows system uses pop up windows for saving ANLDE system Your browser should Student Software Engineering Project Web SynDic 22 3 4 Processing a set of ANLDE systems The Web SynDic system allows a user to process a set of ANLDE systems The set of ANLDE systems should be given manually by a user or generated automatically by a selected generator Recently only homogeneous ANLDE systems are supported by Web SynDic Process a Set of ANLDE systems form is shown in Figure 13 EE Web SynDic Process a Set of ANLDE Systems Mozilla E lex File Edit View Go Bookmarks Tools Window Help z 2 v gt v a amp http ize
31. d into three parts subforms User information form User password form and User account form User information subform is used to configure personal user information such as full name email and other information After pressing Submit button all changes are saved in the user profile In the User password subform a user may change own password He she should input new password an re type it For the security reasons a user should also fill Old password text field After pressing Change password button new password is saved in the user profile For removing user account a user should input his her password in the User account subform and press Remove account button If the password is valid then the user profile is deleted If a user has administrator privileges and uses Manage users service see section 4 2 then Old password text field in the User password subform and Password text field in the User account subform are not shown Student Software Engineering Project Web SynDic 31 O Web SynDie User Information Mozilla x a File Edit View Go Bookmarks Tools Window Help el Q 6 Q Y _ amp http zeta cs karelia ru 8080 Web SynDic main jsp page userinfo gt i i PETROZAVODSK STATE UNIVERSITY mR MS Department of Computer Science Wes SynDIc User Profile Process User information e ANLDE System e Set of ANLDE Systems Documentation e ANLDE Theory Full name system Administrator Email kulakovecs karel
32. e Solver Spooler queue see section 3 5 2 During solving time the Web Syndic system shows the processing form see Figure 6 After processing the Web SynDic system displays Solution Report see Figure 15 The Solution report contains the following information e Number of ANLDE systems in the set e The characteristics of ANLDE system set minimum equations average equations maximum equations minimum unknowns Student Software Engineering Project Web SynDic 24 EE Web SynDic Solution Report Mozilla yg le x Elle Edit View Go Bookmarks Tools Window Help 2 X gt v 3 H http zeta 3480 Web SynDic main jsp page report solution set lan Back Forward Reload Stop PETROZAVODSK STATE UNIVERSITY Department of Computer Science Were SynDic Solution Report 1 Number of ANLDE systems in the set 3 Process 2 The set characteristics sep E o Minimum equations 3 Gusher o Average equations 3 0 Y o Maximum equations 3 Documentation o Minimurn unknowns 6 e ANLDE Theory o Average unknowns 6 0 o Maximum unknowns 6 o Maximum coefficients 9 Send Notes o Minimum number of solutions 3 Algorithms o Average number of solutions 3 333333 configuration o Maximum number of solutions 4 3 Waiting time User Guide Log In o Solver spooler buffer OO min 00 sec Nickname 4 Performance metrics of the algorithms Password r E s in ister Summary Summ
33. e she enters login and password in the Log In form and clicks on the Log in button After successful login contents of main window are changed Log In area now contains user status in the Web SynDic system User Profile link appears in User Menu to provide additional Web SynDic feature Logout from the web system is performed using Log out link It appears after successful login in Log In area It is strongly recommended for every registered user to explicitly log out at the end of her his session Student Software Engineering Project Web SynDic 30 la Web SynDic Registration o Mozilla Xx a File Edit View Go Bookmarks Tools Window Help m Q 6 Y S http lzeta cs karelia 1u 8480 W eb SynDicllogin servlet m T E Bookmarks ALT ee So pres Ha meu gt OpenOffice KET amp 030H O Mozillaru weekly gt ial Department of Computer Science ll WEB SYNDIc Registration Process Full name e ANLDE System Email e Set of ANLDE il ler TT t oe Password Documentation Re type password e ANLDE Theory e User Guide Information about yourself Send Notes Algorithms configuration Log In Nickname Password Register required field Register Figure 19 Registration form 3 7 User Profile Configuration When a user is logged in the web system see subsection 3 6 he she may use User profile link to manage own profile The User profile see Fig 20 form is divide
34. ear Diophantine Equations and their Application for Modelling of Internet Link Workload Structure PhD Thesis Department of Computer Science University of Petrozavodsk 2002 185 p in Russian Dmitry G Korzun Grammar Based Algorithms for Solving Certain Classes of Nonnegative Linear Diophantine Systems Proceedings of Annual international Finnish Data Processing Week at the University of Petrozavodsk FDPW 2000 Advances in Methods of Modern Information Technology Vol 3 Petrozavodsk 2001 pp 52 67 Kirill A Kulakov Testirovanie i experimantal ny analiz algoritmov resheniya neotrica tel nyh lineynyh diophantovih uravneniy BSc Thesis Department of Computer Science University of Petrozavodsk 2003 50 p in Russian Schrijver A Theory of linear and integer programming Wiley Chichester 1986 G Huet An algorithm to generate the basis of solutions to homogeneous linear diophantine equations Information Processing Letters 1978 Vol 3 No 7 pp 144 147 Domenjoud E Solving Systems of Linear Diophantine Equations An Algebraic Approach In U Tarlecki ed Proceedings of 16th International Simposium on Mathematical Foun dations of Computer Science Springer Verlag 1991 LNCS 520 PP 141 150
35. earching a particular solution of the NLDE system if any It may include searching any particular solution or any minimal solution or a particular solution satisfied to some other criteria 3 Searching Hilbert basis of the NLDE system The list can be prolonged For instance an interesting problem is counting basis solutions The listed problems are very complex in the computational sense The solvability and particular solution searching problems are NP complete 9 The problem of searching Hilbert basis is even more complex overNP This is a reason for dicovering particular classes of NLDE systems that have efficient polyn imial algorithms for solving We suggest basing on the original work of M Filgueiras and A P Tomas 1 an interesting approach for this using formal grammars to establish such classes of NLDE systems A formal grammar is assigned to a NLDE system and solution searching is moved from set Z to a set of derivations in the grammar one searches a derivation instead of a NLDE Student Software Engineering Project Web SynDic 8 solution see Figure 2 The idea is the same as in operations calculus where the problem of solving an integral differential equation is reduced to solving an algebraic equation in complex numbers Figure 2 Association between NLDE and formal grammars a general view The methods and algorithms of the formal grammars theory have been very developed starting from 50th Our a
36. ee the form for changing the constraints see Fig 25 After setting some values do not forget to press Submit button OS x File Edit View Go Bookmarks Tabs Help lt gt amp 2 a gg A Back Forward Stop Reload Home History Bookmarks Find http zeta cs karelia ru 8480 Web SynDic main jsp RS PETROZAVODSK STATE UNIVERSITY es karelia ru Department of Computer Science Wes SynDIc Web System for Demonstrating the Syntactic Algorithms for Solving Linear Equations in Nonnegative Integers Process e ANLDE System e Set of ANLDE Welcome to Web SynDic Systems Dear System Administrator You may and can do everything with the Web SynDic system Remember this be Documentation carefull and do not force the system to collapse e ANLDE Theory e User Guide Do not forget to read your email for Web SynDic user notes Send Notes User Profile Algorithms configuration Manage Users Constraints Activity Statistics You have logged in as admin log out Server Load 1 active users Done Be Figure 25 Changing constraints Be careful while changing bounds on limits you can overload or even corrupt the web system 4 4 Viewing activity statistics Administrator has ability to view activity statistics collected by the web system The activity statistics mean summarized information appropriate to selected domain and metrics for current Perhaps in future there will be low
37. er bounds too Student Software Engineering Project Web SynDic 36 month Activity statistics domain is a criterion by which statistics information is summarized e g user nickname or IP address Activity statistics metrics define categories for statistics report e g requests for solving or number of sessions To view activity statistics follow the link Activity Statistics If you have administrator privileges you will see form for viewing activity statistics see Fig 26 Here you can choose the type of statistics report Ol Web SynDk Activity Statistics x File Edit View Go Bookmarks Tabs Help gt a q 4 QM Back Forward Stop Reload Home History Bookmarks Find http zeta cs karelia ru 8480 Web SynDic main jsp page statistics PETROZAVODSK STATE UNIVERSITY X D Department of Computer Science WEB SyNDIC Activity Statistics Process Use this form to view the web system s activity statistics Available only for the e ANLDE System administrator e Set of ANLDE Systems Domain IP address gt Docmentation Metrics Sum session time iv e ANLDE Theory _Get Report e User Guide Send Notes User Profile Algorithms configuration Manage Users Constraints Activity Statistics You have logged in as admin log out Server Load 2 active users Done lu Figure 26 Viewing activity statistics A statistics report contains time of report generation and statistic
38. er value lt param value gt lt context param gt Jakarta Tomcat 5 0 compatibility issues At this moment sending notes subsystem is not working correctly under Tom cat 5 0 It ignores configuration of mail Session JNDI resource in TOMCAT_HOME conf server xml and uses localhost as SMTP server by default Student Software Engineering Project Web SynDic 39 6 Frequently Asked Questions Question I am trying to save ANLDE system set of ANLDE systems but browser doesn t open corresponding window with the system as described in documentation Why Answer The Web SynDic system uses pop up windows for saving ANLDE systems Your browser probably blocks pop up windows Enable pop up windows and try again Question Sometimes Maximum process virtual size in Solution report is N A Why Answer The Web Syndic system uses external programs for collecting resource usage infor mation These programs read solver process system information which should be updated at least one time So if solver executes too fast the information is not updated If you still want to know Maximum process virtual size you may try to solve the system several times until this information is obtained Question I am trying to solve a set of ANLDE systems but the solver fails How can I solve this set anyway Answer At present the Web SynDic system doesn t support detailed error messages for ANLDE system sets You may tr
39. ia ru Information The Web System Administrator e User Manual Send Notes User Profile Algorithms configuration Manage Users Submit Constraints Activity Statistics You have logged in as admin log out Usar password Old password New password 1 active users y a Server Load Figure 20 User profile form 3 8 Web SynDic notes Web SynDic allows a user to send any her his opinion to the Web SynDic system administrator A special case here is user s disagreement with found solution s of the processed ANLDE system To compose a general note i e note about Web SynDic as a whole system a user clicks on the Send notes link in Main Menu whereupon he she will be returned with the following form see Fig 21 The user writes as plain text what he she wish to send and clicks on the Send note button The composed note will be transferred to the Web SynDic system administrator by email Web SynDic provides a feature to send note about particular solved ANLDE system s When a report on solution is returned a user may select Note on solution link for sending more detailed opinion about this solution or just press the Agree with the result button whenever he she satisfied with the solution If a user selects Note on solution then Notes on Solution form will appear see Fig 22 With the form the user can choose one of the two possibilities e Agreement with the result of solvi
40. ing one task i e single ANLDE system or ANLDE system set If sum of CPU work times is greater than the restriction then the solving process is interrupted with corresponding error message Max memory for solving maximum virtual memory for each solving process If amount of memory exceeds the limit then the solving process is interrupted with corresponding error message Max number of basis solutions in report maximum number of basis solutions in re port If number of solutions exceeds this limit then other solutions are left out Student Software Engineering Project Web SynDic 12 EE Web SynDic Algorithms Configuration Mozilla le x File Edit View Go Bookmarks Tools Window Help p Fi xi S KE Ed FE 2 v ig y 3 de http zeta cs prv 8480 Web SynDic main jsp jsessionid 61B57997CBE7002344EF1424543E Y stop E Back Forward Reload es karelia ru Department of Computer Science Wep SynDic Algorithms Configuration Process Parameter Current value Max value e Set of ANLDE Max CPU time for solving sec 60 90 Systems Max memory for solving KB 4096 5120 Documentation Max number of basis solutions in ANLDE Theory report roo 100 User Guide Generator Limits Send Notes Max CPU time for generation sec 60 90 Algorithms Max memory for generation KB f4096 5120 configuration Generator Parameters Log In Belek of equations in ANLDE E Io Nickname 0 Number of unknowns in A
41. m see Fig 24 To manage a user you need to enter nickname into the form and press Get Profile button If you have administrator privileges and the nickname is valid you will see the standard form for editing user profile see section 3 7 If any error has been occurred you get a message with the error description After editing the information do not forget to press Submit button if you want the changes to be saved Student Software Engineering Project Web SynDic CO Web SynDie x File Edit View Go Bookmarks Tabs Help a gt Q amp Q amp Back Forward Stop Reload Home History Bookmarks Find amp http zeta cs karelia ru 8480 Web SynDic main jsp y Go y RS PETROZAVODSK STATE UNIVERSITY es karelia ru Department of Computer Science Wes SynDIc Web System for Demonstrating the Syntactic Algorithms for Solving Linear Equations in Nonnegative Integers Process e ANLDE System e Set of ANLDE Welcome to Web SynDic Systems Dear System Administrator You may and can do everything with the Web SynDic system Remember this be Documentation carefull and do not force the system to collapse e ANLDE Theory e User Guide Do not forget to read your email for Web SynDic user notes Send Notes User Profile Algorithms configuration Manage Users Constraints Activity Statistics You have logged in as admin log out Server Load 1 active users Done o Ss Figure 23 Administr
42. ng In this case the user may or may not attach ANLDE system s to the note using the Attach processed system checkbox Student Software Engineering Project Web SynDic El Web SynDte User Notes x File Edit View Go Bookmarks Tabs Help lt gt amp 2 QQ 9 Aa Back Forward Stop Reload Home History Bookmarks Find http zeta cs karelia ru 8480 Web SynDic main jsp jsessionid D CEAEE110526D61E8E5C9D8 3AC6BE7 34 page notes PETROZAVODSK STATE UNIVERSITY Sal a Department of Computer Science Wes SyYNDIC Send Notes on Web SynDic Process Dear guest e ANLDE System e Set of ANLDE Write here any opinion about Web SynDic as a whole web system For noting on a concrete ANLDE processing case perform this processing first then use the Systems 5 hyperlink from the page report on solution Documentation e ANLDE Theory e User Guide Send Notes Algorithms configuration Log In Send notes Nickname Your note will be sent to the system administrator kulakov cs karelia ru Password a E Any your comment remark or observation is welcome We are open for fruitful discussion and criticism you may also continue working as anonymous user but your profile and ly Done A ae Ey Figure 21 General note E Web SynDk User Notes x File Edit View Go Bookmarks Tabs Help 9 0 0 q A Back Forward Stop Reload Home History Bookmarks Find 6D http zeta cs karelia ru 84
43. ns the number of solutions from the default solver e Waiting time in Solver Spooler buffer If buffer is empty then Solver Spooler executes new task immediately and waiting time equals to zero e Performance metrics of the algorithms algorithm name summary CPU work time in seconds Student Software Engineering Project Web SynDic 19 Student Software Engineering Project Web SynDic 20 ST ill lel x R A Ae p Di Ls ocess an ANLDE System oe a a x o summary neal work mein seconds sl Eile Edit View Go Bookmarks Tools Window Help 2 y gt y Y Ay http zeta 8480 Web SynDic main jsp page process maximum process virtual size in kilobytes Back Forwar d Reload Stop e ANLDE System x5 2 x1 5 x3 9 x4 x5 e Set of MADE x2 x1 x2 x3 x4 solving result Systems x4 x6 5 x1 9 x3 8 x4 x6 es At the present the time unit for CPU work time is 0 001 second If Solver uses CPU work e AN eory User Guide time which is less than 0 001 second then lt 0 001 is printed in the report page Send Notes Algorithms save Store this ANLDE system in a text format If the value is not available for example Maximum process virtual size is not available configuration a 2 Solve the given ANLDE system with when algorithm executes too fast then N A is displayed in the corresponding field the syntactic algorithm You may Log In select one alternative solver to
44. omatically a new ANLDE system by the selected generator osin _Resister Generator Parameters Figure 1 Input a test ANLDE system resource usage and solutions will be loaded Student Software Engineering Project Web SynDic 5 More detailed information on solving ANLDE systems can be found in section 3 3 2 2 2 Generating a test ANLDE system Web SynDic allows to generate ANLDE systems instead of manual input Such a generated system characterized with simple Hilbert basis The reason is that the generation is based on original methods by Kirill Kulakov 8 These methods were also used for comprehensive automatic testing of the syntactic solver For generating one ANLDE system use ANLDE system link in the left side part of main form This link opens Process an ANLDE System form Press button Generate and Web SynDic returns this form with generated ANLDE system To save an ANLDE system shown in System text field click on the Save button You will see a new browser window containing the ANLDE system Then you can save it in a text file 9 using standard browser features like Save As item of the File menu More detailed information on generating ANLDE systems can be found in section 3 3 1 2 3 Generating and solving a set of ANLDE systems Web SynDic allows to generate and solve a set of ANLDE systems For generating a set of ANLDE systems use Set of ANLDE systems link in the left side part of main form
45. ponding formal grammar see 7 6 Web SynDic is intended to Student Software Engineering Project Web SynDic 42 the Web SynDic server homogenous NLDE system available on http www ncc up pt apt dioph demonstrate and test such algorithms System Privileged user who manages and controls the web system administrator Trivial solution All zero solution O 0 0 of a homogeneous NLDE system Web SynDic It stands for Web based demonstrating and testing the Syntactic algo rithms for solving nonnegative linear Diophantine equations rule tact D is used to transform the string Syntactic to the string SynDic References 1 Miguel Filgueiras Ana Paula Tomas Solving Linear Constraints on Finite Domains through Parsing In P Barahona L Moniz Pereira A Porto eds Proceedings of the 5th Portuguese Conference on Artificial Intelligence Springer Verlag 1991 LNAI 541 pp 1 16 as Yury A Bogoyavlensky Dmitry G Korzun General solution of a linear diophantine system associated with a context free grammar Transactions of the Petrozavodsk State University issue on Applied Mathematics and Computer Science vol 6 Petrozavodsk 1997 pp 79 94 In Russian Obshchiy vid resheniya sistemy lineynih diophantovih uravneniy associ trovannoy s kontextno svobodnoy grammatikoy Trudy Petrozavodskogo gosudarstvennogo universiteta Ser Prikladnaya matematika i informatika Vyp
46. pproach turns out that they can be fruitfully used to construct really efficient algorithms for solving some particular classes of NLDE system The efficiency means here that the algorithms are polynomial or pseudopolynomial comparing with the general NP complete and overNP case with exponential complexity The pseudopolynomiality allows to select those problems from the set of complex ones that are permissible for practical solving NLDE systems associated with CF grammars The syntactic algorithms Consider a CF grammar G N 2 P and two strings v and w Let G have m rules P r1 12 Tm n nonterminals N Aj Ao An and t terminals X d1 d2 a Grammar rules r has the form A a where a is a string in N U 2 The start nonterminal symbol is not required One can construct an associated with the grammar NLDE system ANLDE system for short as follows oy Ti ez b y k 1 2 n ie for each nonterminal Az 1 5 S iz bg k n 1 n 2 n t ie for each terminal ak n i l where J U UJ 1 2 m is a partition of 1 m Yki Z bk Z Let us denote this system as S G v w The ANLDE system has m unknowns correspond to m grammar rules n t equations correspond to n t grammar symbols Each set J contains indecies i such that rule r Student Software Engineering Project Web SynDic 9 has right hand side with nonternimal Az i e Az a The coefficients y
47. press Reload button of your browser and the generated system set will be put into solver spooler queue if it has available space Question I have logged in as the system administrator and I want to manage users I follow Manage Users link and see form which prompts me to enter user nickname Is it possible to get a list of all users in the Web SynDic system Answer The list of all users is currently unavailable This feature will be added in future releases In this version you have to enter user nickname manually Question I have logged in as the system administrator and I want to get activity statistics report I follow Activity Statistics link set IP address as a report domain and press Student Software Engineering Project Web SynDic 41 Get Report button After getting report some fields in the IP address Host column contain only IP addresses Why Answer Sometimes it is possible to get only IP address of host not the full host name In this case only IP address is displayed in the corresponding column of the report 7 Glossary Activity Summarized information about the web system usage appropriate to selected statistics domain and metrics for current month ANLDE system Associated with a formal grammar NLDE system See 2 6 CF grammar Context free grammar Computer Science CSDept Computer Science Department The PetrSU CSDept web site is http www cs karelia ru Constraints Upper limits
48. registered starts using the system It is open until a user logs out or closes the connection If a user logs out then the logical session is closed at once but if a user closes the connection for example closes the browser window Student Software Engineering Project Web SynDic 28 the session is still alive for a some period of time default is 15 min and configured by Jakarta Tomcat server If a user has established a session and is not using the system for a long time the session is also terminated automatically Each session has own identifier on the server side A new session identifier is generated whenever the session has been established If cookies are enabled in user s browser then the cookies are used to store session identifier Otherwise the session identifier is passed by the URL string in a browser window 3 5 2 Server load information One of the important features of the Web SynDic system is server load information presented to each user According to that information user may estimate waiting time while generating or solving ANLDE systems and correlate performance metrics of algorithms The Web SynDic server load information consists of the following items e active users number of all currently active users in the system i e number of all opened sessions see section 3 5 1 for details e registered users number of registered users in the system see section 3 6 for de tails e generator ta
49. s information appropriate to selected domain and metrics for current month You can choose either nickname and IP address as the domain of the report Number of sessions total sessions time requests for solving requests for generation total system time total work time agreements with solutions can be selected as metrics for a required report After pressing Get Report button you will see the statistics report Records in the report are sorted by domain An example of statistics report with nickname selected as domain and number of sessions selected as metrics is shown in Fig 27 Student Software Engineering Project Web SynDic 37 Student Software Engineering Project Web SynDic 38 5 Installation and Configuration Instructions Software requirements Web SynDic requires Java 1 4 or later http java sun com and Jakarta Tomcat 4 1 x or 5 0 x http jakarta apache org Web SynDic distribution The Web SynDic software consists of the platform independent part and external solving and generation programs You will need the versions of these programs compiled for your platform Cl Web SynDk Statistics Report x e e d a Ta Da Installation instructions gt B 9 8 ae Back fomerd O Sen Reload Home History Bookmarks Find To install Web SynDic into Jakarta Tomcat server copy the Web SynDic directory or amp http zeta cs karelia ru 8480 Web SynDic main jsp page report statistics amp domain 1
50. s this set of systems with Web SynDic later xl 6 x1 8 x2 5 x4 x2 X4 x6 7 x1 6 x2 4 x4 x6 x3 x5 4 xl x2 x3 2 x4 x5 amp xl 3 x1 x2 9 x5 x2 X5 2 x1 4x2 4 x5 x3 x4 x6 7 xl 3x2 x3 x4 6 x5 x6 2 xl x4 xX5 xl 3 x4 8 x5 x E Foroso ice Pp MecTHaa HHTpaceTb Z e User Guide Send Notes alternative solver none gt Solve a set Start processing your set loadesolve Algorithms configuration Log In Nickname Password Generate a New Set Log in Register Select a generator Gauss y Brau manie den andinas Generator Parameters y E Foroso EDN MecTHaa MHTpaceTb Figure 17 Save a set of ANLDE systems 4 Using standard browser functions you can save the system in a file The Web SynDic system uses pop up windows for saving ANLDE system set Your browser should support pop up windows 3 5 Server Load 3 5 1 User Session One of the main concept of the Web SynDic system is session There are two types of sessions a physical server session and a logical Web SynDic session Web SynDic session is a continuous time period of user s working with the Web SynDic Web SynDic session stores all information about current work in the system for example ANLDE systems algorithms configuration etc Further we will use term session instead of Web SynDic session Session is established when any user regular on
51. sfull message is displayed you become a registered user Question How can I contact the Web SynDic team Answer You may click Web SynDic Team hypertext link at the bottom right corner of any pageof the web system Detailed contact information should be displayed on the Web SynDic Team page Question I want to know more about the Web SynDic system development Where can I get Web SynDic documentation Answer You may find this and all other interesting information about the Web SynDic system latest news publications at the Web SynDic website http zeta cs karelia ru Web SynDic Question I want to generate and solve set of ANLDE systems I follow link Set of ANLDE systems and press Generate amp Solve button The system successfully finishes generation process but after that Buffer is full Task rejected error message is shown What is happening Answer The Web SynDic system uses two independent spoolers for generating and solving ANLDE systems correspondingly Each spooler may process only one task at the moment and store limited number of other tasks ANLDE systems or system sets for processing in its buffer After generating ANLDE system set the Web SynDic system tries to put generated set into the solver spooler queue Thus if the solver spooler buffer is already filled with other users tasks the corresponding error message is returned to you This error is not fatal Moreover after waiting for a while you can
52. should be greater than the number of equa tions Number of ANLDE systems in set Number of ANLDE systems in generated set This parameter is not used while generating single ANLDE system Max values of coefficients for ANLDE system maximum value of coefficients in gen erated ANLDE system Max values of components in basis solution maximum value of components in basis solutions Max number of basis solutions for ANLDE system maximum number of basis so lutions for ANLDE system 3 3 Processing a test ANLDE system Web SynDic can be used for solving test ANLDE system and showing report on solution to the user The ANLDE system should be given manually by a user or generated automatically by a selected generator Recently only homogeneous ANLDE systems are supported by the Web SynDic system Process an ANLDE system form is shown in Figure 4 Web SynDic system checks each solution by substitution the solution into the given ANLDE system Also if user uses alternative solver then the Web SynDic system compares correspond ing solutions 3 3 1 Creating ANLDE system The Web SynDic system supports two ways for creating ANLDE system e Manual input User can input ANLDE system manually into the text area of the cor responding form see Figure 4 The ANLDE system should be in ANLDE format see section 3 1 e Automatic generation The Web SynDic system supports two generators called Gauss and Gordano After
53. sks number of tasks queued for generation e solver tasks number of tasks queued for solving All this information is shown in the corresponding Server Load form at the left bottom part of the browser window Example information on server load including active users number registered users number solver tasks and generator tasks is presented in Fig 18 3 6 Registration and Log In There are two general types of users in the Web SynDic system a regular user and a registered user A regular user is any Web SynDic user and she he is not required to register and log in the web system A registered user has to have an account in the web system and his her personal information including limits for solving and generating ANLDE systems is saved in personal user profile Web SynDic allows any regular user to register whenever she he wishes When the reg istration is complete this user may log in the web system using assigned unique identifier Student Software Engineering Project Web SynDic 29 OS x File Edit View Go Bookmarks Tabs Help gt O 0 oga Back Forward Stop Reload Home History Bookmarks Find 6D http zeta cs karelia ru 8480 Web SynDic main jsp Go e ANLD PASO We consider a special class of homogenous NLDE systems that are Associated with a e User Guide context free grammars ANLDE systems See an example of such a system and its Send Notes processing The attractive property of the demonstrated synta
54. t hand side of some equation at most one time Blank and comment lines are ignored The sample of ANLDE system Sample ANLDE system Student Software Engineering Project Web SynDic 11 x1 x4 2 x1 3x x3 x2 x3 x1 2xx2 x3 Format for a set of ANLDE systems is following lt ANLDE system 1 gt h lt ANLDE system 2 gt lt ANLDE System N gt The format represents ANLDE System Set lt ANLDE System 1 gt lt ANLDE System N gt Each system is in the ANLDE system format Blank and comment lines are ignored String with symbols s is a delimiter for ANLDE systems These strings may additionally contain blank symbols u At only 3 2 Algorithms Configuration One of the important Web SynDic features is ability to configure external algorithms used for generation and solving ANLDE systems The algorithms are configured by setting restrictions limits and parameters Each restriction has two items current value and maximum value The values of items should be integers greater than zero except maximum number of basis solutions in report which can be set to zero Algorithms configuration form allows to configure solver limits section 3 2 1 generator limits section 3 2 2 and generator parameters section 3 2 3 Example of Algorithms Configuration form is shown in Figure 3 3 2 1 Solver limits User can set the following solver limits Max CPU time for solving maximum CPU time in seconds for solv
55. ta 8480 Web SynDic main jsp page processset 2 Back Forward Reload Stop PETROZAVODSK STATE UNIVERSITY Department of Computer Science Were SynDic Process a Set of ANLDE Systems Process Load a Set from a Text File ANLDE System Set of ANLDE Browse Systems DOGUMentati n For comparison of the syntactic algorithm with another solver select one alternative solver lt none gt ANLDE Theory User Guide Solve aset_ Start processing your set load amp solve Send Notes Algorithms configuration Generate a New Set Log In Select a generator Gauss y Nickname E i enerator Parameters P d eee Parameter Current value Max value _togin Register Number of equations in ANLDE Figure 13 Process a Set of ANLDE Systems CPU time limit is used as a common restriction for the whole solving process while processing ANLDE system set If the solver is unable to solve any ANLDE system in the set then the solving process is stopped and descriptive error message is displayed to the user 3 4 1 Loading and solving ANLDE system set The Web SynDic system supports solving a set of ANLDE systems previously loaded from a file The form for loading and solving ANLDE systems is shown in Figure 13 The loading and solving process consists of the following steps 1 Set solver parameters using Algorithms configuration form see section 3 2 You may also use default values 2 Use the button Browse to select
56. w v w are strings in this alphabet If ai a Vi 1 2 m where a is a right hand side of rule ry ando AWI Sw Aw e Theo Gu 5 Gn w According to the theorem one can take the grammar G see the above example and v w BA aaAaaaA ANLDE system are the same The derivation BA gt AAAaBA AAAGA gt aBBaAAaA S aaAAadA gt aaAaBBaaA 2 aaAaaaA T However for v w B aaaaaA constructs the mentioned above solution x 0 2 1 5 there is no derivation B aaaaaA in the grammar G This means one does not take into accont i the order of symbols in r v w and ii symmetric addition subtraction of symbols in v w Theorem 3 Vector x ZY is a solution of ANLDE system S G v w iff x corresponds to a derivation v gt w where v Af v w Af w and the order of symbols in sentential forms is ignored 3 1 2 ANLDE system format The Web SynDic system uses ANLDE systems in the following format Comment x x2 xK2 c11 x1 c12 x2 c1Nx xN x K2 1 x K2 2 xK3 c21 x1 c22 x2 c2N xN x KM 1 x KM 2 xN cM1 x1 cM2 x2 cMN xN The format represents one ANLDE system c11 c12 c1N c21 c22 cMN are coef ficients optional default value is 1 x1 x2 xN are unknowns may appear in any order some may be skipped If there is no unknowns after the sign write 0 Each unknown must appear in the lef
57. work menu at the left Systems ignore the error and return to the start page HOCIMERtAHAN Process an ANLDE System ANLDE Theory User Guide Send Notes Algorithms configuration Input a test ANLDE system a list of samples Log In Nickname Password Login Register Save Store this ANLDE system in a text format P Figure 8 Generator failed 16 Student Software Engineering Project Web SynDic 17 e Number of equations is greater than number of unknowns Check that the number of equations is less than the number of unknowns e Numbers of equations and unknowns are equal The generator does not support this class of ANLDE systems You can input the system manually e CPU time limit exceeded Try to increase time limit Time limit is too small or gener ator parameters are too large Try to increase time limit or change generator parameters e Algorithm cannot generate ANLDE system s or memory limit exceeded The generator is unable to generate ANLDE system with current parameters or memory limit is too small Try to increase memory limit or change generator parameters e Generator failed The generator parameters are possibly wrong or the program itself failed to execute for some reason We will be pleased if you will send note see section 3 8 containing generator parameters in this case e Generator failure parameter maximum value of coefficients for ANLDE s
58. y to solve each ANLDE system separately and manually remove unsolvable system from the set Question What does there is an ANLDE system already in processing warning mean Answer The Web SynDic can process no more than one ANLDE system or set of systems for a user at the same time So after you have requested generating or solving a system you can not send new requests until the processing of the previous system is finished Question Why does my task spends so much time waiting in solving and generation queues Answer The Web SynDic does not solve or generate ANLDE systems concurrently So if there are many users processing ANLDE systems your task will be added to the end of queue and will wait until all previously requested processings are finished You may see the number of queued tasks in the Server Load section of the left hand panel on any page of the web system Question Why I may want to register in the web system Answer Your algorithms configuration values will be saved on server and restored every time you log in Also we will be able to identify notes sent by you Question How can I register in the Web SynDic system Student Software Engineering Project Web SynDic 40 Answer You should click Register button of the Log in form and fill all necessary text fields with your information Then press Register button in the User registration form If all text fields are filled correctly and Registration succe
59. ystem ex ceeded The maximum value of coefficients for ANLDE system is too small Try to increase it e Generator failure parameter maximum value of components in basis solutions ex ceeded The maximum value of components in basis solutions is too small Try to increase it e Generator failure parameter maximum number of basis solutions exceeded The max imum number of basis solutions is too small Try to increase it e Generator failure generated system is not correct The generator is unable to generate ANLDE system or generated ANLDE system is invalid We will be pleased if you will send note see section 3 8 containing generator parameters in this case 3 3 2 Solving ANLDE system The Web SynDic system default solver is Syntactic User can also use alternative solvers Slopes and Lp_solve The solving process consist of the following steps 1 Insert valid ANLDE system into the text area of the Process an ANLDE system form Alternatively you can generate it automatically see section 3 3 1 If ANLDE system is invalid or text area is empty then the Web SynDic system prints error message see Figure 9 Student Software Engineering Project Web SynDic 18 Ek web SynDic Process an ANLDE System Mozilla yA File Edit View Go Bookmarks Tools Window Help E Roni X Eat y a a i amp http izeta 8480 Web SynDic process servlet 3 6 ul C karelia ru Department of Computer Science
60. ystem with the syntactic algorithm You may select one alternative solver to compare the solvers Generate Gauss Generate automatically a new ANLDE system by the selected generator Generator Parameters Parameter Current value Max value Number of equations in ANLDE system 3 100 Number of unknowns in ANLDE system E 150 Max values of coefficients for ANLDE system fio 1000 Max values of components for basis solution roo 10000 Max number of basis solutions for ANLDE system 100 100 Figure 5 Generator parameters File Edit View Go Bookmarks Tools Window Help 2 X gt v 3 a amp http zeta cs prv 8480 Web SynDic process servlet jsessionid D4EC3CF21 1EE4713F9E0E6 Y Back Forward Reload Stop a PETROZAVODSK STATE UNIVERSITY Department of Computer Science Wes SynDic Process ANLDE System Set of ANLDE Systems Documentation ANLDE Theory User Guide Send Notes Algorithms configuration Log In Nickname Password The web system is processing your request Please wait O OK waiting in solving queue gt solving Use this link if the requested page does not load automatically for you i i zi Waiting for zeta espry Hoea Figure 6 Web SynDic wait page Student Software Engineering Project Web SynDic EE web SynDic Process an ANLDE System Mozilla File Edit View Go Bookmarks Tools Window Help 2 X gt v 3
61. z is the number of occurances of nonterminal Az by occ a Az 1 lt k lt n and terminal az by occ a az_ Nn 1 lt k lt n t in the right hand side of the rule r A gt a The coefficients by is the difference between the number of occurancies of Az bg occ w Ax occ v Ax 1 lt k lt n and ag_n bk occ w ak n occ v Ax n 1 lt k lt n t in the strings w and v For example consider the grammar G with nonterminals A and B n 2 the only terminal a t 1 and m 4 rules listed in Table 1 col 1 Let v B and w aaAaaa CF grammar ANLDE system original ANLDE system reduced ri A AAB A v1 22 2x1 3x3 1 11 T 373 1 ra A aBBa B E sed sd B AAAaB 13 24 11 Ta 23 Ly L2 4 a 2 9 3 5 2 2 3 5 rai Boe e is emty string Each grammar rule is marked with corresponding r Each equation of the ANLDE system is market with a coresponding grammar symbol Table 1 An example of ANLDE system Then the ANLDE system for the grammar G has the form presented in Table 1 col 2 The simplified system is shown in col 3 Let us note the requirement J U UJ 1 2 m may be reduced to hU UJn C 1 2 m If there is some i I U UT then one can add x to both sides of some equation but exactly to one equation For example the NLDE system v1 2 211 3x3 1 4 121 2x2

User manual - Web

Contents

Download Pdf Manuals

Related Search

Related Contents