umu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 29) Show all publications
Björklund, H., Drewes, F. & Ericson, P. (2019). Parsing Weighted Order-Preserving Hyperedge Replacement Grammars. In: F. Drewes, P. de Groote, G. Penn (Ed.), Proc. 16th Meeting on the Mathematics of Language (MOL 2019): . Paper presented at 16th Meeting on the Mathematics of Language (MOL 2019), Toronto, Canada, July 18–19, 2019. Association for Computational Linguistics
Open this publication in new window or tab >>Parsing Weighted Order-Preserving Hyperedge Replacement Grammars
2019 (English)In: Proc. 16th Meeting on the Mathematics of Language (MOL 2019) / [ed] F. Drewes, P. de Groote, G. Penn, Association for Computational Linguistics, 2019Conference 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-06-13
Björklund, H., Martens, W. & Schwentick, T. (2018). Conjunctive query containment over trees using schema information. Acta Informatica, 55(1), 17-56
Open this publication in new window or tab >>Conjunctive query containment over trees using schema information
2018 (English)In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 55, no 1, p. 17-56Article in journal (Refereed) Published
Abstract [en]

We study the containment, satisfiability, and validity problems for conjunctive queries over trees with respect to a schema. We show that conjunctive query containment and validity are 2EXPTIME -complete with respect to a schema, in both cases where the schema is given as a DTD or as a tree automaton. Furthermore, we show that satisfiability for conjunctive queries with respect to a schema can be decided in NP . The problem is NP -hard already for queries using only one kind of axis. Finally, we consider conjunctive queries that can test for equalities and inequalities of data values. Here, satisfiability and validity are decidable, but containment is undecidable, even without schema information. On the other hand, containment with respect to a schema becomes decidable again if the "larger" query is not allowed to use both equalities and inequalities.

Place, publisher, year, edition, pages
SPRINGER, 2018
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-144935 (URN)10.1007/s00236-016-0282-1 (DOI)000424053100002 ()
Available from: 2018-02-23 Created: 2018-02-23 Last updated: 2018-06-09Bibliographically 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
Computing Science
Identifiers
urn:nbn:se:umu:diva-153384 (URN)
Available from: 2018-11-19 Created: 2018-11-19 Last updated: 2019-01-07Bibliographically 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
Woldemariam, Y. D., Bensch, S. & Björklund, H. (2017). Predicting User Competence from Linguistic Data. In: Sivaji Bandyopadhyay (Ed.), Proceedings of the 14th International Conference on Natural Language Processing (ICON-2017): . Paper presented at 14th International Conference on Natural Language Processing (ICON-2017) (pp. 476-484). Jadavpur University
Open this publication in new window or tab >>Predicting User Competence from Linguistic Data
2017 (English)In: Proceedings of the 14th International Conference on Natural Language Processing (ICON-2017) / [ed] Sivaji Bandyopadhyay, Jadavpur University , 2017, p. 476-484Conference paper, Published paper (Refereed)
Abstract [en]

We investigate the problem of predicting the competence of users of the crowd-sourcing platform Zooniverse by analyzing their chat texts. Zooniverse is an online platform where objects of different types are displayed to volunteer users to classify. Our research focuses on the Zoonivers Galaxy Zoo project, where users classify the images of galaxies and discuss their classifications in text. We apply natural language processing methods to extract linguistic features including syntactic categories, bag-of-words, and punctuation marks. We trained three supervised machine-learning classifiers on the resulting dataset: k-nearest neighbors, decision trees (with gradient boosting) and naive Bayes. They are evaluated (regarding accuracy and F-measure) with two different but related domain datasets. The performance of the classifiers varies across the feature set configurations designed during the training phase. A challenging part of this research is to compute the competence of the users without ground truth data available. We implemented a tool that estimates the proficiency of users and annotates their text with computed competence. Our evaluation results show that the trained classifier models give results that are significantly better than chance and can be deployed for other crowd-sourcing projects as well. 

