Timed automaton
ऑटोमेटा सिद्धांत में, एक समयबद्ध ऑटोमेटन एक सीमित ऑटोमेटन है जो वास्तविक मूल्य वाली घड़ियों के एक सीमित सेट के साथ विस्तारित होता है। एक समयबद्ध स्वचालित चाल के दौरान, घड़ी के मान एक ही गति के साथ बढ़ते हैं। ऑटोमेटन के संक्रमण के साथ, घड़ी के मूल्यों की तुलना पूर्णांकों से की जा सकती है। ये तुलनाएँ रक्षक बनाती हैं जो संक्रमण को सक्षम या अक्षम कर सकती हैं और ऐसा करके स्वचालित के संभावित व्यवहार को बाधित कर सकती हैं। इसके अलावा, घड़ियों को रीसेट किया जा सकता है। समयबद्ध ऑटोमेटा एक प्रकार के संकर ऑटोमेटा का एक उप-वर्ग है। समयबद्ध स्वचालित का उपयोग कंप्यूटर प्रणालियों के समय व्यवहार को मॉडल और विश्लेषण करने के लिए किया जा सकता है, जैसे, वास्तविक समय प्रणाली या नेटवर्क। पिछले 20 वर्षों में सुरक्षा और जीवंतता दोनों गुणों की जांच करने के तरीके विकसित किए गए हैं और उनका गहन अध्ययन किया गया है। यह दिखाया गया है कि समयबद्ध स्वचालित के लिए राज्य की पहुंच की समस्या निर्णायक है, जो इसे संकर स्वचालित का एक दिलचस्प उप-वर्ग बनाती है। एक्सटेंशन का व्यापक रूप से अध्ययन किया गया है, जिनमें स्टॉपवॉच, वास्तविक समय के कार्य, लागत कार्य और समयबद्ध खेल शामिल हैं। टाइमड ऑटोमेटा और एक्सटेंशन को इनपुट और विश्लेषण करने के लिए विभिन्न प्रकार के उपकरण मौजूद हैं, जिनमें मॉडल चेकर यूपीपीएएएल, क्रोनोस और शेड्यूलेबिलिटी एनालाइजर टाइम्स शामिल हैं। ये उपकरण अधिक से अधिक परिपक्व होते जा रहे हैं, लेकिन फिर भी ये सभी शैक्षणिक अनुसंधान उपकरण हैं। उदाहरण औपचारिक रूप से परिभाषित करने से पहले कि टाइमड ऑटोमेटन क्या है, कुछ उदाहरण दिए गए हैं। यूनरी वर्णमाला पर समयबद्ध शब्दों की भाषा पर विचार करें जैसे कि पहली बार इकाई के दौरान एक है, और दो क्रमिक के बीच एक से कम समय इकाई है। इस भाषा को पहचानने वाला एक समयबद्ध स्वचालित यंत्र, जो पास में चित्रित है, एक ही घड़ी का उपयोग करता है, जो कभी भी एक के बराबर नहीं होनी चाहिए। यह घड़ी दौड़ की शुरुआत के बाद के समय को गिनती है यदि कोई उत्सर्जित नहीं हुआ था, या अन्यथा अंतिम उत्सर्जित समय से। इसका मतलब है कि हर बार जब एक उत्सर्जित होता है, तो यह घड़ी शून्य पर रीसेट हो जाती है। द्विआधारी वर्णमाला पर समयबद्ध शब्दों की भाषा पर विचार करें जैसे कि प्रत्येक के बाद अगली समय इकाई में a हो। इस भाषा को पहचानने वाला समयबद्ध स्वचालित, पास में चित्रित, याद करता है कि क्या एक ऐसा था जिसका अभी तक अनुसरण नहीं किया गया था। यदि ऐसा नहीं है, तो यह दौड़ को स्वीकार करता है, अन्यथा यह इसे अस्वीकार कर देता है। इसके अलावा, जब ऐसा होता है, तो इसमें एक घड़ी होती है जो उस समय को रिकॉर्ड करती है जब से पहली बार ऐसा उत्सर्जित किया गया था। इस मामले में, ए उत्सर्जित नहीं किया जा सकता है यदि घड़ी कम से कम एक के बराबर है, और इस प्रकार रन विफल हो जाता है। औपचारिक परिभाषा समयबद्ध स्वचालित औपचारिक रूप से, एक समयबद्ध स्वचालित एक टुपल है जिसमें निम्नलिखित घटक होते हैंः एक सीमित समूह है जिसे वर्णमाला या क्रियाएँ कहा जाता है। एक परिमित समुच्चय है। के तत्वों को स्थान या 'राज्य' कहा जाता है। प्रारंभ स्थानों का समूह है। एक परिमित समुच्चय है जिसे घड़ियाँ कहा जाता है। स्वीकार करने वाले स्थानों का समूह है। किनारों का एक समूह है, जिसे ट्रांजिशन ऑफ कहा जाता है, जहां से घड़ियों को शामिल करने वाली घड़ी की बाधाओं का समूह है, और इसका पावरसेट है। एक किनारे से स्थानों से कार्रवाई, गार्ड और घड़ी रीसेट के साथ एक संक्रमण है। विस्तारित राज्य एक स्थान और घड़ी मूल्यांकन के साथ एक जोड़ी को या तो विस्तारित राज्य या राज्य कहा जाता है। ध्यान दें कि शब्द अवस्था इस प्रकार अस्पष्ट है, क्योंकि, लेखक के आधार पर, इसका अर्थ या तो एक जोड़ी या एक तत्व हो सकता है। स्पष्टता के लिए, यह लेख तत्व के लिए स्थान शब्द और जोड़े के लिए विस्तारित स्थान शब्द का उपयोग करेगा। यहाँ टाइमड ऑटोमेटा और फाइनाइट ऑटोमेटा के बीच सबसे बड़ा अंतर है। एक परिमित स्वचालित में, निष्पादन के कुछ बिंदु पर, अवस्था को पूरी तरह से पढ़े गए अक्षरों की संख्या और संभावित मूल्यों की एक सीमित संख्या द्वारा वर्णित किया जाता है, जिन्हें वास्तव में "अवस्थाएँ" कहा जाता है। इसका मतलब है कि, एक अवस्था और पढ़ने के लिए शब्द के प्रत्यय को देखते हुए, शेष दौड़ पूरी तरह से निर्धारित की जाती है। इस प्रकार, "फाइनाइट ऑटोमेटा" नाम में "फाइनाइट" शब्द। हालाँकि, जैसा कि नीचे "रन" अनुभाग में समझाया गया है, फिर से शुरू करने के लिए घड़ियों का उपयोग यह निर्धारित करने के लिए किया जाता है कि कौन से संक्रमण लिए जा सकते हैं। इस प्रकार, ऑटोमेटन की स्थिति जानने के लिए, आप दोनों को पता होना चाहिए कि आप किस स्थान पर हैं, और घड़ी का मूल्यांकन। एक समयबद्ध शब्द के साथ, गैर-नकारात्मक संख्या के बढ़ते अनुक्रम और ऊपर के रूप में एक समयबद्ध स्वचालित को देखते हुए, एक रन निम्नलिखित बाधा को संतुष्ट करने वाले रूप का एक अनुक्रम हैः (आरंभीकरण) (पवित्रीकरण), सभी के लिए, रूप में एक बढ़त मौजूद है जैसे किः हम मानते हैं कि समय इकाइयाँ बीत गई हैं, और इस समय, गार्ड संतुष्ट है। आई. ई. संतुष्ट करता है, नई घड़ी का मूल्यांकन किस समय इकाइयों को पारित करता है और जिसमें घड़ियों को रीसेट किया जाता है, के अनुरूप होता है। औपचारिक रूप से। दौड़ को स्वीकार करने की धारणा को परिमित शब्दों के लिए परिमित स्वचालित रूप से और अनंत शब्दों के लिए बुची स्वचालित रूप से परिभाषित किया गया है। अर्थात्, यदि लंबाई की सीमा है, तो रन स्वीकार कर रहा है। यदि शब्द अनंत है, तो दौड़ स्वीकार करना है यदि और केवल तभी जब ऐसी अनंत संख्या में स्थिति मौजूद हो। जैसा कि परिमित और बुची ऑटोमेटन के मामले में, एक समयबद्ध ऑटोमेटन नियतात्मक या गैर-नियतात्मक हो सकता है। सहज रूप से, उन मामलों में से प्रत्येक में नियतात्मक होने का एक ही अर्थ है। इसका मतलब है कि प्रारंभ स्थानों का समूह एक सिंगलटन है, और यह कि, एक स्थिति और एक अक्षर को देखते हुए, केवल एक ही संभावित स्थिति है जिसे पढ़ने से प्राप्त किया जा सकता है। हालांकि, समयबद्ध स्वचालित के मामले में औपचारिक परिभाषा थोड़ी अधिक जटिल है। औपचारिक रूप से, एक समयबद्ध स्वचालित समय निर्धारक होता है यदिः प्रत्येक जोड़ी संक्रमणों के लिए एक एकल टन होता है और, संतुष्ट करने वाले घड़ियों के मूल्यांकन का सेट, संतोषजनक घड़ियों के मूल्यांकन के सेट से अलग होता है। समापन गुण गैर-निर्धारक समयबद्ध स्वचालित द्वारा मान्यता प्राप्त भाषाओं का वर्ग हैः संघ के तहत बंद, वास्तव में, दो समयबद्ध स्वचालित का असंबद्ध संघ उन स्वचालित द्वारा मान्यता प्राप्त भाषा के संघ को पहचानता है। चौराहे के नीचे बंद। पूरक के तहत बंद नहीं। समस्याएं और उनकी जटिलता समयबद्ध स्वचालित से संबंधित कुछ समस्याओं की कम्प्यूटेशनल जटिलता अब दी गई है। समयबद्ध स्वचालित के लिए खालीपन की समस्या को एक क्षेत्र स्वचालित का निर्माण करके और यह जांचकर हल किया जा सकता है कि क्या यह खाली भाषा को स्वीकार करता है। यह समस्या PSPACE-पूर्ण है। गैर-निर्धारक समयबद्ध स्वचालित की सार्वभौमिकता समस्या अनिश्चित है, और अधिक सटीक रूप से Π है। हालाँकि, जब ऑटोमेटन में एक ही घड़ी होती है, तो गुण निर्णायक होता है; हालाँकि, यह आदिम पुनरावर्ती नहीं है। इस समस्या में यह तय करना शामिल है कि क्या प्रत्येक शब्द को एक समयबद्ध स्वचालित द्वारा स्वीकार किया जाता है। वैकल्पिक समयबद्ध ऑटोमेटनः सार्वभौमिक परिवर्तनों के साथ समयबद्ध ऑटोमेटन का एक विस्तार भी देखें। नोट्स ऑटोमेटा (गणना)