umu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 84) Show all publications
Björklund, J., Drewes, F. & Zechner, N. (2019). Efficient enumeration of weighted tree languages over the tropical semiring. Journal of computer and system sciences (Print), 104, 119-130
Open this publication in new window or tab >>Efficient enumeration of weighted tree languages over the tropical semiring
2019 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 104, p. 78p. 119-130Article in journal (Refereed) Published
Abstract [en]

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

Publisher
p. 78
Keywords
weighted tree automaton, N-best analysis, tropical semiring
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-132963 (URN)10.1016/j.jcss.2017.03.006 (DOI)000472246300008 ()
Available from: 2017-03-27 Created: 2017-03-27 Last updated: 2019-07-12Bibliographically approved
Drewes, F., Hoffmann, B. & Minas, M. (2019). Extending Predictive Shift-Reduce Parsing to Contextual Hyperedge Replacement Grammars. In: Esther Guerra, Fernando Orejas (Ed.), Graph Transformation: 12th International Conference, ICGT 2019, Held as Part of STAF 2019, Eindhoven, The Netherlands, July 15–16, 2019, Proceedings. Paper presented at ICGT 2019: 12th International Conference on Graph Transformation, July 15-16, 2019, Eindhoven, The Netherlands (pp. 55-72). Springer
Open this publication in new window or tab >>Extending Predictive Shift-Reduce Parsing to Contextual Hyperedge Replacement Grammars
2019 (English)In: Graph Transformation: 12th International Conference, ICGT 2019, Held as Part of STAF 2019, Eindhoven, The Netherlands, July 15–16, 2019, Proceedings / [ed] Esther Guerra, Fernando Orejas, Springer, 2019, p. 55-72Conference paper, Published paper (Refereed)
Abstract [en]

Parsing with respect to grammars based on hyperedge replacement (HR) is NP-hard in general, even for some fixed grammars. In recent work, wehave devised predictive shift-reduce parsing (PSR), a very efficientalgorithm that applies to a wide subclass of HR grammars. In thispaper, we extend PSR parsing to contextual HR grammars, a moderateextension of HR grammars that have greater generative power, and aretherefore better suited for the practical specification of graph anddiagram languages. Although the extension requires considerablemodifications of the original algorithm, it turns out that theresulting parsers are still very efficient.

Place, publisher, year, edition, pages
Springer, 2019
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 11629
Keywords
contextual hyperedge replacement grammar, graph parsing, grammar analysis
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-158625 (URN)10.1007/978-3-030-23611-3_4 (DOI)978-3-030-23610-6 (ISBN)978-3-030-23611-3 (ISBN)
Conference
ICGT 2019: 12th International Conference on Graph Transformation, July 15-16, 2019, Eindhoven, The Netherlands
Available from: 2019-05-03 Created: 2019-05-03 Last updated: 2019-07-16Bibliographically approved
Drewes, F., Hoffmann, B. & Minas, M. (2019). Formalization and Correctness of Predictive Shift-Reduce Parsers for Graph Grammars Based on Hyperedge Replacement. The Journal of logical and algebraic methods in programming, 104, 303-341
Open this publication in new window or tab >>Formalization and Correctness of Predictive Shift-Reduce Parsers for Graph Grammars Based on Hyperedge Replacement
2019 (English)In: The Journal of logical and algebraic methods in programming, ISSN 2352-2208, E-ISSN 2352-2216, Vol. 104, p. 303-341Article in journal (Refereed) Published
Abstract [en]

Hyperedge replacement (HR) grammars can generate NP-complete graph languages, which makes parsing hard even for fixed HR languages. Therefore, we study predictive shift-reduce (PSR) parsing that yields efficient parsers for a subclass of HR grammars, by generalizing the concepts of SLR(1) string parsing to graphs. We formalize the construction of PSR parsers and show that it is correct. PSR parsers run in linear space and time, and are more efficient than the predictive top-down (PTD) parsers recently developed by the authors.

