umu.sePublikationer
Ändra sökning
Länk till posten
Permanent länk

Direktlänk
BETA
Björklund, Johanna
Alternativa namn
Publikationer (10 of 42) Visa alla publikationer
Björklund, J., Cohen, S. B., Drewes, F. & Satta, G. (2019). Bottom-Up Unranked Tree-to-Graph Transducers for Translation into Semantic Graphs. In: Heiko Vogler, Andreas Maletti (Ed.), Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing: . Paper presented at The 14th International Conference on Finite-State Methods and Natural Language Processing, FSMNLP, Dresden, Germany, September 23–25, 2019 (pp. 7-17). Association for Computational Linguistics, Article ID W19-3104.
Öppna denna publikation i ny flik eller fönster >>Bottom-Up Unranked Tree-to-Graph Transducers for Translation into Semantic Graphs
2019 (Engelska)Ingår i: Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing / [ed] Heiko Vogler, Andreas Maletti, Association for Computational Linguistics, 2019, s. 7-17, artikel-id W19-3104Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

We propose a formal model for translating unranked syntactic trees, such as dependency trees, into semantic graphs. These tree-to-graph transducers can serve as a formal basis of transition systems for semantic parsing which recently have been shown to perform very well, yet hitherto lack formalization. Our model features "extended" rules and an arc-factored normal form, comes with an efficient translation algorithm, and can be equipped with weights in a straightforward manner.

Ort, förlag, år, upplaga, sidor
Association for Computational Linguistics, 2019
Nationell ämneskategori
Datavetenskap (datalogi) Språkteknologi (språkvetenskaplig databehandling)
Forskningsämne
datalogi; datorlingvistik
Identifikatorer
urn:nbn:se:umu:diva-162561 (URN)
Konferens
The 14th International Conference on Finite-State Methods and Natural Language Processing, FSMNLP, Dresden, Germany, September 23–25, 2019
Tillgänglig från: 2019-08-22 Skapad: 2019-08-22 Senast uppdaterad: 2019-10-30Bibliografiskt granskad
Björklund, J., Drewes, F. & Zechner, N. (2019). Efficient enumeration of weighted tree languages over the tropical semiring. Journal of computer and system sciences (Print), 104, 119-130
Öppna denna publikation i ny flik eller fönster >>Efficient enumeration of weighted tree languages over the tropical semiring
2019 (Engelska)Ingår i: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 104, s. 78s. 119-130Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We generalise a search algorithm by Mohri and Riley from strings to trees. The original algorithm takes as input a nondeterministic weighted automaton M over the tropical semiring and an integer N, and outputs N strings of minimal weight with respect to M. In our setting, M is a weighted tree automaton, again over the tropical semiring, and the output is a set of N trees with minimal weight in this language. We prove that the algorithm is correct, and that its time complexity is a low polynomial in N and the relevant size parameters of M. 