Place, publisher, year, edition, pages
Jadavpur University, 2017
National Category
Language Technology (Computational Linguistics)
Identifiers
urn:nbn:se:umu:diva-146185 (URN)
Conference
14th International Conference on Natural Language Processing (ICON-2017)
Available from: 2018-04-03 Created: 2018-04-03 Last updated: 2018-06-09Bibliographically approved
Woldemariam, Y. D., Björklund, H. & Bensch, S. (2017). Predicting User Competence from Linguistic Data. In: Proceedings of the 14th International Conference on Natural Language Processing (ICON-2017): . Paper presented at 14th International Conference on Natural Language Processing (ICON-2017), Kolkata, India, December 18-21, 2017 (pp. 476-484). NLP Association of India
Open this publication in new window or tab >>Predicting User Competence from Linguistic Data
2017 (English)In: Proceedings of the 14th International Conference on Natural Language Processing (ICON-2017), NLP Association of India , 2017, p. 476-484Conference paper, Published paper (Refereed)
Abstract [en]

We investigate the problem of predicting the competence of users of the crowdsourcing platform Zooniverse by analyzing their chat texts. Zooniverse is an online platform where objects of different types are displayed to volunteer users to classify. Our research focuses on the Zoonivers Galaxy Zoo project, where users classify the images of galaxies and discuss their classifications in text. We apply natural language processing methods to extract linguistic features including syntactic categories, bag-of-words, and punctuation marks. We trained three supervised machine-learning classifiers on the resulting dataset: k-nearest neighbors, decision trees (with gradient boosting) and naive Bayes. They are evaluated (regarding accuracy and F-measure) with two different but related domain datasets. The performance of the classifiers varies across the feature set configurations designed during the training phase. A challenging part of this research is to compute the competence of the users without ground truth data available. We implemented a tool that estimates the proficiency of users and annotates their text with computed competence. Our evaluation results show that the trained classifier models give results that are significantly better than chance and can be deployed for other crowd-sourcing projects as well.

Place, publisher, year, edition, pages
NLP Association of India, 2017
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:umu:diva-144304 (URN)
Conference
14th International Conference on Natural Language Processing (ICON-2017), Kolkata, India, December 18-21, 2017
Available from: 2018-01-30 Created: 2018-01-30 Last updated: 2019-06-26Bibliographically approved
Berglund, M., Björklund, H. & Drewes, F. (2017). Single-Rooted DAGs in Regular DAG Languages: Parikh Image and Path Languages. In: M. Kuhlmann, T. Scheffler (Ed.), Proceedings of the 13th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+13): . Paper presented at 13th International Workshop on Tree-Adjoining Grammar and Related Formalisms (TAG+13), Umeå, Sweden, September 4-6, 2017 (pp. 94-101). Association for Computational Linguistics
Open this publication in new window or tab >>Single-Rooted DAGs in Regular DAG Languages: Parikh Image and Path Languages
2017 (English)In: Proceedings of the 13th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+13) / [ed] M. Kuhlmann, T. Scheffler, Association for Computational Linguistics , 2017, p. 94-101Conference paper, Published paper (Refereed)
Abstract [en]

In a recent survey (Drewes, 2017) of results on DAG automata  some open problems are formulated for the case where the  DAG language accepted by a DAG automaton A is restricted to DAGs with a single root, denoted by L(A)u. Here we consider each of  those problems, demonstrating that: (i) the finiteness  of L(A)u is decidable, (ii) the path languages of L(A)u can be characterized in  terms of the string languages accepted by partially blind  multicounter automata, and  (iii) the Parikh image of L(A)u is semilinear.

Place, publisher, year, edition, pages
Association for Computational Linguistics, 2017
Keywords
DAG automaton, regular DAG language
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-137919 (URN)
Conference
13th International Workshop on Tree-Adjoining Grammar and Related Formalisms (TAG+13), Umeå, Sweden, September 4-6, 2017
Available from: 2017-07-31 Created: 2017-07-31 Last updated: 2019-06-19Bibliographically 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
Projects
Parameterized Natural Language Parsing [2011-06080_VR]; Umeå University
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-4696-9787

Search in DiVA

Show all publications