एक्सप्रेसिव पॉवर (कंप्यूटर विज्ञान)

From Vigyanwiki


कंप्यूटर विज्ञान में, किसी लैंग्वेज की एक्सप्रेसिव पॉवर (जिन्हें एक्स्प्रेस्सिविटी या एक्स्प्रीस्सिवेनेस भी कहा जाता है) विचारों की व्यापकता है जिनको उस लैंग्वेज में प्रस्तुत और संप्रेषित किया जा सकता है। लैंग्वेज जितनी अधिक एक्स्प्रेस्सिव होती है, विचारों की विविधता और मात्रा उतनी ही अधिक होती है जिसका उपयोग प्रतिनिधित्व करने के लिए किया जा सकता है।

उदाहरण के लिए, वेब ओन्टोलॉजी लैंग्वेज एक्स्प्रीस्सिवेनेस लैंग्वेज प्रोफ़ाइल (ओडब्लूएल 2 ईएल) में विचारों (जैसे निषेध) का अभाव होता है जिसे ओडब्लूएल 2 आरएल (नियम लैंग्वेज ) में व्यक्त किया जा सकता है। इसलिए कहा जा सकता है कि ओडब्लूएल 2 ईएल में ओडब्लूएल 2 आरएल की तुलना से कम एक्सप्रेसिव पॉवर होती है। ये प्रतिबंध ओडब्लूएल 2 आरएल की तुलना में ओडब्लूएल 2 ईएल से अधिक कुशल (बहुपद समय) लाॅजिक की अनुमति देते हैं। इसलिए ओडब्लूएल 2 ईएल अधिक कुशल लाॅजिक (ज्ञान प्रतिनिधित्व लैंग्वेज का प्रसंस्करण) के लिए कुछ एक्सप्रेसिव पॉवर का ट्रेड्स करता है।[1]

सूचना विवरण

एक्सप्रेसिव पॉवर शब्द का प्रयोग विभिन्न अर्थों के साथ किया जा सकता है। इसका कारण उस लैंग्वेज में व्यक्त किया जाता है जहाँ विचारों की माप हो सकती है:[2]

  • सहजता की सावधानी किए बिना (सैद्धांतिक एक्स्प्रीस्सिवेनेस )
  • संक्षिप्त और सहजता से (व्यावहारिक एक्स्प्रीस्सिवेनेस )

पहला भाव गणित और लाॅजिक के उन फ़ील्ड पर हावी है जो लैंग्वेजों के फॉर्मल डिस्क्रिप्शन और उनके अर्थ से संबंधित होते हैं, जैसे फॉर्मल लैंग्वेज थ्योरी , मैथमेटिकल लाॅजिक और प्रक्रिया बीजगणित।[2]

अनौपचारिक चर्चाओं में, यह शब्द अधिकांशतः दूसरे अर्थ या दोनों को संदर्भित करता है। प्रोग्रामिंग लैंग्वेज चर्चा करते समय अधिकांशतः ऐसा होता है।[3] जहाँ इन शब्दों के अनौपचारिक उपयोगों को फॉर्मल बनाने का प्रयास किया गया है।[4]

एक्सप्रेसिव पॉवर की धारणा सदैव विशेष प्रकार की चीज़ से संबंधित होती है जिसका वर्णन संबंधित लैंग्वेज कर सकती है, और इस शब्द का उपयोग सामान्यतः उन लैंग्वेज ओं की तुलना करते समय किया जाता है जो समान प्रकार की चीज़ों, या कम से कम तुलनीय प्रकार की चीज़ों का वर्णन करती हैं।[4]

लैंग्वेज ओं और औपचारिकताओं के डिज़ाइन में एक्सप्रेसिव पॉवर और विश्लेषणात्मकता के मध्य व्यापार-विवृत सम्मिलित है। औपचारिकता जितनी अधिक अभिव्यक्त हो सकती है, उतना ही कठिन हो जाता है यह समझना कि औपचारिकता के उदाहरण क्या कहते हैं। तथा निर्णय संबंधी समस्याओं का उत्तर देना भी कठिन हो जाता है और पूरी तरह से अनिर्णीत समस्या हो जाती है।[5]

