{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T23:40:10Z","timestamp":1749944410014,"version":"3.41.0"},"reference-count":8,"publisher":"EDP Sciences","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[1986]]},"DOI":"10.1051\/ita\/1986200201911","type":"journal-article","created":{"date-parts":[[2017,2,2]],"date-time":"2017-02-02T14:56:50Z","timestamp":1486047410000},"page":"191-206","source":"Crossref","is-referenced-by-count":0,"title":["How much semigroup structure is needed to encode graphs ?"],"prefix":"10.1051","volume":"20","author":[{"given":"P.","family":"Goral\u010d\u00edk","sequence":"first","affiliation":[]},{"given":"A.","family":"Goral\u010d\u00edkov\u00e1","sequence":"additional","affiliation":[]},{"given":"V.","family":"Koubek","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2011,1,8]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"1. BABAI L., Moderately exponential bound for graph isomorphism, FCT'81, Lecture Notes in Comp. Sci, n. 117, Springer, 1981, pp. 34-50.6529680462.68040","key":"R1","DOI":"10.1007\/3-540-10854-8_4"},{"doi-asserted-by":"crossref","unstructured":"2. BOOTH K. S., Isomorphism testing for graphs, semigroups, and finite automata are polynomially equivalent problems, SIAM J. Comput. Vol. 7, 1976, pp. 273-279.4836890381.68042","key":"R2","DOI":"10.1137\/0207023"},{"unstructured":"3. BOOTH K. S. and COLBOURN Ch. J., Problems polynomially equivalent to graph isomorphism, Tech. Rep. CS-77-04, Univ. of Waterloo, 1979.","key":"R3"},{"doi-asserted-by":"crossref","unstructured":"4. CLIFFORD A. H. and PRESTON G. B., The algebraic theory of semigroups, A.M.S., Providence, Rhode Island, 1967.0178.01203","key":"R4","DOI":"10.1090\/surv\/007.2\/02"},{"unstructured":"5. EILENBERG S., Automata, Languages, and Machines, Vol. B, Academic Press, 1976.5303830359.94067","key":"R5"},{"doi-asserted-by":"crossref","unstructured":"6. KU\u010cERA L. and TRNKOV\u00c1 V., Isomorphism completeness for some algebraic structures, FCT'81, Lecture Notes in Comp. Sci, n. 117, Springer, 1981, pp. 218-225.6529880476.68035","key":"R6","DOI":"10.1007\/3-540-10854-8_24"},{"unstructured":"7. KU\u010cERA L. and TRNKOV\u00c1 V., Isomorphism testing in unary algebras [to appear in SIAM J. Comput].9532870665.68029","key":"R7"},{"doi-asserted-by":"crossref","unstructured":"8. MICALI S. and VAZIRANI V. V., An O(\u221a|v|.|E|) algorithm for finding maximum matching in generai graphs, Proc. FOCS'80, pp. 17-27.","key":"R8","DOI":"10.1109\/SFCS.1980.12"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1986200201911\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T23:16:38Z","timestamp":1749942998000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1986200201911"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"references-count":8,"journal-issue":{"issue":"2"},"alternative-id":["ita1986200201911"],"URL":"https:\/\/doi.org\/10.1051\/ita\/1986200201911","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"type":"print","value":"0988-3754"},{"type":"electronic","value":"1290-385X"}],"subject":[],"published":{"date-parts":[[1986]]}}}