Input/output automaton
ઇનપુટ/આઉટપુટ ઓટોમેટા એક ઔપચારિક મોડેલ પ્રદાન કરે છે, જે અસિંક્રોનસ સહવર્તી પ્રણાલીના મોટાભાગના પ્રકારોનું વર્ણન કરવા માટે લાગુ પડે છે. તેના પોતાના પર, I/O ઓટોમેટન મોડેલમાં ખૂબ જ મૂળભૂત માળખું છે જે તેને વિવિધ પ્રકારની વિતરિત સિસ્ટમોનું મોડેલ બનાવવા માટે સક્ષમ બનાવે છે. અસિંક્રોનસ પ્રણાલીઓના ચોક્કસ પ્રકારોનું વર્ણન કરવા માટે, આ મૂળભૂત મોડેલમાં વધારાની રચના ઉમેરવી આવશ્યક છે. આ મોડેલ પ્રક્રિયાઓ અને સંદેશ ચેનલો જેવા સિસ્ટમ ઘટકો વિશે વર્ણન અને તર્ક માટે એક સ્પષ્ટ પદ્ધતિ રજૂ કરે છે જે એકબીજા સાથે ક્રિયાપ્રતિક્રિયા કરે છે, મનસ્વી સંબંધિત ઝડપે કાર્ય કરે છે. આઇ/ઓ ઓટોમેટા સૌપ્રથમ નેન્સી એ. લિન્ચ અને માર્ક આર. ટટલ દ્વારા "વિતરિત અલ્ગોરિધમ્સ માટે શ્રેણીબદ્ધ શુદ્ધતા પુરાવા", 1987 માં રજૂ કરવામાં આવ્યા હતા. I/O ઓટોમેટન એક વિતરિત સિસ્ટમ ઘટકનું મોડેલ બનાવે છે જે અન્ય સિસ્ટમ ઘટકો સાથે ક્રિયાપ્રતિક્રિયા કરી શકે છે. તે એક સરળ પ્રકારનું સ્ટેટ મશીન છે જેમાં સંક્રમણો નામવાળી ક્રિયાઓ સાથે સંકળાયેલા છે. ત્રણ પ્રકારની ક્રિયાઓ છેઃ ઇનપુટ, આઉટપુટ અને આંતરિક ક્રિયાઓ. ઓટોમેટન તેના પર્યાવરણ સાથે વાતચીત કરવા માટે તેની ઇનપુટ અને આઉટપુટ ક્રિયાઓનો ઉપયોગ કરે છે, જ્યારે આંતરિક ક્રિયાઓ માત્ર ઓટોમેટનને જ દેખાય છે. આંતરિક અને આઉટપુટ ક્રિયાઓ કે જે ઓટોમેટન દ્વારા પસંદ કરવામાં આવે છે અને હાથ ધરવામાં આવે છે તેનાથી વિપરીત, ઇનપુટ ક્રિયાઓ-જે ફક્ત પર્યાવરણમાંથી આવે છે-ઓટોમેટનના નિયંત્રણ હેઠળ નથી. ઉદાહરણો I/O ઓટોમેટાનો ઉપયોગ ડિસ્ટ્રિબ્યુટેડ સિસ્ટમના વ્યક્તિગત ઘટકોનું મોડેલ બનાવવા માટે થઈ શકે છે, જેમ કે પ્રક્રિયા, મેસેજ પાસિંગ સિસ્ટમમાં મેસેજ ચેનલ અથવા શેર્ડ મેમરી સિસ્ટમમાં શેર્ડ ડેટા સ્ટ્રક્ચર. પ્રક્રિયા I/O ઓટોમેટન આકૃતિ 1 એ એસિંક્રોનસ મેસેજ-પાસિંગ ડિસ્ટ્રિબ્યુટેડ સિસ્ટમમાં પ્રક્રિયા માટે I/O ઓટોમેટનનું ઉદાહરણ દર્શાવે છે. આ સેટિંગમાં, પ્રોસેસ પાઇ મેસેજ પાસિંગ સિસ્ટમનો ઉપયોગ કરીને અન્ય પ્રક્રિયાઓ સાથે વાતચીત કરે છે. તેની આઉટપુટ ક્રિયાઓ મોકલો (m) i, j સ્વરૂપની હોય છે, જે Pj પ્રક્રિયા કરવા માટે સામગ્રી m સાથે સંદેશ મોકલતી પ્રક્રિયા Pi નું પ્રતિનિધિત્વ કરે છે. ઇનપુટ ક્રિયાઓ ફોર્મ રિસીવ (m) k, i ની હોય છે, જે પ્રક્રિયા Pk માંથી m બાય પ્રોસેસ Pi સમાવિષ્ટો સાથે સંદેશની રસીદ રજૂ કરે છે. (પીઆઇની આંતરિક ક્રિયાઓ, જે પ્રક્રિયા ચાલી રહી છે તે અલ્ગોરિધમને અનુરૂપ હશે તે બતાવવામાં આવી નથી.) એફ. આઈ. એફ. ઓ. સંદેશ ચેનલ સંદેશ ચેનલને આઈ/ઓ ઓટોમેટન દ્વારા પણ તૈયાર કરી શકાય છે. આકૃતિ 2 સી. આઈ., જે. નામની એક લાક્ષણિક એકમુખી એફ. આઈ. એફ. ઓ. ચેનલ ઓટોમેટનને સમજાવે છે. તેમાં મોકલો (m) i, j ફોર્મની ઇનપુટ ક્રિયાઓ છે અને ફોર્મ પ્રાપ્ત કરો (m) i, j ની આઉટપુટ ક્રિયાઓ છે. દરેક સંદેશ m માં 0 અથવા 1 (m ω {0,1}) હોઈ શકે છે. ઓટોમેટનની સ્થિતિ એ તમામ સંદેશાઓની ફીફો કતારને સંગ્રહિત કરે છે જે મોકલવામાં આવ્યા છે પરંતુ હજુ સુધી પ્રાપ્ત થયા નથી. લાક્ષણિક ડિસ્ટ્રિબ્યુટેડ સિસ્ટમમાં જ્યાં પ્રોસેસ ઓટોમેટા અને કોમ્યુનિકેશન ચેનલ ઓટોમેટા બંને અસ્તિત્વ ધરાવે છે, તેઓ એવી રીતે રચાય છે કે એક ઓટોમેટનની આઉટપુટ ક્રિયાઓ અન્ય ઓટોમેટાની સમાન-નામના ઇનપુટ ક્રિયાઓ સાથે મેળ ખાય છે અને ચલાવવામાં આવે છે. ઉદાહરણ તરીકે, બે પ્રક્રિયાઓ, પી. આઈ. અને પી. જે. થી બનેલી પ્રણાલી અને પી. જે. પ્રક્રિયા કરવા માટે પ્રક્રિયા પી. આઈ. થી સંચાર ચેનલ સી. આઈ., જે. નો વિચાર કરો. આ સેટિંગમાં, પ્રક્રિયા પાઇ આઉટપુટ ક્રિયા મોકલે છે (m) i, j, જો અને માત્ર ત્યારે જ જો ચેનલ Ci, j પણ તેની મોકલે છે (m) i, j ઇનપુટ ક્રિયા ચલાવે છે. અણુ વાંચન/લેખન રજિસ્ટર આકૃતિ 3 બે પ્રક્રિયાઓ, P1 અને P2 સાથે વહેંચાયેલ મેમરી સિસ્ટમમાં અણુ વાંચન/લેખન રજિસ્ટર I/O ઓટોમેટનને સમજાવે છે. રજિસ્ટરમાં સંગ્રહિત મૂલ્ય V એ પૂર્ણાંક (V bul Z) પ્રકારનું છે. ઓટોમેટનની સ્થિતિ આ મૂલ્યને સંગ્રહિત કરે છે. ઇનપુટ ક્રિયાઓમાં લેખન (V) નો સમાવેશ થાય છે, જે રજિસ્ટરમાં મૂલ્ય V લખવાની વિનંતી કરતી પ્રક્રિયા Pi નું પ્રતિનિધિત્વ કરે છે (જ્યાં i ω {1,2} અને V ω Z), અને રીડી, જે હાલમાં રજિસ્ટરમાં સંગ્રહિત મૂલ્યને વાંચવાની વિનંતી કરતી પ્રક્રિયા Pi ને અનુરૂપ છે. આઉટપુટ ક્રિયા અકીનો ઉપયોગ પ્રક્રિયા પી. આઈ. ને જાણ કરવા માટે થાય છે કે લેખન વિનંતી સફળતાપૂર્વક પૂર્ણ થઈ છે. આઉટપુટ ક્રિયા Vi એ પ્રક્રિયા Pi દ્વારા વાંચવાની વિનંતીના પ્રતિભાવ તરીકે પરત કરવામાં આવતા મૂલ્ય V નું પ્રતિનિધિત્વ કરે છે. ઓટોમેટનમાં આંતરિક ક્રિયાઓ પણ પર્ફોર્મ _ રાઈટ (V) નો સમાવેશ થાય છે, જે રજિસ્ટરમાં V મૂલ્ય લખે છે (ઓટોમેટનની સ્થિતિને અપડેટ કરીને), અને પર્ફોર્મ _ રીડ, જેનો ઉપયોગ રાજ્યમાં સંગ્રહિત V મૂલ્યને વાંચવા માટે થાય છે. (આ આંતરિક ક્રિયાઓ આકૃતિ 3 માં દર્શાવવામાં આવી નથી.) ઔપચારિક સ્પષ્ટીકરણ I/O ઓટોમેટન A, અથવા ફક્ત ઓટોમેટન, પાંચ ઘટકોનો સમાવેશ કરે છેઃ Sig (A) જણાવે છે કે (A) પ્રારંભ (A) ટ્રાન્સ (A) કાર્યો (A) આ પાંચ ઘટકો નીચે વર્ણવેલ છે. હસ્તાક્ષર I/O ઓટોમેટન A ના ઔપચારિકરણનું પ્રારંભિક પગલું એ તેની સહી, સિગ (A) ની વ્યાખ્યા છે. સિગ્નેચર S એ I/O ઓટોમેટનની ક્રિયાઓને ક્રિયાઓના ત્રણ અલગ-અલગ સમૂહોનો ઉપયોગ કરીને વર્ણવે છેઃ in (S): ઇનપુટ ક્રિયાઓ, out (S): આઉટપુટ ક્રિયાઓ અને int (S): આંતરિક ક્રિયાઓ. ઇનપુટ, આઉટપુટ અને આંતરિક ક્રિયાઓના ઉપરોક્ત ઔપચારિકરણના આધારે, નીચેની વસ્તુઓને વ્યાખ્યાયિત કરવી શક્ય છે. ext (S): બાહ્ય ક્રિયાઓ, જેને (S) ≤ out (S) સ્થાનિક (S) માં વ્યાખ્યાયિત કરવામાં આવી છેઃ સ્થાનિક રીતે નિયંત્રિત ક્રિયાઓ, જેને (S) ≤ int (S) extsig (S) તરીકે વ્યાખ્યાયિત કરવામાં આવી છેઃ બાહ્ય હસ્તાક્ષર, જેને (S) માં, બહાર (S), ω) કૃત્યો (S) તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, તેને હસ્તાક્ષરની તમામ ક્રિયાઓના સમૂહ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. આ મર્યાદિત ઓટોમેટાની સામાન્ય કલ્પનાનું નોંધપાત્ર સામાન્યીકરણ છે, કારણ કે તે કાઉન્ટર્સ અને અમર્યાદિત લંબાઈની કતારો જેવા અમર્યાદિત ડેટા સ્ટ્રક્ચર્સ સાથે મોડેલિંગ સિસ્ટમોને સક્ષમ કરે છે. પ્રારંભિક અવસ્થાઓનો સમૂહ (પ્રારંભિક અવસ્થાઓ તરીકે પણ ઓળખાય છે) એ બિન-ખાલી અવસ્થાઓનો ઉપસમૂહ છે. બહુવિધ શરૂઆતની સ્થિતિઓને મંજૂરી આપવામાં આવી છે જેથી કેટલીક ઇનપુટ માહિતીને શરૂઆતની સ્થિતિઓમાં સામેલ કરી શકાય. સંક્રમણ સંબંધ ઓટોમેટન A ના સ્થિતિ-સંક્રમણ સંબંધને ટ્રાન્સ (A) સ્ટેટ્સ (A) × એક્ટ્સ (sig (A)) × સ્ટેટ્સ (A) તરીકે સૂચવવામાં આવે છે. તે ગુણધર્મને સંતોષે છે કે "દરેક સ્થિતિ s અને દરેક ઇનપુટ ક્રિયા π માટે, એક સંક્રમણ (s, π, s ') bul ટ્રાન્સ (A) છે". સંક્રમણ, જેને I/O ઓટોમેટન A ના પગલા તરીકે પણ ઓળખવામાં આવે છે, તેને ટ્રાન્સ (A) ના તત્વ (s, π, s ') તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. જ્યારે π એ ઇનપુટ ક્રિયા હોય ત્યારે ઇનપુટ સંક્રમણ એ સંક્રમણ (s, π, s ') નો સંદર્ભ આપે છે, જ્યારે π એ આઉટપુટ ક્રિયા હોય ત્યારે આઉટપુટ સંક્રમણ એ સંક્રમણ (s, π, s') સૂચવે છે. કોઈપણ સ્થિતિ s અને ક્રિયા π માટે, જો I/O ઓટોમેટન A સ્વરૂપ (s, π, s ') નું અમુક સંક્રમણ ધરાવે છે, તો પછી π ને s માં સક્ષમ હોવાનું કહેવાય છે. I/O ઓટોમેટાને ઇનપુટ-સક્ષમ તરીકે વર્ણવવામાં આવે છે કારણ કે દરેક સ્થિતિમાં તમામ ઇનપુટ ક્રિયાઓ સક્ષમ કરવી જરૂરી છે. શાંત સ્થિતિને એવી સ્થિતિ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે જ્યાં માત્ર ઇનપુટ ક્રિયાઓ સક્ષમ હોય છે. I/O ઓટોમેટન A નો પાંચમો ઘટક, ટાસ્ક (A), એક ટાસ્ક પાર્ટીશન છે, જેને A ની સ્થાનિક રીતે નિયંત્રિત ક્રિયાઓ પર સમાનતા સંબંધ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, જેમાં સૌથી વધુ સંખ્યાબંધ સમાનતા વર્ગો હોય છે. અનૌપચારિક રીતે, ટાસ્ક પાર્ટીશન ટાસ્ક (A), A ની અંદર "ટાસ્ક" અથવા "થ્રેડ્સ ઓફ કંટ્રોલ" નું અમૂર્ત વર્ણન રજૂ કરે છે. આ પાર્ટીશનનો ઉપયોગ ઓટોમેટનના અમલ પર નિષ્પક્ષતાની શરતોને વ્યાખ્યાયિત કરવા માટે થાય છે. આ શરતો માટે ઓટોમેટનને તેના અમલીકરણ દરમિયાન તેના દરેક કાર્યોને યોગ્ય વળાંક આપવાનું ચાલુ રાખવાની જરૂર છે. આ ખાસ કરીને સિસ્ટમ ઘટકનું મોડેલિંગ કરતી વખતે મદદરૂપ થાય છે જે બહુવિધ નોકરીઓ કરે છે. દાખલા તરીકે, એક ઘટક કે જે ચાલુ અલ્ગોરિધમમાં ભાગ લે છે જ્યારે સમયાંતરે તેના પર્યાવરણને એક સાથે સ્થિતિની માહિતીની જાણ કરે છે, તેના બે કાર્યો હશે. આ પાર્ટીશન ત્યારે પણ ઉપયોગી છે જ્યારે ઘણા ઓટોમેટા રચાય છે (મોટા સિસ્ટમ ઓટોમેટનનું ઉત્પાદન કરવા માટે) જ્યારે સ્પષ્ટ કરે છે કે રચનામાં તમામ ઓટોમેટા રચાયેલ સિસ્ટમમાં પગલાં લેવાનું ચાલુ રાખે છે. ઉદાહરણોઃ ચેનલ I/O ઓટોમેટનની ઔપચારિક વ્યાખ્યા ઉપર વર્ણવ્યા મુજબ, Ci, j એ I/O ઓટોમેટનનું ઉદાહરણ છે જે પ્રક્રિયા Pi થી પ્રક્રિયા Pj સુધી એક દિશાસૂચક FIFO ચેનલનું પ્રતિનિધિત્વ કરે છે. ધારો કે m એ દ્વિસંગી સંદેશ છેઃ m bul {0,1}. ઓટોમેટન Ci, j ને ઔપચારિક રીતે નીચે પ્રમાણે વ્યાખ્યાયિત કરી શકાય છે. સહીઃ સિગ (Ci, j) સ્પષ્ટ કરે છે કે ઓટોમેટનમાં બે પ્રકારની ક્રિયાઓ હોય છેઃ (Ci, j) ની ઇનપુટ ક્રિયા મોકલો (m) i, j સ્વરૂપની હોય છે, જ્યાં m bul {0,1} હોય છે. (Ci, j) ની આઉટપુટ ક્રિયા રિસીવ (m) i, j સ્વરૂપની હોય છે, જ્યાં m bul {0,1} હોય છે. સાહજિક રીતે, મોકલો (m) i, j ક્રિયા સૂચવે છે કે સંદેશ m એ ચેનલમાં દાખલ થયો છે જ્યારે તે પ્રક્રિયા Pi દ્વારા મોકલવામાં આવે છે અને ક્રિયા પ્રાપ્ત કરે છે (m) i, j સૂચવે છે કે સંદેશ m એ ચેનલ છોડી દીધો છે જ્યારે તે Pj પ્રક્રિયા કરવા માટે પહોંચાડવામાં આવે છે. સ્થિતિઓઃ સ્થિતિઓ (Ci, j) એ ઘટકોના તમામ મર્યાદિત ક્રમોનો સમૂહ છે m ± {0,1}. અંતઃપ્રેરણાપૂર્વક, રાજ્ય વર્તમાનમાં પ્રેષકના માર્ગમાં સંદેશાના ક્રમને રજૂ કરે છે, પી. આઈ. પ્રક્રિયા કરે છે, પ્રાપ્તકર્તાને પ્રક્રિયા કરે છે, પી. જે. પ્રક્રિયા કરે છે, જે ક્રમમાં તેઓ મોકલવામાં આવ્યા હતા. પ્રારંભ (Ci, j), જે કતારની પ્રારંભિક સ્થિતિઓનું પ્રતિનિધિત્વ કરે છે, તેમાં માત્ર ખાલી ક્રમ હોય છે. સંક્રમણો સંક્રમણ સંબંધને પૂર્વશરત-અસર શૈલીમાં તૈયાર કરી શકાય છે, જ્યાં દરેક ચોક્કસ પ્રકારની ક્રિયાનો સમાવેશ કરતા તમામ સંક્રમણોને કોડના એક ભાગમાં જૂથબદ્ધ કરવામાં આવે છે. આ કોડમાં, ક્રિયા થવાની મંજૂરી આપતા પહેલા જે શરતોને સંતોષવી આવશ્યક છે, તેને પૂર્વ-સ્થિતિ s પર વિધેય તરીકે ઔપચારિક કરવામાં આવે છે, જે ક્રિયા થાય તે પહેલાંની સ્થિતિ છે. ક્રિયાના અમલના પરિણામે રાજ્યમાં થતા ફેરફારોને એક સરળ કાર્યક્રમના સ્વરૂપમાં કોડેડ કરવામાં આવે છે. આ કાર્યક્રમ એક જ સંક્રમણ તરીકે અવિભાજ્ય રીતે ચલાવવામાં આવે છે. જો આ કાર્યક્રમ રાજ્યને લાગુ પડે છે, તો નવા રાજ્યનું પરિણામ આવે છે. Ci, j ના સંક્રમણોને આ રીતે વર્ણવવામાં આવે છેઃ મોકલવા માટે (m) i, j: પૂર્વશરતઃ કોઈ અસર નથીઃ m એ સ્થિતિમાં સંગ્રહિત ક્રમના અંતમાં ઉમેરવામાં આવે છે (જ્યાં m bul {1,0}) પ્રાપ્ત કરવા માટે (m) i, j: પૂર્વશરતઃ m એ સ્થિતિમાં સંગ્રહિત ક્રમમાં પ્રથમ તત્વ છે (જ્યાં m bul {1,0}) અસરઃ સ્થિતિમાં સંગ્રહિત ક્રમના પ્રથમ તત્વને દૂર કરો સહજ ભાવે, મોકલવાની ક્રિયાને કોઈપણ સમયે ચલાવી શકાય છે; તે સંદેશ m ને ચે ચેનલમાં સંદેશાઓની કતારના અંતમાં ઉમેરવાનું કારણ બને છે. પ્રાપ્ત ક્રિયા કતારના પ્રથમ ઘટકને દૂર કરે છે અને પરત કરે છે. ટાસ્ક ટાસ્ક (Ci, j), એક ટાસ્ક પાર્ટીશનનું પ્રતિનિધિત્વ કરે છે જે ફોર્મની બધી ક્રિયાઓને એક જ કાર્યમાં એકત્રિત કરે છે. સહજ ભાવે, Pj પર પ્રક્રિયા કરવા માટે સંદેશાઓ સોંપવાનું એક જ કાર્ય માનવામાં આવે છે. {પ્રાપ્ત કરો (m) i, j: m bul {0,1}}. એક્ઝેક્યુશન અને ટ્રેસ એક્ઝેક્યુશન ઓટોમેટનના રનમાં, એક સ્ટ્રિંગ પેદા થાય છે જે ઓટોમેટન મોડેલ્સના ઘટકની વર્તણૂકનું વર્ણન કરે છે. "I/O ઓટોમેટન A નો એક્ઝેક્યુશન ટુકડો કાં તો એક મર્યાદિત ક્રમ છે, s0, π1, s1, π2,., πr, sr, અથવા અનંત ક્રમ, s0, π1, s1, π2,., πr, sr,., વૈકલ્પિક સ્થિતિઓ અને A ની ક્રિયાઓ કે જેથી (sk, πk + 1, sk + 1) એ દરેક k ≤ 0 માટે A નું સંક્રમણ છે". એક મર્યાદિત ક્રમ સ્થિતિ સાથે સમાપ્ત થવો જોઈએ. એક્ઝેક્યુશનને એક્ઝેક્યુશન ફ્રેગમેન્ટ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે જે સ્ટાર્ટ સ્ટેટથી શરૂ થાય છે. એ ની ફાંસીનો સમૂહ એક્ઝિક્યુશન્સ (એ) દ્વારા રજૂ થાય છે. I/O ઓટોમેટન A માં પહોંચી શકાય તેવી સ્થિતિ એ A ના મર્યાદિત અમલની અંતિમ સ્થિતિ છે. ધારો કે α એ A નો એક મર્યાદિત અમલ ટુકડો છે જે સ્ટેટ sf સાથે સમાપ્ત થાય છે. આગળ ધારો કે α 'એ A નો કોઈપણ અમલ ટુકડો છે જે sf થી શરૂ થાય છે, જે α ની છેલ્લી સ્થિતિ છે. આ કિસ્સામાં, α અને α 'ને સંયોજિત કરીને અને sf ની ડુપ્લિકેટ ઘટનાને દૂર કરીને ઉત્પન્ન થયેલ ક્રમ, α ની છેલ્લી સ્થિતિ, α. α' દ્વારા રજૂ થાય છે. આ ક્રમ I/O ઓટોમેટન A નો અમલ ટુકડો પણ છે. ટ્રેસ I/O ઓટોમેટન A નું ટ્રેસ એ બાહ્ય ક્રિયાઓનો ક્રમ છે જે A ના કેટલાક અમલ α માં થાય છે. A ના તમામ નિશાનોનો સમૂહ નિશાન (A) તરીકે રજૂ થાય છે. ઉદાહરણોઃ ત્રણ ફાંસીની સજા એ, બી અને સી એ ચેનલ I/O ઓટોમેટનની ઔપચારિક વ્યાખ્યામાં વર્ણવેલ ઓટોમેટન Ci, j ની ત્રણ ફાંસીની સજા છે (જ્યાં સંદેશ m bul {0,1}). આ ઉદાહરણમાં, સ્થિતિઓ કૌંસમાં કતારમાં સંદેશાઓનો ક્રમ મૂકીને સૂચવવામાં આવે છે; ખાલી ક્રમ λ દ્વારા રજૂ થાય છે. (a) [λ], મોકલો (1) i, j, [1], પ્રાપ્ત કરો (1) i, j, [λ], મોકલો (0) i, j, [0], પ્રાપ્ત કરો (0) i, j, [λ] (b) [λ], મોકલો (1) i, j, [1], પ્રાપ્ત કરો (1) i, j, [λ], મોકલો (0) i, j, [0] (c) [λ], મોકલો (1) i, j, [1], મોકલો (1) i, j, [11], મોકલો (1) i, j, [11], મોકલો (0) i, j, [110]. ઓટોમેટા કમ્પોઝિશન ઓપરેશન પર ઓપરેશન્સ રચના શક્ય છે. આ કિસ્સામાં, દરેક ઘટક ઓટોમેટામાં સમાન નામ ધરાવતી ક્રિયાઓ એકસાથે ઓળખવામાં આવે છે. તેથી, જ્યારે ઘટક ઓટોમેટા એક પગલું લે છે જેમાં ક્રિયા π નો સમાવેશ થાય છે, ત્યારે તેમના હસ્તાક્ષરમાં π સાથે અન્ય તમામ ઘટક ઓટોમેટા પણ તે ક્રિયા કરે છે. ઓટોમેટા 'એ' અને 'એ' ની રચનાની મંજૂરી માટેની શરતો નીચે દર્શાવેલ છેઃ 'એ' ની આંતરિક ક્રિયાઓ 'એ' ની ક્રિયાઓથી અલગ હોવી જોઈએ. આ 'એ' માં એક પગલાની કામગીરીને અટકાવે છે જ્યારે 'એ' ની ક્રિયાઓ જેવી જ નામની 'એ' ની આંતરિક ક્રિયાઓ કરવામાં આવે છે. A અને A 'ની આઉટપુટ ક્રિયાઓ અસંગત હોવી જોઈએ. આ શરત એ સુનિશ્ચિત કરે છે કે માત્ર એક ઘટક ઓટોમેટન આઉટપુટ ક્રિયાના પ્રદર્શનને નિયંત્રિત કરે છે. જો કમ્પોઝિશન ઓટોમેટાના અગણિત સંગ્રહમાંથી બનાવવામાં આવે છે, તો ત્યાં એક વધારાનો અવરોધ છેઃ દરેક ક્રિયા માત્ર મર્યાદિત રીતે ઘણા ઘટક ઓટોમેટાની ક્રિયા હોવી જરૂરી છે. ઓટોમેટાની અનંત રચના લોજિકલ સિસ્ટમોના મોડેલિંગને મંજૂરી આપે છે જે ઘણા લોજિકલ ઘટકોમાંથી બનાવવામાં આવી શકે છે. લોજિકલ સિસ્ટમ ઘણીવાર ભૌતિક સિસ્ટમ પર લાગુ કરવામાં આવે છે જેમાં ઓછા ઘટકો હોય છે. ઉદાહરણોઃ રચના આકૃતિ 4 બે પ્રક્રિયાઓ, પી. આઈ. અને પી. જે. અને એફ. આઈ. એફ. ઓ. સંદેશ ચેનલ સી. આઈ., જે. ની રચનાને દર્શાવે છે, જે એક ઓટોમેટનની આઉટપુટ ક્રિયાઓને અન્ય ઓટોમેટાની સમાન નામવાળી ઇનપુટ ક્રિયાઓ સાથે મેળ ખાય છે. આમ, પ્રક્રિયા પી. આઈ. દ્વારા કરવામાં આવેલ મોકલો (એમ) આઈ, જે આઉટપુટ મેળ ખાય છે અને ચેનલ સી. આઈ., જે. દ્વારા કરવામાં આવેલ મોકલો (એમ) આઈ, જે ઇનપુટ સાથે કરવામાં આવે છે. પ્રોસેસ પાઇ સંદેશ m મોકલે છે, જ્યાં m bul {1,0} ચેનલ Ci દ્વારા, j થી પ્રોસેસ Pj. પ્રોસેસ પી. જે. તેની આંતરિક ક્રિયા રિવર્સનો ઉપયોગ કરીને પી. આઈ. તરફથી પ્રાપ્ત સંદેશ m માં બીટને ઉલટાવી દે છે-ચિત્રમાં બતાવેલ નથી-અને સંદેશને સિસ્ટમના અન્ય ભાગોમાં આગળ મોકલે છે. "તેમને આંતરિક ક્રિયાઓ તરીકે પુનઃવર્ગીકૃત કરીને" I/O ઓટોમેટનની આઉટપુટ ક્રિયાઓને છુપાવવી શક્ય છે. આ તેમને સિસ્ટમના અન્ય ભાગો સાથેના સંચારમાંથી બાકાત રાખવાની અસર ધરાવે છે. ઔપચારિક રીતે, સહીઓ માટે છુપાવવાની કામગીરી નીચે મુજબ વર્ણવવામાં આવી છેઃ ચાલો S એ સહી હોય અને φ બહાર (S). હાઈડ (S) એ નવી સહી S 'છે, જ્યાં (S') = ઇન (S) આઉટ (S ') = આઉટ (S)-φ ઇન્ટ (S') = ઇન્ટ (S) ≤ ≤ ≤ ≤ તેથી, "જો A ઓટોમેટન છે અને φ આઉટ (A) છે, તો હાઈડ (A) એ ઓટોમેટન A 'છે જે સિગ (A) ને સિગ (A') = હાઈડ (A ') સાથે બદલીને A માંથી મેળવવામાં આવે છે". નિષ્પક્ષતા યાદ રાખો કે કાર્ય વિભાજનને I/O ઓટોમેટનની સ્થાનિક રીતે નિયંત્રિત ક્રિયાઓ પર સમકક્ષતા સંબંધ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, જેમાં સૌથી વધુ ગણતરીમાં ઘણા સમકક્ષતા વર્ગો હોય છે. આ સેટિંગમાં, નિષ્પક્ષતાને દરેક કાર્યને સતત ક્રિયા કરવાની તક પૂરી પાડવા તરીકે વ્યાખ્યાયિત કરી શકાય છે. I/O ઓટોમેટન A માં, ચાલો C એ કાર્યોના વર્ગ (A) નું પ્રતિનિધિત્વ કરે છે. ઔપચારિક રીતે, A નો એક્ઝેક્યુશન ટુકડો α વાજબી માનવામાં આવે છે જો નીચે આપેલા માપદંડ દરેક વર્ગ C માટે ધરાવે છેઃ "જો α મર્યાદિત હોય, તો C એ α ની અંતિમ સ્થિતિમાં સક્ષમ નથી". "જો α અનંત હોય, તો α ક્યાં તો C માંથી અનંત ઘણી ઘટનાઓ ધરાવે છે અથવા અનંત ઘણી એવી સ્થિતિઓ ધરાવે છે જેમાં C સક્ષમ નથી". એક ઘટનાને "અનુક્રમમાં ક્રિયાની ઘટના, ઉદાહરણ તરીકે, અમલ અથવા ટ્રેસ" તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. નિષ્પક્ષતાની વ્યાખ્યાના આધારે, "અનંત વારંવાર", દરેક કાર્ય (અથવા સમકક્ષતા વર્ગ સી) ને ક્રિયા કરવાની તક મળે છે. જ્યારે કાર્ય (અથવા સમકક્ષતા વર્ગ) C ને ક્રિયા કરવાની તક મળે છે, ત્યારે બે કિસ્સાઓ શક્ય છેઃ C માં ક્રિયા વર્તમાન સ્થિતિમાં સક્ષમ છે અને કરી શકાય છે, અથવા C માં કોઈ પણ ક્રિયા વર્તમાન સ્થિતિમાં સક્ષમ નથી અને તેથી, કરી શકાતી નથી. આમ, અંતિમ સ્થિતિ Sf સાથે મર્યાદિત વાજબી અમલને એક અમલ તરીકે વ્યાખ્યાયિત કરી શકાય છે જ્યાં ઓટોમેટન સતત રાઉન્ડ-રોબિન ફેશનમાં તમામ કાર્યોને વળાંક આપે છે, પરંતુ કોઈ ક્રિયાઓ ચલાવવામાં આવતી નથી કારણ કે Sf માં કોઈ સક્ષમ નથી. I/O ઓટોમેટન A ના વાજબી અમલનો સમૂહ ફેઇરેક્સ (A) દ્વારા રજૂ થાય છે. ધારો કે β એ A ના વાજબી અમલનું નિશાન છે. પછી β એ A નું વાજબી ચિહ્ન છે. એ ના સેટ વાજબી નિશાન ફેરટ્રેસિસ (એ) દ્વારા રજૂ થાય છે. અમલના ઉદાહરણમાં, અમલ (એ) વાજબી છે, કારણ કે તેની અંતિમ સ્થિતિમાં કોઈ પ્રાપ્ત ક્રિયા સક્ષમ નથી. અમલ (બી) મર્યાદિત છે, તેમ છતાં પ્રાપ્ત ક્રિયા તેની અંતિમ સ્થિતિમાં સક્ષમ છે. તેથી, અમલ (બી) વાજબી નથી. એક્ઝેક્યુશન (સી) અનંત છે, તેમાં પ્રાપ્ત ઘટનાઓ શામેલ નથી, અને પ્રથમ પગલું પછીના તમામ બિંદુઓ પર, પ્રાપ્ત ક્રિયાઓ સક્ષમ છે. તેથી, તે યોગ્ય અમલ નથી. નિષ્પક્ષતાની વ્યાખ્યામાં નોંધપાત્ર ગુણધર્મ છેઃ "રચનાની ન્યાયી અમલવારી એ ઘટકોની ન્યાયી અમલવારીની રચના છેઃ" એટલે કે, ન્યાયી (Πi AI) = Πi વાજબી (AI). ગુણધર્મો અને પ્રૂફ પદ્ધતિઓ I/O ઓટોમેટા એસિંક્રોનસ સિસ્ટમોનું સચોટ વર્ણન પ્રદાન કરે છે. તેનો ઉપયોગ "સિસ્ટમો શું કરી શકે છે" તે વિશેના "ચોક્કસ દાવાઓ" ને ઔપચારિક બનાવવા અને સાબિત કરવા માટે પણ થાય છે. આ વિભાગમાં સંખ્યાબંધ મહત્વપૂર્ણ પ્રકારનાં ગુણધર્મોનું વર્ણન કરવામાં આવ્યું છે. આ, તેમજ વધુ ગુણધર્મો અને સાબિતી પદ્ધતિઓ, ડિસ્ટ્રિબ્યુટેડ અલ્ગોરિધમ્સમાં સમજાવવામાં આવી છે. ઇનપુટ સક્ષમ ગુણધર્મો ઇનપુટ સક્ષમ ગુણધર્મ જણાવે છે કે ઓટોમેટન ઇનપુટ ક્રિયાઓને બનતા અટકાવી શકતું નથી. આ ગુણધર્મ હોવાના બે નોંધપાત્ર ફાયદાઓ છેઃ કારણ કે આ મોડેલ મનસ્વી ઇનપુટ્સનો સામનો કરવા માટે રચાયેલ છે, અનપેક્ષિત ઇનપુટ્સને સંભાળવામાં નિષ્ફળતાને કારણે સિસ્ટમ ભૂલોના મુખ્ય સ્ત્રોતને દૂર કરવામાં આવે છે. ઇનપુટ-સક્ષમ ગુણધર્મ "બાહ્ય ક્રિયાઓના ક્રમ પર આધારિત ઓટોમેટન માટે બાહ્ય વર્તનની સરળ કલ્પનાઓ" નો ઉપયોગ કરે છે. આ ગુણધર્મની ધારણા વિના મોડેલમાં અમુક પ્રમેયોના પુરાવા નિષ્ફળ થઈ શકે છે. ટ્રેસ ગુણધર્મો I/O ઓટોમેટનની આંતરિક ક્રિયાઓ વપરાશકર્તા માટે અદ્રશ્ય હોય છે; I/O ઓટોમેટન બ્લેક બોક્સ હોવાનું જણાય છે અને વપરાશકર્તા માત્ર "ઓટોમેટનના અમલ (અથવા વાજબી અમલ) ના નિશાન" જુએ છે. I/O ઓટોમેટાના અમુક ગુણધર્મો અને તેમના પુરાવાઓને સામાન્ય રીતે "તેમના નિશાન અથવા વાજબી નિશાનના ગુણધર્મો" તરીકે ઔપચારિક કરવામાં આવે છે. ધારો કે પી એક ટ્રેસ પ્રોપર્ટી છે; પી પાસે નીચેના ઘટકો છેઃ સિગ (પી), જે કોઈ આંતરિક ક્રિયાઓ ટ્રેસ (પી) વગરની સહીનું પ્રતિનિધિત્વ કરે છે, જે "કૃત્યોમાં ક્રિયાઓના ક્રમ (સિગ (પી))" ના સમૂહને અનુરૂપ છે. આ સમૂહ અનંત હોઈ શકે છે. ટ્રેસ પ્રોપર્ટી બાહ્ય હસ્તાક્ષર તેમજ તે ઇન્ટરફેસ પર જોવામાં આવેલા ક્રમના સમૂહ (અથવા ગુણધર્મ) નું વર્ણન કરે છે. કેટલીકવાર કૃત્યો (સિગ (પી)) ને લઘુલિપિ સંકેતન કૃત્યો (પી) દ્વારા રજૂ કરવામાં આવે છે. જ્યારે ઉલ્લેખ કરવામાં આવે છે કે I/O ઓટોમેટન A એ ટ્રેસ પ્રોપર્ટી P ને સંતોષે છે, ત્યારે (ઓછામાં ઓછા) બે અલગ અલગ અર્થોનો હેતુ હોઈ શકે છેઃ "extsig (A) = sig (P) અને traces (A) ષ્ ટ્રેસ (P)" "extsig (A) = sig (P) અને નિષ્પક્ષ ટ્રેસ (A) ષ્ ટ્રેસ (P)" સાહજિક રીતે, તેનો અર્થ એ થાય છે કે જ્યારે A બાહ્ય વર્તણૂક પેદા કરે છે ત્યારે તે ગુણધર્મ P દ્વારા માન્ય છે. જો કે, A માટે ખરેખર P ના દરેક ટ્રેસનું પ્રતિનિધિત્વ કરવું જરૂરી નથી. કારણ કે A ઇનપુટ-સક્ષમ છે, પછી ઇનપુટ ક્રિયાઓના દરેક સંભવિત ક્રમ માટે, નિષ્પક્ષતા (A) (અને તેથી ટ્રેસ (A) માં A દ્વારા પ્રતિસાદનો સમાવેશ થાય છે. જો ફેરટ્રેસિસ (એ) ટ્રેસ (પી) ધરાવે છે, તો પ્રોપર્ટી પીમાં તમામ જનરેટેડ સિક્વન્સ હોવા આવશ્યક છે. સલામતી ગુણધર્મો સાહજિક રીતે, સલામતી ગુણધર્મ એ હકીકતને રજૂ કરે છે કે કંઇ "ખરાબ" થતું નથી. વધુ ઔપચારિક રીતે, ચાલો પી એક ટ્રેસ પ્રોપર્ટી છે. પી એ ટ્રેસ સલામતી મિલકત અથવા સલામતી મિલકત છે, જો નીચેના માપદંડ ટ્રેસ (પી) માટે ધરાવે છે. નિશાન (પી) ખાલી નથીઃ કોઈ પણ ઘટના બને તે પહેલાં કંઈક ખરાબ ન થઈ શકે; તેથી, નિશાન (પી) પર ખાલીપણું ન હોવું એ વાજબી શરત છે. ટ્રેસ (પી) એ "ઉપસર્ગ-બંધ" છેઃ ચાલો β bul ટ્રેસ (પી) અને β 'એ β ના મર્યાદિત ઉપસર્ગને રજૂ કરે છે. વિસ્તૃત કરવા માટે, ધારો કે ત્યાં એક ટ્રેસ છે જેમાં કંઇ ખરાબ થતું નથી. તેથી, તે ટ્રેસના કોઈપણ ઉપસર્ગમાં કંઈ ખરાબ થતું નથી. આમ, ઉપસર્ગ-બંધ હોવું એ નિશાન (પી) પર વાજબી શરત છે. ટ્રેસ (પી) "મર્યાદા-બંધ" છેઃ ચાલો β1, β2,. . . ટ્રેસ (પી) માં મર્યાદિત ક્રમના અનંત ક્રમનું પ્રતિનિધિત્વ કરે છે. ઉપરાંત, ધારો કે દરેક i માટે, βi એ βi + 1 નો ઉપસર્ગ છે. આ કિસ્સામાં, અનન્ય ક્રમ β, એટલે કે "ક્રમિક વિસ્તરણ ક્રમ હેઠળ βi ની મર્યાદા" પણ ટ્રેસ (P) માં અસ્તિત્વ ધરાવે છે. તેથી, જો ટ્રેસમાં કંઈક ખરાબ થવાનું હોય, તો તે ટ્રેસમાં ચોક્કસ ચોક્કસ ઘટનાનું પરિણામ હશે. આ કિસ્સામાં મર્યાદા બંધ કરવી એ ટ્રેસ (પી) પર વાજબી શરત છે. જીવંતતાના ગુણધર્મો અનૌપચારિક રીતે, જીવંતતાના ગુણધર્મને આખરે કંઈક "સારું" થાય છે તેવું અર્થઘટન કરી શકાય છે. તેથી, કોઈ ચોક્કસ સમયે શું થયું છે તે ધ્યાનમાં લીધા વિના, ભવિષ્યમાં કોઈક સમયે કંઈક સારું થઈ શકે છે. વધુ ઔપચારિક રીતે, ચાલો P એક ટ્રેસ પ્રોપર્ટી છે. પી એક ટ્રેસ જીવંત ગુણધર્મ છે, અથવા જીવંત ગુણધર્મ છે, "જો કૃત્યો (પી) પરના દરેક મર્યાદિત ક્રમમાં ટ્રેસ (પી) માં કેટલાક વિસ્તરણ હોય". ટાઈમ I/O ઓટોમેટનઃ પ્રોબેબિલિસ્ટિક I/O ઓટોમેટનઃ સામાન્ય રીતે સલામતીના ગુણધર્મો અને જીવંત ગુણધર્મોની ચર્ચા માટે, સલામતી અને જીવંત ગુણધર્મો જુઓ. આ પણ જુઓ સંવાદની ક્રમિક પ્રક્રિયાઓ અભિનેતા મોડેલ સંદર્ભો ડિસ્ટ્રિબ્યુટેડ કમ્પ્યુટિંગ