उदाहरण

फॉर्मल लैंग्वेज थ्योरी में

फॉर्मल लैंग्वेज थ्योरी अधिकतर स्ट्रिंग्स के सेट का वर्णन करने के लिए औपचारिकताओं का अध्ययन करता है, जैसे कि संदर्भ-मुक्त व्याकरण और नियमित एक्स्प्रीस्सिवेनेस होते है। औपचारिकता का प्रत्येक उदाहरण, उदा. प्रत्येक व्याकरण और प्रत्येक नियमित एक्स्प्रीस्सिवेनेस, स्ट्रिंग के विशेष सेट का वर्णन करती है। इस संदर्भ में, औपचारिकता की एक्सप्रेसिव पॉवर उसके उदाहरणों द्वारा वर्णित स्ट्रिंग्स के सेट का सेट है, और एक्सप्रेसिव पॉवर की तुलना करना इन सेटों की तुलना करने का स्तिथि है।

इस क्षेत्र में औपचारिकताओं की सापेक्ष एक्सप्रेसिव पॉवर का वर्णन करने के लिए महत्वपूर्ण मापदंड चॉम्स्की हायरार्की है। उदाहरण के लिए, यह कहता है कि नियमित एक्स्प्रीस्सिवेनेस , गैर-नियतात्मक परिमित ऑटोमेटन और नियमित व्याकरण में समान एक्सप्रेसिव पॉवर होती है, जबकि संदर्भ-मुक्त व्याकरण अधिक होती है; इसका कारण यह है कि पहले तीन औपचारिकताओं द्वारा वर्णित स्ट्रिंग्स के सेट सामान्तर हैं, और संदर्भ-मुक्त व्याकरण द्वारा वर्णित स्ट्रिंग्स के सेट का उचित उपसमुच्चय है।

इस क्षेत्र में, एक्सप्रेसिव पॉवर की व्यय अध्ययन का केंद्रीय विषय है। उदाहरण के लिए, यह ज्ञात है कि यह तय करना कठिन है कि क्या दो इच्छित नियमित एक्स्प्रीस्सिवेनेस याँ स्ट्रिंग के ही सेट का वर्णन करती हैं, जबकि इच्छा से संदर्भ-मुक्त व्याकरण के लिए ऐसा करना अनिर्णीत समस्या है। चूँकि, यह अभी भी कुशलता से तय किया जा सकता है कि कोई दी गई स्ट्रिंग सेट में है या नहीं।

अधिक एक्स्प्रेस्सिव औपचारिकताओं के लिए, यह समस्या कठिन या अनिश्चित भी हो सकती है। ट्यूरिंग पूर्ण औपचारिकता के लिए, जैसे कि इच्छानुसार फॉर्मल ग्राम्मर्स, न केवल यह समस्या है, किंतु उनके द्वारा वर्णित स्ट्रिंग के सेट के संबंध में प्रत्येक गैर-तुच्छ संपत्ति अनिश्चित है, तथ्य जिसे राइस प्रमेय के रूप में जाना जाता है।

संक्षिप्तता पर भी कुछ परिणाम होते हैं; उदाहरण के लिए, गैर-नियतात्मक स्टेट मशीनें और नियमित व्याकरण नियमित एक्स्प्रीस्सिवेनेसों की तुलना में अधिक संक्षिप्त होते हैं, इस अर्थ में कि पश्चात् वाले के आकार में कोई बदलाव किए बिना पूर्व में अनुवाद किया जा सकता है (अर्थात ओ(1) में), जबकि इसका उत्क्रम संभव नहीं है।

समान विचार उन औपचारिकताओं पर प्रयुक्त होते हैं जो स्ट्रिंग्स के सेट का नहीं, किंतु ट्रीयों के सेट (उदाहरण के लिए एक्सएमएल स्कीमा लैंग्वेज तुलना), ग्राफ़ या अन्य संरचनाओं का वर्णन करते हैं।

