tag:blogger.com,1999:blog-3722233.post5945310957520182605..comments2023-03-25T10:00:22.914-05:00Comments on Computational Complexity: why are regular expressions defined the way they areLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-16308287624018609922017-03-09T06:16:26.295-06:002017-03-09T06:16:26.295-06:00I've meant containment-wise minimal set of (si...I've meant containment-wise minimal set of (simple) axioms, not least number.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61269978508889071312017-03-08T09:19:53.226-06:002017-03-08T09:19:53.226-06:00I was hoping that Chomsky's use may have been ...I was hoping that Chomsky's use may have been the origin, but as far as I can tell this isn't the case. According the wikipedia, the paper in which Chomsky introduced his pseudonymous hierarchy of languages is https://chomsky.info/wp-content/uploads/195609-.pdf. But as one can see, he didn't use regular expressions at all, just finite state machines (as the deterministic case of a finite-state Markov process, which is a fairly ubiquitous concept in the sciences).Joshhttps://www.blogger.com/profile/12723950176543566251noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66436905172701878252017-03-08T09:13:49.081-06:002017-03-08T09:13:49.081-06:00Your first sentence is actually usually *not* the ...Your first sentence is actually usually *not* the case. Rather, a balance is typically struck between economy of axioms and their ease of use. For example, in group theory, groups are typically defined by three simple-looking and natural axioms. But in fact, groups can be defined by just *one* (rather complicated-looking and unnatural) axiom, e.g. see https://www.cs.unm.edu/~mccune/projects/gtsax/. In that regard, what axioms one chooses to use for a particular type of mathematical object is somewhat analogous to what programming language one chooses to express one's algorithms in...Joshhttps://www.blogger.com/profile/12723950176543566251noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4365331110471577612017-03-07T05:57:47.054-06:002017-03-07T05:57:47.054-06:00Intersection and difference are O(1) operations if...Intersection and difference are O(1) operations if you use Brzozowski derivatives to construct your NFA, of course.<br /><br />But this raises an interesting question: Consider some set of "interesting" operations that regular languages are closed under: KLEENE CLOSURE, CONCAT, UNION, INTERSECTION, SET DIFFERENCE, maybe INTERLEAVE PRODUCT... we know that the first three will imply the others. Is there some other set of three "interesting" operations that will do the job instead? Like, are the languages closed under *, concat, and intersection also closed under union?Pseudonymhttps://www.blogger.com/profile/04272326070593532463noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33539021933937508882017-03-07T03:48:54.366-06:002017-03-07T03:48:54.366-06:00Here are "clickable" links to the questi...Here are "clickable" links to the <a href="http://cstheory.stackexchange.com/questions/31458/who-introduced-nondeterministic-m-automata-and-proved-that-the-finite-ones-reco" rel="nofollow">question</a> and the <a href="https://www7.in.tum.de/um/courses/auto/ws1314/script/autonotes.pdf" rel="nofollow">lecture notes</a>.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80812220021932170782017-03-07T03:05:29.464-06:002017-03-07T03:05:29.464-06:00In math every object is always defined with the le...In math every object is always defined with the least number of necessary axioms, and then the rest is shown to follow/be equivalent. This is math. Imagine if you defined planar graphs as graphs that can be drawn in the plane AND colored with four colors. It would certainly make the Four Color Theorem a lot easier to prove.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16262836818936473872017-03-07T01:09:09.044-06:002017-03-07T01:09:09.044-06:00I would say: because the advantage you would have ...I would say: because the advantage you would have in proving some of the closure properties using regular expressions would be negated.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8589295877283034692017-03-06T20:37:38.994-06:002017-03-06T20:37:38.994-06:00An ahistorical reason: If your initial model were ...An ahistorical reason: If your initial model were NFAs rather than DFAs then simulation of intersection of regular languages by NFAs would be just as problematic as simulation of Kleene star by DFAs. At least with the current definition, simulation by NFAs is trivial. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18587505515360144952017-03-06T17:08:47.139-06:002017-03-06T17:08:47.139-06:00The answer by KWillets can be translated into an a...The answer by KWillets can be translated into an algebraic context by considering an arbitrary monoid M instead of only finitely generated free monoids. One then introduces the rational sets over M inductively starting from finite sets via UNION, CONCAT and *. Then one introduces an appropriate notion of nondeterministic M-automaton, and shows that a set is rational exactly if it is accepted by a finite nondeterministic M-automaton.<br /><br />At least this question (http://cstheory.stackexchange.com/questions/31458/who-introduced-nondeterministic-m-automata-and-proved-that-the-finite-ones-reco) implicitly claims this, and J.-E. Pin confirms it with a reference to the supposedly original publication. If you care less about references to original publications, then these lecture notes (https://www7.in.tum.de/um/courses/auto/ws1314/script/autonotes.pdf) by Manfred Kufleitner provide easy to follow proofs with many images and applications like Angluinâ€™s learning algorithm for recognizable sets (oh wait, recognizable sets are the other part of the story corresponding to deterministic automata).Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87888483074607407072017-03-06T14:51:37.239-06:002017-03-06T14:51:37.239-06:00On page 73 of his classic RAND report (available a...On page 73 of his classic RAND report (available at http://www.rand.org/pubs/research_memoranda/RM704.html), Kleene writes "We did not include the operations & (and) and overline (not) in our definition of regular events, because in the converse theorem (Theorem 6) we do not need to. In this section we will show that net constructions can be managed so that the two operations can be included." Right above Section 7.6 of that landmark paper, Kleene also says: "But, of course, the fact that our three operations are completely general (by Theorem 6) does not settle the question whether they will prove to be a convenient and practical way to deal with events. Possibly some other selection will prove to be more convenient. Or, we may add other operations and express these in turn in terms of our three." <br /><br />So Kleene's choice of operations appears to be guided by an analysis of the paper by McCulloch and Pitts, and economy of description. <br /><br />My two-cent worth. Luca Acetohttps://www.blogger.com/profile/01092671728833265127noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10813006361135885202017-03-06T13:02:16.172-06:002017-03-06T13:02:16.172-06:00Offhand I'd say that UNION, CONCAT and * are O...Offhand I'd say that UNION, CONCAT and * are O(1) operations while the others are not (on an NFA, which is pretty weak). KWilletshttps://www.blogger.com/profile/10925155896023006453noreply@blogger.com