umu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 13) Show all publications
Snook, K., Barri, T., Bolles, M., Ericson, P., Fravel, C., Gossmann, J., . . . Thomas, R. (2020). Concordia: A musical XR instrument for playing the solar system. Journal of New Music Research, 49(1), 88-103
Open this publication in new window or tab >>Concordia: A musical XR instrument for playing the solar system
Show others...
2020 (English)In: Journal of New Music Research, ISSN 0929-8215, E-ISSN 1744-5027, Vol. 49, no 1, p. 88-103Article in journal (Refereed) Published
Abstract [en]

Kepler Concordia, a new scientific and musical instrument enabling players to explore the solar system and other data within immersive extended-reality (XR) platforms, is being designed by a diverse team of musicians, artists, scientists and engineers using audio-first principles. The core instrument modules will be launched in 2019 for the 400th anniversary of Johannes Kepler's Harmonies of the World, in which he laid out a framework for the harmony of geometric form as well as the three laws of planetary motion. Kepler's own experimental process can be understood as audio-first because he employed his understanding of Western Classical music theory to investigate and discover the heliocentric, elliptical behaviour of planetary orbits. Indeed, principles of harmonic motion govern much of our physical world and show up at all scales in mathematics and physics. Few physical systems, however, offer such rich harmonic complexity and beauty as our own solar system. Concordia is a musical instrument that is modular, extensible and designed to allow players to generate and explore transparent sonifications of planetary movements rooted in the musical and mathematical concepts of Johannes Kepler as well as researchers who have extended Kepler's work, such as Hartmut Warm. Its primary function is to emphasise the auditory experience by encouraging musical explorations using sonification of geometric and relational information of scientifically accurate planetary ephemeris and astrodynamics. Concordia highlights harmonic relationships of the solar system through interactive sonic immersion. This article explains how we prioritise data sonification and then add visualisations and gamification to create a new type of experience and creative distributed-ledger powered ecosystem. Kepler Concordia facilitates the perception of music while presenting the celestial harmonies through multiple senses, with an emphasis on hearing, so that, as Kepler wrote, 'the mind can seize upon the patterns'.

Place, publisher, year, edition, pages
Routledge, 2020
Keywords
Sonification, astronomy, mathematics, ephemeris, immersive media, musical instruments
National Category
Musicology
Identifiers
urn:nbn:se:umu:diva-168217 (URN)10.1080/09298215.2020.1714666 (DOI)000509212100001 ()
Note

Special Issue.

Available from: 2020-02-27 Created: 2020-02-27 Last updated: 2020-02-27Bibliographically approved
Ericson, P. (2019). Order-preserving graph grammars. (Doctoral dissertation). Umeå: Umeå universitet, Institutionen för datavetenskap
Open this publication in new window or tab >>Order-preserving graph grammars
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
Alternative title[sv]
Ordningsbevarande grafgrammatiker
Abstract [en]

The field of semantic modelling concerns formal models for semantics, that is, formal structures for the computational and algorithmic processing of meaning. This thesis concerns formal graph languages motivated by this field. In particular, we investigate two formalisms: Order-Preserving DAG Grammars (OPDG) and Order-Preserving Hyperedge Replacement Grammars (OPHG), where OPHG generalise OPDG.

Graph parsing is the practise of, given a graph grammar and a graph, to determine if, and in which way, the grammar could have generated the graph. If the grammar is considered fixed, it is the non-uniform graph parsing problem, while if the grammars is considered part of the input, it is named the uniform graph parsing problem. Most graph grammars have parsing problems known to be NP-complete, or even exponential, even in the non-uniform case. We show both OPDG and OPHG to have polynomial uniform parsing problems, under certain assumptions.

We also show these parsing algorithms to be suitable, not just for determining membership in graph languages, but for computing weights of graphs in graph series.

Additionally, OPDG is shown to have several properties common to regular languages, such as MSO definability and MAT learnability. We moreover show a direct corresponcence between OPDG and the regular tree grammars.

Finally, we present some limited practical experiments showing that real-world semantic graphs appear to mostly conform to the requirements set by OPDG, after minimal, reversible processing.

