umu.sePublikationer
Ändra sökning
Avgränsa sökresultatet
12 1 - 50 av 86
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 1. Aichroth, Patrick
    et al.
    Weigel, Christian
    Kurz, Thomas
    Stadler, Horst
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Björklund, Johanna
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Schlegel, Kai
    Berndl, Emanuel
    Perez, Antonio
    Bowyer, Alex
    Volpini, Andrea
    MICO - MEDIA IN CONTEXT2015Ingår i: 2015 IEEE International Conference on Multimedia & Expo Workshops (ICMEW), 2015Konferensbidrag (Refereegranskat)
    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.

  • 2.
    Bensch, Suna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Björklund, Henrik
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Algorithmic properties of Millstream systems2010Ingår i: Developments in Language Theory: 14th International Conference, DLT 2010 / [ed] Sheng Yu, Springer Berlin/Heidelberg, 2010, s. 54-65Konferensbidrag (Refereegranskat)
    Abstract [en]

    Millstream systems have recently been proposed as a formalization of the linguistic idea that natural language should be described as a combination of different modules related by interfaces. In this paper we investigate algorithmic properties of Millstream systems having regular tree grammars as modules and MSO logic as interface logic. We focus on the so-called completion problem: Given trees generated by a subset of the modules, can they be completed into a valid configuration of the Millstream system?

  • 3.
    Bensch, Suna
    et al.
    Umeå universitet, Teknisk-naturvetenskaplig fakultet, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskaplig fakultet, Institutionen för datavetenskap.
    Millstream Systems2009Rapport (Övrigt vetenskapligt)
    Abstract [en]

    We introduce Millstream systems, a mathematical framework in the tradition of the Theory of Computation that uses logic to formalize the interfaces between different aspects of language, the latter being described by any number of independent modules. Unlike other approaches that serve a similar goal, Millstream systems neither presuppose nor establish a particular linguistic theory or focus, but can be instantiated in various ways to accomodate different points of view.

  • 4.
    Bensch, Suna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Millstream Systems: a formal model for linking language modules by interfaces2010Ingår i: Proc. ACL 2010 Workshop on Applications of Tree Automata in Natural Language Processing (ATANLP 2010), The Association for Computer Linguistics , 2010Konferensbidrag (Refereegranskat)
  • 5.
    Bensch, Suna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, FrankUmeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Proceedings of Umeå's 16th student conference in computing science: USCCS 20132013Proceedings (redaktörskap) (Övrigt vetenskapligt)
  • 6.
    Bensch, Suna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, FrankUmeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.Freund, RudolfTechnical University Vienna.Otto, FriedrichTechnical University Kassel.
    Fifth Workshop on Non-Classical Models for Automata and Applications - NCMA 2013, Umeå, Sweden, August 13 - August 14, 2013, Proceedings2013Proceedings (redaktörskap) (Refereegranskat)
  • 7.
    Bensch, Suna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Hellström, Thomas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Grammatical Inference of Graph Transformation Rules2015Ingår i: Proceedings of the 7th Workshop on Non-Classical Modelsof Automata and Applications (NCMA 2015), Austrian Computer Society , 2015, s. 73-90Konferensbidrag (Refereegranskat)
  • 8.
    Bensch, Suna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, FrankUmeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.Hirvensalo, MikaOtto, Friedrich
    Fundamenta Informaticae: special issue2015Proceedings (redaktörskap) (Övrigt vetenskapligt)
  • 9.
    Bensch, Suna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Jürgensen, Helmut
    Department of Computer Science, The University of Western Ontario, London, Canada.
    van der Merwe, Brink
    Department of Computer Science, Stellenbosch University, South Africa.
    Correct readers for the incremental construction of Millstream configurations by graph transformation2012Rapport (Övrigt vetenskapligt)
    Abstract [en]

    Millstream systems have been proposed as a non-hierarchical method for modelling natural language. Millstream congurations represent and connect multiple structural aspects of sentences. We present a method by which the Millstream congurations corresponding to a sentence are constructed. The construction is incremental, that is, it proceeds as the sentence is being read and is complete when the end of the sentence is reached. It is based on graph transformations and a lexicon which associates words with rules for the graph transformations.

  • 10.
    Bensch, Suna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Jürgensen, Helmut
    The University of Western Ontario.
    van der Merwe, Brink
    University of Stellenbosch.
    Correct Readers for the Incremental Construction of Millstream Configurations by Graph TransformationManuskript (preprint) (Övrigt vetenskapligt)
  • 11.
    Bensch, Suna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Jürgensen, Helmut
    Department of Computer Science, Western University, London, Canada.
    van der Merwe, Brink
    Department of Computer Science, Stellenbosch University, South Africa.
    Graph transformation for incremental natural language analysis2014Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 531, s. 1-25Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Millstream systems have been proposed as a non-hierarchical method for modelling natural language. Millstream configurations represent and connect multiple structural aspects of sentences. We present a method by which the Millstream configurations corresponding to a sentence are constructed. The construction is incremental, that is, it proceeds as the sentence is being read and is complete when the end of the sentence is reached. It is based on graph transformations and a lexicon which associates words with graph transformation rules that implement the incremental construction process.

  • 12.
    Bensch, Suna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Jürgensen, Helmut
    Middlesex College, The University of Western Ontario.
    van der Merwe, Brink
    Department of Mathematical Sciences, University of Stellenbosch.
    Incremental Construction of Millstream Configurations Using Graph Transformation2011Ingår i: Proceedings of the 9th International Workshop on Finite State Methods and Natural Language Processing, Stroudsburg: Association for Computational Linguistics , 2011, s. 93-97Konferensbidrag (Refereegranskat)
  • 13.
    Berglund, Martin
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank (Bidragsgivare)
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Characterizing Non-Regularity2014Rapport (Övrigt vetenskapligt)
    Abstract [en]

    This paper considers a characterization of the context-free non-regular languages, conjecturing that there for all such languages exists a fixed string thatcan be pumped to exhibit infinitely many equivalence classes. A proof is given only for a special case, but the general statement is conjectured to hold. The conjecture is then shown to imply that the shuffle of two context-free languagesis not context-free.

  • 14.
    Berglund, Martin
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Björklund, Henrik
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    On the Parameterized Complexity of Linear Context-Free Rewriting Systems2013Ingår i: Proceedings of the 13th Meeting on the Mathematics of Language (MoL 13), Association for Computational Linguistics, 2013, s. 21-29Konferensbidrag (Övrigt vetenskapligt)
    Abstract [en]

    We study the complexity of uniform membership for Linear Context-Free RewritingSystems, i.e., the problem where we aregiven a string w and a grammar G and areasked whether w ∈ L(G). In particular,we use parameterized complexity theoryto investigate how the complexity dependson various parameters. While we focusprimarily on rank and fan-out, derivationlength is also considered.

  • 15.
    Berglund, Martin
    et al.
    Stellenbosch University.
    Björklund, Henrik
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Single-Rooted DAGs in Regular DAG Languages: Parikh Image and Path Languages2017Ingår i: Proceedings of the 13th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+13) / [ed] M. Kuhlmann, T. Scheffler, Association for Computational Linguistics , 2017, s. 94-101Konferensbidrag (Refereegranskat)
    Abstract [en]

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

  • 16.
    Berglund, Martin
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Björklund, Henrik
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    van der Merwe, Brink
    Stellenbosch University, South Africa.
    Watson, Bruce
    Stellenbosch University, South Africa.
    Cuts in Regular Expressions2013Ingår i: Developments in Language Theory: 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings / [ed] Marie-Pierre Béal, Olivier Carton, Springer Berlin/Heidelberg, 2013, s. 70-81Konferensbidrag (Refereegranskat)
    Abstract [en]

    Most software packages with regular expression matching engines offer operators that extend the classical regular expressions, such as counting, intersection, complementation, and interleaving. Some of the most popular engines, for example those of Java and Perl, also provide operators that are intended to control the nondeterminism inherent in regular expressions. We formalize this notion in the form of the cut and iterated cut operators. They do not extend the class of languages that can be defined beyond the regular, but they allow for exponentially more succinct representation of some languages. Membership testing remains polynomial, but emptiness testing becomes PSPACE-hard. 

  • 17.
    Berglund, Martin
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    On the complexity of variants of the k Best strings problem2010Ingår i: Proceedings of the Prague stringology conference 2010, dblp , 2010, s. 76-88Konferensbidrag (Refereegranskat)
    Abstract [en]

    We investigate the problem of extracting the k best strings from a nondeterministic weighted automaton over a semiring S. This problem, which has been considered earlier in the literature, is more difficult than extracting the k best runs, since distinct runs may not correspond to distinct strings. Unsurprisingly, the computational complexity of the problem depends on the semiring S used. We study three different cases, namely the tropical and complex tropical semirings, and the semiring of positive real numbers. For the first case, we establish a polynomial algorithm. For the second and third cases, NP-completeness and undecidability results are shown.

  • 18.
    Berglund, Martin
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    On the complexity of variants of the k best strings problem2010Ingår i: Proc. Prague Stringology Conference 2010 / [ed] M. Balík, J. Holub, 2010Konferensbidrag (Refereegranskat)
  • 19.
    Berglund, Martin
    et al.
    Stellenbosch University.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Merwe, Brink van der
    University of Stellenbosch.
    On Regular Expressions with Backreferences and Transducers2018Ingår i: Tenth Workshop on Non-Classical Models of Automata and Applications (NCMA 2018) / [ed] Rudolf Freund, Michal Hospodár, Galina Jirásková, Giovanni Pighizzini, Österreichische Computer Gesellschaft , 2018, s. 49-64Konferensbidrag (Refereegranskat)
    Abstract [en]

    Modern regular expression matching software features many extensions, some general, while some are very narrowly specified. Here we consider the generalization of adding a class of operators which can be described by, e.g. finite-state transducers. Combined with backreferences, they enable new classes of languages to be matched. The addition of finite-state transducers is shown to make membership testing undecidable. Following this result, we study the complexity of membership testing for various restricted cases of the model.

  • 20.
    Berglund, Martin
    et al.
    Stellenbosch University.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Merwe, Brink van der
    University of Stellenbosch.
    The output size problem for string-to-tree transducers2018Ingår i: Journal of Automata, Languages and Combinatorics, Vol. 23, nr 1-3, s. 19-38Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The output size problem, for a string-to-tree transducer, is to determine the asymptotic behavior of the function describing the maximum size of output trees, with respect to the length of input strings. We show that the problem to determine, for a given regular expression, the worst-case matching time of a backtracking regular expression matcher, can be reduced to the output size problem. The latter can, in turn, be solved by determining the degree of ambiguity of a non-deterministic finite automaton.

  • 21.
    Berglund, Martin
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    van der Merwe, Brink
    University of Stellenbosch, South Africa.
    Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching2014Konferensbidrag (Refereegranskat)
    Abstract [en]

    We consider in some detail how regular expression matching happens in Java, as a popular representative of the category of regex-directed matching engines. We extract a slightly idealized algorithm for this scenario. Next we define an automata model which captures all the aspects needed to perform matching, of the Java style, in a formal way. Finally, two types of static analysis, which take a regular expression and tells whether there exists a family of strings which make Java-style matching run in exponential time, are done.

  • 22.
    Björklund, Henrik
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Ericson, Petter
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Between a Rock and a Hard Place: Parsing for Hyperege Replacement DAG Grammars2016Ingår i: Proc. 10th International Conference on Language and Automata Theory and Applications (LATA 2016) / [ed] A.H. Dediu, J. Janoušek, C. Martín-Vide, and B. Truthe, Springer Publishing Company, 2016, Vol. 9618, s. 521-532Konferensbidrag (Refereegranskat)
    Abstract [en]

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

  • 23.
    Björklund, Henrik
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Ericson, Petter
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Parsing Weighted Order-Preserving Hyperedge Replacement Grammars2019Ingår i: Proceedings of the 16th Meeting on the Mathematics of Language / [ed] F. Drewes, P. de Groote, G. Penn, Association for Computational Linguistics, 2019, s. 1-11Konferensbidrag (Refereegranskat)
    Abstract [en]

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

  • 24.
    Björklund, Henrik
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Ericson, Petter
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Parsing Weighted Order-Preserving Hyperedge Replacement Grammars2018Rapport (Övrigt vetenskapligt)
    Abstract [en]

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

  • 25.
    Björklund, Henrik
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Ericson, Petter
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Starke, Florian
    Faculty of Computer Science, TU Dresden.
    Uniform Parsing for Hyperedge Replacement Grammars2018Rapport (Övrigt vetenskapligt)
    Abstract [en]

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

  • 26.
    Björklund, Johanna
    et al.
    Umeå universitet.
    Cohen, Shay B.
    University of Edinburgh.
    Drewes, Frank
    Umeå universitet.
    Satta, Giorgio
    University of Padova.
    Bottom-Up Unranked Tree-to-Graph Transducers for Translation into Semantic Graphs2019Ingår i: Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing / [ed] Heiko Vogler, Andreas Maletti, Association for Computational Linguistics, 2019, s. 7-17, artikel-id W19-3104Konferensbidrag (Refereegranskat)
    Abstract [en]

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

  • 27.
    Björklund, Johanna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Jonsson, Anna
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    A Comparison of Two N-Best Extraction Methods for Weighted Tree Automata2018Ingår i: Implementation and Application of Automata: 23rd International Conference, CIAA 2018, Charlottetown, PE, Canada, July 30 – August 2, 2018, Proceedings, Springer, 2018, s. 197-108Konferensbidrag (Refereegranskat)
    Abstract [en]

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

  • 28.
    Björklund, Johanna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Jonsson, Anna
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Finding the N Best Vertices in an Infinite Weighted Hypergraph2017Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 682, s. 78s. 30-41Artikel i tidskrift (Refereegranskat)
    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. 

  • 29.
    Björklund, Johanna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Jonsson, Anna
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    On the N best problem for hypergraphs2016Ingår i: / [ed] A. Maletti, 2016Konferensbidrag (Övrigt vetenskapligt)
    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.

  • 30.
    Björklund, Johanna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Satta, Giorgio
    University of Padova, Italy.
    Z-Automata for Compact and Direct Representation of Unranked Tree Languages2019Ingår i: Implementation and Application of Automata: 24th International Conference, CIAA 2019 Košice, Slovakia, July 22–25, 2019, Proceedings / [ed] Michal Hospodár, Galina Jirásková, Springer, 2019, s. 83-94Konferensbidrag (Refereegranskat)
    Abstract [en]

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

  • 31.
    Björklund, Johanna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Zechner, Niklas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    An efficient best-trees algorithm for weighted tree automata over the tropical semiring2015Ingår i: 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, s. 97-108Konferensbidrag (Refereegranskat)
    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.

  • 32.
    Björklund, Johanna
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Zechner, Niklas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Efficient enumeration of weighted tree languages over the tropical semiring2019Ingår i: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 104, s. 78s. 119-130Artikel i tidskrift (Refereegranskat)
    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. 

  • 33.
    Blum, Johannes
    et al.
    University of Würzburg.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Language Theoretic Properties of Regular DAG Languages2019Ingår i: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 265, s. 78s. 57-76Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We study sets of directed acyclic graphs, called regular DAG languages, which are accepted by a recently introduced type of DAG automata motivated by current developments in natural language processing. We prove (or disprove) closure properties, establish pumping lemmata, characterize finite regular DAG languages, and show that "unfolding" turns regular DAG languages into regular tree languages, which implies a linear growth property and the regularity of the path languages of regular DAG languages. Further, we give polynomial decision algorithms for the emptiness and finiteness problems, and show that deterministic DAG automata can be minimized and tested for equivalence in polynomial time.

  • 34.
    Blum, Johannes
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Properties of Regular DAG Languages2016Ingår i: Proc. 10th International Conference on Language and Automata Theory and Applications (LATA 2016) / [ed] A.H. Dediu, J. Janoušek, C. Martín-Vide, and B. Truthe, Springer Publishing Company, 2016, s. 427-438Konferensbidrag (Refereegranskat)
    Abstract [en]

    A DAG is a directed acyclic graph. We study the properties of DAG automata and their languages, called regular DAG languages. In particular, we prove results resembling pumping lemmas and show that the finiteness problem for regular DAG languages is in P.

  • 35.
    Chiang, David
    et al.
    University of Notre Dame.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Gildea, Daniel
    University of Rochester.
    Lopez, Adam
    University of Edinburgh.
    Satta, Giorgio
    University of Padua.
    Weighted DAG automata for semantic graphs2018Ingår i: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 44, nr 1, s. 119-186Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Graphs have a variety of uses in natural language processing, particularly as representations of linguistic meaning. A deficit in this area of research is a formal framework for creating, combining, and using models involving graphs that parallels the frameworks of finite automata for strings and finite tree automata for trees. A possible starting point for such a framework is the formalism of directed acyclic graph (DAG) automata, defined by Kamimura and Slutzki and extended by Quernheim and Knight. In this article, we study the latter in depth, demonstrating several new results, including a practical recognition algorithm that can be used for inference and learning with models defined on DAG automata. We also propose an extension to graphs with unbounded node degree and show that our results carry over to the extended formalism.

  • 36. Corradini, Andrea
    et al.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Term graph rewriting and parallel term rewriting2011Ingår i: Proceedings of the 6th International Workshop on Computing with Terms and Graphs: Saarbrücken, Germany, 2nd April / [ed] Rachid Echahed, Open Publishing Association , 2011, s. 3-18Konferensbidrag (Refereegranskat)
    Abstract [en]

    The relationship between Term Graph Rewriting and Term Rewriting is well understood: a single term graph reduction may correspond to several term reductions, due to sharing. It is also known that if term graphs are allowed to contain cycles, then one term graph reduction may correspond to infinitely many term reductions. We stress that this fact can be interpreted in two ways. According to the "sequential interpretation", a term graph reduction corresponds to an infinite sequence of term reductions, as formalized by Kennaway et.al. using strongly converging derivations over the complete metric space of infinite terms. Instead according to the "parallel interpretation" a term graph reduction corresponds to the parallel reduction of an infinite set of redexes in a rational term. We formalize the latter notion by exploiting the complete partial order of infinite and possibly partial terms, and we stress that this interpretation allows to explain the result of reducing circular redexes in several approaches to term graph rewriting.

  • 37.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    DAG automata for meaning representation2017Ingår i: Proceedings of the 15th Meeting on the Mathematics of Language (MoL 2017) / [ed] Makoto Kanazawa, Philippe de Groote, Mehrnoosh Sadrzadeh, 2017, Vol. W17-34, s. 88-99, artikel-id W17-3409Konferensbidrag (Övrigt vetenskapligt)
    Abstract [en]

    Languages of directed acyclic graphs (DAGs) are of interest in Natural Lanuage Processing because they can be used to capture the structure of semantic graphs like those of Abstract Meaning Representation. This paper gives an overview of recent results on a family of automata recognizing such DAG languages.

  • 38.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Delegation Networks2007Rapport (Övrigt vetenskapligt)
    Abstract [en]

    We introduce a generalization of tree-based generators called delegation networks. These make it possible to generate objects such as strings, trees, graphs, and pictures in a modular way by combining tree-based generators of several types. Our main result states that, if all underlying tree generators generate regular tree languages (or finite tree languages), then the tree-generating power of delegation networks is the same as that of context-free tree grammars working in IO mode.

  • 39.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskaplig fakultet, Institutionen för datavetenskap.
    From Tree-Based Generators to Delegation Networks2007Ingår i: Proc. 2nd International Conference on Algebraic Informatics, 2007, s. 48-72Konferensbidrag (Refereegranskat)
  • 40.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskaplig fakultet, Datavetenskap.
    Grammatical Picture Generation: A Tree-Based Approach.2006Bok (Övrigt vetenskapligt)
  • 41.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Implementation and application of automata: 20th international conference, CIAA 2015, Umeå, Sweden, August 18-21, 2015, Proceedings2015Proceedings (redaktörskap) (Övrigt vetenskapligt)
  • 42.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskaplig fakultet, Datavetenskap.
    Links2007Ingår i: International Journal of Foundations of Computer Science, Vol. 18, s. 1187-1196Artikel i tidskrift (Refereegranskat)
  • 43.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskaplig fakultet, Institutionen för datavetenskap.
    MAT Learners for Recognizable Tree Languages and Tree Series2009Ingår i: Acta Cybernetica, Vol. 19, nr 2, s. 249-274Artikel i tidskrift (Refereegranskat)
  • 44.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Millstream systems and graph transformation for complex linguistic models (Extended abstract)2013Ingår i: Descriptional Complexity of Formal Systems: 15th International Workshop, DCFS 2013, London, ON, Canada, July 22-25, 2013. Proceedings / [ed] Helmut Jurgensen, Rogério Reis, 2013, s. 14-16Konferensbidrag (Refereegranskat)
    Abstract [en]

    Allan Turing [5] suggested to regard the ability to communicate in human language as an indication of true intelligence. If a computer would be able to engage in such a communication with human beings without them being able to identify the computer, the computer should be considered to be intelligent. Although it is debatable whether this conclusion could really be drawn from the Turing test (see also [6]), it shows how complex human language is and how many facets it has. Some of the most important dimensions of language are phonology, morphology, syntax, semantics, and pragmatics. Pragmatics includes the whole field of contextual and ontological knowledge. These dimensions are not orthogonal, but are intertwined in many ways. Even if we restrict ourselves to text input and output, thus disregarding phonology, this creates an amazingly complex structure. While computational linguists try to make progress understanding the relation between the various dimensions, we usually restrict ourselves to syntax in natural language processing, sometimes extended by limited attempts to make a semantic interpretation or to make use of ontological knowledge. The reason for this is, of course, the descriptional and computational complexity of the models required.

  • 45.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    On DAG Languages and DAG Transducers2017Ingår i: Bulletin of the European Association for Theoretical Computer Science, ISSN 0252-9742, Vol. 121, s. 78s. 142-163Artikel i tidskrift (Övrigt vetenskapligt)
    Abstract [en]

    We review recent results regarding DAG automata and regular DAG languages and point out some open problems that may be interesting to work on. Moreover, a notion of DAG transducers is suggested.

  • 46.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Preface2017Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 679, s. 1-1Artikel i tidskrift (Övrigt vetenskapligt)
  • 47.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Selected Decision Problems for Square-Refinement Collage Grammars2011Ingår i: ALGEBRAIC FOUNDATIONS IN COMPUTER SCIENCE: ESSAYS DEDICATED TO SYMEON BOZAPALIDIS ON THE OCCASION OF HIS RETIREMENT, Berlin/Heidelberg: Springer Berlin/Heidelberg, 2011, Vol. 7020, s. 1-29Konferensbidrag (Refereegranskat)
    Abstract [en]

    We consider collage grammars whose rules subdivide the unit square into smaller and smaller rectangles. The decidability status of selected decision problems for this type of grammars is surveyed: the membership problem, the emptiness and finiteness problems, connectedness and disconnectedness of the generated pictures, and the question whether a generated collage contains a rectangle whose lower-left corner is a point on the diagonal.

  • 48.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    Towards the tree automata workbench marbles2010Ingår i: Electronic Communications of the EASST, ISSN 1863-2122, Vol. 16, s. 16-Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The conceptual ideas that are intended to become the basis for the tree automata workbench Marbles are sketched. The goal is to design and implement an extensible system that facilitates experiments with virtually any kind of algorithm on tree automata. Moreover, the system will be released with a library and an application programmer's interface to make it accessible to anyone who wants to apply tree automata algorithms in research and development.

  • 49.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskaplig fakultet, Institutionen för datavetenskap.
    Towards the Tree Automata Workbench Marbles2009Ingår i: Manipulation of Graphs, Algebras and Pictures: Essays Dedicated to Hans-Jörg Kreowski on the Occasion of His 60th Birthday, 2009, s. 83-98Kapitel i bok, del av antologi (Refereegranskat)
  • 50.
    Drewes, Frank
    et al.
    Umeå universitet, Teknisk-naturvetenskaplig fakultet, Datavetenskap.
    Engelfriet, Joost
    Branching Synchronization Grammars with Nested Tables.2004Ingår i: Journal of Computer and System Sciences, ISSN 0022-0000, Vol. 68, nr 3, s. 611-656Artikel i tidskrift (Refereegranskat)
12 1 - 50 av 86
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf