| 1. |
- Berglund, Martin, 1981-, et al.
(författare)
-
Parsing unranked tree languages, folded once
- 2023
-
Ingår i: Fundamentals of computation theory. - : Springer Nature. - 9783031435867 ; , s. 60-73
-
Konferensbidrag (refereegranskat)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.
(författare)
-
Parsing unranked tree languages, folded once
- 2024
-
Ingår i: Algorithms. - : MDPI. - 1999-4893. ; 17:6
-
Tidskriftsartikel (refereegranskat)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.
(författare)
-
Shuffled languages : representation and recognition
- 2013
-
Ingår i: Theoretical Computer Science. - : Elsevier. - 0304-3975 .- 1879-2294. ; 489-490, s. 1-20
-
Tidskriftsartikel (refereegranskat)abstract
- Language models that use interleaving, or shuffle, operators have applications in various areas of computer science, including system verification, plan recognition, and natural language processing. We study the complexity of the membership problem for such models, in other words, how difficult it is to determine if a string belongs to a language or not. In particular, we investigate how interleaving can be introduced into models that capture the context-free languages.
|
|
| 4. |
- Berglund, Martin, 1981-, et al.
(författare)
-
Transduction from trees to graphs through folding
- 2023
-
Ingår i: Information and Computation. - : Elsevier. - 0890-5401 .- 1090-2651. ; 295
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 5. |
- Björklund, Henrik, et al.
(författare)
-
Compression of finite-state automata through failure transitions
- 2014
-
Ingår i: Theoretical Computer Science. - : Elsevier. - 0304-3975 .- 1879-2294. ; 557, s. 87-100
-
Tidskriftsartikel (refereegranskat)abstract
- Several linear-time algorithms for automata-based pattern matching rely on failure transitions for efficient back-tracking. Like epsilon transitions, failure transition do not consume input symbols, but unlike them, they may only be taken when no other transition is applicable. At a semantic level, this conveniently models catch-all clauses and allows for compact language representation.This work investigates the transition-reduction problem for deterministic finite-state automata (DFA). The input is a DFA A and an integer k. The question is whether k or more transitions can be saved by replacing regular transitions with failure transitions. We show that while the problem is NP-complete, there are approximation techniques and heuristics that mitigate the computational complexity. We conclude by demonstrating the computational difficulty of two related minimisation problems, thereby cancelling the ongoing search for efficient algorithms.
|
|
| 6. |
- Björklund, Henrik, et al.
(författare)
-
Implementing a speech-to-text pipeline on the MICO platform
- 2016
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 7. |
- Björklund, Henrik, et al.
(författare)
-
Minimisation and Characterisation of Order-Preserving DAG Grammars
- 2018
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Order-preserving DAG grammars (OPDGs) is a formalism for processing semantic infor- mation in natural languages [5, 4]. OPDGs are sufficiently expressive to model abstract meaning representations, a graph-based form of semantic representation in which nodes en- code objects and edges relations. At the same time, they allow for efficient parsing in the uniform setting, where both the grammar and subject graph are taken as part of the input.In this article, we introduce an initial algebra semantic for OPDGs, which allows us to view them as regular tree grammars. This makes it possible to transfer a number of results from that domain to OPDGs, both in the unweighted and the weighted case. In particular, we show that deterministic OPDGs can be minimised efficiently, and that they are learnable in the so-called MAT setting. To conclude, we show that the languages generated by OPDGs are MSO-definable.
|
|
| 8. |
- Björklund, Henrik, et al.
(författare)
-
On the Regularity and Learnability of Ordered DAG Languages
- 2017
-
Ingår i: Implementation and Application of Automata. - Cham : Springer International Publishing. - 9783319601335 - 9783319601342 ; , s. 27-39
-
Konferensbidrag (refereegranskat)abstract
- Order-Preserving DAG Grammars (OPDGs) is a subclass of Hyper-Edge Replacement Grammars that can be parsed in polynomial time. Their associated class of languages is known as Ordered DAG Lan- guages, and the graphs they generate are characterised by being acyclic, rooted, and having a natural order on their nodes. OPDGs are useful in natural-language processing to model abstract meaning representa- tions. We state and prove a Myhill-Nerode theorem for ordered DAG languages, and translate it into a MAT-learning algorithm for the same class. The algorithm infers a minimal OPDG G for the target language in time polynomial in G and the samples provided by the MAT oracle.
|
|
| 9. |
- Björklund, Henrik, et al.
(författare)
-
Tree-based generation of restricted graph languages
- 2024
-
Ingår i: International Journal of Foundations of Computer Science. - : World Scientific. - 0129-0541. ; 35:1 & 2, s. 215-243
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 10. |
|
|
| 11. |
- Ahlgren, Serina, et al.
(författare)
-
Review of methodological choices in LCA of biorefinery systems - key issues and recommendations
- 2015
-
Ingår i: Biofuels, Bioproducts and Biorefining. - : Wiley. - 1932-1031 .- 1932-104X. ; 9:5, s. 606-619
-
Forskningsöversikt (refereegranskat)abstract
- The current trend in biomass conversion technologies is toward more efficient utilization of biomass feedstock in multiproduct biorefineries. Many life-cycle assessment (LCA) studies of biorefinery systems have been performed but differ in how they use the LCA methodology. Based on a review of existing LCA standards and guidelines, this paper provides recommendations on how to handle key methodological issues when performing LCA studies of biorefinery systems. Six key issues were identified: (i) goal definition, (ii) functional unit, (iii) allocation of biorefinery outputs, (iv) allocation of biomass feedstock, (v) land use, and (vi) biogenic carbon and timing of emissions. Many of the standards and guidelines reviewed here provide only general methodological recommendations. Some make more specific methodological recommendations, but these often differ between standards. In this paper we present some clarifications (e.g. examples of research questions and suitable functional units) and methodological recommendations (e.g. on allocation).
|
|
| 12. |
- Ahnström, Johan, et al.
(författare)
-
Farmers' Interest in Nature and Its Relation to Biodiversity in Arable Fields
- 2013
-
Ingår i: International Journal of Ecology. - : Hindawi Publishing Corporation. - 1687-9708 .- 1687-9716.
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 13. |
|
|
| 14. |
- Aho, Teija, et al.
(författare)
-
Impacts of effective population size on genetic diversity and relatedness in hatchery reared Brown trout (Salmo trutta L.)
- 2006
-
Ingår i: Aquaculture. - : Elsevier BV. - 0044-8486 .- 1873-5622. ; 253:1-4, s. 244-248
-
Tidskriftsartikel (refereegranskat)abstract
- Many populations of brown trout are managed by hatchery breeding and supportive release. Using a limited number of individuals as founders creates a bottleneck, which can lead to loss of genetic diversity in a population. In this study 17 populations of hatchery-reared brown trout were examined genetically using microsatellite markers. Genetic variation measured as gene diversity and allelic richness were analysed and the effects of effective population size of founders and time since founding on these parameters were explored. Allelic richness and gene diversity decreased with increasing time since founding of the stock, and there was a negative relationship between current effective population size and time since founding. Allelic richness was positively correlated with effective population size at founding. The results indicate that considerations concerning effective population size in hatcheries must be taken seriously to promote high levels of genetic variation among individuals and minimise loss of genetic diversity.
|
|
| 15. |
- Aichroth, Patrick, et al.
(författare)
-
MICO - MEDIA IN CONTEXT
- 2015
-
Ingår i: 2015 IEEE International Conference on Multimedia & Expo Workshops (ICMEW). - 9781479970797
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 16. |
|
|
| 17. |
- Andersson, Eric, et al.
(författare)
-
Generating semantic graph corpora with graph expansion grammar
- 2023
-
Ingår i: 13th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2023). - : Open Publishing Association. ; , s. 3-15
-
Konferensbidrag (refereegranskat)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.
|
|
| 18. |
- Arrendal, Johanna, 1975-
(författare)
-
Conservation Genetics of the Eurasian Otter in Sweden
- 2007
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In this thesis, molecular genetic methods were used to study a threatened species, the Eurasian otter. Estimates of population size and population dynamics parameters were obtained, the genetic effects of a restocking program was evaluated, and a population viability analysis was conducted to assess which demographic parameters are most important for the future viability of an otter population. Many of the studies were based on noninvasive genetic sampling of faeces. In the genetic evaluation of the restocking program, it was found that the released otters had contributed to subsequent generations. However, the effects were to a large degree limited to the near surroundings of the release areas. Comparison of two census methods, snow-tracking and noninvasive genetic census based on faeces, showed that approximately only half of the otters detected with the genetic census were found with the snow-tracking census. It is recommended to combine these two methods to obtain the most reliable estimates of population size. A short-term study on population dynamics in otters showed that apparent survival was higher in females than in males and that the rate of addition was also high and likely influenced by migration. The population viability analysis incorporated both genetics and demography and revealed that survival to first reproduction was the most crucial demographic parameter affecting the viability of the study population. This result suggests that conservation efforts should be focused on protocols that enhance the survival prospects of young females. Environmental stochasticity was also found to have large effects on the probability of extinction of this population.
|
|
| 19. |
- Arrendal, Johanna, et al.
(författare)
-
Reliability of noninvasive genetic census of otters compared to field censuses
- 2007
-
Ingår i: Conservation Genetics. - : Springer Science and Business Media LLC. - 1566-0621 .- 1572-9737. ; 8:5, s. 1097-1107
-
Tidskriftsartikel (refereegranskat)abstract
- Conservation and management actions are often highly dependent on accurate estimations of population sizes. However, these estimates are difficult to obtain for elusive and rare species. We compared two census methods for Eurasian otter: snow tracking and noninvasive genetic census based on the genotyping of faecal samples. With the noninvasive genetic census we detected the presence of almost twice as many otters as with snow tracking (23 and 10–15, respectively), and mark-recapture estimates based on the genetic census indicated that the real number of otters could be even higher. Our results indicate that snow tracking tends to underestimate the number of individuals and also that it is more susceptible to subjective assessment. We compared the strengths and weaknesses of the two methods.
|
|
| 20. |
- Belfrage, Kristina, et al.
(författare)
-
Effects of farm size and on-farm landscape heterogeneity on biodiversity-case study of twelve farms in a swedish landscape
- 2015
-
Ingår i: Agroecology and Sustainable Food Systems. - : Informa UK Limited. - 2168-3565 .- 2168-3573. ; 39:2, s. 170-188
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 21. |
- Bensch, Suna, et al.
(författare)
-
Deterministic Stack Transducers
- 2016
-
Ingår i: Implementation and Application of Automata. - Cham : Springer. - 9783319409450 - 9783319409467 ; , s. 27-38
-
Konferensbidrag (refereegranskat)abstract
- We introduce and investigate stack transducers, which are one-way stack automata with an output tape. A one-way stack automaton is a classical pushdown automaton with the additional ability to move the stack head inside the stack without altering the contents. For stack transducers, we distinguish between a digging and a non-digging mode. In digging mode, the stack transducer can write on the output tape when its stack head is inside the stack, whereas in non-digging mode, the stack transducer is only allowed to emit symbols when its stack head is at the top of the stack. These stack transducers have a motivation from natural language interface applications, as they capture long-distance dependencies in syntactic, semantic, and discourse structures.We study the computational capacity for deterministic digging and non-digging stack transducers, as well as for their non-erasing and checking versions. We finally show that even for the strongest variant of stack transducers the stack languages are regular.
|
|
| 22. |
- Bensch, Suna, et al.
(författare)
-
Deterministic Stack Transducers
- 2017
-
Ingår i: International Journal of Foundations of Computer Science. - : World Scientific Publishing Co. Pte. Ltd.. - 0129-0541. ; 28:5, s. 583-601
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce and investigate stack transducers, which are one-way stack automata with an output tape. A one-way stack automaton is a classical pushdown automaton with the additional ability to move the stack head inside the stack without altering the contents. For stack transducers, we distinguish between a digging and a non-digging mode. In digging mode, the stack transducer can write on the output tape when its stack head is inside the stack, whereas in non-digging mode, the stack transducer is only allowed to emit symbols when its stack head is at the top of the stack. These stack transducers have a motivation from natural-language interface applications, as they capture long-distance dependencies in syntactic, semantic, and discourse structures. We study the computational capacity for deterministic digging and non-digging stack transducers, as well as for their non-erasing and checking versions. We finally show that even for the strongest variant of stack transducers the stack languages are regular.
|
|
| 23. |
- Berglund, Martin, et al.
(författare)
-
Recognizing shuffled languages
- 2011
-
Ingår i: Language and Automata Theory and Applications. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783642212536 ; , s. 142-154
-
Konferensbidrag (refereegranskat)abstract
- Language models that use interleaving, or shuffle, operators have applications in various areas of computer science, including system verification, plan recognition, and natural language processing. We study the complexity of the membership problem for such models, i.e., how difficult it is to determine if a string belongs to a language or not. In particular, we investigate how interleaving can be introduced into models that capture the context-free languages.
|
|
| 24. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
A Comparative Evaluation of the Efficiency of N-Best Algorithms on Language Data
-
Annan publikation (övrigt vetenskapligt/konstnärligt)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.
|
|
| 25. |
- Björklund, Johanna, et al.
(författare)
-
A Comparison of Two N-Best Extraction Methods for Weighted Tree Automata
- 2018
-
Ingår i: Implementation and Application of Automata. - Cham : Springer. - 9783319948126 - 9783319948119 ; , s. 197-108
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 26. |
- Björklund, Johanna, et al.
(författare)
-
A Taxonomy of Minimisation Algorithms for Deterministic Tree Automata
- 2016
-
Ingår i: Journal of universal computer science (Online). - 0948-695X .- 0948-6968. ; 22:2, s. 180-196
-
Tidskriftsartikel (refereegranskat)abstract
- We present a taxonomy of algorithms for minimising deterministic bottom-up tree automata (DTAs) over ranked and ordered trees. Automata of this type and its extensions are used in many application areas, including natural language processing (NLP) and code generation. In practice, DTAs can grow very large, but minimisation keeps things manageable. The proposed taxonomy serves as a unifying framework that makes algorithms accessible and comparable, and as a foundation for efficient implementation. Taxonomies of this type are also convenient for correctness and complexity analysis, as results can frequently be propagated through the hierarchy. The taxonomy described herein covers a broad spectrum of algorithms, ranging from novel to well-studied ones, with a focus on computational complexity.
|
|
| 27. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Aggregation-based minimization of finite state automata
- 2021
-
Ingår i: Acta Informatica. - : Springer Nature. - 0001-5903 .- 1432-0525. ; 58, s. 177-194
-
Tidskriftsartikel (refereegranskat)abstract
- We present a minimization algorithm for non-deterministic finite state automata that finds and merges bisimulation-equivalent states. The bisimulation relation is computed through partition aggregation, in contrast to existing algorithms that use partition refinement. The algorithm simultaneously generalises and simplifies an earlier one by Watson and Daciuk for deterministic devices. We show the algorithm to be correct and run in time O(n2r2|Σ|), where n is the number of states of the input automaton M, r is the maximal out-degree in the transition graph for any combination of state and input symbol, and |Σ| is the size of the input alphabet. The algorithm has a higher time complexity than derivatives of Hopcroft’s partition-refinement algorithm, but represents a promising new solution approach that preserves language equivalence throughout the computation process. Furthermore, since the algorithm essentially computes the maximal model of a logical formula derived from M, optimisation techniques from the field of model checking become applicable.
|
|
| 28. |
- Björklund, Johanna, et al.
(författare)
-
An efficient best-trees algorithm for weighted tree automata over the tropical semiring
- 2015
-
Ingår i: Proc. 9th International Conference on Language and Automata Theory and Applications. - Cham : Springer. ; , s. 97-108
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 29. |
- Björklund, Johanna, et al.
(författare)
-
An evaluation of structured language modeling for automatic speech recognition
- 2017
-
Ingår i: Journal of universal computer science (Online). - Graz : Graz university of technology, Institute for information systems computer media IICM. - 0948-695X .- 0948-6968. ; 23:11, s. 1019-1034
-
Tidskriftsartikel (refereegranskat)abstract
- We evaluated probabilistic lexicalized tree-insertion grammars (PLTIGs) on a classification task relevant for automatic speech recognition. The baseline is a family of n-gram models tuned with Witten-Bell smoothing. The language models are trained on unannotated corpora, consisting of 10,000 to 50,000 sentences collected from the English section of Wikipedia. For the evaluation, an additional 150 random sentences were selected from the same source, and for each of these, approximately 3,200 variations were generated. Each variant sentence was obtained by replacing an arbitrary word by a similar word, chosen to be at most 2 character edits from the original. The evaluation task consisted of identifying the original sentence among the automatically constructed (and typically inferior) alternatives. In the experiments, the n-gram models outperformed the PLTIG model on the smaller data set, but as the size of data grew, the PLTIG model gave comparable results. While PLTIGs are more demanding to train, they have the advantage that they assign a parse structure to their input sentences. This is valuable for continued algorithmic processing, for example, for summarization or sentiment analysis.
|
|
| 30. |
- Björklund, Johanna, 1978-, et al.
(författare)
-
Aspects of plan operators in a tree automata framework
- 2012
-
Ingår i: 2012 15th International Conference on Information Fusion (FUSION). - : IEEE. - 9780982443842 - 9781467304177 ; , s. 1462-1467
-
Konferensbidrag (refereegranskat)abstract
- Plan recognition addresses the problem of inferring an agents goals from its action. Applications range from anticipating care-takers’ needs to predicting volatile situations. In this contribution, we describe a prototype plan recognition system that is based on the well-researched theory of (weighted) finite tree automata. To illustrate the system’s capabilities, we use data gathered from matches in the real-time strategy game StarCraft II. Finally, we discuss how more advanced plan operators can be accommodated for in this framework while retaining computational efficiency by taking after the field of formal model checking and over-approximating the target language.
|
|
| 31. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Assessing ecosystem services in perennial intercropping systems : participatory action research in Swedish modern agrofores
- 2014
-
Ingår i: Farming systems facing global challenges. - : IFSA Europe, Leibniz-Centre for Agricultural Landscape Research (ZALF), Humboldt-Universität zu Berlin. ; , s. 112-113, s. 1950-1959
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- The focus of this paper is on how to assess ecosystem services in complex agroforestry systems using a case of edible forest gardens. Benefits of doing these assessments in a participatory learning and action research (PLAR) context are elaborated, as well as difficulties and questions that this has raised. The PLAR group comprised farmers on 13 smallholdings, researchers and a facilitator, which through collaboration and participatory methods have developed a general design of a forest garden, 60 m2 in size and established it on all 13 participating farms. Important values of the work are that ecosystem services are related to specific local contexts and that methodology for multi-criteria assessments of the generation of ecosystem services on a farm scale are being developed. Farmers engaged in formulating research questions, development of field trial designs, sampling and analysis of results improves the relevance and quality of the research as well as advance the adoption of new knowledge.
|
|
| 32. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Assessing multifunctionality in relation to resource use : a holistic approach to measure efficiency, developed by participatory research
- 2012
-
Ingår i: Methods and procedures for building sustainable farming systems. - Dordrecht : Springer Netherlands. - 9789400750036 - 9789400750029 ; , s. 161-173
-
Bokkapitel (refereegranskat)abstract
- Today’s intensive agriculture needs to be transformed into sustainable production of food, and this process requires good tools that can assess whether an action is leading towards this in the long term. A critical issue is what optimal yield comprises in terms of other functions of agriculture, as higher yields might lead to e.g. a reduction in biodiversity or soil carbon. In this study, emergy analysis and footprinting were combined to assess and illustrate the total resource use caused by a farming activity (milk production) and to identify the renewable fraction of this resource use. The total efficiency was defined as a function of the resource use and the multifunctionality of production. The classification of ecosystem services in the Millennium Ecosystem Assessment (MA) was used as the basis for ranking multifunctionality. The results were expressed in the form of ecosystem bundles for the four MA categories (provisioning, supporting, regulating and cultural functions). Three scenarios with different degrees of input intensity and milk production were constructed and compared with the current production mode. The ratio of local renewable resource use to total resource use differed greatly between the different production strategies, being 1:3 for a self-sufficient organic farm and 1:14 for a conventional farm with maximum milk yield. Milk production was five-fold higher on the conventional farm, while generation of ecosystem services increased with increasing self-sufficiency under the local conditions prevailing in the study. Ecosystem services in all categories except provisioning were ranked higher when self-sufficiency increased.
|
|
| 33. |
|
|
| 34. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Bottom-up unranked tree-to-graph transducers for translation into semantic graphs
- 2019
-
Ingår i: Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing. - : Association for Computational Linguistics. ; , s. 7-17
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 35. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Bottom-up unranked tree-to-graph transducers for translation into semantic graphs
- 2021
-
Ingår i: Theoretical Computer Science. - : Elsevier. - 0304-3975 .- 1879-2294. ; 870, s. 3-28
-
Tidskriftsartikel (refereegranskat)abstract
- We develop a finite-state transducer for translating unranked trees into general graphs. This work is motivated by recent progress in semantic parsing for natural language, where sentences are first mapped into tree-shaped syntactic representations, and then these trees are translated into graph semantic representations. We investigate formal properties of our tree-to-graph transducers and develop a polynomial time algorithm for translating a weighted language of input trees into a packed representation, from which best-score graphs can be efficiently recovered.
|
|
| 36. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Bridging Perception, Memory, and Inference through Semantic Relations
- 2021
-
Ingår i: Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. - : Association for Computational Linguistics (ACL). - 9781955917094 ; , s. 9136-9142
-
Konferensbidrag (refereegranskat)abstract
- There is a growing consensus that surface form alone does not enable models to learn meaning and gain language understanding. This warrants an interest in hybrid systems that combine the strengths of neural and symbolic methods. We favour triadic systems consisting of neural networks, knowledge bases, and inference engines. The network provides perception, that is, the interface between the system and its environment. The knowledge base provides explicit memory and thus immediate access to established facts. Finally, inference capabilities are provided by the inference engine which reflects on the perception, supported by memory, to reason and discover new facts. In this work, we probe six popular language models for semantic relations and outline a future line of research to study how the constituent subsystems can be jointly realised and integrated.
|
|
| 37. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Ecosystem-based agriculture combining production and conservation : a viable way to feed the world in the long term?
- 2012
-
Ingår i: Journal of Sustainable Agriculture. - : Taylor & Francis. - 1044-0046 .- 1540-7578. ; 36:7, s. 824-855
-
Tidskriftsartikel (refereegranskat)abstract
- This study analyzed examples of sustainable ecosystem-based agriculture where management methods supported livelihoods of smallholders while at the same time local ecosystem services were enhanced in Ethiopia, Brazil, and the Philippines. Participation by farmers and collective actions were found to be a crucial driving force, as local specific knowledge and “learning by doing” were main components of the development. Social cohesion, particularly through associations and cooperatives, and improved marketing opportunities were also important drivers. Furthermore, recognition by authorities at all levels was perceived as crucial. Effects of climate change, insecure property rights, and political instability were potential threats. The possibilities of such systems to be scaled up beyond self-sufficiency raised further questions.
|
|
| 38. |
- Björklund, Johanna, et al.
(författare)
-
Efficient enumeration of weighted tree languages over the tropical semiring
- 2019
-
Ingår i: Journal of computer and system sciences (Print). - : Elsevier BV. - 0022-0000 .- 1090-2724. ; 104, s. 119-130
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 39. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Exploring the potential of edible forest gardens : experiences from a participatory action research project in Sweden
- 2019
-
Ingår i: Agroforestry Systems. - : Springer. - 0167-4366 .- 1572-9680. ; 93:3, s. 1107-1118
-
Tidskriftsartikel (refereegranskat)abstract
- To meet the environmental challenges that are presently confronting society, the narrow focus on agricultural production needs to be altered to one that places equal value on the generation of crucial ecosystem services. Current research shows that perennial intercropping systems such as agroforestry may be a feasible alternative. Based on studies during the establishment of edible forest gardens in 12 participating farms in Sweden, this paper explores the potential of utilizing multi-strata designs for food production in temperate, highincome countries. Design and species composition of such gardens, types of food they provide, and how they would best fit into the present landscape are discussed. Factors for success and major problems related to the establishment are shared. Potential benefits were found to be closely related to a thorough analysis of the social and ecological contexts before establishment. Characteristics of the site and goals of the garden need to guide species and design choices. If forest garden approaches to food production should contribute to more than local selfsufficiency, the gardens need to increase in scale. Marginal lands and transitions areas between different land uses may be appropriate. Large knowledge gaps concerning potential production, social and economic benefits, and agronomic issues were identified.
|
|
| 40. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Faster Computation of N-Best Lists for Weighted Tree Automata
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We show that a previously proposed algorithm for the N-best trees problem – not to be confused with the easier N-best runs problem – can be made more efficient by changing how it arranges and explores the search space. Given an integer N and a weighted tree automaton (wta) M over the tropical semiring, the algorithm computes N trees of minimal weight with respect to M. Compared to the original algorithm, the modifications increase the laziness of the evaluation strategy, which makes the new algorithm asymptotically more efficient than its predecessor.
|
|
| 41. |
- Björklund, Johanna, et al.
(författare)
-
Finding the N Best Vertices in an Infinite Weighted Hypergraph
- 2017
-
Ingår i: Theoretical Computer Science. - : Elsevier. - 0304-3975 .- 1879-2294. ; 682, s. 30-41
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 42. |
|
|
| 43. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Generation and polynomial parsing of graph languages with non-structural reentrancies
- 2023
-
Ingår i: Computational linguistics - Association for Computational Linguistics (Print). - : Association for Computational Linguistics. - 0891-2017 .- 1530-9312. ; 49:4, s. 841-882
-
Tidskriftsartikel (refereegranskat)abstract
- Graph-based semantic representations are popular in natural language processing (NLP), where it is often convenient to model linguistic concepts as nodes and relations as edges between them. Several attempts have been made to find a generative device that is sufficiently powerful to describe languages of semantic graphs, while at the same allowing efficient parsing. We contribute to this line of work by introducing graph extension grammar, a variant of the contextual hyperedge replacement grammars proposed by Hoffmann et al. Contextual hyperedge replacement can generate graphs with non-structural reentrancies, a type of node-sharing that is very common in formalisms such as abstract meaning representation, but which context-free types of graph grammars cannot model. To provide our formalism with a way to place reentrancies in a linguistically meaningful way, we endow rules with logical formulas in counting monadic second-order logic. We then present a parsing algorithm and show as our main result that this algorithm runs in polynomial time on graph languages generated by a subclass of our grammars, the so-called local graph extension grammars.
|
|
| 44. |
|
|
| 45. |
|
|
| 46. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Improved N-Best Extraction with an Evaluation on Language Data
- 2022
-
Ingår i: Computational linguistics - Association for Computational Linguistics (Print). - : MIT Press. - 0891-2017 .- 1530-9312. ; 48:1, s. 119-153
-
Tidskriftsartikel (refereegranskat)abstract
- We show that a previously proposed algorithm for the N-best trees problem can be made more efficient by changing how it arranges and explores the search space. Given an integer N and a weighted tree automaton (wta) M over the tropical semiring, the algorithm computes N trees of minimal weight with respect to M. Compared with the original algorithm, the modifications increase the laziness of the evaluation strategy, which makes the new algorithm asymptotically more efficient than its predecessor. The algorithm is implemented in the software BETTY, and compared to the state-of-the-art algorithm for extracting the N best runs, implemented 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 with respect to running time, while TIBURON seems to be the more memory-efficient choice.
|
|
| 47. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Learning tree languages
- 2016
-
Ingår i: Topics in grammatical inference. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783662483954 - 9783662483930 - 9783662569207 ; , s. 173-214
-
Bokkapitel (refereegranskat)abstract
- Tree languages have proved to be a versatile and rewarding extension of the classical notion of string languages.Many nice applications have been established over the years, in areas such as Natural Language Processing, Information Extraction, and Computational Biology. Although some properties of string languages transfer easily to the tree case, in particular for regular languages, several computational aspects turn out to be harder. It is therefore both of theoretical and of practical interest to investigate howfar and in whatways Grammatical Inference algorithms developed for the string case are applicable to trees. This chapter surveys known results in this direction. We begin by recalling the basics of tree language theory. Then, the most popular learning scenarios and algorithms are presented. Several applications of Grammatical Inference of tree languages are reviewed in some detail. We conclude by suggesting a number of directions for future research.
|
|
| 48. |
- Björklund, Johanna, et al.
(författare)
-
Local selling as a driving force for increased on-farm biodiversity
- 2009
-
Ingår i: Journal of Sustainable Agriculture. - : Informa UK Limited. - 1044-0046 .- 1540-7578. ; 33:8, s. 885-902
-
Tidskriftsartikel (refereegranskat)abstract
- This paper addresses the question of whether local selling of farm products improves on-farm biodiversity in rural areas. In contrast to the main agricultural trend of farms specializing and increasing in size in response to national and global markets, increasing numbers of Swedish farmers are diverting their efforts towards selling at local markets. Based on case studies of six farms selling their products locally, this paper explores the nature of the diversity on these farms and identifies qualities in the interaction between the farmers and their consumers that are supporting this diversity. The study showed that farmers who interacted with consumers were encouraged to diversify their production. Marketing a large diversity of products at a local market led to better income for participating farmers. Animal farms maintained important biodiversity associated with their extensive way of rearing animals on semi-natural pastures. Access to local markets promoted this.
|
|
| 49. |
- Björklund, Johanna, 1978-, et al.
(författare)
-
MAT Learning of Universal Automata
- 2013
-
Ingår i: Language and Automata Theory and Applications. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783642370632 - 9783642370649 ; , s. 141-152
-
Konferensbidrag (refereegranskat)abstract
- A MAT learning algorithm is presented that infers the universal automaton (UA) for a regular target language, using a polynomial number of queries with respect to that automaton. The UA is one of several canonical characterizations for regular languages. Our learner is based on the concept of an observation table, which seems to be particularly fitting for this computational model, and the necessary notions and definitions are adapted from the literature to the case of UA.
|
|
| 50. |
- Björklund, Johanna, et al.
(författare)
-
Minimization of Finite State Automata Through Partition Aggregation
- 2017
-
Ingår i: Language and Automata Theory and Applications. - Cham : Springer International Publishing AG. - 9783319537320 - 9783319537337 ; , s. 223-235
-
Konferensbidrag (refereegranskat)abstract
- We present a minimization algorithm for finite state automata that finds and merges bisimulation-equivalent states, identified through partition aggregation. We show the algorithm to be correct and run in time O(n(2)d(2) vertical bar Sigma vertical bar), where n is the number of states of the input automaton M, d is the maximal outdegree in the transition graph for any combination of state and input symbol, and vertical bar Sigma vertical bar is the size of the input alphabet. The algorithm is slower than those based on partition refinement, but has the advantage that intermediate solutions are also language equivalent to M. As a result, the algorithm can be interrupted or put on hold as needed, and the derived automaton is still useful. Furthermore, the algorithm essentially searches for the maximal model of a characteristic formula for M, so many of the optimisation techniques used to gain efficiency in SAT solvers are likely to apply.
|
|