Place, publisher, year, edition, pages
Umeå: Umeå universitet, Institutionen för datavetenskap, 2019. p. 56
Series
Report / UMINF, ISSN 0348-0542 ; 19.01
Keywords
Graph grammars, graph parsing, graph series, hyperedge replacement, uniform parsing problem, abstract meaning representation, semantic modelling, order preservation, reentrancy preservation, minimally adequate teacher, weighted graph grammars
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-154777 (URN)978-91-7855-017-3 (ISBN)
Public defence
2019-02-04, MA121, Umeå, 13:00 (English)
Opponent
Supervisors
Available from: 2019-01-14 Created: 2019-01-07 Last updated: 2019-07-05Bibliographically approved
Björklund, H., Drewes, F. & Ericson, P. (2019). Parsing Weighted Order-Preserving Hyperedge Replacement Grammars. In: F. Drewes, P. de Groote, G. Penn (Ed.), Proceedings of the 16th Meeting on the Mathematics of Language: . Paper presented at 16th Meeting on the Mathematics of Language (MOL 2019), Toronto, Canada, July 18–19, 2019 (pp. 1-11). Association for Computational Linguistics
Open this publication in new window or tab >>Parsing Weighted Order-Preserving Hyperedge Replacement Grammars
2019 (English)In: Proceedings of the 16th Meeting on the Mathematics of Language / [ed] F. Drewes, P. de Groote, G. Penn, Association for Computational Linguistics, 2019, p. 1-11Conference paper, Published paper (Refereed)
Abstract [en]

We introduce a weighted extension of the recently proposed notion oforder-preserving hyperedge-replacement grammars and prove that the weightof a graph according to such a weighted graph grammar can be computeduniformly in quadratic time (under assumptions made precise in the paper).

Place, publisher, year, edition, pages
Association for Computational Linguistics, 2019
Keywords
Graph grammar, Hyperedge replacement, Abstract meaning representation, Weighted uniform parsing
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-159908 (URN)
Conference
16th Meeting on the Mathematics of Language (MOL 2019), Toronto, Canada, July 18–19, 2019
Available from: 2019-06-10 Created: 2019-06-10 Last updated: 2019-10-30Bibliographically approved
Björklund, H., Björklund, J. & Ericson, P. (2018). Minimisation and Characterisation of Order-Preserving DAG Grammars. Umeå: Umeå University
Open this publication in new window or tab >>Minimisation and Characterisation of Order-Preserving DAG Grammars
2018 (English)Report (Other academic)
Abstract [en]

Order-preserving DAG grammars (OPDGs) is a formalism for processing semantic infor- mation in natural languages [5, 4]. OPDGs are sufficiently expressive to model abstract meaning representations, a graph-based form of semantic representation in which nodes en- code objects and edges relations. At the same time, they allow for efficient parsing in the uniform setting, where both the grammar and subject graph are taken as part of the input.

In this article, we introduce an initial algebra semantic for OPDGs, which allows us to view them as regular tree grammars. This makes it possible to transfer a number of results from that domain to OPDGs, both in the unweighted and the weighted case. In particular, we show that deterministic OPDGs can be minimised efficiently, and that they are learnable in the so-called MAT setting. To conclude, we show that the languages generated by OPDGs are MSO-definable.

Place, publisher, year, edition, pages
Umeå: Umeå University, 2018. p. 19
Series
Report / UMINF, ISSN 0348-0542 ; 18.15
Keywords
graph grammars, minimally adequate teacher, order preservation, weighted graph grammars, weighted learning
National Category
Computer Sciences
Research subject
business data processing
Identifiers
urn:nbn:se:umu:diva-153394 (URN)
Available from: 2018-11-19 Created: 2018-11-19 Last updated: 2019-07-05Bibliographically approved
Björklund, H., Drewes, F. & Ericson, P. (2018). Parsing Weighted Order-Preserving Hyperedge Replacement Grammars. Umeå: Umeå Universitet
Open this publication in new window or tab >>Parsing Weighted Order-Preserving Hyperedge Replacement Grammars
2018 (English)Report (Other academic)
Abstract [en]

We introduce a weighted extension of the recently proposed notion of order-preserving hyperedge-replacement grammars and prove that the weight of a graph according to such a weighted graph grammar can be computed uniformly in quadratic time (under assumptions made precise in the paper).

Place, publisher, year, edition, pages
Umeå: Umeå Universitet, 2018. p. 12
Series
Report / UMINF, ISSN 0348-0542 ; 18.16
Keywords
graph grammars, order-preservation, parsing, weighted graph grammars
National Category
Computer Sciences
Research subject
business data processing
Identifiers
urn:nbn:se:umu:diva-153395 (URN)
Available from: 2018-11-19 Created: 2018-11-19 Last updated: 2019-07-05Bibliographically approved
Björklund, H., Drewes, F., Ericson, P. & Starke, F. (2018). Uniform Parsing for Hyperedge Replacement Grammars. Umeå: Umeå universitet
Open this publication in new window or tab >>Uniform Parsing for Hyperedge Replacement Grammars
2018 (English)Report (Other academic)
Abstract [en]

