En kvasi-polynom-tid algoritm presenteras för provtagning nästan enhetligt slumpmässigt från n-slice av språket L(G) som genereras av en godtycklig sammanhangsfri grammatik G. (N-slice av ett språk L över ett alfabet är undergrupp L\ n av ord av längd exakt n.) Tiden komplexitet algoritmen är "?2 (n jGj) O(log n), där parametern " begränsar variationen av utdatadistribution från uniform, och jGj är ett naturligt mått på storleken på grammatik G. Algoritmen gäller för en klass av språk provtagning problem som inkluderar skivor av sammanhangsfria språk som en lämplig subklass. Vi tar upp problemet med provtagning (nästan) enhetligt på måfå ett ord av längd n från ett sammanhangsfritt språk L, och det relaterade problemet med att uppskatta antalet ord av längd n i L. Idealiskt skulle vi vilja få ett provtagningsförfarande som körs i tid polynom i längden n och storleken på den grammatik som används för att ange L. Detta problem har övervägts av många författare (till exempel Mairson 7]), som har föreslagit e cient lösningar baserade på dynamisk programmering, men alltid begränsat till specialfallet av entydig grammatik. Ingen polynomalgoritm har föreslagits för allmän kontextfri grammatik. Låt G vara en kontextfri grammatik som genererar språket L = L(G I denna anmärkning behandlar vi i synnerhet f; g-program och f+; g-program. 2 När det gäller f ; g-program algebra är = (2 ; f ; g), där är ett nite alfabet, 2 är uppsättningen av alla språk över, och operatörerna och är union och konkatetering av språk, som är bekanta från definitionen av \ reguljärt uttryck." (Observera att vi blandar ihop symbolen 2 med singeltonsspråket f g.) När det gäller f+; g-program är algebran = (Z X]; X; f+; g), där X är en nite uppsättning indeterminater, Ovanstående definitioner är standard, men vi nd det lämpligt att generalisera begreppet f; g-program något, så att godtyckliga föreningar av tidigare beräknade värden kan bildas i en enda operation, även om konkatering fortfarande är begränsad till par av värden. Vi säger att fackföreningsoperationen har obegränsade fan-in, medan konkateteringsoperationen har fan-in två. På samma sätt kommer våra f+; g-program vanligtvis att ha additionsoperationer med obegränsade fan-in, och multiplikationsoperationer av fan-in två. De ne en nästan enhetlig provtagare (för språk) att vara en randomiserad procedur som tar som inmatning en f ; g-program för (eller annan beskrivning av) ett språk L, och en tolerans 0 < " < 1 och producerar som utgång ett ord Y 2 L (en slumpmässig variabel) sådan att (1 + ")?1 jLj?1 Pr (Y = y) (1 + ") jLj?1 för alla y 2 L. Också de ne en randomiserad approximationsschema (för språk) att vara en randomiserad procedur som tar input som ovan, och producerar som utgång ett nummer b L (en slumpmässig variabel) sådan att (1+")?1 jLj b L (1+") jLj med sannolikhet minst 3 4. Vårt viktigaste resultat kan nu anges. Teorem 1 Det finns en nästan enhetlig provtagare av tid komplexitet "?2 (nC) O(log n) för att producera prover från ett språk L n, där L presenteras som en f ; g-program av storlek C. Det finns också en randomiserad approximationsschema med samma inmatning specification och samtidigt komplexitet. Den fackliga verksamheten i programmet kan ha obegränsade fan-in, men konkatetering verksamhet måste alla ha fan-in två. Beviset för Theorem 1 vilar på två idéer: Monte-Carlo provtagning från en union av uppsättningar, och djupkompression av kretsar. Vi undersöker dessa i sin tur. Karp och Luby 4, 5] införde en enkel och elegant metod för att uppskatta storleken på och, som en biprodukt, för enhetlig provtagning från unionen av en samling nite uppsättningar, alla vars storlekar är kända i förväg. En direkt tillämpning av deras teknik ger ett enhetligt urvalsförfarande för språk som beräknas av f; g-program med två växlingar av union och konkatetering: alltså består av ett block av fackföreningar, följt av ett block av konkatenationer, följt av ett annat block av fackföreningar. Kannan, Sweedyk och Mahaney 3] itererade metoden Karp-Luby 3 för att få ett nästan enhetligt provtagningsförfarande för språk som beräknas av allmänna f ; g-program. Omräknat på språket i denna artikel, det väsentliga innehållet i resultatet av Kannan et al. är följande.
Gore m.fl. REF utvecklar en subexponentiell tidsalgoritm för provtagning av ord från (eventuellt tvetydiga) grammatiker, där sannolikheten för att generera ett ord varierar från enhetlig med en faktor 1 +,  på (0, 1).
A Quasi-Polynomial-Time Algorithm for Sampling Words from a Context-Free Language
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}