Well-structured transition system
કોમ્પ્યુટર વિજ્ઞાનમાં, ખાસ કરીને ઔપચારિક ચકાસણીના ક્ષેત્રમાં, સારી રીતે સંરચિત સંક્રમણ પ્રણાલીઓ (ડબલ્યુએસટીએસ) એ અનંત સ્થિતિ પ્રણાલીઓનો એક સામાન્ય વર્ગ છે, જેના માટે પ્રણાલીની સ્થિતિઓ વચ્ચે એક પ્રકારનો ક્રમ અસ્તિત્વમાં હોવાને કારણે ઘણી ચકાસણી સમસ્યાઓ નિર્ણાયક છે, જે પ્રણાલીના સંક્રમણ સાથે સુસંગત છે. ડબલ્યુ. એસ. ટી. એસ. નિર્ણાયકતાના પરિણામો પેટ્રી નેટ, લોસી ચેનલ સિસ્ટમ્સ અને વધુ પર લાગુ કરી શકાય છે. ઔપચારિક વ્યાખ્યા યાદ રાખો કે સમૂહ પર સારી રીતે-અર્ધ-ક્રમ એ અર્ધ-ક્રમ છે (એટલે કે, પૂર્વ ક્રમ અથવા પ્રતિબિંબીત, સંક્રમક દ્વિસંગી સંબંધ) જેમ કે તત્વોનો કોઈપણ અનંત ક્રમ, સાથે વધતી જોડી ધરાવે છે. આ સેટ સારી રીતે-અર્ધ-ઓર્ડર કરેલો અથવા ટૂંક સમયમાં WQO હોવાનું કહેવાય છે. આપણા હેતુઓ માટે, સંક્રમણ પ્રણાલી એ એક માળખું છે, જ્યાં કોઈપણ સમૂહ (તેના તત્વોને અવસ્થાઓ કહેવામાં આવે છે), અને (તેના તત્વોને સંક્રમણ કહેવામાં આવે છે). સામાન્ય રીતે સંક્રમણ પ્રણાલીમાં પ્રારંભિક સ્થિતિઓ, સંક્રમણ પરના લેબલ, સ્વીકાર કરતી સ્થિતિઓ વગેરે જેવી વધારાની રચના હોઈ શકે છે. (બિંદુઓ દ્વારા સૂચવવામાં આવ્યું છે), પરંતુ તેઓ અહીં આપણી ચિંતા કરતા નથી. સારી રીતે સંરચિત સંક્રમણ પ્રણાલીમાં સંક્રમણ પ્રણાલીનો સમાવેશ થાય છે, જે સ્થિતિઓના સમૂહ પર સારી રીતે અર્ધ-ક્રમબદ્ધ હોય છે. સાથે ઉપરની તરફ સુસંગત છેઃ એટલે કે, તમામ સંક્રમણો માટે (આ દ્વારા અમારો અર્થ છે) અને એવા બધા માટે કે જે અસ્તિત્વમાં છે (એટલે કે, શૂન્ય અથવા વધુ સંક્રમણોના ક્રમ દ્વારા પહોંચી શકાય છે) અને. સારી રીતે સંરચિત પ્રણાલીઓ એક સારી રીતે સંરચિત પ્રણાલી એ એક સંક્રમણ પ્રણાલી છે જેમાં મર્યાદિત નિયંત્રણ સ્થિતિ સમૂહથી બનેલી સ્થિતિ સમૂહ હોય છે, એક ડેટા મૂલ્યો સમૂહ, જે નિર્ણાયક પૂર્વ-ક્રમથી સજ્જ હોય છે, જે રાજ્યો સુધી વિસ્તૃત હોય છે, જે ઉપર વ્યાખ્યાયિત કર્યા મુજબ સારી રીતે સંરચિત હોય છે (એકવિધ છે, એટલે કે. ઉપર તરફ સુસંગત, ના સંદર્ભમાં) અને વધુમાં કોઈપણ ઉપર તરફના બંધ ઉપગણના પૂર્વગામીઓના સમૂહ માટે મિનિમાનો ગણતરીપાત્ર સમૂહ છે. સારી રીતે સંરચિત પ્રણાલીઓ કોમ્પ્યુટર વિજ્ઞાનમાં આવતી પ્રણાલીઓના ચોક્કસ વર્ગોના મોડેલિંગ માટે સારી રીતે સંરચિત સંક્રમણ પ્રણાલીઓના સિદ્ધાંતને અપનાવે છે અને આવી પ્રણાલીઓનું વિશ્લેષણ કરવા માટે નિર્ણય પ્રક્રિયાઓ માટેનો આધાર પૂરો પાડે છે, તેથી પૂરક જરૂરિયાતોઃ ડબલ્યુએસટીએસની વ્યાખ્યા પોતે સંબંધોની ગણતરીક્ષમતા વિશે કશું કહેતી નથી. કોમ્પ્યુટર વિજ્ઞાનમાં ઉપયોગો કોઈપણ સુવ્યવસ્થિત પ્રણાલી માટે સારી રીતે સંરચિત પ્રણાલીઓની વ્યાપકતા નક્કી કરી શકાય છે, અને તેથી અબ્દુલ્લા એટ અલના પછાત અલ્ગોરિધમ દ્વારા આપેલ નિયંત્રણ સ્થિતિની સુલભતા નક્કી કરી શકાય છે. અથવા સારી રીતે સંરચિત પ્રણાલીઓના ચોક્કસ પેટા વર્ગો માટે (કડક એકવિધતાને આધિન, દા. ત. અમર્યાદિત પેટ્રી જાળીના કિસ્સામાં) કાર્પ-મિલર આવરણક્ષમતા આલેખ પર આધારિત આગળના વિશ્લેષણ દ્વારા. પછાત અલ્ગોરિધમ પછાત અલ્ગોરિધમ નીચેના પ્રશ્નનો જવાબ આપવાની મંજૂરી આપે છેઃ સારી રીતે રચાયેલી પ્રણાલી અને સ્થિતિને જોતાં, શું કોઈ સંક્રમણ માર્ગ છે જે આપેલ પ્રારંભિક સ્થિતિથી રાજ્યમાં દોરી જાય છે (આવી સ્થિતિ આવરી લે છે તેવું કહેવાય છે)? આ પ્રશ્ન માટે એક સાહજિક સમજૂતી છેઃ જો કોઈ ભૂલની સ્થિતિ રજૂ કરે છે, તો તે ધરાવતી કોઈપણ સ્થિતિને પણ ભૂલની સ્થિતિ તરીકે ગણવી જોઈએ. જો એક સારી-અર્ધ-ક્રમ મળી શકે કે જે રાજ્યોના આ "નિયંત્રણ" નું મોડેલ બનાવે છે અને જે સંક્રમણ સંબંધના સંદર્ભમાં એકવિધતાની જરૂરિયાતને પણ પૂર્ણ કરે છે, તો આ પ્રશ્નનો જવાબ આપી શકાય છે. એક ન્યૂનતમ ભૂલ સ્થિતિને બદલે, એક સામાન્ય રીતે ભૂલ સ્થિતિઓના ઉપર તરફના બંધ સમૂહને ધ્યાનમાં લે છે. અલ્ગોરિધમ એ હકીકતો પર આધારિત છે કે સારી રીતે અર્ધ-ક્રમમાં, કોઈપણ ઉપર તરફના બંધ સમૂહમાં મિનિમાનો મર્યાદિત સમૂહ હોય છે, અને ઉપર તરફના બંધ ઉપગણોનો કોઈપણ ક્રમ મર્યાદિત રીતે ઘણા પગલાંઓ (1) પછી એકરૂપ થાય છે. અલ્ગોરિધમને મેમરીમાં સ્થિતિઓના ઉપર તરફના બંધ સમૂહને સંગ્રહિત કરવાની જરૂર છે, જે તે કરી શકે છે કારણ કે ઉપર તરફના બંધ સમૂહને મિનિમાના મર્યાદિત સમૂહ તરીકે રજૂ કરી શકાય છે. તે ભૂલ સ્થિતિઓના સમૂહના ઉપર તરફના બંધથી શરૂ થાય છે અને દરેક પુનરાવર્તન પર તાત્કાલિક પૂર્વગામીઓના સમૂહ (એકવિધતા દ્વારા પણ ઉપર તરફના બંધ) ની ગણતરી કરે છે અને તેને સમૂહમાં ઉમેરે છે. આ પુનરાવર્તન સારી-અર્ધ-ઓર્ડરના ગુણધર્મ (1) ને કારણે મર્યાદિત સંખ્યામાં પગલાં પછી સમાપ્ત થાય છે. જો આખરે મેળવેલા સમૂહમાં હોય, તો આઉટપુટ "હા" છે (એક સ્થિતિ સુધી પહોંચી શકાય છે), અન્યથા તે "ના" છે (આવી સ્થિતિ સુધી પહોંચવું શક્ય નથી). સંદર્ભો વેલફાઉન્ડનેસ ઓટોમેટા (ગણતરી)