It is well known that hyperedge-replacement grammars can generate NP-complete graph languages even under seemingly harsh restrictions. This means that the parsing problem is difficult even in the non-uniform setting, in which the grammar is considered to be fixed rather than being part of the input. Little is known about restrictions under which truly uniform polynomial parsing is possible. In this paper we propose a low-degree polynomial-time algorithm that solves the uniform parsing problem for a restricted type of hyperedge-replacement grammars which we expect to be of interest for practical applications.

Place, publisher, year, edition, pages
Umeå: Umeå universitet, 2018. p. 21
Series
Report / UMINF, ISSN 0348-0542 ; 18.13
Keywords
graph grammars, hyperedge replacement, order-preserving graph grammars, uniform parsing problem
National Category
Computer Sciences
Research subject
business data processing
Identifiers
urn:nbn:se:umu:diva-153384 (URN)
Available from: 2018-11-19 Created: 2018-11-19 Last updated: 2019-01-07Bibliographically approved
Ericson, P. (2017). Complexity and expressiveness for formal structures in Natural Language Processing. (Licentiate dissertation). Umeå: Umeå Universitet
Open this publication in new window or tab >>Complexity and expressiveness for formal structures in Natural Language Processing
2017 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

The formalized and algorithmic study of human language within the field of Natural Language Processing (NLP) has motivated much theoretical work in the related field of formal languages, in particular the subfields of grammar and automata theory. Motivated and informed by NLP, the papers in this thesis explore the connections between expressibility – that is, the ability for a formal system to define complex sets of objects – and algorithmic complexity – that is, the varying amount of effort required to analyse and utilise such systems. Our research studies formal systems working not just on strings, but on more complex structures such as trees and graphs, in particular syntax trees and semantic graphs. The field of mildly context-sensitive languages concerns attempts to find a useful class of formal languages between the context-free and context-sensitive. We study formalisms defining two candidates for this class; tree-adjoining languages and the languages defined by linear context-free rewriting systems. For the former, we specifically investigate the tree languages, and define a subclass and tree automaton with linear parsing complexity. For the latter, we use the framework of parameterized complexity theory to investigate more deeply the related parsing problems, as well as the connections between various formalisms defining the class. The field of semantic modelling aims towards formally and accurately modelling not only the syntax of natural language statements, but also the meaning. In particular, recent work in semantic graphs motivates our study of graph grammars and graph parsing. To the best of our knowledge, the formalism presented in Paper III of this thesis is the first graph grammar where the uniform parsing problem has polynomial parsing complexity, even for input graphs of unbounded node degree.

Place, publisher, year, edition, pages
Umeå: Umeå Universitet, 2017. p. 18
Series
Report / UMINF, ISSN 0348-0542 ; 17.13
Keywords
graph grammars, formal languages, natural language processing, parameterized complexity, abstract meaning representation, tree automata, deterministic tree-walking transducers, mildly context-sensitive languages, hyperedge replacement, tree adjoining languages, minimally adequate teacher
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-135014 (URN)9789176017227 (ISBN)
Presentation
2017-05-19, MA121, MIT-huset 901 87 Umeå, Umeå, 10:15 (English)
Supervisors
Available from: 2017-05-17 Created: 2017-05-16 Last updated: 2018-06-09Bibliographically approved
Björklund, H., Björklund, J. & Ericson, P. (2017). On the Regularity and Learnability of Ordered DAG Languages. In: Arnaud Carayol and Cyril Nicaud (Ed.), Implementation and Application of Automata: 22nd International Conference, CIAA 2017, Marne-la-Vallée, France, June 27-30, 2017, Proceedings. Paper presented at 22nd International Conference Implementation and Application of Automata, CIAA 2017, Université Paris-Est Marne-la-Vallée, France, 27-30 June 2017 (pp. 27-39). Cham
Open this publication in new window or tab >>On the Regularity and Learnability of Ordered DAG Languages
2017 (English)In: Implementation and Application of Automata: 22nd International Conference, CIAA 2017, Marne-la-Vallée, France, June 27-30, 2017, Proceedings / [ed] Arnaud Carayol and Cyril Nicaud, Cham, 2017, p. 27-39Conference paper, Published paper (Refereed)
Abstract [en]

