Διαφορά μεταξύ των αναθεωρήσεων του «Κανονική γλώσσα»

(→‎Αποτελέσματα πολυπλοκότητας: Διόρθωση συνδέσμου)
 
== Αποτελέσματα πολυπλοκότητας ==
Στη [[θεωρία πολυπλοκότητας]], η κλάση πολυπλοκότητας όλων των κανονικών γλωσσών αναφέρεται μερικές φορές ως REGULAR ή REG και ισοδυναμεί με [[DSPACE]](O(1)), δηλαδή τα [[Πρόβλημα απόφασης|προβλήματα απόφασης]] που μπορούν να επιλυθούν σε σταθερό χώρο (ο χώρος που χρησιμοποιείται είναι ανεξάρτητος του μεγέθους της εισόδου). Ισχύει ότι '''REGULAR''' ≠ '''[[:en:AC0|'''AC]]'''<sup>[[AC0|0]]</sup>]], αφού εμπεριέχει το πρόβλημα της ισοτιμίας κατά το οποίο πρέπει να αποφανθούμε αν το πλήθος των 1 ψηφίων στην είσοδο είναι άρτιο ή περιττό, και αυτό το πρόβλημα δεν ανήκει στο '''AC'''<sup>0</sup>.<ref>{{Πρότυπο:Cite journal|url=|title=Parity, circuits, and the polynomial-time hierarchy|last2=Saxe|first2=J. B.|journal=Math. Systems Theory|issue=|doi=10.1007/bf01744431|year=1984|volume=17|pages=13–27|last3=Sipser|first3=M.|last1=Furst|first1=M.}}</ref> Από την άλλη πλευρά, η '''REGULAR''' δεν περιλαμβάνει την '''AC'''<sup>0</sup>, διότι η μη κανονική γλώσσα των [[Καρκινική γραφή|παλίνδρομων]] ή η μη κανονική γλώσσα <math>\{0^n 1^n : n \in \mathbb N\}</math> μπορούν αμφότερες να αναγνωριστούν στην '''AC'''<sup>0</sup>.<ref>{{Πρότυπο:Cite book|title=Logical foundations of proof complexity|last2=Nguyen|first2=Phuong|publisher=Association for Symbolic Logic|year=2010|isbn=0-521-51729-X|edition=1. publ.|location=Ithaca, NY|pages=75|last1=Cook|first1=Stephen}}</ref>
 
Αν μια γλώσσα ''δεν'' είναι κανονική, τότε απαιτεί μια μηχανή με τουλάχιστον Ω(log log n) χώρο για την αναγνώριση (όπου n το μέγεθος της εισόδου)<ref>J. Hartmanis, P. L. Lewis II, and R. E. Stearns. </ref>. Με άλλα λόγια, το DSPACE(o(log log n)) ισοδυναμεί με την κλάση των κανονικών γλωσσών. Στην πράξη, τα περισσότερα μη κανονικά προβλήματα επιλύονται από μηχανές που καταλαμβάνουν τουλάχιστον [[Λογαριθμικός χώρος|λογαριθμικό χώρο]].
56

επεξεργασίες