| 1. |
- Berglund, Martin, 1981-, et al.
(author)
-
Parsing unranked tree languages, folded once
- 2023
-
In: Fundamentals of computation theory. - : Springer Nature. - 9783031435867 ; , s. 60-73
-
Conference paper (peer-reviewed)abstract
- A regular unranked tree folding consists of a regular unranked tree language and a folding operation that merges, i.e., folds, selected nodes of a tree to form a graph; the combination is a formal device for representing graph languages. If, in the process of folding, the order among edges is discarded so that the result is an unordered graph, then two applications of a fold operation is enough to make the associated parsing problem NP-complete. However, if the order is kept, then the problem is solvable in non-uniform polynomial time. In this paper we address the remaining case where only one fold operation is applied, but the order among edges is discarded. We show that under these conditions, the problem is solvable in non-uniform polynomial time.
|
|
| 2. |
- Berglund, Martin, 1981-, et al.
(author)
-
Parsing unranked tree languages, folded once
- 2024
-
In: Algorithms. - : MDPI. - 1999-4893. ; 17:6
-
Journal article (peer-reviewed)abstract
- A regular unranked tree folding consists of a regular unranked tree language and a folding operation that merges (i.e., folds) selected nodes of a tree to form a graph; the combination is a formal device for representing graph languages. If, in the process of folding, the order among edges is discarded so that the result is an unordered graph, then two applications of a fold operation are enough to make the associated parsing problem NP-complete. However, if the order is kept, then the problem is solvable in non-uniform polynomial time. In this paper, we address the remaining case, where only one fold operation is applied, but the order among the edges is discarded. We show that, under these conditions, the problem is solvable in non-uniform polynomial time.
|
|
| 3. |
- Berglund, Martin, 1981-, et al.
(author)
-
Transduction from trees to graphs through folding
- 2023
-
In: Information and Computation. - : Elsevier. - 0890-5401 .- 1090-2651. ; 295
-
Journal article (peer-reviewed)abstract
- We introduce a fold operation that realises a tree-to-graph transduction by merging selected nodes in the input tree to form a possibly cyclic output graph. The work is motivated by the increasing use of graph-based representations in semantic parsing. We show that a suitable class of graphs languages can be generated by applying the fold operation to regular unranked tree languages. We investigate two versions of the fold operation, one that preserves a depth-first ordering between the edges, and one that does not. Finally, we demonstrate that the time complexity for the associated non-uniform membership problem is solvable in polynomial time for the order-preserving version, and NP-complete for the order-cancelling one.
|
|
| 4. |
- Björklund, Henrik, et al.
(author)
-
Implementing a speech-to-text pipeline on the MICO platform
- 2016
-
Reports (other academic/artistic)abstract
- MICO is an open-source platform for cross-media analysis, querying, and recommendation. It is the major outcome of the European research project Media in Context, and has been contributed to by academic and industrial partners from Germany, Austria, Sweden, Italy, and the UK. A central idea is to group sets of related media objects into multimodal content items, and to process and store these as logical units. The platform is designed to be easy to extend and adapt, and this makes it a useful building block for a diverse set of multimedia applications. To promote the platform and demonstrate its potential, we describe our work on a Kaldi-based speech-recognition pipeline.
|
|
| 5. |
- Björklund, Henrik, et al.
(author)
-
Tree-based generation of restricted graph languages
- 2024
-
In: International Journal of Foundations of Computer Science. - : World Scientific. - 0129-0541. ; 35:1 & 2, s. 215-243
-
Journal article (peer-reviewed)abstract
- Order-preserving DAG grammars (OPDGs) is a formalism for representing languages of structurally restricted graphs. As demonstrated in [17], they are sufficiently expressive to model abstract meaning representations in natural language processing, a graph-based form of semantic representation in which nodes encode objects and edges relations. At the same time, they can be parsed in O (n2 + nm) , where m and n are the sizes of the grammar and the input graph, respectively. In this work, we provide an initial algebra semantic for OPDGs, which allows us to view them as regular tree grammars under an equivalence theory. This makes it possible to transfer results from the field of formal tree languages to the domain of OPDGs, both in the unweighted and the weighted case. In particular, we show that deterministic OPDGs can be minimised efficiently, and that they are learnable under the \minimal adequeate teacher" paradigm, that is, by querying an oracle for equivalence between languages, and membership of individual graphs. To conclude, we demonstrate that the languages generated by OPDGs are definable in monadic second-order logic.
|
|
| 6. |
|
|
| 7. |
- Ahnström, Johan, et al.
(author)
-
Farmers' Interest in Nature and Its Relation to Biodiversity in Arable Fields
- 2013
-
In: International Journal of Ecology. - : Hindawi Publishing Corporation. - 1687-9708 .- 1687-9716.
-
Journal article (peer-reviewed)abstract
- Biodiversity declines in farmland have been attributed to intensification of farming at the field level and loss of heterogeneity at the landscape level. However, farmers are not solely optimizing production; their actions are also influenced by social factors, tradition and interest in nature, which indirectly influence biodiversity but rarely are incorporated in studies of farmland biodiversity. We used social science methods to quantify farmers’ interest in nature on 16 farms with winter wheat fields in central Sweden, and combined this with biodiversity inventories of five organism groups (weeds, carabid beetles, bumblebees, solitary bees, and birds) and estimates of landscape composition andmanagement intensity at the field level.Agricultural intensity,measured as crop density, and farmers’ interest in nature explained variation in biodiversity, measured as the proportion of the regional species richness found on single fields. Interest in nature seemed to incorporate many actions taken by farmers and appeared to be influenced by both physical factors, for example, the surrounding landscape, and social factors, for example, social motivations.This study indicates that conservation of biodiversity in farmland, and design of new agri-environmental subsidy systems, would profit from taking farmers’ interest in nature and its relation to agricultural practices into account.
|
|
| 8. |
- Andersson, Eric, et al.
(author)
-
Generating semantic graph corpora with graph expansion grammar
- 2023
-
In: 13th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2023). - : Open Publishing Association. ; , s. 3-15
-
Conference paper (peer-reviewed)abstract
- We introduce LOVELACE, a tool for creating corpora of semantic graphs.The system uses graph expansion grammar as a representational language, thus allowing users to craft a grammar that describes a corpus with desired properties. When given such grammar as input, the system generates a set of output graphs that are well-formed according to the grammar, i.e., a graph bank.The generation process can be controlled via a number of configurable parameters that allow the user to, for example, specify a range of desired output graph sizes.Central use cases are the creation of synthetic data to augment existing corpora, and as a pedagogical tool for teaching formal language theory.
|
|
| 9. |
- Belfrage, Kristina, et al.
(author)
-
Effects of farm size and on-farm landscape heterogeneity on biodiversity-case study of twelve farms in a swedish landscape
- 2015
-
In: Agroecology and Sustainable Food Systems. - : Informa UK Limited. - 2168-3565 .- 2168-3573. ; 39:2, s. 170-188
-
Journal article (peer-reviewed)abstract
- In this study in Sweden, six small (<50 ha) and six large farms (>135 ha) participated. The aims of the study were to a) measure differences between small and large farms regarding on-farm landscape heterogeneity, and b) evaluate relations between on-farm landscape heterogeneity and biodiversity, measured as numbers of breeding bird species, bird territories, butterflies, bumblebees, and herbaceous plant species. Sample area of the same size, placed on each farm, was used for the biodiversity assessments and on-farm landscape heterogeneity studies. On-farm landscape heterogeneity was classified with the Shannon-Wiener diversity index. Linear regression was applied to analyze relationships between on-farm landscape heterogeneity and biodiversity indicators. Multivariate regression was used to analyze relations between single bird species and specific on-farm habitats. Small farms had significantly higher on-farm landscape heterogeneity than large farms. Strong positive relations between on-farm landscape heterogeneity and number of breeding birds, butterflies, and herbaceous plant species were found. Total on-farm landscape heterogeneity seems to be more important for bird diversity than do specific landscape elements. The study indicates that, to increase biodiversity, farm size should be taken into consideration.
|
|
| 10. |
- Björklund, Johanna, 1961-, et al.
(author)
-
A Comparative Evaluation of the Efficiency of N-Best Algorithms on Language Data
-
Other publication (other academic/artistic)abstract
- The N-best extraction problem consists in selecting the N highest ranking hypotheses from a set of hypotheses, with respect to a given ranking system. In our setting, the hypotheses and ranking are jointly represented by a weighted tree automaton (wta) over the tropical semiring: the hypotheses are trees, or runs on trees, and the ranking is decided by the weight assigned to them. In previous work, we presented an algorithm for N-best extraction that combines techniques to restrict the search space, and proved it to be correct and efficient. The algorithm is now implemented in the software Betty, allowing us to complement the deductive study with an empirical investigation. In particular, we compare our algorithm to the state-of-the-art algorithm for extracting the N best runs, implemented in in the software toolkit Tiburon. The data sets used in the experiments are wtas resulting from real-world natural language processing tasks, as well as artificially created wtas with varying degrees of nondeterminism. We find that Betty outperforms Tiburon on all tested data sets.
|
|
