Izomorfizmy struktury danych

Zastrzeżenie: Nie jestem teoretykiem CS.

Pochodząc z algebry abstrakcyjnej, jestem przyzwyczajony do radzenia sobie z rzeczami równymi do izomorfizmu - ale mam problem z przetłumaczeniem tej koncepcji na struktury danych. Najpierw pomyślałem, że wystarczy zestaw teoretycznych morfizmów bijectywnych, ale dość szybko wpadłem na ścianę - są to tylko kodowania i nie wychwytują obliczeniowej istoty struktury danych.

Czy istnieje bardziej restrykcyjna (ale bardziej przydatna) definicja? (A jeśli nie, to dlaczego?) Czy istnieje kanoniczna definicja kategorii „skonstruowanych struktur danych”?

Nie ma takiej kanonicznej kategorii, z tego samego powodu nie ma kanonicznej kategorii obliczeń. Istnieją jednak duże i przydatne struktury algebraiczne na strukturach danych.

Jedną z bardziej ogólnych takich struktur, która jest nadal użyteczna, jest teoria gatunków kombinatorycznych. Gatunek jest funktorem , gdzie jest kategorią zbiorów skończonych i bijektycji między nimi. Można myśleć o gatunkach jako o rodzinach struktur indeksowanych abstrakcyjnymi zbiorami lokalizacji. To tłumaczy funkcjonalność w stosunku do - takie rodziny muszą być niezmienne w odniesieniu do zmiany nazw etykiet abstrakcyjnych. Następnie rachunek gatunków zasadniczo odtwarza metody generowania funkcji na poziomie funcjonalnym, aby generować zestawy struktur danych zamiast zliczeń.B $F : B \to B$$B$$B$

Aby zobaczyć tę teorię zaimplementowaną w języku programowania, możesz przeczytać artykuł Sympozjum Haskella Brenta Yorgeya, gatunki oraz funktory i typy, o rany ! . Myślę, że Sage ma również pakiet gatunków, choć oczywiście jest zorientowany raczej na algebrę komputerową niż na programowanie.

Rzeczywiście, istnieje inne pojęcie niż izomorfizm, które jest bardziej przydatne w programowaniu. Nazywa się to „równoważnością behawioralną” (czasami nazywaną „równoważnością obserwacyjną”) i ustala się ją poprzez „relację symulacji” między strukturami danych, a nie przez bijectie. Weszli algebraiści i ustanowili obszar zwany „algebraicznymi typami danych” w informatyce, gdzie przez jakiś czas pchali izomorfizmy i początkowe algebry. W końcu informatycy zdali sobie sprawę, że zostali wprowadzeni w błąd. Dobry artykuł mówiący o tych kwestiach to „O równoważności obserwacyjnej i specyfikacji algebraicznej” Sannelli i Tarleckiego.

Napisałem odpowiedź na inne pytanie w cstheory dotyczące relacji logicznych i symulacji, które mówi o bardziej ogólnej historii relacji symulacyjnych w informatyce. Zapraszam do przeczytania tego i śledzenia podanych tam referencji. Rozdział 5 „Rzemiosła programowania” Reynoldsa jest szczególnie pouczający.

W podręczniku Algebraic Automata Theory autorstwa Holcombe znajduje się następujący interesujący cytat (s. 42):

Istnieje wiele innych wyników dotyczących homomorfizmów i ilorazów ... Chociaż mają one niezależne znaczenie algebraiczne, nie okazały się jeszcze szczególnie przydatne w badaniach automatów i powiązanych dziedzin. W rzeczywistości algebraiczna teoria maszyn odbiega od kierunku obranego w innych teoriach algebraicznych pod jednym ważnym względem ... W teorii automatów nacisk kładziony jest jednak nie na to, jak „wyglądają” maszyny, ale na to, co „potrafią” . Będziemy uważać dwie maszyny za bardzo blisko powiązane, jeśli obie mogą „robić to samo”, mogą jednak nie być algebraicznie izomorficzne!

Zamiast pytać, jak możemy wzmocnić / osłabić pojęcie izomorfizmu, inną możliwością jest pytanie: jakie jest właściwe pojęcie równoważności między strukturami obliczeniowymi i jaka jest struktura matematyczna leżąca u podstaw tego pojęcia.

Jedną dużą rodziną konstrukcji są węgielnie. Struktury takie jak listy, drzewa, automaty, zarówno o skończonej, jak i nieskończonej różnorodności, można opisać jako węgiel drzewny. Następnie możemy badać homomorfizm lub izomorfizm między węgielnicami.

Jednak nawet homomorfizmy między węgielnicami nie opowiadają całej historii. Pomocne może okazać się wyszukiwanie symulacji, bisimulacji i innych relacji logicznych. Jeśli wolisz podejście algebraiczne (w przeciwieństwie do relacyjnego), połączenia Galois są jedną z opcji. Oto kilka punktów wyjścia.

• Relacje logiczne i połączenia Galois według Backhouse i Backhouse.
• Universal carbongebra: teoria systemów autorstwa Jana Rutten

Oświadczenie: Nie jestem pewien, czy zrozumiałem twoje pytanie. Czy chcesz porozmawiać o izomorfizmie między dwiema strukturami danych, czy między dwiema „specyfikacjami struktury danych”? (Są to czasami nazywane abstrakcyjnymi typami danych).

Jeśli weźmie się pod uwagę model sondy komórkowej, myślę, że łatwo powstaje koncepcja izomorfizmu. Jest tak, ponieważ model sondy komórkowej modeluje obliczenia na podstawie drzewa decyzyjnego, dlatego izomorfizm jest łatwy do zdefiniowania. Myślę, że model sondy komórkowej pomógłby, zarówno jeśli weźmie się pod uwagę izomorfizm między implementacjami struktury danych, jak i jeśli weźmie się pod uwagę specyfikacje struktury danych.

Aby uzyskać informacje na temat modelu sondy komórkowej, patrz np. Badanie Miltersen. ( Cell Probe Complexity: A Survey )

Jeśli powiesz więcej o tym, dlaczego musisz zdefiniować izomorfizm między strukturami danych, może być możliwe zapewnienie dodatkowej pomocy. Napisz do mnie.