[ Summary
| Research Interests
| Publications
| Preprints
| Invited and workshop papers
| Theses and technical reports
| Teaching
| Contact ]
Summary
Jakob Grue Simonsen, Dr. Scient., PhD, MBA
Professor at DIKU.
Research Interests
My primary research theme is the mathematics of computation (how to describe the act of performing computations by man, alien, or machine by mathematics). This includes computing and calculations involving mathematical structures that are intrinsically infinite in nature, but must necessarily be computed using only finite resources.
In addition, I maintain a serious professional interest in other areas of computer science such as information retrieval and human-computer interaction.
Currently, I work in the following areas:
I have previously been active in the following areas:
Publications
In (a reasonable approximation to) reverse chronological order.
International peer-reviewed journals:
- [J25] J.A. Avery, J.-Y. Moyen, P. Růžička, "Chains, Antichains, and Complements in Infinite Partition Lattices".
Algebra Universalis 79(2), article 37. Birkhäuser, 2018.
published version
- [J24] C. Kop, J.G. Simonsen, "Complexity Hierarchies and Higher-order Cons-free Term Rewriting".
Logical Methods in Computer Science 13(3), 2017.
published version (open access)
- [J23] S.K. Jakobsen, J.G. Simonsen, "Some Remarks on Real Numbers Induced by First-Order Spectra".
Notre Dame Journal of Formal Logic 57(3), p. 355-368. Duke University Press, 2016.
published version
- [J22] C. Petersen, J.G. Simonsen, C. Lioma, "Power Laws in Information Retrieval".
ACM Transactions on Information Systems 34(2), article 8. The ACM Press, 2016.
published version
- [J21] D. Byrd, J.G. Simonsen, "Towards a Standard Testbed for Optical Music Recognition: Definitions, Metrics, and Page Images".
Journal of New Music Research 44(3), p.169-195. Taylor & Francis, 2015.
published version
- [J20] J. Michalco, J.G. Simonsen, K. Hornbæk, "An Exploration of the Relation between Expectations and User Experience".
International Journal of Human-Computer Interaction 31(9), p. 603-617. Taylor & Francis, 2015.
published version
- [J19] J.G. Simonsen, "A Confluent Rewriting System having no Computable, One-Step, Normalizing Strategy".
ACM Transactions on Computational Logic 16(2), paper 10. The ACM Press, 2015.
published version
- [J18] J. Ketema, J.G. Simonsen, "Least Upper Bounds on the Size of Confluence and Church-Rosser Diagrams in Term Rewriting and Lambda-Calculus".
ACM Transactions on Computational Logic 14(4), paper 7. 2013.
published version
preliminary version
- [J17] J.S.B. Nielsen, J.G. Simonsen, "An Experimental Investigation of the Normality of Irrational Algebraic Numbers".
Mathematics of Computation 82, p. 1837-1858. American Mathematical Society, 2013.
published version
preliminary version
accompanying tables
code
- [J16] A.M. Ben-Amram, N.H. Christensen, J.G. Simonsen, "Models of Computation with no Linear Speedup".
Chicago Journal of Theoretical Computer Science. Vol. 2012, article 7. University of Chicago, 2012.
published version (open access)
- [J15] N.D. Jones, J.G. Simonsen, "Programs = Data = First-Class Citizens in a Computational World".
Philosophical Transactions of the Royal Society A 370, p. 3305-3318. The Royal Society, 2012
published version
preliminary version
- [J14] L. Hartmann, N.D. Jones, J.G. Simonsen, S. Vrist, "Programming in Biomolecular Computation: Programs, Self-Interpretation and Visualisation".
Scientific Annals of Computer Science XXI(1), p. 73-106. University of Iași 2012
published version (open access)
- [J13] J. Ketema, J.G. Simonsen, "Infinitary Combinatory Reduction Systems".
Information and Computation 209(6), p. 893-926. Elsevier, 2011.
published version
- [J12] J.G. Simonsen, "Beta-Shifts, their Languages and Computability".
Theory of Computing Systems 48, p. 297-318. Springer-Verlag, 2011.
published version
preliminary version
- [J11] J. Endrullis, H. Geuvers, J.G. Simonsen, H. Zantema, "Levels of Undecidability in Rewriting".
Information and Computation 209(2), p. 227-245. Elsevier, 2011.
published version
preliminary version
- [J10] J. Ketema, J.G. Simonsen, "Infinitary Combinatory Reduction Systems: Normalising Reduction Strategies".
Logical Methods in Computer Science 6(1), paper 7, 2010.
published version (open access)
- [J9] J. Ketema, J.G. Simonsen, "Infinitary Combinatory Reduction Systems: Confluence".
Logical Methods in Computer Science 5(4), paper 3, 2009.
published version (open access)
- [J8] J.G. Simonsen, "On the Computational Complexity of the Languages of General Symbolic Dynamical Systems and Beta-Shifts".
Theoretical Computer Science 410, p. 4878--4891. Elsevier, 2009.
published version
preliminary version
- [J7] F. Henglein, K.F. Larsen, J.G. Simonsen, C. Stefansen, "POETS: Process-Oriented Event-Driven Transaction Systems".
Journal of Logic and Algebraic Programming 78(5), p. 381-401. Elsevier, 2009.
published version
preliminary version
- [J6] J. Andersen, E. Elsborg, F. Henglein, J.G. Simonsen, C. Stefansen, "Compositional Specification of Commercial Contracts".
International Journal on Software Tools for Technology Transfer 8(6), p.485-516. Springer-Verlag, 2006.
published version
preliminary version
- [J5] J.G. Simonsen "On Local Non-Compactness in Recursive Mathematics"
Mathematical Logic Quarterly 52(4), p. 323-330. Wiley, 2006.
published version
preliminary version
- [J4] J.G. Simonsen, "On Modularity in Infinitary Rewriting".
Information and Computation
204(6), p. 957-988. Elsevier, 2006.
published version
preliminary version
- [J3] J.G. Simonsen "On the Computability of the Topological Entropy of Subshifts"
Discrete Mathematics and Theoretical Computer Science 8, p. 83--96, 2006.
published version (open access).
- [J2] J.G. Simonsen, "Specker Sequences Revisited".
Mathematical Logic Quarterly (formerly Zeitschrift fuer Mathematische Logik und Grundlagen der Mathematik). 51(5), p. 532-540, Wiley, 2005.
preliminary version
- [J1] J.G Simonsen, "On Confluence and Residuals in Cauchy Convergent Transfinite Rewriting"
Information Processing Letters 91(4), p.141-146, Elsevier, 2004.
published version
preliminary version
International peer-reviewed conferences
- [AC34] C. Lioma, J.G. Simonsen, B. Larsen, "Evaluation Measures for Relevance and Credibility in Ranked Lists".
Proceedings of the 3rd ACM International Conference on the Theory of Information Retrieval (ICTIR '17), p. 91-98. The ACM Press, 2017.
published version
- [C33] V. Danos, T. Heindel, I. Garnier, J.G. Simonsen, "Continuous-Time Markov Chains as Transformers of Unbounded Observables".
Proceedings of the 20th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS '17), p. 338-354. Springer-Verlag, 2017.
published version
- [C32] C. Kop, J.G. Simonsen, "The Power of Non-Determinism in Higher-Order Implicit Complexity".
Proceedings of the 26th European Symposium on Programming (ESOP '17), p. 668-695. Springer-Verlag, 2017.
published version
- [C31] C. Petersen, J.G. Simonsen, C. Lioma, K. Järvelin, "Adaptive Distributional Extensions to DFR Ranking".
Proceedings of the 2016 ACM International Conference on Information and Knowledge Management (CIKM '16)", p(.2005-2008 (short paper). The ACM Press, 2016.
published version
- [C30] C. Lioma, F. Tarissan, J.G. Simonsen, C. Petersen, B. Larsen, "Exploiting the Bipartite Structure of Entity Grids for Document Coherence and Retrieval".
Proceedings of the 2016 ACM International Conference on the Theory of Information Retrieval (ICTIR '16), p. 11-20. The ACM Press, 2016.
published version
- [C29] C. Petersen, N. Rotbart, J.G. Simonsen, C. Wulff-Nilsen, "Brief Announcement: Labeling Schemes for Power-Law Graphs".
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC '16), p. 39-31 (brief announcement). The ACM Press, 2016.
published version
- [C28] C. Petersen, N. Rotbart, J.G. Simonsen, C. Wulff-Nilsen, "Near Optimal Adjacency Labeling Schemes for Power-Law Graphs".
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP '16). Schloss Dagstuhl: Leibniz Zentrum für Informatik, 2016.
published version
- [C27] C. Kop, J.G. Simonsen, "Complexity Hierarchies and Higher-Order Cons-Free Rewriting".
Proceedings of the 1st International Conference on Formal Structures for Computation and Deduction (FSCD '16), paper 23. Schloss Dagstuhl: Leibniz-Zentrum für Informatik, 2016
published version (open access)
- [C26] M.K. Rasmussen, G.M. Troiano, M.G. Petersen, J.G. Simonsen, K. Hornbæk, "Sketching Shape-changing Interfaces: Exploring Vocabulary, Metaphors Use, and Affordances".
Proceedings of the ACM SIGCHI Conference on Human Factors in Computing Systems (CHI '16), p. 2740-2751. The ACM Press, 2016
published version
- [C25] C. Petersen, J.G. Simonsen, C. Lioma, "The Impact of Using Combinatorial Optimisation for Static Caching of Posting Lists".
Proceedings of the Asia Information Retrieval Societies Conference (AIRS '15), p. 420-425. Lecture Notes in Computer Science 9460. Springer-Verlag, 2015.
published version
- [C24] C. Petersen, C. Lioma, J.G. Simonsen, B. Larsen, "Entropy and Graph Based Modelling of Document Coherence using Discourse Entities: An Application to Information Retrieval".
Proceedings of the ACM SIGIR International Conference on the Theory of Information Retrieval (ICTIR '15), p.191-200. The ACM Press, 2015
published version
- [C23] A. Sordoni, Y. Bengio, H. Vahabi, C. Lioma, J.G. Simonsen, J.-Y. Nie, "A Hierarchical Recurrent Encoder-Decoder for Generative Context-Aware Query Suggestion".
Proceedings of the 24th ACM International Conference on Information and Knowledge Management (CIKM '15), p. 553-562. The ACM Press, 2015
published version
- [C22] M.G. Grünbaum, J.G. Simonsen, "The Affordances of Broken Affordances".
Proceedings of the 15th IFIP TC.13 International Conference on Human-Computer Interaction (INTERACT '15), p. 185-202. Springer-Verlag, 2015.
published version
- [C21] C. Lioma, J.G. Simonsen, B. Larsen, N.D. Hansen, "Non-Compositional Term Dependence for Information Retrieval".
Proceedings of the 38th Annual ACM Special Interest Group on Information Retrieval Conference (SIGIR '15), p. 595-604. The ACM Press, 2015.
published version
- [C20] S. Hedegaard, J.G. Simonsen, "Mining Until it Hurts: Automatic Extraction of Usability Issues from Online Reviews Compared to Traditional Usability Evaluation".
Proceedings of the 8th Nordic Conference on Human-Computer Interaction (NordiCHI '14), p. 157-166. The ACM Press, 2014.
published version
- [C19] D. de Carvalho, J.G. Simonsen, "An Implicit Characterization of the Polynomial-Time Decidable Sets by Cons-Free Rewriting".
Proceedings of the Joint 25th International Conference on Rewriting Techniques and Applications and 12th International Conference on Typed Lambda Calculi and Applications (RTA-TLCA '14). Lecture Notes in Computer Science 8560, p. 179-193. Springer-Verlag, 2014.
published version
preliminary version with appendices
- [C18] K. Hornb�k, S.S. Sander, J. Bargas-Avila, J.G. Simonsen, "Is Once Enough? On the Extent and Content of Replications in Human-Computer Interaction".
Proceedings of the ACM SIGCHI Conference on Human Factors in Computing Systems (CHI '14), p. 3523-3532. The ACM Press, 2014.
published version (open access)
Received CHI '14 honourable mention (given to at most 5% of submitted papers).
- [C17] S. Hedegaard, J.G. Simonsen, "Extracting Usability and User Experience Information from Online User Reviews".
Proceedings of the ACM SIGCHI Conference on Human Factors in Computing Systems
(CHI '13), p. 2089-2098. The ACM Press, 2013.
published version
preliminary version
Received CHI '13 honourable mention (given to at most 5% of submitted papers).
- [C16] J. Ketema, J.G. Simonsen, "Characterizing Languages by Normalization and Termination in String Rewriting (Extended Abstract)".
Proceedings of the 16th International Conference on Developments in Language Theory (DLT '12) (Short paper).
Lecture Notes in Computer Science 7410,
p. 459-464. Springer Verlag, 2012.
published version
preliminary version
- [C15] S.B. Andersen, J.G. Simonsen, "Term Rewriting Systems as Topological Dynamical Systems".
Proceedings of the 23rd International Conference on Rewriting Techniques and Applications (RTA '12).
LIPIcs 15, p. 53-68
published version (open access)
- [C14] E.P. Bugge, K.L. Juncher, B.S. Mathiesen, J.G. Simonsen, "Using Sequence Alignment and Voting to Improve Optical Music Recognition from Multiple Recognizers".
Proceedings of the 12th International Society for Music Information Retrieval Conference (ISMIR '11).
published version (open access)
- [C13] A. Schnabl, J.G. Simonsen, "The Exact Hardness of Deciding Derivational and Runtime Complexity".
Proceedings of the 20th Conference on Computer Science Logic (CSL '11). LIPIcs 12, p. 481-495
published version (open access)
- [C12] S. Hedegaard, J.G. Simonsen, "Lost in Translation: Authorship Attribution using Frame Semantics".
Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL '11) (Short paper), p.6570
published version (open access)
- [C11] N.B.B. Grathwohl, J. Ketema, J.D. Pallesen, J.G. Simonsen, "Anagopos: A Reduction Graph Visualizer for Term Rewriting and Lambda Calculus".
Proceedings of the 22nd International Conference on Rewriting Techniques and Applications (RTA '11). LIPIcs 10, p. 61-70.
published version (open access)
code
- [C10] C. Appel, V. van Oostrom, J.G. Simonsen, "Higher-Order (Non-)Modularity".
Proceedings of the 21st International Conference on Rewriting Techniques and Applications (RTA '10). LIPIcs 7, p. 17-32. Schloss Dagstuhl, 2010.
published version (open access)
- [C9] J.G. Simonsen, "Weak Convergence and Uniform Normalization in Infinitary Rewriting".
Proceedings of the 21st International Conference on Rewriting Techniques and Applications (RTA '10). LIPIcs 7, p. 311-324. Schloss Dagstuhl, 2010.
published version (open access)
- [C8] J. Ketema, J.G. Simonsen, "Least Upper Bounds on the Size of Church-Rosser Diagrams in Term Rewriting and Lambda Calculus".
Proceedings of the 10th International Symposium on Functional and Logic Programming (FLOPS '10). Lecture Notes in Computer Science 6009, p. 272--287. Springer Verlag, 2010.
published version
preliminary version
- [C7] S. Hedegaard, S. Houen, J.G. Simonsen, "LAIR: A Language for Automated
Semantics-Aware Text Sanitization based on Frame Semantics".
Proceedings of the 3rd IEEE International Conference on Semantic Computing (ICSC '09), p. 47--52. IEEE Computer Society 2009.
published version
preliminary version
- [C6] J.G. Simonsen, "The Π _{0}^{2}-Completeness of most of the Properties of Rewriting You Care About (and Productivity)".
Proceedings of the 20th International Conference on Rewriting Techniques and Applications (RTA '09). Lecture Notes in Computer Science 5595, p. 535--549. Springer Verlag, 2009.
published version
preliminary version
- [C5] J. Ketema, J.G. Simonsen, "On Confluence of Infinitary Combinatory Reduction Systems".
Proceedings of the 12th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR 2005). Lecture Notes in Artificial Intelligence 3835, p. 199--214, Springer-Verlag, 2005.
published version
preliminary version
- [C4] J.G. Simonsen, "On Beta-Shifts having Arithmetical Languages".
Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005). Lecture Notes in Computer Science 3618, p. 757--768, Springer-Verlag, 2005.
published version
preliminary version
- [C3] J. Ketema, J.G. Simonsen, "Infinitary Combinatory Reduction Systems".
Proceedings of the 16th International Conference on Rewriting Techniques and Applications (RTA 2005). Lecture Notes in Computer Science 3467, p. 438--452, Springer-Verlag, 2005.
published version
preliminary version
- [C2] J. Andersen, E. Elsborg, F. Henglein, J.G. Simonsen, C. Stefansen, "Compositional Specification of Commercial Contracts".
Proceedings of the 1st International Symposium on Leveraging Applications of Formal Methods (ISOLA 2004). University of Cyprus Report TR-2004-6, 103-110. University of Cyprus 2005. (Superseded by [J6]).
preliminary version
- [C1] J.G. Simonsen, "On the Modularity of Confluence in Infinitary Term Rewriting".
Proceedings of the 15th International Conference on Rewriting Techniques and Applications (RTA 2004). Lecture Notes in Computer Science 3091, p.185-199, Springer-Verlag, 2004 (Superseded by [J4]).
published version
preliminary version
Received the RTA 2004 Best Paper Award.
(Rigorously) peer-reviewed workshops
- [W5] J. Frey, J.G. Simonsen. "Toposes for Time Complexity Classes". Proceedings of the 7th Workshop on Developments in Implicit Computation (DICE '16).
- [W4] J.-Y. Moyen, J.G. Simonsen. "More Intensional Versions of Rice's Theorem". Proceedings of the 7th Worskshop on Developments in Implicit Computation (DICE '16).
- [W3] C. Petersen, C. Lioma, J.G. Simonsen. "Comparative Study of Search Engine Result Visualisation: Ranked Lists versus Graphs". 3rd European Workshop on Human-Computer Interaction and Information Retrieval (EuroHCIR '13). CEUR Workshop Proceedings 1033, p. 27-30. 2013.
published version (open access)
- [W2] L. Hartmann, N.D. Jones, J.G. Simonsen, "Programming in Biomolecular Computation". 1st International Workshop on Interactions between Computer Science and Biology (CS2Bio '10). Electronic Notes in Theoretical Computer Science 268, p. 97-114. Elsevier, 2010.
published version
preliminary version
- [W1] L. Hartmann, N.D. Jones, J.G. Simonsen, "Interpretive Overhead and Optimal Specialisation. Or: Life without the Pending List". First Workshop on Metacompuation in Russia (META 2008).
Invited papers and papers at lightly refereed workshops
- [A4] L. Hartmann, N.D. Jones, J.G. Simonsen, "Programming in Biomolecular Computation". Nordic Workshop in Programming Theory (NWPT '09) (Superseded, and vastly expanded and improved, by [W2]).
- [A3] M.I. Nielsen, K.F. Larsen, J.G. Simonsen, "Requirements for Logical Models for Value-Added Tax Legislation". Short paper session of the Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR '08).
- [A2] F. Henglein, K.F. Larsen, J.G. Simonsen, C. Stefansen, "Compositional Contract Specification for REA". Invited paper for the First Workshop on Formal Languages and Analysis of Contract-Oriented Software (FLACOS 2007).
- [A1] J.G. Simonsen, "A Factorization Theorem in Higher-Order Rewriting with Application to Modular Reduction Semantics". Brazilian Symposium on Programming Languages (SBLP 2000).
Theses and technical reports
- [D4] J.G. Simonsen, "Rewriting the Finite and the Infinite". Doktordisputats for the degree of Dr. Scient. (equivalent to the French and German Habilitation).
- [D3] J.G. Simonsen, "On Computable Approximation of Infinite Objects". PhD dissertation.
- [D2] J.G. Simonsen, "Higher-Order Rewriting with Applications to Impure Functional Languages". Speciale for the degree of Cand. Scient. (roughly equivalent to a master's thesis).
- [D1] B.M. Andersen, J.G. Simonsen, "Kuglefunktioner" (Eng. "Spherical Harmonics"). Bachelor's thesis, in Danish.
Teaching
Current teaching