Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикада, әсіресе категориялар теориясында, коалгебра – функтор бойынша анықталатын және төменде сипатталған белгілі қасиеттері бар құрылым. Алгебралар мен коалгебралар үшін функтор – қолтаңбаны ұйымдастырудың ыңғайлы және жалпы тәсілі. Бұл компьютер ғылымында қолданылады: коалгебра мысалдарының ішінде жалқау бағалау, ағындар сияқты шексіз деректер құрылымдары және өтпелі жүйелер бар. Коалгебралар алгебраларға дуалды. Дәл сол сияқты, берілген қолтаңба мен теңдеулер теориясы үшін барлық алгебралар класы бір түрлілік құраса, берілген теңдеулер теориясын қанағаттандыратын барлық коалгебралар класы ковариетті құрайды, мұнда қолтаңба берілген.
In mathematics, specifically in category theory, an coalgebra is a structure defined according to a functor , with specific properties as defined below. For both algebras and coalgebras, a functor is a convenient and general way of organizing a signature. This has applications in computer science: examples of coalgebras include lazy evaluation, infinite data structures, such as streams, and also transition systems. coalgebras are dual to algebras. Just as the class of all algebras for a given signature and equational theory form a variety, so does the class of all coalgebras satisfying a given equational theory form a covariety, where the signature is given by .
Мысалдар
Эндофункторды қарастырайық, ол жиынтықты оның ажыратылған қосылысына жеке жиынтықпен жібереді. Бұл эндофунктордың коалгебрасы , мұндағы – конатуральды сандар, теріс емес бүтін сандардан және сонымен қатар шексіздіктен тұрады, ал функция былай берілген , үшін және . Шындығында, бұл эндофунктордың терминалды коалгебрасы. Көбірек жалпылап айтқанда, кейбір жиынтықты орнатыңыз және оны жіберетін функторды қарастырыңыз . Содан кейін коалгебра – бұл алфавит бойынша шекті немесе шексіз ағын , мұнда – күйлер жиынтығы және – күйлердің өту функциясы. Күйге өту функциясын қолдану екі мүмкін нәтиже бере алады: ағынның келесі күйімен бірге элемент немесе ағында басқа мәндер жоқ екенін көрсететін жеке «соңғы күй» ретінде жеке жиынтықтың элементі. Көптеген практикалық қолданыстарда, мұндай коалгебралық объектінің күйлердің өту функциясы , түрінде болуы мүмкін, ол оңай «таңдаушылар», «байқаушылар», «әдістер» жинағына жіктеледі. Практикалық қызығушылық тудыратын ерекше жағдайларға атрибут мәндерін беретін байқаушылар және қосымша параметрлерді қабылдап, күйлерді қайтаратын мутатор әдістері жатады. Бұл жіктелу бастапқы алгебралардың «құрылысшылардың» қосындыларына жіктелуімен екі еселенеді. P ковариантты функтор ретінде қарастырылатын жиынтықтар санатындағы қуат жиынтығы құрылымы болсын. P коалгебралары бинарлық қатынасы бар жиынтықтармен биективті сәйкестікте. Енді басқа жиынтықты, A-ны орнатыңыз. Онда P(A×()) эндофункторы үшін коалгебралар таңбаланған өту жүйелерімен биективті сәйкестікте болады, ал коалгебралар арасындағы гомоморфизмдер таңбаланған өту жүйелері арасындағы функционалдық бисимуляцияларға сәйкес келеді.
Consider the endofunctor that sends a set to its disjoint union with the singleton set A coalgebra of this endofunctor is given by , where is the so called conatural numbers, consisting of the nonnegative integers and also infinity, and the function is given by , for and In fact, is the terminal coalgebra of this endofunctor. More generally, fix some set , and consider the functor that sends to Then an coalgebra is a finite or infinite stream over the alphabet , where is the set of states and is the state transition function. Applying the state transition function to a state may yield two possible results: either an element of together with the next state of the stream, or the element of the singleton set as a separate "final state" indicating that there are no more values in the stream. In many practical applications, the state transition function of such a coalgebraic object may be of the form , which readily factorizes into a collection of "selectors", "observers", "methods" Special cases of practical interest include observers yielding attribute values, and mutator methods of the form taking additional parameters and yielding states. This decomposition is dual to the decomposition of initial algebras into sums of 'constructors'. Let P be the power set construction on the category of sets, considered as a covariant functor. The P coalgebras are in bijective correspondence with sets with a binary relation. Now fix another set, A. Then coalgebras for the endofunctor P(A×( )) are in bijective correspondence with labelled transition systems, and homomorphisms between coalgebras correspond to functional bisimulations between labelled transition systems.
Қолданбалар
Компьютерлік ғылымда коалгебра потенциалды шексіз жүйелер мен деректер құрылымдарының мінез-құлқын анықтау үшін ыңғайлы және жеткілікті жалпы тәсіл ретінде пайда болды, мысалы, объектіге бағытталған бағдарламалаудағы сыныптар, ағындар және ауысу жүйелері. Алгебралық спецификация конструкторлар арқылы жасалатын индуктивті дерек түрлерін пайдаланып, әдетте функционалдық мінез-құлықпен айналысса, коалгебралық спецификация селекторлар арқылы байқалатын коиндуктивті процесс түрлерімен модельделген мінез-құлықпен айналысады, бұл автоматтар теориясының рухына жақын. Ағындар сияқты, мүмкін шексіз мінез-құлықтың толық жиынтығын құрайтын соңғы коалгебралар мұнда маңызды рөл атқарады. Мұндай жүйелердің қасиеттерін білдіруге арналған табиғи логика – коалгебралық модальдық логика.
In computer science, coalgebra has emerged as a convenient and suitably general way of specifying the behaviour of systems and data structures that are potentially infinite, for example classes in object oriented programming, streams and transition systems. While algebraic specification deals with functional behaviour, typically using inductive datatypes generated by constructors, coalgebraic specification is concerned with behaviour modelled by coinductive process types that are observable by selectors, much in the spirit of automata theory. An important role is played here by final coalgebras, which are complete sets of possibly infinite behaviours, such as streams. The natural logic to express properties of such systems is coalgebraic modal logic.