Well-structured transition system
கணினி அறிவியலில், குறிப்பாக முறையான சரிபார்ப்பு துறையில், நன்கு கட்டமைக்கப்பட்ட மாற்றம் அமைப்புகள் (டபிள்யூஎஸ்டிஎஸ்) என்பது எல்லையற்ற நிலை அமைப்புகளின் ஒரு பொதுவான வகுப்பாகும், இதற்காக பல சரிபார்ப்பு சிக்கல்கள் தீர்மானிக்கக்கூடியவை, ஏனெனில் அமைப்பின் நிலைகளுக்கு இடையில் ஒரு வகையான வரிசை இருப்பதால் இது அமைப்பின் மாற்றங்களுடன் இணக்கமாக உள்ளது. WSTS தீர்மானகரமான முடிவுகளை பெட்ரி வலைகள், இழப்பு சேனல் அமைப்புகள் மற்றும் பலவற்றிற்கு பயன்படுத்தலாம். முறையான வரையறை ஒரு தொகுப்பில் ஒரு நன்கு-அரை-வரிசைப்படுத்தல் என்பது ஒரு அரை-வரிசைப்படுத்தல் (அதாவது, ஒரு முன்கூட்டிய வரிசை அல்லது பிரதிபலிப்பு, இடைநிலை பைனரி உறவு) என்று நினைவில் கொள்ளுங்கள், அதாவது எந்த எல்லையற்ற உறுப்புகளின் வரிசையும், பெருகிவரும் ஜோடியைக் கொண்டுள்ளது. செட் நன்கு-அரை-ஆர்டர் செய்யப்பட்டதாக அல்லது விரைவில் WQO என்று கூறப்படுகிறது. நமது நோக்கங்களுக்காக, ஒரு மாற்றம் அமைப்பு என்பது ஒரு அமைப்பு, அங்கு எந்த தொகுப்பும் (அதன் கூறுகள் நிலைகள் என்று அழைக்கப்படுகின்றன), மற்றும் (அதன் கூறுகள் மாற்றங்கள் என்று அழைக்கப்படுகின்றன). பொதுவாக ஒரு மாற்றம் அமைப்பு ஆரம்ப நிலைகள், மாற்றங்கள் குறித்த லேபிள்கள், நிலைகளை ஏற்றுக்கொள்வது போன்ற கூடுதல் கட்டமைப்பைக் கொண்டிருக்கலாம். (புள்ளிகளால் சுட்டிக்காட்டப்படுகிறது), ஆனால் அவை இங்கே எங்களைப் பற்றி கவலைப்படுவதில்லை. ஒரு நன்கு கட்டமைக்கப்பட்ட மாற்றம் அமைப்பு ஒரு மாற்றம் அமைப்பைக் கொண்டுள்ளது, இது நிலைகளின் தொகுப்பில் நன்கு அரை-வரிசைப்படுத்துவதாகும். இது மேல்நோக்கி இணக்கமானதுஃ அதாவது, அனைத்து மாற்றங்களுக்கும் (இதன் மூலம் நாம் அர்த்தப்படுத்துகிறோம்) மற்றும் அத்தகைய அனைத்திற்கும், (அதாவது, பூஜ்ஜியம் அல்லது அதற்கு மேற்பட்ட மாற்றங்களின் வரிசையால் அடைய முடியும்) மற்றும். நன்கு கட்டமைக்கப்பட்ட அமைப்புகள் ஒரு நன்கு கட்டமைக்கப்பட்ட அமைப்பு என்பது ஒரு வரையறுக்கப்பட்ட கட்டுப்பாட்டு நிலை தொகுப்பிலிருந்து உருவாக்கப்பட்ட நிலை அமைப்பைக் கொண்ட ஒரு மாற்றம் அமைப்பாகும், இது ஒரு தரவு மதிப்புகள் தொகுப்பாகும், இது ஒரு தீர்மானிக்கக்கூடிய முன்-வரிசையுடன் வழங்கப்படுகிறது, இது மாநிலங்களுக்கு நீட்டிக்கப்படுகிறது, இது மேலே வரையறுக்கப்பட்டுள்ளபடி நன்கு கட்டமைக்கப்பட்டுள்ளது (மோனோடோனிக், அதாவது. மேல்நோக்கி இணக்கமானது) மற்றும் கூடுதலாக எந்தவொரு மேல்நோக்கிய மூடிய துணைக்குழுவின் முன்னோடிகளின் தொகுப்பிற்கான கணக்கிடக்கூடிய மினிமாவின் தொகுப்பைக் கொண்டுள்ளது. நன்கு கட்டமைக்கப்பட்ட அமைப்புகள் கணினி அறிவியலில் எதிர்கொள்ளும் சில வகை அமைப்புகளை மாதிரியாக்குவதற்கு நன்கு கட்டமைக்கப்பட்ட மாற்றம் அமைப்புகளின் கோட்பாட்டை மாற்றியமைக்கின்றன, மேலும் அத்தகைய அமைப்புகளை பகுப்பாய்வு செய்வதற்கான முடிவு நடைமுறைகளுக்கு அடிப்படையை வழங்குகின்றன, எனவே துணைத் தேவைகள்ஃ ஒரு WSTS இன் வரையறை உறவுகளின் கணக்கீடு பற்றி எதுவும் சொல்லவில்லை. கணினி அறிவியலில் பயன்பாடுகள் நன்கு கட்டமைக்கப்பட்ட எந்தவொரு அமைப்புக்கும் நன்கு கட்டமைக்கப்பட்ட அமைப்புகளின் பாதுகாப்பை தீர்மானிக்க முடியும், எனவே அப்துல்லா மற்றும் பிறரின் பின்தங்கிய வழிமுறையால் கொடுக்கப்பட்ட கட்டுப்பாட்டு நிலையை அடைய முடியும். அல்லது நன்கு கட்டமைக்கப்பட்ட அமைப்புகளின் குறிப்பிட்ட துணைப்பிரிவுகளுக்கு (கடுமையான மோனோடோனிசிட்டிக்கு உட்பட்டு, எ. கா. வரம்பற்ற பெட்ரி வலைகளின் விஷயத்தில்) ஒரு கார்ப்-மில்லர் கவர் செய்யக்கூடிய வரைபடத்தின் அடிப்படையில் ஒரு முன்னோக்கி பகுப்பாய்வு மூலம். பின்தங்கிய வழிமுறை பின்வரும் கேள்விக்கு பதிலளிக்க பின்தங்கிய வழிமுறை அனுமதிக்கிறதுஃ நன்கு கட்டமைக்கப்பட்ட அமைப்பு மற்றும் ஒரு நிலை கொடுக்கப்பட்டால், கொடுக்கப்பட்ட தொடக்க நிலையில் இருந்து ஒரு நிலைக்கு வழிவகுக்கும் ஏதேனும் மாற்றம் பாதை உள்ளதா (அத்தகைய நிலை உள்ளடக்கியது என்று கூறப்படுகிறது)? இந்தக் கேள்விக்கான ஒரு உள்ளுணர்வு விளக்கம்ஃ ஒரு பிழை நிலையைக் குறிக்கிறது என்றால், அதைக் கொண்ட எந்த நிலையும் ஒரு பிழை நிலையாகக் கருதப்பட வேண்டும். மாநிலங்களின் இந்த "கட்டுப்பாடு" மாதிரிகள் மற்றும் இடைநிலை உறவைப் பொறுத்தவரை மோனோடோனிசிட்டியின் தேவையை பூர்த்தி செய்யும் ஒரு நல்ல-அரை-வரிசையைக் கண்டறிய முடிந்தால், இந்த கேள்விக்கு பதிலளிக்க முடியும். ஒரு குறைந்தபட்ச பிழை நிலைக்கு பதிலாக, ஒருவர் பொதுவாக மேல்நோக்கி மூடிய பிழை நிலைகளின் தொகுப்பைக் கருதுகிறார். இந்த வழிமுறை நன்கு அரை வரிசையில், எந்த மேல்நோக்கிய மூடிய தொகுப்பும் ஒரு வரையறுக்கப்பட்ட மினிமாவைக் கொண்டுள்ளது என்ற உண்மைகளை அடிப்படையாகக் கொண்டது, மேலும் மேல்நோக்கிய மூடிய துணைக்குழுக்களின் எந்தவொரு வரிசையும் இறுதியாக பல படிகளுக்குப் பிறகு இணைகிறது (1). அல்காரிதம் நினைவகத்தில் மேல்நோக்கி மூடிய நிலைகளின் தொகுப்பை சேமிக்க வேண்டும், ஏனெனில் மேல்நோக்கி மூடிய தொகுப்பு மினிமாவின் வரையறுக்கப்பட்ட தொகுப்பாக குறிப்பிடப்படுகிறது. இது பிழை நிலைகளின் தொகுப்பின் மேல்நோக்கிய மூடுதலில் இருந்து தொடங்கி, ஒவ்வொரு மறு செய்கையிலும் உடனடி முன்னோடிகளின் தொகுப்பை (மோனோடோனிசிட்டி மூலம் மேல்நோக்கி மூடப்படுகிறது) கணக்கிடுகிறது மற்றும் அதை தொகுப்பில் சேர்க்கிறது. நன்கு-அரை-ஆர்டர்களின் பண்பு (1) காரணமாக, இந்த மறு செய்கை ஒரு வரையறுக்கப்பட்ட எண்ணிக்கையிலான படிகளுக்குப் பிறகு முடிவடைகிறது. இறுதியாக பெறப்பட்ட தொகுப்பில் இருந்தால், வெளியீடு "ஆம்" (ஒரு நிலையை அடைய முடியும்), இல்லையெனில் அது "இல்லை" (அத்தகைய நிலையை அடைய முடியாது). குறிப்புகள் நன்கு நிறுவப்பட்ட தானியங்கி (கணக்கீடு)