Fixed-parameter decidability: Extending parameterized complexity analysis

Autor: Witteveen, J., Torenvliet, L.

Publikováno v: Mathematical Logic Quarterly, 62(6), 596-607. Wiley-VCH Verlag

We extend the reach of fixed-parameter analysis by introducing classes of parameterized sets defined based on decidability instead of complexity. Known results in computability theory can be expressed in the language of fixed-parameter analysis, maki

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::222aaa03b51cdc98f37bc776e51154dd
https://dare.uva.nl/personal/pure/en/publications/fixedparameter-decidability(0ed49ac9-ee12-4703-a723-b22e1b50460a).html

Discovering Motifs in Real-World Social Networks

Autor: Romijn, L., Ó Nualláin, B., Torenvliet, L., Italiano, G.F., Margaria-Steffen, T., Pokorný, J., Quisquater, J.-J., Wattenhofer, R.

Publikováno v: Lecture Notes in Computer Science ISBN: 9783662460771
SOFSEM
SOFSEM 2015: Theory and Practice of Computer Science: 41th International Conference on Current Trends in Theory and Practice of Computer Science, Pec pod Sněžkou, Czech Republic, January 24-29, 2015: proceedings, 463-474
STARTPAGE=463;ENDPAGE=474;TITLE=SOFSEM 2015: Theory and Practice of Computer Science

We built a framework for analyzing the contents of large social networks, based on the approximate counting technique developed by Gonen and Shavitt. Our toolbox was used on data from a large forum—boards.ie—the most prominent community website i

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::374ea41bc9d28400f67133ee8086c979
https://doi.org/10.1007/978-3-662-46078-8_38

Nonapproximablity of the normalized information distance

Autor: Terwijn, S.A., Torenvliet, L., Vitányi, P.M.B.

Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of the file involved, using a real-world compression program. This practi

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=narcis______::ca1a80a86633c5906bdd762067dbb023
https://dare.uva.nl/personal/pure/en/publications/nonapproximablity-of-the-normalized-information-distance(1ca22f7e-597a-4b03-8ab5-6f464c690721).html

A Post's program for complexity theory

Autor: Buhrman, H.M., Torenvliet, L.

Publikováno v: Bulletin of the European Association for Theoretical Computer Science, 85, 41-51

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=narcis______::976fe04db2f3558370a89baccd83cd8d
https://dare.uva.nl/personal/pure/en/publications/a-posts-program-for-complexity-theory(c460ea9e-b7c3-442f-a018-7548436a6218).html

A thread algebra with multi-level strategic interleaving

Autor: Bergstra, J.A., Middelburg, C.A., Cooper, S.B., Löwe, B., Torenvliet, L.

Publikováno v: New Computational Paradigms ISBN: 9783540261797
CiE
New Computational Paradigms: First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005. Proceedings, 35-48
STARTPAGE=35;ENDPAGE=48;TITLE=New Computational Paradigms

In a previous paper, we developed an algebraic theory of threads and multi-threads based on strategic interleaving. This theory includes a number of plausible interleaving strategies on thread vectors. The strategic interleaving of a thread vector co

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::670582579c583284846cf7ab840769ba
https://doi.org/10.1007/11494645_5