Umeå universitets logga

In graph grammars based on borrowing hyperedge replacement (BHR), a production replaces a hyperedge by a hypergraph that contains borrowed nodes, which are later contracted with other nodes of the graph being derived. In contrast to context-free hyperedge replacement, this allows graph languages of unbounded treewidth to be defined. Here we further equip the productions of BHR grammars with conditions, which are specified by graph formulas that may require (or forbid) the existence of paths of arbitrary length in the graphs of the language. This is defined in such a way that the top-down parsers for BHR grammars devised in earlier work can be extended to verify these conditions.

We introduce dynamically weighted tree transducers (dyn-wtts), a weighted generalization of top-down tree transducers with regular look-ahead in which rule weights are determined by external tree weighters mapping input trees to values in a commutative semiring. The general framework allows for any kind of device defining a weighted tree language to serve as a tree weighter. In this paper, we focus on weighters implemented by different classes of tree automata and show how the resulting classes of weighted tree transformations relate to one another and to known classes. In particular, we show how conventional top-down weighted tree transducers (with and without regular look-ahead) can be expressed as dyn-wtts, also in the linear and non-deleting cases.

A frequent problem in document clustering and topic modeling is the lack of ground truth. Models are typically intended to reflect some aspect of how human readers view texts (the general theme, sentiment, emotional response, etc), but it can be difficult to assess whether they actually do. The only real ground truth is human judgement. To enable researchers and practitioners to collect such judgement in a cost-efficient standardized way, we have developed the crowdsourcing solution CIPHE -- Cluster Interpretation and Precision from Human Exploration. CIPHE is an adaptable framework which systematically gathers and evaluates data on the human perception of a set of document clusters where participants read sample texts from the cluster. In this article, we use CIPHE to study the limitations that keyword-based methods pose in topic modeling coherence evaluation. Keyword methods, including word intrusion, are compared with the outcome of the thorougher CIPHE on scoring and characterizing clusters. The results show how the abstraction of keywords skews the cluster interpretation for almost half of the compared instances, meaning that many important cluster characteristics are missed. Further, we present a case study where CIPHE is used to (a) provide insights into the UK news domain and (b) find out how the evaluated clustering model should be tuned to better suit the intended application. The experiments provide evidence that CIPHE characterizes clusters in a predictable manner and has the potential to be a valuable framework for using human evaluation in the pursuit of nuanced research aims.

Engelfriet and Vereijken have shown that linear graph grammars based on hyperedge replacement generate graph languages that can be considered as interpretations of regular string languages over typed symbols. In this paper we show that finite automata can be lifted from strings to graphs within the same framework. For the efficient recognition of graphs with these automata, we make them deterministic by a modified powerset construction, and state sufficient conditions under which deterministic finite graph automata recognize graphs without the need to use backtracking.

In many application areas, it is necessary to specify and check  properties of graphs.  Such properties may be complex, placing structural requirements on graph regions of unbounded size. In this paper, we show that alternating graph automata can check such graph properties, e.g., whether a given input graph is a tree, or whether  it contains a Hamiltonian cycle or not.  In fact, we show that these automata can accept PSPACE-complete graph languages and that, conversely, their uniform membership  problem is contained in PSPACE.

In many application areas, it is necessary to specify and check  properties of graphs.  Such properties may be complex, placing structural requirements on graph regions of unbounded size. In this paper, we show that alternating graph automata can check such graph properties, e.g., whether a given input graph is a tree, or whether  it contains a Hamiltonian cycle or not.  In fact, we show that these automata can accept PSPACE-complete graph languages and that, conversely, their uniform membership  problem is contained in PSPACE.

Graph-based modeling plays a fundamental role in many areas of computer science. In this paper, we introduce systems of graph formulas with variables for specifying graph properties; this notion generalizes the graph formulas introduced in earlier work by incorporating recursion. We show that model that extends traditional finite-state these formula systems have the same expressive power as alternating graph automata, a computational automata to graphs, and allows both existential and universal states. In particular, we provide a bidirectional translation between formula systems and alternating graph automata, proving their equivalence in specifying graph languages. This result implies that alternating graph automata can be naturally represented using logic-based formulations, thus bridging the gap between automata-theoretic and logic-based approaches to graph language specification.

Document clustering models serve unique application purposes, which turns model quality into a property that depends on the needs of the individual investigator. We propose a framework, Cluster Interpretation and Precision from Human Exploration (CIPHE), for collecting and quantifying human interpretations of cluster samples. CIPHE tasks survey participants to explore actual document texts from cluster samples and records their perceptions. It also includes a novel inclusion task that is used to calculate the cluster precision in an indirect manner. A case study on news clusters shows that CIPHE reveals which clusters have multiple interpretation angles, aiding the investigator in their exploration.

We study graph expansion grammars, a type of graph grammar that has recently been introduced with motivations in natural language processing. Graph expansion generalizes the well-known hyperedge replacement. In contrast to the latter, the former is able to generate graph languages of unbounded treewidth, like the set of all graphs. In an earlier paper, the complexity of the membership problem of the generated languages was studied, the main result being a polynomial parsing algorithm for local DAG expansion grammars (there called local DAG expansion grammars), a subclass of graph expansion grammars that generates directed acyclic graphs. Here, we study the generative power of local graph expansion grammars. While they, un- restricted, are able to simulate Turing machines, we identify natural restrictions that give rise to a pumping lemma and ensure that the generated languages have regular path languages as well as a semi-linear Parikh image. 

The AB Game is a game similar to the popular game Mastermind. We study a version of this game called Static Black-Peg AB Game. It is played by two players, the codemaker and the codebreaker. The codemaker creates a so-called secret by placing a color from a set of c colors on each of p ≤ c pegs, subject to the condition that every color is used at most once. The codebreaker tries to determine the secret by asking questions, where all questions are given at once and each question is a possible secret. As an answer the codemaker reveals the number of correctly placed colors for each of the questions. After that, the codebreaker only has one more try to determine the secret and thus to win the game. 

For given p and c, our goal is to find the smallest number k of questions the codebreaker needs to win, regardless of the secret, and the corresponding list of questions, called a (k + 1)-strategy. We present a (⌈4c/3⌉ − 1)-strategy for p = 2 for all c ≥ 2, and a ⌊(3c − 1)/2⌋-strategy for p = 3 for all c ≥ 4 and show the optimality of both strategies, i.e., we prove that no (k + 1)-strategy for a smaller k exists.