Evan Driscoll, Aditya Thakur, Amanda Burton et al. · Minds at UW (University of Wisconsin) · 2011
WALi-NWA is a C++ library for constructing, querying, and operating on \nnested-word automata. It is a portion of the WALi library, which \nprovides types and operations for weighted automata. While the NWA \nportions of WALi are mostly logically separate from the rest of WALi, it \ndoes use facilities provided by WALi and inter-operates with WALi's \nweighted pushdown system (WPDS) code.
Cited by 4Open access
Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier et al. · Logical Methods in Computer Science · 2019
We consider the problem of evaluating in streaming (i.e., in a single left-to-right pass) a nested word transduction with a limited amount of memory. A transduction T is said to be height bounded memory (HBM) if it can be evaluated with a memory that depends only on the size of T and on the height of the input word. We show that it is decidable in coNPTime for a nested word transduction defined by a visibly pushdown transducer (VPT), if it is HBM. In this case, the required amount of memory may depend exponentially on the height of the word. We exhibit a sufficient, decidable condition for a VPT to be evaluated with a memory that depends quadratically on the height of the word. This condition defines a class of transductions that strictly contains all determinizable VPTs.
Cited by 13Open access
Christian Schilling, Albert-ludwigs-universität Freiburg Im Breisgau, Matthias Heizmann et al. · 2013
Cited by 0
Dmitry Chistikov, Rupak Majumdar · Lecture notes in computer science · 2013
Cited by 5
Evan Driscoll, Aditya Thakur, Thomas Reps · Lecture notes in computer science · 2012
Cited by 16
Xiaoxue Piao, Kai Salomaa · Theoretical Computer Science · 2009
Cited by 30
Yo-Sub Han, Kai Salomaa · Theoretical Computer Science · 2009
Cited by 23
Iovka Boneva, Joachim Niehren, Momar Sakho · Lecture notes in computer science · 2020
Cited by 1
Iovka Boneva, Joachim Niehren, Momar Sakho · HAL (Le Centre pour la Communication Scientifique Directe) · 2020
We study the problem of whether regular expressions for nested words can be compiled to small deterministic nested word au-tomata (NWAs). In theory, we obtain a positive answer for small deter-ministic regular expressions for nested words. In practice of navigational path queries, nondeterministic NWAs are obtained for which NWA de-terminization explodes. We show that practical good solutions can be obtained by using stepwise hedge automata as intermediates.
Cited by 0Open access
Swarat Chaudhuri, Rajeev Alur · 2008
In classical automata-theoretic model checking [6], a system model generates a language L of words modeling system executions, and verification involves
Cited by 0
Olivier Gauwin Joachim Niehren, Inria Lille · 2009
Abstract. Earliest query answering (eqa) is an objective of streaming algorithms for XML query answering, that aim for close to optimal memory management. In this paper, we show that eqa is infeasible even for a small fragment of XPath unless P=NP. We then present an eqa algorithm for queries and schemas defined by deterministic nested word automata (dnwas) and distinguish a large class of dnwas for which streaming query answering is feasible in polynomial space and time. 1
Cited by 0
Evan Driscoll, Aditya Thakur, Thomas Reps · 2012
Abstract. Nested-word automata (NWAs) are a language formalism that helps bridge the gap between finite-state automata and pushdown automata. NWAs can express some context-free properties, such as parenthesis matching, yet retain all the desirable closure characteristics of finite-state automata. This paper describes OpenNWA, a C++ library for working with NWAs. The library provides the expected automata-theoretic operations, such as intersection, determinization, and complementation. It is packaged with WALi—the W eighted Automaton Library—and interoperates closely with the weighted pushdown system portions of WALi. 1
Cited by 0
Olivier Gauwin, Joachim Niehren, Sophie Tison · Lecture notes in computer science · 2009
Cited by 19
Emmanuel Filiot, Olivier Gauwin, Pierre-alain Reynier et al. · 2012
We consider the problem of evaluating in streaming (i.e. in a single left-to-right pass) a nested word transduction with a limited amount of memory. A transduction T is said to be height bounded memory (HBM) if it can be evaluated with a memory that depends only on the size of T and on the height of the input word. We show that it is decidable in coNPTime for a nested word transduction defined by a visibly pushdown transducer (VPT), if it is HBM. In this case, the required amount of memory may depend exponentially on the height of the word. We exhibit a sufficient, decidable condition for a VPT to be evaluated with a memory that depends quadratically on the height of the word. This condition defines a class of transductions that strictly contains all determinizable VPTs. 1
Cited by 0
Manfred Droste, Bundit Pibaljommee · International Journal of Foundations of Computer Science · 2014
Nested words have been introduced by Alur and Madhusudan as a model for e.g. recursive programs or XML documents and have received much recent interest. In this paper, we investigate a quantitative automaton model and a quantitative logic for nested words. The behavior resp. the semantics map nested words to weights which are taken from a strong bimonoid. Strong bimonoids can be viewed as semirings without requiring the distributivity assumption which was essential in the classical theory of formal power series; strong bimonoids include e.g. all bounded lattices and many other structures from multi-valued logics. Our main results show that weighted nested word automata and suitable weighted MSO logics are expressively equivalent. This extends the classical Büchi-Elgot result from words to a weighted setting for nested words.
Cited by 3
Peng Tang, Ming Lei, Chunhua Song et al. · Lecture notes in computer science · 2026
Cited by 0
Shaoguo Cui, Guangping HU · 2022
Nested named entity recognition is aimed at overlapping entities. The span-based approach considers nested named entity recognition as a two-stage task: span extraction and span classification. However, this method has some problems such as error propagation and long entity recognition. Therefore, this paper put forward a word pair relationship classification model, which describes nested entities as words and multi relationship classification tasks between words. Firstly, the grid matrix representation of word pairs is constructed by traversing the text. Then, in order to enhance the connection between word and word, the distance information and position information of word pairs are fused into the grid matrix representation of word pairs. Finally, through the grid matrix to prediction category relationships of all pairs of words. The experimental results show that the F1-score of the proposed word pair classification model reaches 77.3% on the nested entity recognition dataset GENIA, and its nested entity recognition ability is superior to the existing models.
Cited by 0
Trung Trinh, Tho Quan, Trung Mai · arXiv (Cornell University) · 2019
Most of the information on the Internet is represented in the form of microtexts, which are short text snippets such as news headlines or tweets. These sources of information are abundant, and mining these data could uncover meaningful insights. Topic modeling is one of the popular methods to extract knowledge from a collection of documents; however, conventional topic models such as latent Dirichlet allocation (LDA) are unable to perform well on short documents, mostly due to the scarcity of word co-occurrence statistics embedded in the data. The objective of our research is to create a topic model that can achieve great performances on microtexts while requiring a small runtime for scalability to large datasets. To solve the lack of information of microtexts, we allow our method to take advantage of word embeddings for additional knowledge of relationships between words. For speed and scalability, we apply autoencoding variational Bayes, an algorithm that can perform efficient black-box inference in probabilistic models. The result of our work is a novel topic model called the nested variational autoencoder, which is a distribution that takes into account word vectors and is parameterized by a neural network architecture. For optimization, the model is trained to approximate the posterior distribution of the original LDA model. Experiments show the improvements of our model on microtexts as well as its runtime advantage.
Cited by 1Open access
Denis Debarbieux, Olivier Gauwin, Joachim Niehren et al. · Theoretical Computer Science · 2015
Cited by 20
Zhuang Qiu, Fernanda Ferreira, Emily Morgan · 2023
In this paper, we report three experiments investigating the cognitive mechanisms that underlie the semantic processing of a linguistic construction largely uninvestigated, namely, the nested structure of two epistemic modals in a single clause, as illustrated in the sentence “He may certainly have forgotten” (Lyons, 1977). Two theoretical approaches provide different account for the processing of this structure. Based on a formal linguistic account (Moss, 2015), the meaning of the second modal should be interpreted within the scope of the first modal, and thus, if the first and second modals switch their positions, a change in meaning would be expected. This account is referred to as the “scope account”. In contrast, a good-enough processing account (Ferreira & Lowder, 2016) predicts that the scope of nested modals may not be thoroughly processed, and thus, the order of the modals should not change interlocutors’ interpretation of the nested expression. We examined these two accounts in three experiments that elicited participants’ interpretation of nested epistemic expressions, focusing on whether or not the order and the adjacency of the component modals affected how the nested expressions are interpreted. The repeated absence of the order effect was observed in all three experiments regardless of the adjacency of the modals. This finding challenges the scope account and suggests a holistic processing mechanism in line with the “good enough” processing framework.
Cited by 0Open access