umu.sePublications
Change search
Refine search result
1 - 40 of 40
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.
    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.

  • 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.
    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.

  • 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.
    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.

  • 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.
    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.

  • 9.
    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. 

  • 10.
    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.

  • 11.
    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.

  • 12.
    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. 

  • 13.
    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.

  • 14.
    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.

  • 15.
    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.

  • 16.
    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)
  • 17.
    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
    Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N). 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.

  • 18.
    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.

  • 19.
    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. 

  • 20.
    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.

  • 21.
    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.
    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.

  • 22.
    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.

  • 23.
    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. 

  • 24.
    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.

  • 25.
    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.

  • 26.
    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.

  • 27.
    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.

  • 28.
    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)
  • 29.
    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)
  • 30.
    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.

  • 31.
    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.
    Extensions of a MAT Learner for Regular Tree Languages2006In: Proceedings of SAIS 2006: 23rd Annual Workshop of the Swedish Artificial Intelligence Society, Umeå: Swedish Artificial Intelligence Society - SAIS , 2006, p. 35-44Conference paper (Refereed)
    Abstract [en]

    In an earlier paper, we proposed a learning algorithm for regular tree languages in the Minimal Adequate Teacher model and investigated its complexity from a theoretical  perspective. Here, we focus on more practical issues. We discuss a concrete implementation made available on the web, which includes two extensions of the basic algorithm. In the paper, the usefulness of these extensions is studied in an experimental setting, by running the variants of the algorithm against target languages with different characteristics.

  • 32.
    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.
    Query Learning of Regular Tree Languages: How to Avoid Dead States2007In: Theory of Computing Systems, ISSN 1432-4350, E-ISSN 1433-0490, Vol. 40, no 2, p. 163-185Article in journal (Refereed)
    Abstract [en]

    We generalize an inference algorithm by Angluin, that learns a regular string language from a "minimally adequate teacher", to regular tree languages. The (deterministic bottom-up) finite tree automaton constructed by the learning algorithm is the minimal partial one recognizing the unknown language. This improves a similar algorithm proposed by Sakakibara by avoiding dead states both in the resulting automaton and the learning phase, which also leads to a considerable improvement with respect to efficiency.

  • 33.
    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.
    Maletti, Andreas
    Universitat Rovira i Virgili, Departament de Filologies Rom aniques.
    MAT Learners for Tree Series - an AbstractData Type and Two Realizations2009Report (Other academic)
    Abstract [en]

    We propose abstract observation tables, an abstract datatype for learning deterministic weighted tree automata in Angluin's minimal adequate teacher model. Besides the "classical" observation table,we show that abstract observation tables can also be implemented byobservation trees. The advantage of the latter is that they often requirefewer queries to the teacher.

  • 34.
    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.
    Maletti, Andreas
    MAT learners for tree series: an abstract data type and two realizations2011In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 48, no 3, p. 165-189Article in journal (Refereed)
    Abstract [en]

    We propose abstract observation tables, an abstract data type for learning deterministic weighted tree automata in Angluin’s minimal adequate teacher (MAT) model, and show that every correct implementation of abstract observation tables yields a correct MAT learner. Besides the “classical” observation table, we show that abstract observation tables can also be implemented by observation trees. The advantage of the latter is that they often require fewer queries to the teacher.

  • 35.
    Högberg, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Adding syntactical information to the vector space model2008In: SLTC 2008: the second Swedish language technology conference, 2008, p. 27-28Conference paper (Refereed)
    Abstract [en]

    We describe an on-going research effort that studies a generalisation of the vector space model, in which the target domain is syntactically annotated text and the index set consists of fractions of parse trees.

  • 36.
    Högberg, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    An inference algorithm for regular tree languages2011In: Natural Language Engineering, ISSN 1351-3249, E-ISSN 1469-8110, Vol. 17, no 2, p. 203-219Article in journal (Refereed)
    Abstract [en]

    We present a randomized inference algorithm for regular tree languages. The algorithm takes as input two disjoint finite nonempty sets of trees P and N, and outputs a nondeterministic finite tree automaton that accepts every tree in P, and rejects every tree in N. The output automaton typically represents a non-trivial generalisation of the examples given in P and N. To obtain compact output automata, we use a heuristics similar to bisimulation minimization.The algorithm has time complexity of O(|N||P|^2). Experiments are conducted on a prototype implementation, and the empirical results appear to second the theoretical results.

  • 37.
    Högberg, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Contributions to the theory and applications of tree languages2007Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    This thesis is concerned with theoretical as well as practical aspects of tree languages. It consists of an introduction and eight papers, organised into three parts. The first part is devoted to algorithmic learning of regular tree languages, the second part to bisimulation minimisation of tree automata, and the third part to tree-based generation of music. We now summarise the contributions made in each part.

    In Part I, an inference algorithm for regular tree languages is presented. The algorithm is a generalisation of a previous algorithm by Angluin, and the learning task is to derive, with the aid of a so-called MAT-oracle, the minimal (partial and deterministic) finite tree automaton M that recognises the target language U over some ranked alphabet Σ. The algorithm executes in time O(|Q| |δ| (m + |Q|)), where Q and δ are the set of states and the transition table of M , respectively, r is the maximal rank of any symbol in Σ, and m is the maximum size of any answer given by the oracle. This improves on a similar algorithm by Sakakibara as dead states are avoided both in the learning phase and in the resulting automaton. Part I also describes a concrete implementation which includes two extensions of the basic algorithm.

    In Part II, bisimulation minimisation of nondeterministic weighted tree automata (henceforth, wta) is introduced in general, and for finite tree automata (which can be seen as wta over the Boolean semiring) in particular. The concepts of backward and forward bisimulation are extended to wta, and efficient minimisation algorithms are developed for both types of bisimulation. In the special case where the underlying semiring of the input automaton is either cancellative or Boolean, these minimisation algorithms can be further optimised by adapting existing partition refinement algorithms by Hopcroft, Paige, and Tarjan. The implemented minimisation algorithms are demonstrated on a typical task in natural language processing.

    In Part III, we consider how tree-based generation can be applied to algorithmic composition. An algebra is presented whose operations act on musical pieces, and a system capable of generating simple musical pieces is implemented in the software Treebag: starting from input which is either generated by a regular tree grammar or provided by the user via a digital keyboard, a number of top-down tree transducers are applied to generate a tree over the operations provided by the music algebra. The evaluation of this tree yields the musical piece generated.

  • 38.
    Högberg, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Kaati, Lisa
    Swedish Defence Research Agency (FOI).
    Weighted unranked tree automata as a framework for plan recognition2010In: Fusion 2010, 2010Conference paper (Other academic)
  • 39.
    Högberg, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Maletti, Andreas
    May, Jonathan
    Backward and forward bisimulation minimisation of tree automata2007In: Implementation and Application of Automata: 12th International Conference, CIAA 2007, 2007Conference paper (Refereed)
    Abstract [en]

    We improve an existing bisimulation minimisation algorithm for tree automata by introducing backward and forward bisimulations and developing minimisation algorithms for them. Minimisation via forward bisimulation is effective for deterministic automata and faster than the previous algorithm. Minimisation via backward bisimulation generalises the previous algorithm and is thus more effective but just as fast. We demonstrate implementations of these algorithms on a typical task in natural language processing.

  • 40.
    Högberg, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Maletti, Andreas
    Vogler, Heiko
    Bisimulation mimisation of weighted automata on unranked trees2009In: Fundamenta Informaticae, ISSN 0169-2968, E-ISSN 1875-8681, Vol. 92, no 1-2, p. 103-130Article in journal (Refereed)
    Abstract [en]

    Several models of automata are available that operate unranked trees. Two well-known examples are the stepwise unranked tree automaton (suta) and the parallel unranked tree automaton (puta). By adding a weight, taken from some semiring, to every transition we generalise these two qualitative automata models to quantitative models, thereby obtaining weighted stepwise unranked tree automata (wsuta) and weighted parallel unranked tree automata (wputa); the qualitative automata models are reobtained by choosing the BOOLEAN semiring. The weighted versions have applications in natural language processing, XML-based data management and quantitative information retrieval. We address the minimisation problem of wsuta and wputa by using (forward and backward) bisimulations and we prove the following results: (1) for every wsuta an equivalent forward (resp. backward) bisimulation minimal wsuta can be computed in time O(mn) where n is the number of states and m is the number of transitions of the given wsuta; (2) the same result is proved for wputa instead of wsuta; (3) if the semiring is additive cancellative or the BOOLEAN semiring, then the bound can be improved to O(mlog n) for both wsuta and wputa; (4) for every deterministic puta we can compute a minimal equivalent deterministic puta in time O(mlog n); (5) the automata models wsuta, wputa, and weighted unranked tree automaton have the same computational power.

1 - 40 of 40
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