caa a22 4500 445805323 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00453-009-9383-3 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9383-3 Signature Theory in Holographic Algorithms [Elektronische Daten] [Jin-Yi Cai, Pinyan Lu] In the theory of holographic algorithms proposed by Valiant, computation is expressed and processed in terms of signatures. We substantially develop the signature theory in holographic algorithms. This theory is developed in terms of d-realizability and d-admissibility. For the class of 2-realizable signatures we prove a Birkhoff-type theorem which determines this class. It gives a complete structural understanding of the relationship between 2-realizability and 2-admissibility. This is followed by characterization theorems for 1-realizability and 1-admissibility. Finally, using this theory of general (i.e., unsymmetric) signatures we give additional counting problems solvable in polynomial time by holographic algorithms. Springer Science+Business Media, LLC, 2009 Holographic algorithms nationallicence Signature nationallicence d -realizability nationallicence Complexity theory nationallicence Counting problems nationallicence Cai Jin-Yi Computer Sciences Department, University of Wisconsin, 53706, Madison, WI, USA aut Lu Pinyan Microsoft Research Asia, 100190, Beijing, China aut Algorithmica Springer-Verlag 61/4(2011-12-01), 779-816 0178-4617 61:4<779 2011 61 453 https://doi.org/10.1007/s00453-009-9383-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9383-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Cai Jin-Yi Computer Sciences Department, University of Wisconsin, 53706, Madison, WI, USA aut NATIONALLICENCE 700 1- Lu Pinyan Microsoft Research Asia, 100190, Beijing, China aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/4(2011-12-01), 779-816 0178-4617 61:4<779 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer