Well-structured transition system
ಗಣಕಯಂತ್ರ ವಿಜ್ಞಾನದಲ್ಲಿ, ನಿರ್ದಿಷ್ಟವಾಗಿ ಔಪಚಾರಿಕ ಪರಿಶೀಲನೆಯ ಕ್ಷೇತ್ರದಲ್ಲಿ, ಸುಸಂಘಟಿತ ಪರಿವರ್ತನಾ ವ್ಯವಸ್ಥೆಗಳು (ಡಬ್ಲ್ಯು. ಎಸ್. ಟಿ. ಎಸ್. ಗಳು) ಅನಂತ ಸ್ಥಿತಿ ವ್ಯವಸ್ಥೆಗಳ ಸಾಮಾನ್ಯ ವರ್ಗವಾಗಿದ್ದು, ಇದಕ್ಕಾಗಿ ಅನೇಕ ಪರಿಶೀಲನಾ ಸಮಸ್ಯೆಗಳು ನಿರ್ಣಾಯಕವಾಗಿವೆ, ಏಕೆಂದರೆ ವ್ಯವಸ್ಥೆಯ ಸ್ಥಿತಿಗಳ ನಡುವೆ ಒಂದು ರೀತಿಯ ಕ್ರಮವು ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ. ಡಬ್ಲ್ಯುಎಸ್ಟಿಎಸ್ ನಿರ್ಣಾಯಕ ಫಲಿತಾಂಶಗಳನ್ನು ಪೆಟ್ರಿ ನೆಟ್ಗಳು, ಲಾಸಿ ಚಾನೆಲ್ ವ್ಯವಸ್ಥೆಗಳು ಮತ್ತು ಹೆಚ್ಚಿನವುಗಳಿಗೆ ಅನ್ವಯಿಸಬಹುದು. ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯಾನ ಒಂದು ಗುಂಪಿನ ಮೇಲೆ ಚೆನ್ನಾಗಿ-ಅರ್ಧ-ಆದೇಶವು ಒಂದು ಅರೆ-ಆದೇಶವಾಗಿದೆ (ಅಂದರೆ, ಪೂರ್ವ-ಆದೇಶ ಅಥವಾ ಪ್ರತಿಫಲಿತ, ಪರಿವರ್ತನಶೀಲ ಅವಳಿ ಸಂಬಂಧ) ಎಂದರೆ ಯಾವುದೇ ಅನಂತ ಅಂಶಗಳ ಅನುಕ್ರಮವು ಹೆಚ್ಚುತ್ತಿರುವ ಜೋಡಿಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಸೆಟ್ ಅನ್ನು ಚೆನ್ನಾಗಿ-ಅರ್ಧ-ಆದೇಶಿಸಲಾಗಿದೆ, ಅಥವಾ ಶೀಘ್ರದಲ್ಲೇ ಡಬ್ಲ್ಯೂಕ್ಯೂಒ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ. ನಮ್ಮ ಉದ್ದೇಶಗಳಿಗಾಗಿ, ಪರಿವರ್ತನೆಯ ವ್ಯವಸ್ಥೆಯು ಒಂದು ರಚನೆಯಾಗಿದೆ, ಅಲ್ಲಿ ಯಾವುದೇ ಸೆಟ್ (ಅದರ ಅಂಶಗಳನ್ನು ಸ್ಥಿತಿಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ), ಮತ್ತು (ಅದರ ಅಂಶಗಳನ್ನು ಪರಿವರ್ತನೆಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ). ಸಾಮಾನ್ಯವಾಗಿ ಪರಿವರ್ತನಾ ವ್ಯವಸ್ಥೆಯು ಆರಂಭಿಕ ಸ್ಥಿತಿಗಳು, ಪರಿವರ್ತನೆಗಳ ಮೇಲಿನ ಗುರುತುಗಳು, ಸ್ವೀಕರಿಸುವ ಸ್ಥಿತಿಗಳು ಮುಂತಾದ ಹೆಚ್ಚುವರಿ ರಚನೆಯನ್ನು ಹೊಂದಿರಬಹುದು. (ಚುಕ್ಕೆಗಳಿಂದ ಸೂಚಿಸಲಾಗಿದೆ), ಆದರೆ ಅವು ಇಲ್ಲಿ ನಮಗೆ ಸಂಬಂಧಿಸಿಲ್ಲ. ಉತ್ತಮವಾಗಿ ರಚಿಸಲಾದ ಪರಿವರ್ತನೆಯ ವ್ಯವಸ್ಥೆಯು ಪರಿವರ್ತನೆಯ ವ್ಯವಸ್ಥೆಯನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಇದು ಸ್ಥಿತಿಗಳ ಗುಂಪಿನ ಮೇಲೆ ಉತ್ತಮ-ಅರ್ಧ-ಕ್ರಮವಾಗಿದೆ. ಇದು ಮೇಲ್ಮುಖವಾಗಿ ಹೊಂದಿಕೊಳ್ಳುತ್ತದೆಃ ಅಂದರೆ, ಎಲ್ಲಾ ಪರಿವರ್ತನೆಗಳಿಗೆ (ಇದರ ಮೂಲಕ ನಾವು ಅರ್ಥೈಸುತ್ತೇವೆ) ಮತ್ತು ಅಂತಹ ಎಲ್ಲದಕ್ಕೂ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ (ಅಂದರೆ, ಶೂನ್ಯ ಅಥವಾ ಹೆಚ್ಚಿನ ಪರಿವರ್ತನೆಗಳ ಅನುಕ್ರಮದಿಂದ ತಲುಪಬಹುದು) ಮತ್ತು. ಸುಸಂಘಟಿತ ವ್ಯವಸ್ಥೆಗಳು ಒಂದು ಸುಸಂಘಟಿತ ವ್ಯವಸ್ಥೆಯು ಒಂದು ಸೀಮಿತ ನಿಯಂತ್ರಣ ಸ್ಥಿತಿಯ ಸೆಟ್ನಿಂದ ಮಾಡಲ್ಪಟ್ಟ ಸ್ಥಿತಿ ಸೆಟ್ನೊಂದಿಗೆ ಪರಿವರ್ತನೆಯ ವ್ಯವಸ್ಥೆಯಾಗಿದೆ, ಒಂದು ದತ್ತಾಂಶ ಮೌಲ್ಯಗಳ ಸೆಟ್, ಇದು ನಿರ್ಣಾಯಕ ಪೂರ್ವ-ಆದೇಶದೊಂದಿಗೆ ಒದಗಿಸಲ್ಪಟ್ಟಿದೆ, ಇದನ್ನು ರಾಜ್ಯಗಳಿಗೆ ವಿಸ್ತರಿಸಲಾಗುತ್ತದೆ, ಇದು ಮೇಲೆ ವ್ಯಾಖ್ಯಾನಿಸಿದಂತೆ ಉತ್ತಮವಾಗಿ ರಚನೆಯಾಗಿದೆ (ಏಕತಾನತೆಯಿಂದ ಕೂಡಿದೆ, ಅಂದರೆ. ಮೇಲ್ಮುಖವಾಗಿ ಹೊಂದಿಕೊಳ್ಳುತ್ತದೆ, ಸಂಬಂಧಿಸಿದಂತೆ) ಮತ್ತು ಹೆಚ್ಚುವರಿಯಾಗಿ ಯಾವುದೇ ಮೇಲ್ಮುಖವಾಗಿ ಮುಚ್ಚಿದ ಉಪಗುಂಪಿನ ಪೂರ್ವವರ್ತಿಗಳ ಗುಂಪಿಗೆ ಗಣಿಸಬಹುದಾದ ಮಿನಿಮಾವನ್ನು ಹೊಂದಿದೆ. ಸುಸಂಘಟಿತ ವ್ಯವಸ್ಥೆಗಳು ಗಣಕಯಂತ್ರ ವಿಜ್ಞಾನದಲ್ಲಿ ಎದುರಾಗುವ ಕೆಲವು ವರ್ಗಗಳ ವ್ಯವಸ್ಥೆಗಳನ್ನು ರೂಪಿಸಲು ಸುಸಂಘಟಿತ ಪರಿವರ್ತನಾ ವ್ಯವಸ್ಥೆಗಳ ಸಿದ್ಧಾಂತವನ್ನು ಅಳವಡಿಸಿಕೊಳ್ಳುತ್ತವೆ ಮತ್ತು ಅಂತಹ ವ್ಯವಸ್ಥೆಗಳನ್ನು ವಿಶ್ಲೇಷಿಸಲು ನಿರ್ಧಾರದ ಕಾರ್ಯವಿಧಾನಗಳಿಗೆ ಆಧಾರವನ್ನು ಒದಗಿಸುತ್ತವೆ, ಆದ್ದರಿಂದ ಪೂರಕ ಅವಶ್ಯಕತೆಗಳುಃ ಡಬ್ಲ್ಯುಎಸ್ಟಿಎಸ್ನ ವ್ಯಾಖ್ಯಾನವು ಸ್ವತಃ ಸಂಬಂಧಗಳ ಗಣನೆಯ ಬಗ್ಗೆ ಏನನ್ನೂ ಹೇಳುವುದಿಲ್ಲ. ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿನ ಉಪಯೋಗಗಳು ಯಾವುದೇ ಸುಸಂಘಟಿತ ವ್ಯವಸ್ಥೆಗೆ ಸುಸಂಘಟಿತ ವ್ಯವಸ್ಥೆಗಳ ವ್ಯಾಪ್ತಿಯನ್ನು ನಿರ್ಧರಿಸಬಹುದು, ಮತ್ತು ಆದ್ದರಿಂದ ಅಬ್ದುಲ್ಲಾ ಮತ್ತು ಇತರರ ಹಿಂದುಳಿದ ಕ್ರಮಾವಳಿಯಿಂದ ನಿರ್ದಿಷ್ಟ ನಿಯಂತ್ರಣ ಸ್ಥಿತಿಯನ್ನು ತಲುಪಬಹುದು. ಅಥವಾ ಸುಸಂಘಟಿತ ವ್ಯವಸ್ಥೆಗಳ ನಿರ್ದಿಷ್ಟ ಉಪವರ್ಗಗಳಿಗೆ (ಕಟ್ಟುನಿಟ್ಟಾದ ಏಕತಾನತೆಗೆ ಒಳಪಟ್ಟು, ಉದಾಹರಣೆಗೆ. ಮಿತಿಯಿಲ್ಲದ ಪೆಟ್ರಿ ಬಲೆಗಳ ಸಂದರ್ಭದಲ್ಲಿ) ಕಾರ್ಪ್-ಮಿಲ್ಲರ್ ವ್ಯಾಪ್ತಿ ರೇಖಾಚಿತ್ರದ ಆಧಾರದ ಮೇಲೆ ಮುಂದಕ್ಕೆ ವಿಶ್ಲೇಷಣೆ. ಹಿಂದುಳಿದ ಅಲ್ಗಾರಿದಮ್ ಹಿಂದುಳಿದ ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನ ಪ್ರಶ್ನೆಗೆ ಉತ್ತರಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆಃ ಉತ್ತಮವಾಗಿ ರಚಿಸಲಾದ ವ್ಯವಸ್ಥೆ ಮತ್ತು ಸ್ಥಿತಿಯನ್ನು ನೀಡಿದರೆ, ನಿರ್ದಿಷ್ಟ ಆರಂಭಿಕ ಸ್ಥಿತಿಯಿಂದ ರಾಜ್ಯಕ್ಕೆ ಹೋಗುವ ಯಾವುದೇ ಪರಿವರ್ತನೆಯ ಮಾರ್ಗವಿದೆಯೇ (ಅಂತಹ ಸ್ಥಿತಿಯನ್ನು ಒಳಗೊಳ್ಳುತ್ತದೆ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ)? ಈ ಪ್ರಶ್ನೆಗೆ ಒಂದು ಅಂತರ್ಬೋಧೆಯ ವಿವರಣೆಯೆಂದರೆಃ ದೋಷ ಸ್ಥಿತಿಯನ್ನು ಪ್ರತಿನಿಧಿಸಿದರೆ, ಅದನ್ನು ಹೊಂದಿರುವ ಯಾವುದೇ ಸ್ಥಿತಿಯನ್ನು ದೋಷ ಸ್ಥಿತಿಯೆಂದು ಪರಿಗಣಿಸಬೇಕು. ರಾಜ್ಯಗಳ ಈ "ನಿಯಂತ್ರಣ" ದ ಮಾದರಿಗಳು ಮತ್ತು ಪರಿವರ್ತನೆಯ ಸಂಬಂಧಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ ಏಕತಾನತೆಯ ಅಗತ್ಯವನ್ನು ಪೂರೈಸುವ ಉತ್ತಮ-ಅರ್ಧ-ಕ್ರಮವನ್ನು ಕಂಡುಕೊಂಡರೆ, ಈ ಪ್ರಶ್ನೆಗೆ ಉತ್ತರಿಸಬಹುದು. ಒಂದು ಕನಿಷ್ಠ ದೋಷ ಸ್ಥಿತಿಯ ಬದಲಿಗೆ, ಸಾಮಾನ್ಯವಾಗಿ ಮೇಲ್ಮುಖವಾಗಿ ಮುಚ್ಚಿದ ದೋಷ ಸ್ಥಿತಿಗಳನ್ನು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಉತ್ತಮ-ಅರ್ಧ-ಕ್ರಮದಲ್ಲಿ, ಯಾವುದೇ ಮೇಲ್ಮುಖವಾಗಿ ಮುಚ್ಚಿದ ಸೆಟ್ ಮಿನಿಮಾದ ಸೀಮಿತ ಗುಂಪನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ಮೇಲ್ಮುಖವಾಗಿ ಮುಚ್ಚಿದ ಉಪಗುಂಪುಗಳ ಯಾವುದೇ ಅನುಕ್ರಮವು ಸೀಮಿತವಾದ ಅನೇಕ ಹಂತಗಳ ನಂತರ ಒಮ್ಮುಖಗೊಳ್ಳುತ್ತದೆ (1). ಅಲ್ಗಾರಿದಮ್ ಮೆಮೊರಿಯಲ್ಲಿ ಮೇಲ್ಮುಖವಾಗಿ ಮುಚ್ಚಿದ ಸ್ಥಿತಿಗಳ ಗುಂಪನ್ನು ಸಂಗ್ರಹಿಸುವ ಅಗತ್ಯವಿದೆ, ಏಕೆಂದರೆ ಮೇಲ್ಮುಖವಾಗಿ ಮುಚ್ಚಿದ ಸೆಟ್ ಅನ್ನು ಮಿನಿಮಾದ ಸೀಮಿತ ಗುಂಪಾಗಿ ಪ್ರತಿನಿಧಿಸಬಹುದು. ಇದು ದೋಷ ಸ್ಥಿತಿಗಳ ಗುಂಪಿನ ಮೇಲ್ಮುಖ ಮುಚ್ಚುವಿಕೆಯಿಂದ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ ತಕ್ಷಣದ ಪೂರ್ವವರ್ತಿಗಳ ಗುಂಪನ್ನು (ಏಕತಾನತೆಯ ಮೂಲಕವೂ ಮೇಲ್ಮುಖವಾಗಿ ಮುಚ್ಚಲಾಗುತ್ತದೆ) ಲೆಕ್ಕ ಹಾಕುತ್ತದೆ ಮತ್ತು ಅದನ್ನು ಗುಂಪಿಗೆ ಸೇರಿಸುತ್ತದೆ. ಈ ಪುನರಾವರ್ತನೆಯು ಸೀಮಿತ ಸಂಖ್ಯೆಯ ಹಂತಗಳ ನಂತರ ಕೊನೆಗೊಳ್ಳುತ್ತದೆ, ಏಕೆಂದರೆ ಉತ್ತಮ-ಅರ್ಧ-ಆದೇಶಗಳ ಗುಣಲಕ್ಷಣ (1). ಅಂತಿಮವಾಗಿ ಪಡೆದ ಸೆಟ್ನಲ್ಲಿದ್ದರೆ, ಔಟ್ಪುಟ್ "ಹೌದು" (ಸ್ಥಿತಿಯನ್ನು ತಲುಪಬಹುದು), ಇಲ್ಲದಿದ್ದರೆ ಅದು "ಇಲ್ಲ" (ಅಂತಹ ಸ್ಥಿತಿಯನ್ನು ತಲುಪಲು ಸಾಧ್ಯವಿಲ್ಲ). ಉಲ್ಲೇಖಗಳು ಸುಸ್ಥಾಪಿತತೆ ಆಟೋಮ್ಯಾಟಾ (ಗಣನೆ)