I den här artikeln löser vi problemet med ursprung-märkning system, som syftar till att tilldela de kortaste möjliga etiketter (bit strängar) till noder av rotade träd, så förfäder frågor mellan två noder kan besvaras genom att inspektera sina tilldelade etiketter endast. Detta problem infördes för mer än 20 år sedan av Kannan et al. [1988] och är bland de mest välstuderade problemen när det gäller informativa märkningssystem. Vi konstruerar ett härstamningssystem för n-node träd med etikettstorlek log 2 n+ O(log log n) bitar, vilket motsvarar log 2 n + (log log n) bitar lägre gräns ges av Alstrup et al. [2003]................................................................. Vårt system bygger på ett förenklat härstamningssystem som fungerar mycket bra på en begränsad uppsättning träd. Särskilt för uppsättningen n-nodeträd med ett djup av högst d har det förenklade härstamningssystemet en etikettstorlek på log 2 n + 2 log 2 d + O(1) bitar. Eftersom djupet av de flesta XML-träd är som mest någon liten konstant, kan en sådan här härstamningssystem vara till praktisk nytta. Dessutom får vi också ett adjaksmärkningssystem som etiketterar n-node träd på djup d med etiketter av storlek log 2 n+ 3 log 2 d+ O(1) bitar. Alla våra system tilldela etiketter i linjär tid, och garantera att alla frågor kan besvaras i konstant tid. Slutligen, vårt härstamningssystem finner tillämpningar för konstruktion av små universella delvis beställda uppsättningar (säten). Specifikt, för varje fast heltal k, möjliggör det byggandet av en universell poset av storlek Õ(n k ) för familjen av n-element posetter med en träddimension på som mest k. Upp till lägre ordning termer, är denna gräns snäv tack vare en lägre gräns av n k‐o(1) av till Alon och Scheinerman [1988].
Vi känner inte till några märkningssystem för gitter, men Fraigniaud och Korman REF har nyligen studerat adjacenssystem för posetter med låg "träddimension".
An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}