Förlag
s. 78
Nyckelord
weighted tree automaton, N-best analysis, tropical semiring
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
urn:nbn:se:umu:diva-132963 (URN)10.1016/j.jcss.2017.03.006 (DOI)000472246300008 ()
Tillgänglig från: 2017-03-27 Skapad: 2017-03-27 Senast uppdaterad: 2019-07-12Bibliografiskt granskad
Björklund, J. & Johansson Falck, M. (2019). How Spatial Relations Structure Linguistic Meaning. In: Holm, Linus & Erik Billing (Ed.), Proceedings of the 15th SweCog Conference: . Paper presented at The 15th SWECOG Conference, 7-8 November, 2019, Umeå (pp. 29-31). Skövde: University of Skövde
Öppna denna publikation i ny flik eller fönster >>How Spatial Relations Structure Linguistic Meaning
2019 (Engelska)Ingår i: Proceedings of the 15th SweCog Conference / [ed] Holm, Linus & Erik Billing, Skövde: University of Skövde , 2019, s. 29-31Konferensbidrag, Publicerat paper (Refereegranskat)
Ort, förlag, år, upplaga, sidor
Skövde: University of Skövde, 2019
Serie
Skövde University Studies in Informatics, ISSN 1653-2325 ; 2019:2
Nyckelord
Corpora analysis, Prepositional phrases, Semantics
Nationell ämneskategori
Språkteknologi (språkvetenskaplig databehandling)
Forskningsämne
datorlingvistik; språkvetenskap
Identifikatorer
urn:nbn:se:umu:diva-165024 (URN)978-91-983667-5-4 (ISBN)
Konferens
The 15th SWECOG Conference, 7-8 November, 2019, Umeå
Tillgänglig från: 2019-11-06 Skapad: 2019-11-06 Senast uppdaterad: 2019-11-11
Björklund, J., Drewes, F. & Satta, G. (2019). Z-Automata for Compact and Direct Representation of Unranked Tree Languages. In: Michal Hospodár, Galina Jirásková (Ed.), Implementation and Application of Automata: 24th International Conference, CIAA 2019 Košice, Slovakia, July 22–25, 2019, Proceedings. Paper presented at Implementation and Application of Automata - 24th International Conference (CIAA 2019), Slovakia, July 22-25, 2019 (pp. 83-94). Springer
Öppna denna publikation i ny flik eller fönster >>Z-Automata for Compact and Direct Representation of Unranked Tree Languages
2019 (Engelska)Ingår i: Implementation and Application of Automata: 24th International Conference, CIAA 2019 Košice, Slovakia, July 22–25, 2019, Proceedings / [ed] Michal Hospodár, Galina Jirásková, Springer, 2019, s. 83-94Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Unranked tree languages are valuable in natural language processing for modelling dependency trees. We introduce a new type of automaton for unranked tree languages, called Z-automaton, that is tailored for this particular application. The Z-automaton offers a compact form of representation, and unlike the closely related notion of stepwise automata, does not require a binary encoding of its input. We establish an arc-factored normal form, and prove the membership problem of Z-automata in normal form to be in O(mn), where m is the size of the transition table of the Z-automaton and n is the size of the input tree.

Ort, förlag, år, upplaga, sidor
Springer, 2019
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 11601
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
urn:nbn:se:umu:diva-158624 (URN)10.1007/978-3-030-23679-3_7 (DOI)978-3-030-23678-6 (ISBN)978-3-030-23679-3 (ISBN)
Konferens
Implementation and Application of Automata - 24th International Conference (CIAA 2019), Slovakia, July 22-25, 2019
Tillgänglig från: 2019-05-03 Skapad: 2019-05-03 Senast uppdaterad: 2019-10-29Bibliografiskt granskad
Björklund, J., Drewes, F. & Jonsson, A. (2018). A Comparison of Two N-Best Extraction Methods for Weighted Tree Automata. In: Implementation and Application of Automata: 23rd International Conference, CIAA 2018, Charlottetown, PE, Canada, July 30 – August 2, 2018, Proceedings. Paper presented at 23rd International Conference on Implementation and Applications of Automata (CIAA 2018), Charlottetown, Canada, July 30-August 2, 2018 (pp. 197-108). Springer
Öppna denna publikation i ny flik eller fönster >>A Comparison of Two N-Best Extraction Methods for Weighted Tree Automata
2018 (Engelska)Ingår i: Implementation and Application of Automata: 23rd International Conference, CIAA 2018, Charlottetown, PE, Canada, July 30 – August 2, 2018, Proceedings, Springer, 2018, s. 197-108Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

We conduct a comparative study of two state-of-the-art al- gorithms for extracting the N best trees from a weighted tree automaton (wta). The algorithms are Best Trees, which uses a priority queue to structure the search space, and Filtered Runs, which is based on an algorithm by Huang and Chiang that extracts N best runs, implemented as part of the Tiburon wta toolkit. The experiments are run on four data sets, each consisting of a sequence of wtas of increasing sizes. Our conclusion is that Best Trees can be recommended when the input wtas exhibit a high or unpredictable degree of nondeterminism, whereas Filtered Runs is the better option when the input wtas are large but essentially deterministic.