डेटाबेस थ्योरी में

डेटाबेस थ्योरी, अन्य बातों के अतिरिक्त, डेटाबेस क्वेरी से संबंधित है, उदा. सूत्र, जो किसी डेटाबेस की सामग्री को देखते हुए, उसमें से कुछ जानकारी निकालते हैं। प्रमुख संबंध परक डेटाबेस प्रतिमान में, डेटाबेस की सामग्री को परिमित गणितीय संबंधों के सीमित सेट के रूप में वर्णित किया गया है; तथा बूलियन क्वेरीज़, जो सदैव सही या गलत उत्पन्न करती हैं, उससे प्रथम-क्रम लाॅजिक में तैयार की जाती हैं।

यह पता चलता है कि प्रथम-क्रम लाॅजिक में एक्सप्रेसिव पॉवर का अभाव है: यह कुछ प्रकार के बूलियन प्रश्नों को व्यक्त नहीं कर सकता है, उदाहरण के लिए सकर्मक समापन से संबंधित प्रश्न भी होते है ।[6] चूँकि, एक्सप्रेसिव पॉवर को जोड़ सावधानी से किया जाना चाहिए और उचित दक्षता के साथ प्रश्नों का मूल्यांकन करना अभी भी संभव होना चाहिए, जो कि स्तिथि नहीं है, उदाहरण के लिए, दूसरे क्रम के लाॅजिक के लिए। परिणाम स्वरुप , ऐसा साहित्य सामने आया जिसमें कई क्वेरी लैंग्वेजों और लैंग्वेज निर्माणों की तुलना एक्सप्रेसिव पॉवर और दक्षता पर की गई, जैसे संगणक वैज्ञानिक के विभिन्न संस्करण।[7]

इसी तरह के विचार अन्य प्रकार के डेटा पर क्वेरी लैंग्वेजों के लिए भी प्रयुक्त होते हैं, जैसे कि एक्सएमएल क्वेरी लैंग्वेजे जैसे एक्सक्वेरी जैसी लैंग्वेज का उपयोग क्र सकते है ।

यह भी देखें

संदर्भ

  1. ↑ Grau, Bernardo Cuenca; Horrocks, Ian; Motik, Boris; Parsia, Bijan; Patel-Schneider, Peter; Sattler, Ulrike (2008). "OWL 2: The next step for OWL". Web Semantics: Science, Services and Agents on the World Wide Web. 6 (4): 309–322. doi:10.1016/j.websem.2008.05.001. ISSN 1570-8268.
  2. ↑ 2.0 2.1 Farmer, William (2007). "Chiron: A multi-paradigm logic". In R. Matuszewski; A. Zalewska (eds.). From Insight to Proof: Festschrift in Honour of Andrzej Trybulec. Studies in Logic, Grammar and Rhetoric. pp. 1–19. ISBN 978-83-7431-128-1.
  3. ↑ Structure and Interpretation of Computer Programs, by Abelson and Sussman
  4. ↑ 4.0 4.1 Felleisen, Matthias (1991-12-01). "प्रोग्रामिंग भाषाओं की अभिव्यंजक शक्ति पर". Science of Computer Programming (in English). 17 (1): 35–75. doi:10.1016/0167-6423(91)90036-W.
  5. ↑ Okhotin, Alexander (December 2005). "Unresolved systems of language equations: Expressive power and decision problems". Theoretical Computer Science. 349 (3): 283–308. doi:10.1016/j.tcs.2005.07.038.
  6. ↑ Serge Abiteboul, Richard B. Hull, Victor Vianu: Foundations of Databases. Addison-Wesley, 1995.
  7. ↑ Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov: Complexity and expressive power of logic programming. ACM Comput. Surv. 33(3): 374-425 (2001).
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=एक्सप्रेसिव_पॉवर_(कंप्यूटर_विज्ञान)&oldid=258523’