Place, publisher, year, edition, pages
Elsevier, 2019
Keywords
hyperedge replacement grammar, graph parsing, grammar analysis
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-155799 (URN)10.1016/j.jlamp.2018.12.006 (DOI)
Available from: 2019-01-28 Created: 2019-01-28 Last updated: 2019-04-15Bibliographically approved
Blum, J. & Drewes, F. (2019). Language Theoretic Properties of Regular DAG Languages. Information and Computation, 265, 57-76
Open this publication in new window or tab >>Language Theoretic Properties of Regular DAG Languages
2019 (English)In: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 265, p. 78p. 57-76Article in journal (Refereed) Published
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.

Place, publisher, year, edition, pages
Elsevier, 2019. p. 78
Keywords
DAG automaton, regular DAG language
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-137918 (URN)10.1016/j.ic.2017.07.011 (DOI)000458499800003 ()
Available from: 2017-07-31 Created: 2017-07-31 Last updated: 2019-04-16Bibliographically approved
Björklund, H., Drewes, F. & Ericson, P. (2019). Parsing Weighted Order-Preserving Hyperedge Replacement Grammars. In: F. Drewes, P. de Groote, G. Penn (Ed.), Proc. 16th Meeting on the Mathematics of Language (MOL 2019): . Paper presented at 16th Meeting on the Mathematics of Language (MOL 2019), Toronto, Canada, July 18–19, 2019. Association for Computational Linguistics
Open this publication in new window or tab >>Parsing Weighted Order-Preserving Hyperedge Replacement Grammars
2019 (English)In: Proc. 16th Meeting on the Mathematics of Language (MOL 2019) / [ed] F. Drewes, P. de Groote, G. Penn, Association for Computational Linguistics, 2019Conference paper, Published 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).

Place, publisher, year, edition, pages
Association for Computational Linguistics, 2019
Keywords
Graph grammar, Hyperedge replacement, Abstract meaning representation, Weighted uniform parsing
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-159908 (URN)
Conference
16th Meeting on the Mathematics of Language (MOL 2019), Toronto, Canada, July 18–19, 2019
Available from: 2019-06-10 Created: 2019-06-10 Last updated: 2019-06-13
Jäger, G. & Drewes, F. (2019). The Metric Dimension of Zn × Zn × Zn is ⌊3n/2⌋. Theoretical Computer Science
Open this publication in new window or tab >>The Metric Dimension of Zn × Zn × Zn is ⌊3n/2⌋
2019 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, , p. 78Article in journal (Refereed) In press
Abstract [en]

In this work we determine the metric dimension of Zn × Zn × Zn as ⌊3n/2⌋ for all n ≥ 2. We prove this result by investigating a variant of Mastermind.

Mastermind is a famous two-player game that has attracted much attention in the literature in recent years. In particular we consider the static (also called non-adaptive) black-peg variant of Mastermind. The game is played by a codemaker and a codebreaker. Given c colors and p pegs, the principal rule is that the codemaker has to choose a secret by assigning colors to the pegs, i.e., the secret is a p-tuple of colors, and the codebreaker asks a number of questions all at once. Like the secret, a question is a p-tuple of colors chosen from the c available colors. The codemaker then answers all of those questions by telling the codebreaker how many pegs in each question are correctly colored. The goal is to find the minimal number of questions that allows the codebreaker to determine the secret from the received answers. We present such a strategy for this game for p = 3 pegs and an arbitrary number c ≥ 2 of colors using ⌊3c/2⌋ + 1 questions, which we prove to be both feasible and optimal.

The minimal number of questions required for p pegs and c colors is easily seen to be equal to the metric dimension of Zpc plus 1 which proves our main result.

Publisher
p. 78
Keywords
weighted tree automaton, N-best analysis, tropical semiring
National Category
Computer Sciences Discrete Mathematics
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-159286 (URN)
Available from: 2019-05-23 Created: 2019-05-23 Last updated: 2019-05-23
Björklund, J., Drewes, F. & Satta, G. (2019). Z-Automata for Compact and Direct Representation of Unranked Tree Languages. In: Michal Hospodár, Galina Jirásková (Ed.), Implementation and Application of Automata: 24th International Conference, CIAA 2019 Košice, Slovakia, July 22–25, 2019 Proceedings. Paper presented at Implementation and Application of Automata - 24th International Conference (CIAA 2019), Slovakia, July 22-25, 2019 (pp. 83-94). Springer
Open this publication in new window or tab >>Z-Automata for Compact and Direct Representation of Unranked Tree Languages
2019 (English)In: 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, Published 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.

Place, publisher, year, edition, pages
Springer, 2019
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 11601
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-158624 (URN)10.1007/978-3-030-23679-3_7 (DOI)978-3-030-23678-6 (ISBN)978-3-030-23679-3 (ISBN)
Conference
Implementation and Application of Automata - 24th International Conference (CIAA 2019), Slovakia, July 22-25, 2019
Available from: 2019-05-03 Created: 2019-05-03 Last updated: 2019-07-16
Björklund, J., Drewes, F. & Jonsson, A. (2018). A Comparison of Two N-Best Extraction Methods for Weighted Tree Automata. In: Implementation and Application of Automata: 23rd International Conference, CIAA 2018, Charlottetown, PE, Canada, July 30 – August 2, 2018, Proceedings. Paper presented at 23rd International Conference on Implementation and Applications of Automata (CIAA 2018), Charlottetown, Canada, July 30-August 2, 2018 (pp. 197-108). Springer
Open this publication in new window or tab >>A Comparison of Two N-Best Extraction Methods for Weighted Tree Automata
2018 (English)In: 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, Published 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.

Place, publisher, year, edition, pages
Springer, 2018
Series
Lecture Notes in Computer Science
Keywords
N-best list, tree automaton
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-149994 (URN)10.1007/978-3-319-94812-6_9 (DOI)000469285600009 ()978-3-319-94812-6 (ISBN)978-3-319-94811-9 (ISBN)
Conference
23rd International Conference on Implementation and Applications of Automata (CIAA 2018), Charlottetown, Canada, July 30-August 2, 2018
Available from: 2018-06-30 Created: 2018-06-30 Last updated: 2019-06-20Bibliographically approved
Berglund, M., Drewes, F. & Merwe, B. v. (2018). On Regular Expressions with Backreferences and Transducers. In: Rudolf Freund, Michal Hospodár, Galina Jirásková, Giovanni Pighizzini (Ed.), Tenth Workshop on Non-Classical Models of Automata and Applications (NCMA 2018): . Paper presented at 10th Workshop on Non-Classical Models of Automata and Applications (NCMA 2018), Košice, Slovakia, August 21 - 22, 2018 (pp. 49-64). Österreichische Computer Gesellschaft
Open this publication in new window or tab >>On Regular Expressions with Backreferences and Transducers
2018 (English)In: 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, Published 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.

Place, publisher, year, edition, pages
Österreichische Computer Gesellschaft, 2018
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-149995 (URN)978-3-903035-21-8 (ISBN)
Conference
10th Workshop on Non-Classical Models of Automata and Applications (NCMA 2018), Košice, Slovakia, August 21 - 22, 2018
Available from: 2018-06-30 Created: 2018-06-30 Last updated: 2019-07-19Bibliographically approved
Björklund, H., Drewes, F. & Ericson, P. (2018). Parsing Weighted Order-Preserving Hyperedge Replacement Grammars. Umeå: Umeå Universitet
Open this publication in new window or tab >>Parsing Weighted Order-Preserving Hyperedge Replacement Grammars
2018 (English)Report (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).

Place, publisher, year, edition, pages
Umeå: Umeå Universitet, 2018. p. 12
Series
Report / UMINF, ISSN 0348-0542 ; 18.16
Keywords
graph grammars, order-preservation, parsing, weighted graph grammars
National Category
Computer Sciences
Research subject
business data processing
Identifiers
urn:nbn:se:umu:diva-153395 (URN)
Available from: 2018-11-19 Created: 2018-11-19 Last updated: 2019-07-05Bibliographically approved
Projects
Tree Automata in Computational Language Technology [2008-06074_VR]; Umeå University
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0001-7349-7693

Search in DiVA

Show all publications