Umeå University's logo

umu.sePublications
Change search
Refine search result
12 1 - 50 of 67
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1. Abdulla, Parosh Aziz
    et al.
    Högberg, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Kaati, Lisa
    Bisimulation minimization of tree automata2007In: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 18, no 4, p. 699-713Article in journal (Refereed)
    Abstract [en]

    We extend an algorithm by Paige and Tarjan that solves the coarsest stable refinement problem to the domain of trees. The algorithm is used to minimize nondeterministic tree automata (NTA) with respect to bisimulation. We show that our algorithm has an overall complexity of $O(\hat{r} m \log n)$, where $\hat{r}$ is the maximum rank of any symbol in the input alphabet, m is the total size of the transition table, and n is the number of states.

  • 2. Abdulla, Parosh Aziz
    et al.
    Katti, Lisa
    Högberg, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Bisimulation minimization of tree automata2006In: Implementation and Application of Automata : 11th International Conference, CIAA 2006, 2006, p. 699-713Conference paper (Refereed)
    Abstract [en]

    We extend an algorithm by Paige and Tarjan that solves the coarsest stable refinement problem to the domain of trees. The algorithm is used to minimize nondeterministic tree automata (NTA) with respect to bisimulation. We show that our algorithm has an overall complexity of O ((r) over cap log n), where (r) over cap is the maximum rank of any symbol in the input alphabet, m is the total size of the transition table, and n is the number of states.

  • 3. Aichroth, Patrick
    et al.
    Weigel, Christian
    Kurz, Thomas
    Stadler, Horst
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Schlegel, Kai
    Berndl, Emanuel
    Perez, Antonio
    Bowyer, Alex
    Volpini, Andrea
    MICO - MEDIA IN CONTEXT2015In: 2015 IEEE International Conference on Multimedia & Expo Workshops (ICMEW), 2015Conference paper (Refereed)
    Abstract [en]

    The abundance of digital content requires cost-effective technologies to extract the hidden meaning from media objects. However, current approaches fail to deal with the challenges related to cross-media analysis, metadata publishing, querying and recommendation that are necessary to overcome this challenge. In this paper, we describe the EU project MICO (Media in Context) which aims to provide the necessary technologies based on open-source software (OSS) core components.

  • 4.
    Andersson, Eric
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Jonsson, Anna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Generating semantic graph corpora with graph expansion grammar2023In: 13th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2023) / [ed] Nagy B., Freund R., Open Publishing Association , 2023, Vol. 388, p. 3-15Conference paper (Refereed)
    Abstract [en]

    We introduce LOVELACE, a tool for creating corpora of semantic graphs.The system uses graph expansion grammar as  a representational language, thus allowing users to craft a grammar that describes a corpus with desired properties. When given such grammar as input, the system generates a set of output graphs that are well-formed according to the grammar, i.e., a graph bank.The generation process can be controlled via a number of configurable parameters that allow the user to, for example, specify a range of desired output graph sizes.Central use cases are the creation of synthetic data to augment existing corpora, and as a pedagogical tool for teaching formal language theory. 

    Download full text (pdf)
    fulltext
  • 5.
    Bensch, Suna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Kutrib, Martin
    Deterministic Stack Transducers2017In: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 28, no 5, p. 583-601Article in journal (Refereed)
    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.

  • 6.
    Bensch, Suna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Kutrib, Martin
    Institut fur Informatik, Universität Giessen.
    Deterministic Stack Transducers2016In: Implementation and Application of Automata / [ed] Yo-Sub Han and Kai Salomaa, Springer, 2016, p. 27-38Conference paper (Refereed)
    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.

  • 7.
    Berglund, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Henrik
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Parsing unranked tree languages, folded once2023In: Fundamentals of computation theory: 24th International Symposium, FCT 2023, Trier, Germany, September 18–21, 2023, Proceedings / [ed] Henning Fernau; Klaus Jansen, Springer Nature, 2023, p. 60-73Conference paper (Refereed)
    Abstract [en]

    A regular unranked tree folding consists of a regular unranked tree language and a folding operation that merges, i.e., folds, selected nodes of a tree to form a graph; the combination is a formal device for representing graph languages. If, in the process of folding, the order among edges is discarded so that the result is an unordered graph, then two applications of a fold operation is enough to make the associated parsing problem NP-complete. However, if the order is kept, then the problem is solvable in non-uniform polynomial time. In this paper we address the remaining case where only one fold operation is applied, but the order among edges is discarded. We show that under these conditions, the problem is solvable in non-uniform polynomial time.

  • 8.
    Berglund, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Henrik
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Shuffled languages: representation and recognition2013In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 489-490, p. 1-20Article in journal (Refereed)
    Abstract [en]

    Language models that use interleaving, or shuffle, operators have applications in various areas of computer science, including system verification, plan recognition, and natural language processing. We study the complexity of the membership problem for such models, in other words, how difficult it is to determine if a string belongs to a language or not. In particular, we investigate how interleaving can be introduced into models that capture the context-free languages.

  • 9.
    Berglund, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Henrik
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Boiret, Adrien
    Laboratoire d'Informatique d'Orléans & INSA CVL, France.
    Transduction from trees to graphs through folding2023In: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 295, article id 105111Article in journal (Refereed)
    Abstract [en]

    We introduce a fold operation that realises a tree-to-graph transduction by merging selected nodes in the input tree to form a possibly cyclic output graph. The work is motivated by the increasing use of graph-based representations in semantic parsing. We show that a suitable class of graphs languages can be generated by applying the fold operation to regular unranked tree languages. We investigate two versions of the fold operation, one that preserves a depth-first ordering between the edges, and one that does not. Finally, we demonstrate that the time complexity for the associated non-uniform membership problem is solvable in polynomial time for the order-preserving version, and NP-complete for the order-cancelling one.

    Download full text (pdf)
    fulltext
  • 10.
    Berglund, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Henrik
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Högberg, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Recognizing Shuffled Languages2011Report (Other academic)
    Abstract [en]

    Language models that use interleaving, or shuffle, operators have applications in various areas of computer science, including system verification, plan recognition, and natural language processing. We study the complexity of the membership problem for such models, i.e., how difficult it is to determine if a string belongs to a language or not. In particular, we investigate how interleaving can be introduced into models that capture the context-free languages.

  • 11.
    Berglund, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Henrik
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Högberg, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Recognizing shuffled languages2011In: Language and Automata Theory and Applications: 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings / [ed] Adrian-Horia Dediu, Shunsuke Inenaga and Carlos Martín-Vide, Springer Berlin/Heidelberg, 2011, p. 142-154Conference paper (Refereed)
    Abstract [en]

    Language models that use interleaving, or shuffle, operators have applications in various areas of computer science, including system verification, plan recognition, and natural language processing. We study the complexity of the membership problem for such models, i.e., how difficult it is to determine if a string belongs to a language or not. In particular, we investigate how interleaving can be introduced into models that capture the context-free languages.

  • 12.
    Bjorklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Fernau, Henning
    Kasprzik, Anna
    Polynomial inference of universal automata from membership and equivalence queries2016In: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 246, p. 3-19Article in journal (Refereed)
    Abstract [en]

    A MAT learning algorithm is presented that infers the universal automaton (UA) for a regular target language, using a polynomial number of queries with respect to that automaton. The UA is one of several canonical characterizations for regular languages. Our learner is based on the concept of an observation table, which seems to be particularly fitting for this computational model, and the necessary definitions are adapted from the literature to the case of UA. 

  • 13.
    Bjorklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Zechner, Niklas
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    My name is legion: estimating author counts based on stylistic diversity2016In: 2016 European intelligence and security informatics conference (EISIC) / [ed] Brynielsson J., Johansson F., IEEE , 2016, p. 108-111Conference paper (Refereed)
    Abstract [en]

    Online propaganda is a growing concern. Fraudulent users write under multiple signatures to give the impression that the opinions they promote are more widespread than they really are, or held by a different demography. The problem as such is not new, but it is becoming increasingly organised and therefore has effects on a larger scale. In this work, we develop methods for assessing the true number of authors of a body of work, to detect artificially inflated user sets. The assessments are based on stylistic richness, here measured as the number of unique features (e.g., words or syntactic fragments) divided by the sum of all features. Initial results suggest that the order of magnitude can be reliable estimated. It is for example possible to differentiate the works of hundreds and thousands of writers.

  • 14.
    Björklund, Henrik
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Dahlgren, Adam
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Demeke, Yonas
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Implementing a speech-to-text pipeline on the MICO platform2016Report (Other academic)
    Abstract [en]

    MICO is an open-source platform for cross-media analysis, querying, and recommendation. It is the major outcome of the European research project Media in Context, and has been contributed to by academic and industrial partners from Germany, Austria, Sweden, Italy, and the UK. A central idea is to group sets of related media objects into multimodal content items, and to process and store these as logical units. The platform is designed to be easy to extend and adapt, and this makes it a useful building block for a diverse set of multimedia applications. To promote the platform and demonstrate its potential, we describe our work on a Kaldi-based speech-recognition pipeline.

    Download full text (pdf)
    fulltext
  • 15.
    Björklund, Henrik
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Ericson, Petter
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Minimisation and Characterisation of Order-Preserving DAG Grammars2018Report (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.

    Download full text (pdf)
    fulltext
  • 16.
    Björklund, Henrik
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Ericson, Petter
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    On the Regularity and Learnability of Ordered DAG Languages2017In: 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 (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. 

  • 17.
    Björklund, Henrik
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Ericson, Petter
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Tree-based generation of restricted graph languages2024In: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 35, no 1 & 2, p. 215-243Article in journal (Refereed)
    Abstract [en]

    Order-preserving DAG grammars (OPDGs) is a formalism for representing languages of structurally restricted graphs. As demonstrated in [17], they are sufficiently expressive to model abstract meaning representations in natural language processing, a graph-based form of semantic representation in which nodes encode objects and edges relations. At the same time, they can be parsed in O (n2 + nm) , where m and n are the sizes of the grammar and the input graph, respectively. In this work, we provide an initial algebra semantic for OPDGs, which allows us to view them as regular tree grammars under an equivalence theory. This makes it possible to transfer results from the field of formal tree languages to the domain of 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 under the \minimal adequeate teacher" paradigm, that is, by querying an oracle for equivalence between languages, and membership of individual graphs. To conclude, we demonstrate that the languages generated by OPDGs are definable in monadic second-order logic.

    Download full text (pdf)
    fulltext
  • 18.
    Björklund, Henrik
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Zechner, Niklas
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Compression of finite-state automata through failure transitions2014In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 557, p. 87-100Article in journal (Refereed)
    Abstract [en]

    Several linear-time algorithms for automata-based pattern matching rely on failure transitions for efficient back-tracking. Like epsilon transitions, failure transition do not consume input symbols, but unlike them, they may only be taken when no other transition is applicable. At a semantic level, this conveniently models catch-all clauses and allows for compact language representation.

    This work investigates the transition-reduction problem for deterministic finite-state automata (DFA). The input is a DFA A and an integer k. The question is whether k or more transitions can be saved by replacing regular transitions with failure transitions. We show that while the problem is NP-complete, there are approximation techniques and heuristics that mitigate the computational complexity. We conclude by demonstrating the computational difficulty of two related minimisation problems, thereby cancelling the ongoing search for efficient algorithms.

    Download full text (pdf)
    fulltext
  • 19.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    The impact of state merging on predictive accuracy in probabilistic tree automata: Dietze’s conjecture revisited2023In: Fundamentals of computation theory: 24th International Symposium, FCT 2023, Trier, Germany, September 18–21, 2023, Proceedings / [ed] Henning Fernau; Klaus Jansen, Springer Nature, 2023, p. 74-87Conference paper (Refereed)
    Abstract [en]

    Dietze’s conjecture concerns the problem of equipping a tree automaton M with weights to make it probabilistic, in such a way that the resulting automaton N predicts a given corpus C as accurately as possible. The conjecture states that the accuracy cannot increase if the states in M are merged with respect to an equivalence relation ∼ so that the result is a smaller automaton M∼. Put differently, merging states can never improve predictions. This is under the assumption that both M and M∼ are bottom-up deterministic and accept every tree in C. We prove that the conjecture holds, using a construction that turns any probabilistic version N∼ of M∼ into a probabilistic version N of M, such that N assigns at least as great a weight to each tree in C as N∼ does.

  • 20.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Tree-to-Graph Transductions with Scope2018In: Developments in Language Theory. DLT 2018., Springer, 2018, p. 133-144Conference paper (Refereed)
    Abstract [en]

    High-level natural language processing requires formal languages to represent semantic information. A recent addition of this kind is abstract meaning representations. These are graphs in which nodes encode concepts and edges relations. Node-sharing is common, and cycles occur. We show that the required structures can be generated through the combination of (i) a regular tree grammar, (ii) a sequence of linear top-down tree transducers, and (iii) a fold operator that merges selected nodes. Delimiting the application of the fold operator to connected subgraphs gains expressive power, while keeping the complexity of the associated membership problem in polynomial time.

  • 21.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Cleophas, Loek
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Stellenbosch University, ZA-7602 Matieland, South Africa.
    A Taxonomy of Minimisation Algorithms for Deterministic Tree Automata2016In: Journal of universal computer science (Online), ISSN 0948-695X, E-ISSN 0948-6968, Vol. 22, no 2, p. 180-196Article in journal (Refereed)
    Abstract [en]

    We present a taxonomy of algorithms for minimising deterministic bottom-up tree automata (DTAs) over ranked and ordered trees. Automata of this type and its extensions are used in many application areas, including natural language processing (NLP) and code generation. In practice, DTAs can grow very large, but minimisation keeps things manageable. The proposed taxonomy serves as a unifying framework that makes algorithms accessible and comparable, and as a foundation for efficient implementation. Taxonomies of this type are also convenient for correctness and complexity analysis, as results can frequently be propagated through the hierarchy. The taxonomy described herein covers a broad spectrum of algorithms, ranging from novel to well-studied ones, with a focus on computational complexity.

    Download full text (pdf)
    fulltext
  • 22.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Cleophas, Loek
    Aggregation-based minimization of finite state automata2021In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 58, p. 177-194Article in journal (Refereed)
    Abstract [en]

    We present a minimization algorithm for non-deterministic finite state automata that finds and merges bisimulation-equivalent states. The bisimulation relation is computed through partition aggregation, in contrast to existing algorithms that use partition refinement. The algorithm simultaneously generalises and simplifies an earlier one by Watson and Daciuk for deterministic devices. We show the algorithm to be correct and run in time O(n2r2|Σ|), where n is the number of states of the input automaton M, r is the maximal out-degree in the transition graph for any combination of state and input symbol, and |Σ| is the size of the input alphabet. The algorithm has a higher time complexity than derivatives of Hopcroft’s partition-refinement algorithm, but represents a promising new solution approach that preserves language equivalence throughout the computation process. Furthermore, since the algorithm essentially computes the maximal model of a logical formula derived from M, optimisation techniques from the field of model checking become applicable.

    Download full text (pdf)
    fulltext
  • 23.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Cleophas, Loek
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Department of Information Science, Stellenbosch University, Stellenbosch, South Africa.
    Minimization of Finite State Automata Through Partition Aggregation2016In: Logical Aspects of Computational Linguistics: Celebrating 20 Years of LACL (1996–2016) / [ed] Amblard, M DeGroote, P Pogodalla, S Retore, C, SPRINGER-VERLAG BERLIN , 2016, p. 328-328Conference paper (Refereed)
  • 24.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Cleophas, Loek
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Department of Information Science, Stellenbosch University, Stellenbosch, South Africa.
    Minimization of Finite State Automata Through Partition Aggregation2017In: 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, p. 223-235Conference paper (Refereed)
    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.

  • 25.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Cleophas, Loek
    Stellenbosch University, Republic of South Africa.
    Karlsson, My
    Codemill.
    An evaluation of structured language modeling for automatic speech recognition2017In: Journal of universal computer science (Online), ISSN 0948-695X, E-ISSN 0948-6968, Vol. 23, no 11, p. 1019-1034Article in journal (Refereed)
    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.

  • 26.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Cohen, Shay B.
    University of Edinburgh, United Kingdom.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Satta, Giorgio
    University of Padova, Italy.
    Bottom-up unranked tree-to-graph transducers for translation into semantic graphs2021In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 870, p. 3-28Article in journal (Refereed)
    Abstract [en]

    We develop a finite-state transducer for translating unranked trees into general graphs. This work is motivated by recent progress in semantic parsing for natural language, where sentences are first mapped into tree-shaped syntactic representations, and then these trees are translated into graph semantic representations. We investigate formal properties of our tree-to-graph transducers and develop a polynomial time algorithm for translating a weighted language of input trees into a packed representation, from which best-score graphs can be efficiently recovered.

    Download full text (pdf)
    fulltext
  • 27.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Cohen, Shay B.
    University of Edinburgh.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Satta, Giorgio
    University of Padova.
    Bottom-up unranked tree-to-graph transducers for translation into semantic graphs2019In: Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing / [ed] Heiko Vogler; Andreas Maletti, Association for Computational Linguistics, 2019, p. 7-17, article id W19-3104Conference paper (Refereed)
    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.

  • 28.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Dahlgren Lindström, Adam
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Bridging Perception, Memory, and Inference through Semantic Relations2021In: Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, Association for Computational Linguistics (ACL) , 2021, p. 9136-9142Conference paper (Refereed)
    Abstract [en]

    There is a growing consensus that surface form alone does not enable models to learn meaning and gain language understanding. This warrants an interest in hybrid systems that combine the strengths of neural and symbolic methods. We favour triadic systems consisting of neural networks, knowledge bases, and inference engines. The network provides perception, that is, the interface between the system and its environment. The knowledge base provides explicit memory and thus immediate access to established facts. Finally, inference capabilities are provided by the inference engine which reflects on the perception, supported by memory, to reason and discover new facts. In this work, we probe six popular language models for semantic relations and outline a future line of research to study how the constituent subsystems can be jointly realised and integrated.

  • 29.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Jonsson, Anna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    A Comparative Evaluation of the Efficiency of N-Best Algorithms on Language DataManuscript (preprint) (Other academic)
    Abstract [en]

    The N-best extraction problem consists in selecting the N highest ranking hypotheses from a set of hypotheses, with respect to a given ranking system. In our setting, the hypotheses and ranking are jointly represented by a weighted tree automaton (wta) over the tropical semiring: the hypotheses are trees, or runs on trees, and the ranking is decided by the weight assigned to them. In previous work, we presented an algorithm for N-best extraction that combines techniques to restrict the search space, and proved it to be correct and efficient. The algorithm is now implemented in the software Betty, allowing us to complement the deductive study with an empirical investigation.  In particular, we compare our algorithm to the state-of-the-art algorithm for extracting the N best runs, implemented in in the software toolkit Tiburon. The data sets used in the experiments are wtas resulting from real-world natural language processing tasks, as well as artificially created wtas with varying degrees of nondeterminism. We find that Betty outperforms Tiburon on all tested data sets.

  • 30.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Jonsson, Anna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    A Comparison of Two N-Best Extraction Methods for Weighted Tree Automata2018In: Implementation and Application of Automata: 23rd International Conference, CIAA 2018, Charlottetown, PE, Canada, July 30 – August 2, 2018, Proceedings, Springer, 2018, p. 197-108Conference paper (Refereed)
    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.

  • 31.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Jonsson, Anna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Faster Computation of N-Best Lists for Weighted Tree AutomataManuscript (preprint) (Other academic)
    Abstract [en]

    We show that a previously proposed algorithm for the N-best trees problem – not to be confused with the easier N-best runs problem – can be made more efficient by changing how it arranges and explores the search space. Given an integer N and a weighted tree automaton (wta) M over the tropical semiring, the algorithm computes N trees of minimal weight with respect to M. Compared to the original algorithm, the modifications increase the laziness of the evaluation strategy, which makes the new algorithm asymptotically more efficient than its predecessor. 

  • 32.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Jonsson, Anna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Finding the N Best Vertices in an Infinite Weighted Hypergraph2017In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 682, p. 78p. 30-41Article in journal (Refereed)
    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. 

  • 33.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Jonsson, Anna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Generation and polynomial parsing of graph languages with non-structural reentrancies2023In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 49, no 4, p. 841-882Article in journal (Refereed)
    Abstract [en]

    Graph-based semantic representations are popular in natural language processing (NLP), where it is often convenient to model linguistic concepts as nodes and relations as edges between them. Several attempts have been made to find a generative device that is sufficiently powerful to describe languages of semantic graphs, while at the same allowing efficient parsing. We contribute to this line of work by introducing graph extension grammar, a variant of the contextual hyperedge replacement grammars proposed by Hoffmann et al. Contextual hyperedge replacement can generate graphs with non-structural reentrancies, a type of node-sharing that is very common in formalisms such as abstract meaning representation, but which context-free types of graph grammars cannot model. To provide our formalism with a way to place reentrancies in a linguistically meaningful way, we endow rules with logical formulas in counting monadic second-order logic. We then present a parsing algorithm and show as our main result that this algorithm runs in polynomial time on graph languages generated by a subclass of our grammars, the so-called local graph extension grammars.

    Download full text (pdf)
    fulltext
  • 34.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Jonsson, Anna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Improved N-Best Extraction with an Evaluation on Language Data2022In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 48, no 1, p. 119-153Article in journal (Refereed)
    Abstract [en]

    We show that a previously proposed algorithm for the N-best trees problem can be made more efficient by changing how it arranges and explores the search space. Given an integer N and a weighted tree automaton (wta) M over the tropical semiring, the algorithm computes N trees of minimal weight with respect to M. Compared with the original algorithm, the modifications increase the laziness of the evaluation strategy, which makes the new algorithm asymptotically more efficient than its predecessor. The algorithm is implemented in the software BETTY, and compared to the state-of-the-art algorithm for extracting the N best runs, implemented in the software toolkit TIBURON. The data sets used in the experiments are wtas resulting from real-world natural language processing tasks, as well as artificially created wtas with varying degrees of nondeterminism. We find that BETTY outperforms TIBURON on all tested data sets with respect to running time, while TIBURON seems to be the more memory-efficient choice.

    Download full text (pdf)
    fulltext
  • 35.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Jonsson, Anna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    On the N best problem for hypergraphs2016In: / [ed] A. Maletti, 2016Conference paper (Other academic)
    Abstract [en]

    We propose an algorithm for computing the $N$ best roots of a weighted hypergraph, in which the weight function is given over an idempotent and multiplicatively monotone semiring. We give a set of conditions that ensures that the weight function is well-defined and that solutions exist. Under these conditions, we prove that the proposed algorithm is correct.  This generalizes a previous result for weighted tree automata, and in doing so, broadens the practical applications.

  • 36.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Jonsson, Anna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Polynomial Graph Parsing with Non-Structural ReentranciesManuscript (preprint) (Other academic)
    Abstract [en]

    Graph-based semantic representations are valuable in natural language processing, where it is often simple and effective to represent linguistic concepts as nodes, and relations as edges between them. Several attempts has been made to find a generative device that is sufficiently powerful to represent languages of semantic graphs, while at the same allowing efficient parsing. We add to this line of work by introducing graph extension grammar, which consists of an algebra over graphs together with a regular tree grammar that generates expressions over the operations of the algebra. Due to the design of the operations, these grammars can generate graphs with non-structural reentrancies, a type of node-sharing that is excessively common in formalisms such as abstract meaning representation, but for which existing devices offer little support. We provide a parsing algorithm for graph extension grammars, which is proved to be correct and run in polynomial time. 

  • 37.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Mollevik, Iris
    Towards Semantic Representations with a Temporal Dimension2020Conference paper (Refereed)
    Abstract [en]

    We outline the initial ideas for a representational framework for capturing temporal aspects in semantic parsing of multimodal data.As a starting point, we take the Abstract Meaning Representations of Banarescu et al. andpropose a way of extending them to coversequential progressions of events. The firstmodality to be considered is text, but the long-term goal is to also incorporate informationfrom visual and audio modalities, as well ascontextual information.

    Download full text (pdf)
    fulltext
  • 38.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Satta, Giorgio
    University of Padova, Italy.
    Z-Automata for Compact and Direct Representation of Unranked Tree Languages2019In: 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, p. 83-94Conference paper (Refereed)
    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.

  • 39.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Zechner, Niklas
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    An efficient best-trees algorithm for weighted tree automata over the tropical semiring2015In: Proc. 9th International Conference on Language and Automata Theory and Applications / [ed] Adrian-Horia Dediu, Enrico Formenti, Carlos Martín-Vide, and Bianca Truthe, Springer, 2015, p. 97-108Conference paper (Refereed)
    Abstract [en]

    We generalise a search algorithm by Mohri and Riley from strings to trees. The original algorithm takes as input a weighted automaton M over the tropical semiring, together with an integer N, and outputs N strings of minimal weight with respect to M. In our setting, M defines a weighted tree language, again over the tropical semiring, and the output is a set of N trees with minimal weight. 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.

  • 40.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Zechner, Niklas
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Efficient enumeration of weighted tree languages over the tropical semiring2019In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 104, p. 78p. 119-130Article in journal (Refereed)
    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. 

  • 41.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Fernau, Henning
    FB IV - Abteilung Informatikwissenschaften, Universität Trier, Trier, Germany.
    Learning tree languages2016In: Topics in grammatical inference / [ed] Jeffrey Heinz; José M. Sempere, Springer Berlin/Heidelberg, 2016, p. 173-214Chapter in book (Refereed)
    Abstract [en]

    Tree languages have proved to be a versatile and rewarding extension of the classical notion of string languages.Many nice applications have been established over the years, in areas such as Natural Language Processing, Information Extraction, and Computational Biology. Although some properties of string languages transfer easily to the tree case, in particular for regular languages, several computational aspects turn out to be harder. It is therefore both of theoretical and of practical interest to investigate howfar and in whatways Grammatical Inference algorithms developed for the string case are applicable to trees. This chapter surveys known results in this direction. We begin by recalling the basics of tree language theory. Then, the most popular learning scenarios and algorithms are presented. Several applications of Grammatical Inference of tree languages are reviewed in some detail. We conclude by suggesting a number of directions for future research.

  • 42.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Fernau, Henning
    Trier University.
    Kasprzik, Anna
    Trier University.
    MAT Learning of Universal Automata2013In: Language and Automata Theory and Applications: 7th International Conference, LATA 2013, Bilbao, Spain, April 2-5, 2013. Proceedings / [ed] Adrian-Horia Dediu, Carlos Martín-Vide, Bianca Truthe, Springer Berlin/Heidelberg, 2013, p. 141-152Conference paper (Refereed)
    Abstract [en]

    A MAT learning algorithm is presented that infers the universal automaton (UA) for a regular target language, using a polynomial number of queries with respect to that automaton. The UA is one of several canonical characterizations for regular languages. Our learner is based on the concept of an observation table, which seems to be particularly fitting for this computational model, and the necessary notions and definitions are adapted from the literature to the case of UA.

  • 43.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Johansson Falck, Marlene
    Umeå University, Faculty of Arts, Department of language studies.
    How Spatial Relations Structure Linguistic Meaning2019In: Proceedings of the 15th SweCog Conference / [ed] Holm, Linus & Erik Billing, Skövde: University of Skövde , 2019, p. 29-31Conference paper (Refereed)
  • 44.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Jönsson, Eric
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Kaati, Lisa
    Swedish Defence Research Institute.
    Aspects of plan operators in a tree automata framework2012In: 2012 15th International Conference on Information Fusion (FUSION), IEEE , 2012, p. 1462-1467Conference paper (Refereed)
    Abstract [en]

    Plan recognition addresses the problem of inferring an agents goals from its action. Applications range from anticipating care-takers’ needs to predicting volatile situations. In this contribution, we describe a prototype plan recognition system that is based on the well-researched theory of (weighted) finite tree automata. To illustrate the system’s capabilities, we use data gathered from matches in the real-time strategy game StarCraft II. Finally, we discuss how more advanced plan operators can be accommodated for in this framework while retaining computational efficiency by taking after the field of formal model checking and over-approximating the target language.

  • 45.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Zechner, Niklas
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Syntactic methods for topic-independent authorship attribution2017In: Natural Language Engineering, ISSN 1351-3249, E-ISSN 1469-8110, Vol. 23, no 5, p. 789-806Article in journal (Refereed)
    Abstract [en]

    The efficacy of syntactic features for topic-independent authorship attribution is evaluated, taking a feature set of frequencies of words and punctuation marks as baseline. The features are 'deep' in the sense that they are derived by parsing the subject texts, in contrast to 'shallow' syntactic features for which a part-of-speech analysis is enough. The experiments are made on two corpora of online texts and one corpus of novels written around the year 1900. The classification tasks include classical closed-world authorship attribution, identification of separate texts among the works of one author, and cross-topic authorship attribution. In the first tasks, the feature sets were fairly evenly matched, but for the last task, the syntax-based feature set outperformed the baseline feature set. These results suggest that, compared to lexical features, syntactic features are more robust to changes in topic.

  • 46.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Simulation relations for pattern matching in directed graphs2013In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 485, p. 1-15Article in journal (Refereed)
    Abstract [en]

    We consider the problem of finding the occurrences of a pattern tree t in a directed graph g, and propose two algorithms, one for preprocessing and one for searching for t in g. It is assumed that the object graph itself is large and static, and that the pattern tree is small and frequently updated. To model varying abstraction levels in the data, we work with partially ordered alphabets and compute simulation relations rather than equivalence relations. In particular, vertices and edges are labelled with elements from a pair of preorders instead of unstructured alphabets. Under the above assumptions, we obtain a search algorithm that runs in time O(height (t) . vertical bar t vertical bar . vertical bar(V-g(+/-)t/R-g(+/-)t vertical bar(2)) where vertical bar (V-g(+/-)t/R-g(+/-)t)vertical bar is the number of equivalence classes in the coarsest simulation relation R-g(+/-)t on the graph g((+/-))t, the disjoint union of g and t. This means that the size of the object graph only affects the running time of the search algorithm indirectly, because of the groundwork done by the preprocessing routine in time O(k . vertical bar g vertical bar . vertical bar(V-g/R-g)vertical bar(2)), where vertical bar(V-g/R-g) is the number of equivalence classes in the coarsest simulation relation R-g on g, taking k = vertical bar V-g vertical bar(2) in the general case and k = height (g) if g is acyclic.

  • 47.
    Brynolfsson, Joel
    et al.
    Swedish Defence Research Agency (FOI).
    Högberg, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Kaati, Lisa
    Swedish Defence Research Agency (FOI).
    Mårtensson, Christian
    Swedish Defence Research Agency (FOI).
    Svenson, Pontus
    Swedish Defence Research Agency (FOI).
    Abstraction techniques for social networks2010In: Proceedings of the 2010 International Conference on Advances in Social Networks Analysis and Mining, IEEE, 2010Conference paper (Refereed)
  • 48.
    Dahlgren Lindström, Adam
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Bensch, Suna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Probing Multimodal Embeddings for Linguistic Properties: the Visual-Semantic Case2020In: Proceedings of the 28th International Conference on Computational Linguistics (COLING), 2020, p. 730-744Conference paper (Refereed)
    Abstract [en]

    Semantic embeddings have advanced the state of the art for countless natural language processing tasks, and various extensions to multimodal domains, such as visual-semantic embeddings, have been proposed. While the power of visual-semantic embeddings comes from the distillation and enrichment of information through machine learning, their inner workings are poorly understood and there is a shortage of analysis tools. To address this problem, we generalize the notion of probing tasks to the visual-semantic case. To this end, we (i) discuss the formalization of probing tasks for embeddings of image-caption pairs, (ii) define three concrete probing tasks within our general framework, (iii) train classifiers to probe for those properties, and (iv) compare various state-of-the-art embeddings under the lens of the proposed probing tasks. Our experiments reveal an up to 12% increase in accuracy on visual-semantic embeddings compared to the corresponding unimodal embeddings, which suggest that the text and image dimensions represented in the former do complement each other

    Download full text (pdf)
    fulltext
  • 49.
    Drewes, Frank
    et al.
    Umeå University, Faculty of Science and Technology, Computing Science.
    Ewert, Sigrid
    Högberg, Johanna
    Umeå University, Faculty of Science and Technology, Computing Science.
    van der Walt, Brink
    van der Walt, Andries
    Random Context Tree Grammars and Tree Transducers.2005In: South African Computer Journal, ISSN 1015-7999, Vol. 34, p. 11-25Article in journal (Refereed)
  • 50.
    Drewes, Frank
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Högberg, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    An Algebra for Tree-Based Music Generation2007In: Algebraic Informatics: 2nd international conference, CAI 2007, Berlin: Springer , 2007, p. 172-188Conference paper (Refereed)
    Abstract [en]

    We present an algebra whose operations act on musical pieces, and show how this algebra can be used to generate music in a tree-based fashion. Starting from input which is either generated by a regular tree grammar or provided by the user via a digital keyboard, a sequence of tree transducers is applied to generate a tree over the operations provided by the music algebra. The evaluation of this tree yields the musical piece generated.

12 1 - 50 of 67
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf