Theory Of Automata Chapter 5 Solution
Magin Sriubas
We show that, given a word equation over a finitely generated free group, the set of all solutions in reduced words forms an EDT0L language. In particular, it is an indexed language in the sense of Aho. The question of whether a description of solution sets in reduced words as an indexed language is possible has been open for some years [9, 10], apparently without much hope that a positive answer could hold. Nevertheless, our answer goes far beyond: they are EDT0L, which is a proper subclass of indexed languages. We can additionally handle the existential theory of equations with rational constraints in free products \(\star _1 \le i \le sF_i\), where each \(F_i\) is either a free or finite group, or a free monoid with involution. In all cases the result is the same: the set of all solutions in reduced words is EDT0L. This was known only for quadratic word equations by [8], which is a very restricted case. Our general result became possible due to the recent recompression technique of Jeż. In this paper we use a new method to integrate solutions of linear Diophantine equations into the process and obtain more general results than in the related paper [5]. For example, we improve the complexity from quadratic nondeterministic space in [5] to quasi-linear nondeterministic space here. This implies an improved complexity for deciding the existential theory of non-abelian free groups: \(\mathsf NSPACE(n\log n\)). The conjectured complexity is \(\mathsf NP\), however, we believe that our results are optimal with respect to space complexity, independent of the conjectured \(\mathsf NP\).
Research supported by the Australian Research Council FT110100178 and the University of Newcastle G1301377. The first author was supported by a Swiss National Science Foundation Professorship FN PP00P2-144681/1. The first and third authors were supported by a University of Neuchtel Overhead grant in 2013.
Manfred Kudlek has the distinction of being the only person to have attended all ICALP conferences during his lifetime. He worked on Lindenmayer systems, visited Kyoto several times, and taught the second author that bikes are the best means of transport inside Kyoto.
This web page ( -cse.ucsd.edu/classes/wi03/cse105/)will be used to make importantannouncements related to the course. All class members areresponsible for reading information on the web page, and checking itfrequently for updates.
This course introduces the basic, formal ideas underlying the notion ofcomputation. Syllabus: finite automata, regular expressions, context-freegrammars, pushdown automata, turing machines, decidability, undecidability,the halting problem, introduction to complexity theory.
Chapter 0: The material covered in this chapter is prerequisite to thiscourse. This material will not be explicitly covered in class, but you aresupposed to read the chapter to make sure you have the necessarybackground.
Below are some pointers to where in the textbook you can find the materialcovered in each lecture. The book also contains many excercises and problemsat the end of each chapter. You are encouraged to try solve them (in additionto the regularly assigned homeworks of course). That's the best way to testyour understanding and problem solving abilities.
Quizzes are scheduled during regular lecture hours, and everybody isexpected to attend. There will be no make up quizzes. Not showing up to aquiz will count as 0 grade. Each quiz will account for 20% of the finalgrade, the final exam gives the remaining 40%. Both the quizes and the finalexam will be closed books, closed notes. You can take 1 double sided sheet ofnotes to the exam, but the notes must be your own.
All students are expected to be familiar with and abide by the rules of UCSD Policy onIntegrity of Scholarship as described in the UCSD General Catalog. Incase of cheating, such policy will be enforced. This means an F grade in thecourse, and action by the Dean of your college (probation or suspension fromUCSD). You are allowed (and encouraged) to collaborate with other students indoing the homeworks, as they will not receive a formal grade. No form ofcollaboration is allowed during the quizzes and final exam.
I have a copy of Dummit and Foote from which I would like to study, however I realize that it contains quite a large amount of material! I would thus like to put together a list of essential topics to cover so that at the end I would have covered a similar content to a third year undergraduate course for mathematicians. One thing I would like to do if possible is get an introduction to Galois theory, it is quite mysterious to me and I would love to get acquainted to the subject.
I am (quite unfortunately) in electrical engineering, although I am directing myself to do a masters in math or perhaps control theory on the mathematical side of things. As such I have taken as many math course as I could and have done some self studying so that I think I now have a reasonable degree of mathematical maturity (real analysis, topology, differential geometry, linear algebra of course, probability and stats, discrete math, etc). Unfortunately I can't take as many pure math courses an as a math undergrad which is why I want to self-study abstract algebra.
I actually did this, and so I have some experience with Dummitt and Foote that I'd like to share. First, if you're not committed to D&F, but just to getting some good basis in modern algebra, I might be inclined to recommend a different book. Let me just tell you some pros and cons about this bible of algebra.
Tons of examples worked out. Every chapter has some general theory, followed by usually about a half dozen explicit examples. It's really good to do these examples by yourself, and then read how the book does them, or read them in the book and then try modified examples for yourself and see if you can follow the same ideas. Another useful thing to do is to try to work some examples as you read through theorems. None of this is unique to D&F but rather just good advice for reading any math book, but it goes double for D&F for reasons I'll explain below.
A billion and two exercises. This is a must for algebra, for the same reason. Practice practice practice. The problems range from routine to difficult (but none are so hard I could never work them out, if you like to be $really$ challenged you may not like this about the book). The first dozen chapters are so have solutions online (google 'project crazy project'). This doesn't include the stuff on Galois theory you're potentially interested in, but it does include everything up to the stuff on modules over PID, if I remember correctly.
It covers nearly everything one could possibly want to know. It really is an encyclopedia of algebra, at a level that's pretty accessible - it does not have the level of formalism that other books, like the one by Lang have. No knowledge of categories is required to learn from the text, and when they are introduced in the discussion of tensor products, all the relevant notions are included.
IT'S LITERALLY HUGE. Trying to finish even a substantial portion of it (let alone all) is a near impossible task. I studied from it for a year when I was an undergrad (probably less advanced than you are now though) and I only got through like 9 chapters.
Many of the later chapters contain things that are not part of a typical first course. The two semester sequence of algebra at my university covers only up to the stuff on Galois theory and fields, which is like 13 or 14 chapters in, and skips around quite a bit (and over some topics completely), yet the book is like 20 some odd chapters long.
Dummit and Foote's style is a little deceptive. They do not do a very good job demarcating which theorems are fundamental for you to understand and which are just 'results' that come up you may want to know. It is my opinion for example, that nilpotent groups, semidirect products and other content from the later chapters on group theory are not particularly important to understanding the basic ideas of group theory, the isomorphism theorems, group actions and Sylow theory, etc.
I really like Dummit and Foote's book. But it's not the be-all and end-all book that some faculty make it out to be. There are other very good books that contain other useful perspectives and are at a variety of levels. So my advice is to use D&F as a list of topics in algebra, and a great source of exercises and examples, while hunting out other references in the areas you like. Modern algebra is an ungodly large field - it's literally one of the three main branches of math - that there is no hope to learn about everything, at least at this stage. So use it as a starting point, and as a springboard into the areas of algebra you like. Ideally you could follow a syllabus from some other place, at least until you feel like you have a sense of direction, and then just peruse many references online using particular chapters or sections of D&F as a place to get started from. A given chapter of D&F is readable (with many exercises done) in anywhere from a week to two weeks, depending on your time and maturity. This is a great way to get some exposure to some ideas, and to help you think about branching out in other directions.
1) Chapter 0. This book is my favorite introduction to algebra. It includes many interesting topics not present in other books, and uses category theory throughout (it has a first chapter to introduce you to it) and is by far the friendliest algebra book I've ever used. As a result it's a little slow, but you can always breeze through it just for it's perspective while working from D&F. The perspective of universal properties is really essential to how algebraists do algebra, and so is immensely useful to carry with you as you learn. It's also the only book I've ever seen which is readable by an undergraduate which actually discusses any homological algebra at all - the others in this list (and D&F, if I remember right) do discuss it, but the discussion is certainly more difficult to read. There's even a short discussion at the end about derived categories and spectral sequences, which are certainly advanced topics.
c80f0f1006