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

  • 2.
    Bensch, Suna
    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.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Algorithmic properties of Millstream systems2010In: Developments in Language Theory: 14th International Conference, DLT 2010 / [ed] Sheng Yu, Springer Berlin/Heidelberg, 2010, p. 54-65Conference paper (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Millstream Systems2009Report (Other academic)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Millstream Systems: a formal model for linking language modules by interfaces2010In: Proc. ACL 2010 Workshop on Applications of Tree Automata in Natural Language Processing (ATANLP 2010), The Association for Computer Linguistics , 2010Conference paper (Refereed)
  • 5.
    Bensch, Suna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, FrankUmeå University, Faculty of Science and Technology, Department of Computing Science.
    Proceedings of Umeå's 16th student conference in computing science: USCCS 20132013Conference proceedings (editor) (Other academic)
  • 6.
    Bensch, Suna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, FrankUmeå University, Faculty of Science and Technology, Department of Computing Science.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, Proceedings2013Conference proceedings (editor) (Refereed)
  • 7.
    Bensch, Suna
    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.
    Hellström, Thomas
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Grammatical Inference of Graph Transformation Rules2015In: Proceedings of the 7th Workshop on Non-Classical Modelsof Automata and Applications (NCMA 2015), Austrian Computer Society , 2015, p. 73-90Conference paper (Refereed)
  • 8.
    Bensch, Suna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, FrankUmeå University, Faculty of Science and Technology, Department of Computing Science.Hirvensalo, MikaOtto, Friedrich
    Fundamenta Informaticae: special issue2015Conference proceedings (editor) (Other academic)
  • 9.
    Bensch, Suna
    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.
    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 transformation2012Report (Other academic)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    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 TransformationManuscript (preprint) (Other academic)
  • 11.
    Bensch, Suna
    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.
    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 analysis2014In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 531, p. 1-25Article in journal (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    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 Transformation2011In: Proceedings of the 9th International Workshop on Finite State Methods and Natural Language Processing, Stroudsburg: Association for Computational Linguistics , 2011, p. 93-97Conference paper (Refereed)
  • 13.
    Berglund, Martin
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank (Contributor)
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Characterizing Non-Regularity2014Report (Other academic)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Björklund, Henrik
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    On the Parameterized Complexity of Linear Context-Free Rewriting Systems2013In: Proceedings of the 13th Meeting on the Mathematics of Language (MoL 13), Association for Computational Linguistics, 2013, p. 21-29Conference paper (Other academic)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Single-Rooted DAGs in Regular DAG Languages: Parikh Image and Path Languages2017In: Proceedings of the 13th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+13) / [ed] M. Kuhlmann, T. Scheffler, Association for Computational Linguistics , 2017, p. 94-101Conference paper (Refereed)
    Abstract [en]

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

  • 16.
    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.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    van der Merwe, Brink
    Stellenbosch University, South Africa.
    Watson, Bruce
    Stellenbosch University, South Africa.
    Cuts in Regular Expressions2013In: 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, p. 70-81Conference paper (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    On the complexity of variants of the k Best strings problem2010In: Proceedings of the Prague stringology conference 2010, dblp , 2010, p. 76-88Conference paper (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    On the complexity of variants of the k best strings problem2010In: Proc. Prague Stringology Conference 2010 / [ed] M. Balík, J. Holub, 2010Conference paper (Refereed)
  • 19.
    Berglund, Martin
    et al.
    Stellenbosch University.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Merwe, Brink van der
    University of Stellenbosch.
    On Regular Expressions with Backreferences and Transducers2018In: 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, p. 49-64Conference paper (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Merwe, Brink van der
    University of Stellenbosch.
    The output size problem for string-to-tree transducers2018In: Journal of Automata, Languages and Combinatorics, Vol. 23, no 1-3, p. 19-38Article in journal (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    van der Merwe, Brink
    University of Stellenbosch, South Africa.
    Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching2014Conference paper (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Ericson, Petter
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Between a Rock and a Hard Place: Parsing for Hyperege Replacement DAG Grammars2016In: Proc. 10th International Conference on Language and Automata Theory and Applications (LATA 2016) / [ed] A.H. Dediu, J. Janoušek, C. Martín-Vide, and B. Truthe, Springer Publishing Company, 2016, Vol. 9618, p. 521-532Conference paper (Refereed)
    Abstract [en]

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

  • 23.
    Björklund, Henrik
    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.
    Ericson, Petter
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Parsing Weighted Order-Preserving Hyperedge Replacement Grammars2019In: Proceedings of the 16th Meeting on the Mathematics of Language / [ed] F. Drewes, P. de Groote, G. Penn, Association for Computational Linguistics, 2019, p. 1-11Conference paper (Refereed)
    Abstract [en]

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

  • 24.
    Björklund, Henrik
    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.
    Ericson, Petter
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Parsing Weighted Order-Preserving Hyperedge Replacement Grammars2018Report (Other academic)
    Abstract [en]

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

  • 25.
    Björklund, Henrik
    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.
    Ericson, Petter
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Starke, Florian
    Faculty of Computer Science, TU Dresden.
    Uniform Parsing for Hyperedge Replacement Grammars2018Report (Other academic)
    Abstract [en]

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

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

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

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

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

  • 29.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Jonsson, Anna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    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.

  • 30.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Satta, Giorgio
    University of Padova, Italy.
    Z-Automata for Compact and Direct Representation of Unranked Tree Languages2019In: Implementation and Application of Automata: 24th International Conference, CIAA 2019 Košice, Slovakia, July 22–25, 2019, Proceedings / [ed] Michal Hospodár, Galina Jirásková, Springer, 2019, p. 83-94Conference paper (Refereed)
    Abstract [en]

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

  • 31.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    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.

  • 32.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    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. 

  • 33.
    Blum, Johannes
    et al.
    University of Würzburg.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Language Theoretic Properties of Regular DAG Languages2019In: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 265, p. 78p. 57-76Article in journal (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Properties of Regular DAG Languages2016In: 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, p. 427-438Conference paper (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Gildea, Daniel
    University of Rochester.
    Lopez, Adam
    University of Edinburgh.
    Satta, Giorgio
    University of Padua.
    Weighted DAG automata for semantic graphs2018In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 44, no 1, p. 119-186Article in journal (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Term graph rewriting and parallel term rewriting2011In: Proceedings of the 6th International Workshop on Computing with Terms and Graphs: Saarbrücken, Germany, 2nd April / [ed] Rachid Echahed, Open Publishing Association , 2011, p. 3-18Conference paper (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    DAG automata for meaning representation2017In: Proceedings of the 15th Meeting on the Mathematics of Language (MoL 2017) / [ed] Makoto Kanazawa, Philippe de Groote, Mehrnoosh Sadrzadeh, 2017, Vol. W17-34, p. 88-99, article id W17-3409Conference paper (Other academic)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Delegation Networks2007Report (Other academic)
    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å University, Faculty of Science and Technology, Departement of Computing Science.
    From Tree-Based Generators to Delegation Networks2007In: Proc. 2nd International Conference on Algebraic Informatics, 2007, p. 48-72Conference paper (Refereed)
  • 40.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Computing Science.
    Grammatical Picture Generation: A Tree-Based Approach.2006Book (Other academic)
  • 41.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Implementation and application of automata: 20th international conference, CIAA 2015, Umeå, Sweden, August 18-21, 2015, Proceedings2015Conference proceedings (editor) (Other academic)
  • 42.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Computing Science.
    Links2007In: International Journal of Foundations of Computer Science, Vol. 18, p. 1187-1196Article in journal (Refereed)
  • 43.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    MAT Learners for Recognizable Tree Languages and Tree Series2009In: Acta Cybernetica, Vol. 19, no 2, p. 249-274Article in journal (Refereed)
  • 44.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Millstream systems and graph transformation for complex linguistic models (Extended abstract)2013In: 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, p. 14-16Conference paper (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    On DAG Languages and DAG Transducers2017In: Bulletin of the European Association for Theoretical Computer Science, ISSN 0252-9742, Vol. 121, p. 78p. 142-163Article in journal (Other academic)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Preface2017In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 679, p. 1-1Article in journal (Other academic)
  • 47.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Selected Decision Problems for Square-Refinement Collage Grammars2011In: ALGEBRAIC FOUNDATIONS IN COMPUTER SCIENCE: ESSAYS DEDICATED TO SYMEON BOZAPALIDIS ON THE OCCASION OF HIS RETIREMENT, Berlin/Heidelberg: Springer Berlin/Heidelberg, 2011, Vol. 7020, p. 1-29Conference paper (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Towards the tree automata workbench marbles2010In: Electronic Communications of the EASST, ISSN 1863-2122, Vol. 16, p. 16-Article in journal (Refereed)
    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å University, Faculty of Science and Technology, Department of Computing Science.
    Towards the Tree Automata Workbench Marbles2009In: Manipulation of Graphs, Algebras and Pictures: Essays Dedicated to Hans-Jörg Kreowski on the Occasion of His 60th Birthday, 2009, p. 83-98Chapter in book (Refereed)
  • 50.
    Drewes, Frank
    et al.
    Umeå University, Faculty of Science and Technology, Computing Science.
    Engelfriet, Joost
    Branching Synchronization Grammars with Nested Tables.2004In: Journal of Computer and System Sciences, ISSN 0022-0000, Vol. 68, no 3, p. 611-656Article in journal (Refereed)
12 1 - 50 of 86
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