Ort, förlag, år, upplaga, sidor
Springer, 2018
Serie
Lecture Notes in Computer Science
Nyckelord
N-best list, tree automaton
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
urn:nbn:se:umu:diva-149994 (URN)10.1007/978-3-319-94812-6_9 (DOI)000469285600009 ()978-3-319-94812-6 (ISBN)978-3-319-94811-9 (ISBN)
Konferens
23rd International Conference on Implementation and Applications of Automata (CIAA 2018), Charlottetown, Canada, July 30-August 2, 2018
Tillgänglig från: 2018-06-30 Skapad: 2018-06-30 Senast uppdaterad: 2019-06-20Bibliografiskt granskad
Björklund, H., Björklund, J. & Ericson, P. (2018). Minimisation and Characterisation of Order-Preserving DAG Grammars. Umeå: Umeå University
Öppna denna publikation i ny flik eller fönster >>Minimisation and Characterisation of Order-Preserving DAG Grammars
2018 (Engelska)Rapport (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
Umeå: Umeå University, 2018. s. 19
Serie
Report / UMINF, ISSN 0348-0542 ; 18.15
Nyckelord
graph grammars, minimally adequate teacher, order preservation, weighted graph grammars, weighted learning
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
administrativ databehandling
Identifikatorer
urn:nbn:se:umu:diva-153394 (URN)
Tillgänglig från: 2018-11-19 Skapad: 2018-11-19 Senast uppdaterad: 2019-07-05Bibliografiskt granskad
Björklund, J., Cleophas, L. & Karlsson, M. (2017). An evaluation of structured language modeling for automatic speech recognition. Journal of universal computer science (Online), 23(11), 1019-1034
Öppna denna publikation i ny flik eller fönster >>An evaluation of structured language modeling for automatic speech recognition
2017 (Engelska)Ingår i: Journal of universal computer science (Online), ISSN 0948-695X, E-ISSN 0948-6968, Vol. 23, nr 11, s. 1019-1034Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We evaluated probabilistic lexicalized tree-insertion grammars (PLTIGs) on a classification task relevant for automatic speech recognition. The baseline is a family of n-gram models tuned with Witten-Bell smoothing. The language models are trained on unannotated corpora, consisting of 10,000 to 50,000 sentences collected from the English section of Wikipedia. For the evaluation, an additional 150 random sentences were selected from the same source, and for each of these, approximately 3,200 variations were generated. Each variant sentence was obtained by replacing an arbitrary word by a similar word, chosen to be at most 2 character edits from the original. The evaluation task consisted of identifying the original sentence among the automatically constructed (and typically inferior) alternatives. In the experiments, the n-gram models outperformed the PLTIG model on the smaller data set, but as the size of data grew, the PLTIG model gave comparable results. While PLTIGs are more demanding to train, they have the advantage that they assign a parse structure to their input sentences. This is valuable for continued algorithmic processing, for example, for summarization or sentiment analysis.

Ort, förlag, år, upplaga, sidor
Graz: Graz university of technology, Institute for information systems computer media IICM, 2017
Nyckelord
language modeling, automatic speech recognition, probabilistic lexicalized tree-insertion grammars
Nationell ämneskategori
Språkteknologi (språkvetenskaplig databehandling)
Identifikatorer
urn:nbn:se:umu:diva-147230 (URN)10.3217/jucs-023-11-1019 (DOI)000429070900002 ()
Tillgänglig från: 2018-05-02 Skapad: 2018-05-02 Senast uppdaterad: 2019-04-29Bibliografiskt granskad
Bensch, S., Björklund, J. & Kutrib, M. (2017). Deterministic Stack Transducers. Paper presented at 21st International Conference on Implementation and Application of Automata (CIAA), JUL 19-22, 2016, Yonsei Univ, Seoul, SOUTH KOREA. International Journal of Foundations of Computer Science, 28(5), 583-601
Öppna denna publikation i ny flik eller fönster >>Deterministic Stack Transducers
2017 (Engelska)Ingår i: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 28, nr 5, s. 583-601Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We introduce and investigate stack transducers, which are one-way stack automata with an output tape. A one-way stack automaton is a classical pushdown automaton with the additional ability to move the stack head inside the stack without altering the contents. For stack transducers, we distinguish between a digging and a non-digging mode. In digging mode, the stack transducer can write on the output tape when its stack head is inside the stack, whereas in non-digging mode, the stack transducer is only allowed to emit symbols when its stack head is at the top of the stack. These stack transducers have a motivation from natural-language interface applications, as they capture long-distance dependencies in syntactic, semantic, and discourse structures. We study the computational capacity for deterministic digging and non-digging stack transducers, as well as for their non-erasing and checking versions. We finally show that even for the strongest variant of stack transducers the stack languages are regular.

Ort, förlag, år, upplaga, sidor
World Scientific Publishing Co. Pte. Ltd., 2017
Nyckelord
Stack transducers, automata theory, computational capacity
Nationell ämneskategori
Datorsystem
Identifikatorer
urn:nbn:se:umu:diva-143669 (URN)10.1142/S0129054117400081 (DOI)000418091500010 ()
Konferens
21st International Conference on Implementation and Application of Automata (CIAA), JUL 19-22, 2016, Yonsei Univ, Seoul, SOUTH KOREA
Tillgänglig från: 2018-01-05 Skapad: 2018-01-05 Senast uppdaterad: 2018-06-09Bibliografiskt granskad
Björklund, J., Drewes, F. & Jonsson, A. (2017). Finding the N Best Vertices in an Infinite Weighted Hypergraph. Theoretical Computer Science, 682, 30-41
Öppna denna publikation i ny flik eller fönster >>Finding the N Best Vertices in an Infinite Weighted Hypergraph
2017 (Engelska)Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 682, s. 78s. 30-41Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We propose an algorithm for computing the N best vertices in a weighted acyclic hypergraph over a nice semiring. A semiring is nice if it is finitely-generated, idempotent, and has 1 as its minimal element. We then apply the algorithm to the problem of computing the N best trees with respect to a weighted tree automaton, and complement theoretical correctness and complexity arguments with experimental data. The algorithm has several practical applications in natural language processing, for example, to derive the N most likely parse trees with respect to a probabilistic context-free grammar. 

Ort, förlag, år, upplaga, sidor
Elsevier, 2017. s. 78
Nyckelord
Hypergraph, N-best problem, Idempotent semiring
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
urn:nbn:se:umu:diva-132501 (URN)10.1016/j.tcs.2017.03.010 (DOI)000405062100005 ()
Anmärkning

Special Issue: SI

Tillgänglig från: 2017-03-15 Skapad: 2017-03-15 Senast uppdaterad: 2018-11-29Bibliografiskt granskad
Björklund, J. & Cleophas, L. (2017). Minimization of Finite State Automata Through Partition Aggregation. In: Drewes, F Martin-Vide, C Truthe, B (Ed.), Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings. Paper presented at 11th International Conference on Language and Automata Theory and Applications (LATA), MAR 06-09, 2017, Umeå, SWEDEN (pp. 223-235). Springer International Publishing AG
Öppna denna publikation i ny flik eller fönster >>Minimization of Finite State Automata Through Partition Aggregation
2017 (Engelska)Ingår i: Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings / [ed] Drewes, F Martin-Vide, C Truthe, B, Springer International Publishing AG , 2017, s. 223-235Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

We present a minimization algorithm for finite state automata that finds and merges bisimulation-equivalent states, identified through partition aggregation. We show the algorithm to be correct and run in time O(n(2)d(2) vertical bar Sigma vertical bar), where n is the number of states of the input automaton M, d is the maximal outdegree in the transition graph for any combination of state and input symbol, and vertical bar Sigma vertical bar is the size of the input alphabet. The algorithm is slower than those based on partition refinement, but has the advantage that intermediate solutions are also language equivalent to M. As a result, the algorithm can be interrupted or put on hold as needed, and the derived automaton is still useful. Furthermore, the algorithm essentially searches for the maximal model of a characteristic formula for M, so many of the optimisation techniques used to gain efficiency in SAT solvers are likely to apply.

Ort, förlag, år, upplaga, sidor
Springer International Publishing AG, 2017
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 10168
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:umu:diva-144128 (URN)10.1007/978-3-319-53733-7_16 (DOI)000418579700016 ()978-3-319-53732-0 (ISBN)978-3-319-53733-7 (ISBN)
Konferens
11th International Conference on Language and Automata Theory and Applications (LATA), MAR 06-09, 2017, Umeå, SWEDEN
Tillgänglig från: 2018-01-22 Skapad: 2018-01-22 Senast uppdaterad: 2018-06-09Bibliografiskt granskad
Organisationer

Sök vidare i DiVA

Visa alla publikationer