Order-Preserving DAG Grammars (OPDGs) is a subclass of Hyper-Edge Replacement Grammars that can be parsed in polynomial time. Their associated class of languages is known as Ordered DAG Lan- guages, and the graphs they generate are characterised by being acyclic, rooted, and having a natural order on their nodes. OPDGs are useful in natural-language processing to model abstract meaning representa- tions. We state and prove a Myhill-Nerode theorem for ordered DAG languages, and translate it into a MAT-learning algorithm for the same class. The algorithm infers a minimal OPDG G for the target language in time polynomial in G and the samples provided by the MAT oracle. 

Place, publisher, year, edition, pages
Cham: , 2017
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743, E-ISSN 1611-3349 ; 10329
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-135010 (URN)10.1007/978-3-319-60134-2_3 (DOI)2-s2.0-85022042128 (Scopus ID)978-3-319-60133-5 (ISBN)978-3-319-60134-2 (ISBN)
Conference
22nd International Conference Implementation and Application of Automata, CIAA 2017, Université Paris-Est Marne-la-Vallée, France, 27-30 June 2017
Available from: 2017-05-16 Created: 2017-05-16 Last updated: 2019-07-05Bibliographically approved
Björklund, H., Drewes, F. & Ericson, P. (2016). Between a Rock and a Hard Place: Parsing for Hyperege Replacement DAG Grammars. In: A.H. Dediu, J. Janoušek, C. Martín-Vide, and B. Truthe (Ed.), Proc. 10th International Conference on Language and Automata Theory and Applications (LATA 2016): . Paper presented at 10th International Conference on Language and Automata Theory and Applications (LATA 2016), Prague, Czech Republic, March 14-18, 2016 (pp. 521-532). Springer Publishing Company, 9618
Open this publication in new window or tab >>Between a Rock and a Hard Place: Parsing for Hyperege Replacement DAG Grammars
2016 (English)In: Proc. 10th International Conference on Language and Automata Theory and Applications (LATA 2016) / [ed] A.H. Dediu, J. Janoušek, C. Martín-Vide, and B. Truthe, Springer Publishing Company, 2016, Vol. 9618, p. 521-532Conference paper, Published paper (Refereed)
Abstract [en]

Motivated by applications in natural language processing, we study the uniform membership problem for hyperedge-replacement grammars that generate directed acyclic graphs. Our major result is a low-degree polynomial-time algorithm that solves the uniform membership problem for a restricted type of such grammars. We motivate the necessity of the restrictions by two different NP-completeness results.

Place, publisher, year, edition, pages
Springer Publishing Company, 2016
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9618
Keywords
Graph grammar, Hyperedge replacement, Abstract meaning representation, DAG grammar, Uniform membership problem, Parsing
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-111984 (URN)10.1007/978-3-319-30000-9_40 (DOI)000378745100045 ()978-3-319-30000-9 (ISBN)978-3-319-29999-0 (ISBN)
Conference
10th International Conference on Language and Automata Theory and Applications (LATA 2016), Prague, Czech Republic, March 14-18, 2016
Available from: 2015-11-29 Created: 2015-11-29 Last updated: 2019-01-07Bibliographically approved
Ericson, P. (2016). Investigating different graph representations of semantics. In: : . Paper presented at Sixth Swedish Language Technology Conference (SLTC), Umeå University, 17-18 November, 2016.
Open this publication in new window or tab >>Investigating different graph representations of semantics
2016 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Combinatory Categorial Grammar is a generic approach to the mechanical understanding of language, where movement is minimised in favour of using combinators such as B (composition) and T (type lifting) to clearly define in which ways various constituents can refer to each other. Taking the tree languages induced by the syntactic derivations and connecting the various leaves linked through the semantics, one ends up with a class of graph languages. The present work aims to point out promising avenues of research in order to investigate this class, specifically in terms of similarities with other graph-based semantic representations, such as Abstract Meaning Representations (AMR), and furthermore what graph generating or recognising formalism would be most suitable to define the class characteristics.

National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-134998 (URN)
Conference
Sixth Swedish Language Technology Conference (SLTC), Umeå University, 17-18 November, 2016
Available from: 2017-05-15 Created: 2017-05-15 Last updated: 2018-06-09Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-8722-5661

Search in DiVA

Show all publications