Search

In a planar L-drawing of a directed graph (digraph) each edge e is represented as a polyline composed of a vertical segment starting at the tail of e and a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Our main focus is on bimodal graphs, i.e., digraphs admitting a planar embedding in which the incoming and outgoing edges around each vertex are contiguous. We show that every plane bimodal graph without 2-cycles admits a planar L-drawing. This includes the class of upward-plane graphs. Finally, outerplanar digraphs admit a planar L-drawing - although they do not always have a bimodal embedding - but not necessarily with an outerplanar embedding., Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

In this paper we investigate the board game Cram, which isan impartial combinatorial game, using an alpha-beta solver. Since Cram is anotoriously hard game in the sense that it is difficult to obtain reliableand useful domain knowledge to use in the search process, we decided torely on knowledge obtained from Combinatorial Game Theory (CGT).The first and most effective addition to our solver is to incorporateendgame databases prefilled with CGT values (nimbers) for all positionsfitting on boards with at most 30 squares. This together with twoefficient move-ordering heuristics aiming at early splitting positions intofragments fitting in the available databases gives a large improvement ofsolving power. Next we define five more heuristics based on CGT thatcan be used to further reduce the sizes of the search trees considerably.In the final version of our program we were able to solve all odd x oddCram boards for which results were available from the literature (evenx even and odd x even boards are trivially solved). Investigating newboards led to solving two boards not solved before, namely the 3 x 21board, a first-player win, and the 5 x 11 board, a second-player win.

Voltage-gated sodium channels (NavChs) are biological pores that control the flow of sodium ions through the cell membrane. In humans, mutations in genes encoding NavChs can disrupt physiological cellular activity thus leading to a wide spectrum of diseases. Here, we present a topological connection between the functional architecture of a NavAb bacterial channel and accumulation of atomic hydropathicity around its pore. This connection is established via a scaling analysis methodology that elucidates how intrachannel hydropathic density variations translate into hydropathic dipole field configurations along the pore. Our findings suggest the existence of a nonrandom cumulative hydropathic topology that is organized parallel to the membrane surface so that pore's stability, as well as, gating behavior are guaranteed. Given the biophysical significance of the hydropathic effect, our study seeks to provide a computational framework for studying cumulative hydropathic topological properties of NavChs and pore-forming proteins in general.

This article proposes a novel study on personality recognition using video data from different scenarios. Our goal is to jointly model nonverbal behavioral cues with contextual information for a robust, multi-scenario, personality recognition system. Therefore, we build a novel multi-stream Convolutional Neural Network (CNN) framework, which considers multiple sources of information. From a given scenario, we extract spatio-temporal motion descriptors from every individual in the scene, spatio-temporal motion descriptors encoding social group dynamics, and proxemics descriptors to encode the interaction with the surrounding context. All the proposed descriptors are mapped to the same feature space facilitating the overall learning effort. Experiments on two public datasets demonstrate the effectiveness of jointly modeling the mutual Person-Context information, outperforming the state-of-the art-results for personality recognition in two different scenarios. Last, we present CNN class activation maps for each personality trait, shedding light on behavioral patterns linked with personality attributes.

Recently it was shown that, if the subtree and chain reduction rules have been applied exhaustively to two unrooted phylogenetic trees, the reduced trees will have at most 15k-9 taxa where k is the TBR (Tree Bisection and Reconnection) distance between the two trees, and that this bound is tight. Here we propose five new reduction rules and show that these further reduce the bound to 11k-9. The new rules combine the ``unrooted generator'' approach introduced in [Kelk and Linz 2018] with a careful analysis of agreement forests to identify (i) situations when chains of length 3 can be further shortened without reducing the TBR distance, and (ii) situations when small subtrees can be identified whose deletion is guaranteed to reduce the TBR distance by 1. To the best of our knowledge these are the first reduction rules that strictly enhance the reductive power of the subtree and chain reduction rules., Comment: Accepted for journal publication. This version contains extra figures. Keywords: fixed-parameter tractability, tree bisection and reconnection, generator, kernelization, agreement forest, phylogenetic network, phylogenetic tree, hybridization number

In this work we investigate dynamical systems designed to approach the solution sets of inclusion problems involving the sum of two maximally monotone operators. Our aim is to design methods which guarantee strong convergence of trajectories towards the minimum norm solution of the underlying monotone inclusion problem. To that end, we investigate in detail the asymptotic behavior of dynamical systems perturbed by a Tikhonov regularization where either the maximally monotone operators themselves, or the vector field of the dynamical system is regularized. In both cases we prove strong convergence of the trajectories towards minimum norm solutions to an underlying monotone inclusion problem, and we illustrate numerically qualitative differences between these two complementary regularization strategies. The so-constructed dynamical systems are either of Krasnoselskii-Mann, of forward-backward type or of forward-backward-forward type, and with the help of injected regularization we demonstrate seminal results on the strong convergence of Hilbert space valued evolutions designed to solve monotone inclusion and equilibrium problems., 30 pages, 21 figures

In this paper we propose two methods for instance transfer based on conformal prediction. As a distinctive character, both of the methods are model independent and combine feature selection and source-instance selection to avoid negative transfer. The methods have been tested experimentally for different types of classification model on several benchmark data sets. The experimental results demonstrate that the new methods are capable of outperforming significantly standard instance transfer methods. (C) 2019 Elsevier B.V. All rights reserved.

The popularity of location-based social networks (LBSNs) has led to a tremendous amount of user check-in data. Recommending points of interest (POIs) plays a key role in satisfying users' needs in LBSNs. While recent work has explored the idea of adopting collaborative ranking (CR) for recommendation, there have been few attempts to incorporate temporal information for POI recommendation using CR. In this article, we propose a two-phase CR algorithm that incorporates the geographical influence of POIs and is regularized based on the variance of POIs popularity and users' activities over time. The time-sensitive regularizer penalizes user and POIs that have been more time-sensitive in the past, helping the model to account for their long-term behavioral patterns while learning from user-POI interactions. Moreover, in the first phase, it attempts to rank visited POIs higher than the unvisited ones, and at the same time, apply the geographical influence. In the second phase, our algorithm tries to rank users' favorite POIs higher on the recommendation list. Both phases employ a collaborative learning strategy that enables the model to capture complex latent associations from two different perspectives. Experiments on real-world datasets show that our proposed time-sensitive collaborative ranking model beats state-of-the-art POI recommendation methods., To appear in IEEE Transactions on Knowledge and Data Engineering (TKDE)

In this paper we consider the Maximum Independent Set problem (MIS) on B 1 -EPG graphs, that is the one-bend ( B 1 ) Edge intersection graphs of Paths on a Grid (EPG graphs). The graph class EPG was introduced in Golumbic et al. (2019) as the class of graphs whose vertices can be represented as simple paths on a rectangular grid so that two vertices are adjacent if and only if the corresponding paths share at least one edge of the underlying grid. The restricted class B k -EPG denotes EPG-graphs where every path has at most k bends. The study of MIS on B 1 -EPG graphs has been initiated in Epstein et al. (2013) where authors prove that MIS is NP-complete on B 1 -EPG graphs, and provide a polynomial 4-approximation. In this article we study the approximability and the fixed parameter tractability of MIS on B 1 -EPG. We show that the class of k ≥ 4 subdivided graphs is a subclass of B 1 -EPG, even if there is only one shape of path and if each path has its vertical part or its horizontal part of length at most 1. This implies that there is no PTAS for MIS (and several other classical problems) on these particular B 1 -EPG graphs. On the positive side, we show that if the length of the horizontal part of every path is bounded by a constant, then MIS admits a PTAS. Finally, we show that MIS is FPT in the standard parameterization on B 1 -EPG restricted to only three shapes of path, and W [ 1 ] -hard on B 2 -EPG. The status for general B 1 -EPG (with the four shapes) is left open.

This report summarises the Digital Ludeme Project, a recently launched 5-year research project being conducted at Maastricht University. This computational study of the world's traditional strategy games seeks to improve our understanding of early games, their development, and their role in the spread of related mathematical ideas throughout recorded human history.

Background/Objective Current severe traumatic brain injury (TBI) outcome prediction models calculate the chance of unfavourable outcome after 6 months based on parameters measured at admission. We aimed to improve current models with the addition of continuously measured neuromonitoring data within the first 24 h after intensive care unit neuromonitoring. Methods Forty-five severe TBI patients with intracranial pressure/cerebral perfusion pressure monitoring from two teaching hospitals covering the period May 2012 to January 2019 were analysed. Fourteen high-frequency physiological parameters were selected over multiple time periods after the start of neuromonitoring (0–6 h, 0–12 h, 0–18 h, 0–24 h). Besides systemic physiological parameters and extended Corticosteroid Randomisation after Significant Head Injury (CRASH) score, we added estimates of (dynamic) cerebral volume, cerebral compliance and cerebrovascular pressure reactivity indices to the model. A logistic regression model was trained for each time period on selected parameters to predict outcome after 6 months. The parameters were selected using forward feature selection. Each model was validated by leave-one-out cross-validation. Results A logistic regression model using CRASH as the sole parameter resulted in an area under the curve (AUC) of 0.76. For each time period, an increased AUC was found using up to 5 additional parameters. The highest AUC (0.90) was found for the 0–6 h period using 5 parameters that describe mean arterial blood pressure and physiological cerebral indices. Conclusions Current TBI outcome prediction models can be improved by the addition of neuromonitoring bedside parameters measured continuously within the first 24 h after the start of neuromonitoring. As these factors might be modifiable by treatment during the admission, testing in a larger (multicenter) data set is warranted.

In this paper, we introduce an unsupervised hierarchical framework for modeling trajectories in surveillance scenarios. Inspired by the object recognition field, a novel feature representation optimized for a neural network learning architecture is proposed. Low levels of the hierarchy capture local spatio-temporal motion attributes such as spatial orientation and speed, while higher levels contribute to obtaining richer semantic information. The bottom-up construction of the hierarchical framework exploits the inherent statistical correlations between neighboring elements using an increasing spatio-temporal grid. Cross-entropy based optimization in combination with autoencoders is used to learn weights for subsequent hierarchical layers. Finally, the Bayesian probabilistic framework built on top of the hierarchical model is proposed for applications such as long-term path prediction and abnormality detection. We demonstrate the efficiency of the proposed model on both indoor and outdoor datasets, achieving results comparable with state-of-the-art methods. (C) 2019 Elsevier B.V. All rights reserved.

Numerical computation is traditionally performed using floating-point arithmetic and truncated forms of infinite series, a methodology which allows for efficient computation at the cost of some accuracy. For most applications, these errors are entirely acceptable and the numerical results are considered trustworthy, but for some operations, we may want to have guarantees that the numerical results are correct, or explicit bounds on the errors. To obtain rigorous calculations, floating-point arithmetic is usually replaced by interval arithmetic and truncation errors are explicitly contained in the result. We may then ask the question of which mathematical operations can be implemented in a way in which the exact result can be approximated to arbitrary known accuracy by a numerical algorithm. This is the subject of computable analysis and forms a theoretical underpinning of rigorous numerical computation. The aim of this article is to provide a straightforward introduction to this subject that is powerful enough to answer questions arising in dynamic system theory.

People express their emotions through multiple channels, such as visual and audio ones. Consequently, automatic emotion recognition can be significantly benefited by multimodal learning. Even-though each modality exhibits unique characteristics; multimodal learning takes advantage of the complementary information of diverse modalities when measuring the same instance, resulting in enhanced understanding of emotions. Yet, their dependencies and relations are not fully exploited in audio–video emotion recognition. Furthermore, learning an effective metric through multimodality is a crucial goal for many applications in machine learning. Therefore, in this article, we propose multimodal emotion recognition metric learning (MERML), learned jointly to obtain a discriminative score and a robust representation in a latent-space for both modalities. The learned metric is efficiently used through the radial basis function (RBF) based support vector machine (SVM) kernel. The evaluation of our framework shows a significant performance, improving the state-of-the-art results on the eNTERFACE and CREMA-D datasets.

Learning arguments is highly relevant to the field of explainable artificial intelligence. It is a family of symbolic machine learning techniques that is particularly human-interpretable. These techniques learn a set of arguments as an intermediate representation. Arguments are small rules with exceptions that can be chained to larger arguments for making predictions or decisions. We investigate the learning of arguments, specifically the learning of arguments from a 'case model' proposed by Verheij [34]. The case model in Verheij's approach are cases or scenarios in a legal setting. The number of cases in a case model are relatively low. Here, we investigate whether Verheij's approach can be used for learning arguments from other types of data sets with a much larger number of instances. We compare the learning of arguments from a case model with the HeRO algorithm [15] and learning a decision tree., Comment: Presented at the 33rd BeNeLux AI Conference (BNAIC/BENELEARN 2021)

Within the field of artificial intelligence, multi-agent systems are used to model and solve complex problems in today's society. The complexity of such systems requires that individual agents have the ability to learn to optimise their own behaviour. An important challenge is to gain qualitative and theoretical insight into the dynamics of these learning multi-agent systems, as their results are often hard to predict in advance. This dissertation describes how methods from the field of evolutionary game theory can be used for this. These methods are then applied to systems such as social networks and the stock market.

Imagine computer programs (agents) that learn to coordinate or to compete. This study investigates how their learning processes influence each other. Such adaptive agents already take vital roles behind the scenes of our society, e.g., high frequency automated traders participate in financial trading and create more volume than human trading in some US markets. However, many learning algorithms only have proven performance guarantees if they act alone - as soon as a second agent influences the outcomes most guarantees are invalid. This dissertation extends guarantees to strategic interactions of several agents and examines how closely algorithms approximate optimal behavior.This research was funded by a TopTalent 2008 grant of NWO.

We compare one-dimensional representations for the isotopy stable dynamics of homeomorphisms in two dimensions. We consider the skeleton graph representative, which captures periodic behaviour, and the homotopy graph representative which captures homo-/heteroclinic behaviour. The main result of this paper is to show that the dual to the skeleton graph representative is the homotopy graph representative of the inverse map. This gives a strong link between different methods for computing the dynamics.

Phylogenetic trees and networks are leaf-labelled graphs used to model evolution. Display graphs are created by identifying common leaf labels in two or more phylogenetic trees or networks. The treewidth of such graphs is bounded as a function of many common dissimilarity measures between phylogenetic trees and this has been leveraged in fixed param- eter tractability results. Here we further elucidate the properties of dis- play graphs and their interaction with treewidth. We show that it is NP-hard to recognize display graphs, but that display graphs of bounded treewidth can be recognized in linear time. Next we show that if a phyloge- netic network displays (i.e. topologically embeds) a phylogenetic tree, the treewidth of their display graph is bounded by a function of the treewidth of the original network (and also by various other parameters). In fact, us- ing a bramble argument we show that this treewidth bound is sharp up to an additive term of 1. We leverage this bound to give an FPT algorithm, parameterized by treewidth, for determining whether a network displays a tree, which is an intensively-studied problem in the field. We conclude with a discussion on the future use of display graphs and treewidth in phylogenetics.

Perfect phylogenies are fundamental in the study of evolutionary trees because they capture the situation when each evolutionary trait emerges only once in history; if such events are believed to be rare, then by Occam's Razor such parsimonious trees are preferable as a hypothesis of evolution. A classical result states that 2-state characters permit a perfect phylogeny precisely if each subset of 2 characters permits one. More recently, it was shown that for 3-state characters the same property holds but for size-3 subsets. A long-standing open problem asked whether such a constant exists for each number of states. More precisely, it has been conjectured that for any fixed integer $r$, there exists a constant $f(r)$ such that a set of $r$-state characters $C$ has a perfect phylogeny if and only if every subset of at most $f(r)$ characters has a perfect phylogeny. In this paper, we show that this conjecture is false. In particular, we show that for any constant $t$, there exists a set $C$ of $8$-state characters such that $C$ has no perfect phylogeny, but there exists a perfect phylogeny for every subset of $t$ characters. This negative result complements the two negative results ("strikes") of Bodlaender et al. We reflect on the consequences of this third strike, pointing out that while it does close off some routes for efficient algorithm development, many others remain open., This article has been accepted for publication in Systematic Biology Published by Oxford University Press

The accuracy and reliability of weather forecasting are of importance for many economic, business and management activities. This paper introduces novel data-driven predictive models based on deep convolutional neural networks (CNN) architecture for temperature and wind speed prediction in weather data. In particular, the proposed deep learning framework employs different upgrading versions of the convolutional neural networks i.e. 1d-, 2d- and 3d-CNN. The introduced models exploit the spatio-temporal multivariate weather data for learning shared representations using historical data and forecasting weather elements for a number of user defined weather stations simultaneously in an end-to-end fashion. The embedded feature learning component of the models as well as coupling the learned features of different input layers have shown to have a significant impact on the prediction task. The proposed models show promising results compared to the classical neural networks architecture used for modeling nonlinear systems. Two experimental setups have been considered based on a dataset collected from the Weather Underground website at six stations located in Netherlands and Belgium as well as a larger dataset with higher temporal resolution from the National Climatic Data Center (NCDC) at five stations located in Denmark. First, we focus on simultaneously predicting the temperature of two main stations of Amsterdam and Brussels for 1-10 days ahead. The second experiment concerns wind speed prediction at three weather stations located in Denmark for 6 and 12 h ahead. The obtained numerical results show that learning new shared representations of the weather data by means of convolutional operations improves the prediction performance. (C) 2019 Elsevier B.V. All rights reserved.

Social complexity requires people to create new ways of interacting with one another to counteract new social boundaries. Board games provide one avenue by which archaeologists may examine the ways in which people interacted. The act of play is liminoid, allowing for people to more easily overcome social boundaries to interaction, while also creating a shared experience for the process of grounding. Thus, games provide an opportunity for people to build relationships and also to negotiate their identity. This research counters previous assertions that only complex societies play strategy games. In Bronze Age Cyprus, middle-range society became increasingly complex with the development of urbanism and differential access to wealth, while also producing a particularly large corpus of ancient board games. Determining where games were played, and then analyzing the social context of games in those spaces using multiple correspondence analysis, it was found that people were more likely to be playing in public during periods of greater complexity. This is likely due to the performative aspects of play, allowing for the communication of status in different ways when games are played in public spaces. The pattern found shows the variation in the ways people incorporated games into their social strategies during periods of different types of complexity.

Many of the famous single-player games, commonly called puzzles, can be shown to be NP-Complete. Indeed, this class of complexity contains hundreds of puzzles, since people particularly appreciate completing an intractable puzzle, such as Sudoku, but also enjoy the ability to check their solution easily once it's done. For this reason, using constraint programming is naturally suited to solve them. In this paper, we focus on logic puzzles described in the Ludii general game system and we propose using the XCSP formalism in order to solve them with any CSP solver., Comment: Accepted at the IEEE Conference on Games (CoG) 2019 (Short paper)

BACKGROUND: The present study examined food cravings in daily life by comparing overweight and normal-weight participants right before eating events and at non-eating moments. It was hypothesised that overweight participants would have (i) more frequent, (ii) stronger and (iii) a greater variety of high-caloric palatable food cravings, and also would (iv) consume more high-caloric palatable foods, than normal-weight participants.METHODS: Ecological momentary assessment (EMA) was used to assess food craving strength and frequency, variety of specific food cravings, and food intake. Fifty-seven overweight and 43 normal-weight adult participants were assessed at eating events and at an average of eight random non-eating moments per day for 2 weeks. Foods were categorised as: high-caloric high palatable foods (HCHP), fruits and salads, staple food dishes and sandwiches, and soups and yoghurts.RESULTS: Overweight participants reported more frequent HCHP food cravings specifically at non-eating moments than did normal-weight participants. Normal-weight participants reported more food cravings for staple foods, specifically at eating events. Moreover, overweight participants craved a greater variety of HCHP foods than normal-weight participants at both eating events and random non-eating moments. No other significant between-group differences were found.CONCLUSIONS: The results highlight the importance for obesity interventions (i) to specifically target high-caloric palatable food cravings that are experienced during the day and are not tied to eating moments and (ii) to aim for a reduction in the variety of high-caloric palatable food cravings. It might be fruitful to deliver treatment aimed at reducing cravings via mobile devices because this allows for easy individual tailoring and timing of interventions.

Monte-Carlo Tree Search (MCTS) has been applied successfully in many domains. Previous research has shown that adding randomization to certain components of MCTS might increase the diversification of the search and improve the performance. In a domain that tackles many games with different characteristics, like General Game Playing (GGP), trying to diversify the search might be a good strategy. This paper investigates the effect of randomizing search-control parameters for MCTS in GGP. Four different randomization strategies are compared and results show that randomizing parameter values before each simulation has a positive effect on the search in some of the tested games. Moreover, parameter randomization is compared with on-line parameter tuning.

This paper studies adaptive learning in the class of weighted network games. This class of games includes applications like research and development within interlinked firms, crime within social networks, the economics of pollution, and defense expenditures within allied nations. We show that for every weighted network game, the set of pure Nash equilibria is non-empty and, generically, finite. Pairs of players are shown to have jointly profitable deviations from interior Nash equilibria. If all interaction weights are either non-negative or non-positive, then Nash equilibria are Pareto inefficient. We show that quite general learning processes converge to a Nash equilibrium of a weighted network game if every player updates with some regularity.

This paper proposes a regime-switching recurrent network model (RS-RNN) for non-stationary time series. The RS-RNN model emits a mixture density with dynamic nonlinear regimes that fit flexibly data distributions with non-Gaussian shapes. The key novelties are: development of an original representation of the means of the component distributions by dynamic nonlinear recurrent networks, and derivation of a corresponding expectation maximization (EM) training algorithm for finding the model parameters. The elaborated switching dynamic nonlinear regimes make the RS-RNN especially attractive for describing non-stationary environmental time series. The results show that the RS-RNN applied to a real-world wind speed time series achieves standardized residuals similar to popular previous models, but it is more accurate distribution forecasting than other linear switching (MS-AR) and nonlinear neural network (MLP and RNN) models.

This paper introduces a novel cross-domain neural-kernel networks architecture for semi-supervised domain adaption problem. The proposed model consists of two stream neural-kernel networks corresponding to the source and target domains which are enriched with a coupling term. Each stream neural-kernel networks follows a combination of neural network layer and an explicit feature map constructed by means of random Fourier features. The introduced coupling term aims at enforcing correlations among the output of the intermediate layers of the two stream networks as well as encouraging the two networks to learn shared representation of the data from both source and target domains. Experimental results are given to illustrate the effectiveness of the proposed approaches on synthetic and real-life datasets. (C) 2019 Elsevier B.V. All rights reserved.

In combination with microspotting, whole-blood microfluidics can provide high-throughput information on multiple platelet functions in thrombus formation. Based on assessment of the inter-and intra-subject variability in parameters of microspot-based thrombus formation, we aimed to determine the platelet factors contributing to this variation. Blood samples from 94 genotyped healthy subjects were analyzed for conventional platelet phenotyping: i.e. hematologic parameters, platelet glycoprotein (GP) expression levels and activation markers (24 parameters). Furthermore, platelets were activated by ADP, CRP-XL or TRAP. Parallel samples were investigated for whole-blood thrombus formation (6 microspots, providing 48 parameters of adhesion, aggregation and activation). Microspots triggered platelet activation through GP Ib-V-IX, GPVI, CLEC-2 and integrins. For most thrombus parameters, inter-subject variation was 2-4 times higher than the intra-subject variation. Principal component analyses indicated coherence between the majority of parameters for the GPVI-dependent microspots, partly linked to hematologic parameters, and glycoprotein expression levels. Prediction models identified parameters per microspot that were linked to variation in agonist-induced alpha(IIb)beta(3) activation and secretion. Common sequence variation of GP6 and FCER1G, associated with GPVI-induced alpha(IIb)beta(3) activation and secretion, affected parameters of GPVI-and CLEC-2-dependent thrombus formation. Subsequent analysis of blood samples from patients with Glanzmann thrombasthenia or storage pool disease revealed thrombus signatures of aggregation-dependent parameters that were subject-dependent, but not linked to GPVI activity. Taken together, this high-throughput elucidation of thrombus formation revealed patterns of inter-subject differences in platelet function, which were partly related to GPVI-induced activation and common genetic variance linked to GPVI, but also included a distinct platelet aggregation component.

Here we show that deciding whether two rooted binary phylogenetic trees on the same set of taxa permit a cherry-picking sequence, a special type of elimination order on the taxa, is NP-complete. This improves on an earlier result which proved hardness for eight or more trees. Via a known equivalence between cherry-picking sequences and temporal phylogenetic networks, our result proves that it is NP-complete to determine the existence of a temporal phylogenetic network that contains topological embeddings of both trees. The hardness result also greatly strengthens previous inapproximability results for the minimum temporal-hybridization number problem. This is the optimization version of the problem where we wish to construct a temporal phylogenetic network that topologically embeds two given rooted binary phylogenetic trees and that has a minimum number of indegree-2 nodes, which represent events such as hybridization and horizontal gene transfer. We end on a positive note, pointing out that fixed parameter tractability results in this area are likely to ensure the continued relevance of the temporal phylogenetic network model., Fixed some tiny things. Accepted for journal publication

One approach to game design is to start with existing ideas and to modify them in interesting new ways. This process of “creative plagiarism” is applied to the Japanese logic puzzle Sudoku to create a new variant called Ludoku, which simplifies some aspects of the original puzzle while adding new strategies without adding undue complexity. This paper describes the design process from initial conception to final product, and how computer analysis was crucial to its success.

In 2001 Allen and Steel showed that, if subtree and chain reduction rules have been applied to two unrooted phylogenetic trees, the reduced trees will have at most 28k taxa where k is the TBR (Tree Bisection and Reconnection) distance between the two trees. Here we reanalyse Allen and Steel's kernelization algorithm and prove that the reduced instances will in fact have at most 15k-9 taxa. Moreover we show, by describing a family of instances which have exactly 15k-9 taxa after reduction, that this new bound is tight. These instances also have no common clusters, showing that a third commonly-encountered reduction rule, the cluster reduction, cannot further reduce the size of the kernel in the worst case. To achieve these results we introduce and use "unrooted generators" which are analogues of rooted structures that have appeared earlier in the phylogenetic networks literature. Using similar argumentation we show that, for the minimum hybridization problem on two rooted trees, 9k-2 is a tight bound (when subtree and chain reduction rules have been applied) and 9k-4 is a tight bound (when, additionally, the cluster reduction has been applied) on the number of taxa, where k is the hybridization number of the two trees., Comment: One figure added, two small typos fixed. This version to appear in SIDMA (SIAM Journal on Discrete Mathematics)

This report summarises the discussions and conclusions of a recent Dagstuhl research meeting, in which the foundations of the new research field of Digital Archaeoludology were established. Starting with the ERC-funded Digital Ludeme Project, research in this field aims to use techniques from the field of Artificial Intelligence (AI), and other computational and data-driven techniques, to study traditional games. The primary goals include gaining improved insight into the ways games may have been played throughout history, and how they influenced and transferred between different civilisations. Additional expected contributions of the Digital Ludeme Project include advances in General Game Playing and related areas of research in AI.

In this paper we investigate the game of Cram, which is the impartial version of Domineering. We have built Cram endgame databases for all board sizes < 30 squares. We developed a program that fills the databases with their Combinatorial Game Theory (CGT) values. Since Cram is an impartial game, all CGT values for Cram positions are so-called nimbers, indicated by ∗ n. The nimber value of a position not only directly determines the game-theoretic value (first- or second-player win), but also provides an optimal playing strategy. When analyzing the resulting databases we observed the following facts. Firstly we confirmed that the CGT values of all investigated empty boards are in agreement with results published in the literature. Since the value of an empty board depends completely on the values of many partially filled positions in the database, this is a strong indication that our process of filling the database with CGT values is correct. Secondly, although the series of values for 2 × n boards is completely regular, namely a value ∗ 0 for n being even and ∗ 1 for n being odd, this was not proven formally so far. We were able to provide such a proof. We also investigated the databases for their contents. So far we encountered nimber values up to ∗ 11 among single-fragment Cram positions. It appears that for a ∗ n value to occur a board size with ≈ 3 n squares is needed, some more for very tall boards ( 1 × n), some less for wider boards ( 4 × n). So far no single-fragment Cram positions were encountered with nimber values ⩾ ∗ 12, although we show a construction of larger multi-fragment positions with nimber values from ∗ 12 up to ∗ 15. In a preliminary experiment we incorporated the CGT endgame databases constructed into a simple alpha-beta solver for the game. Results revealed a large improvement in solving power.

Poly(2-alkyl-2-oxazoline)s (PAOx) are regaining interest for biomedical applications. However, their full potential is hampered by the inability to synthesise uniform high-molar mass PAOx. In this work, we proposed alternative intrinsic chain transfer mechanisms based on 2-oxazoline and oxazolinium chain-end tautomerisation and derived improved polymerization conditions to suppress chain transfer, allowing the synthesis of highly defined poly(2-ethyl-2-oxazoline) s up to ca. 50 kDa (dispersity (D)

In the network design game with n players, every player chooses a path in an edge-weighted graph to connect her pair of terminals, sharing costs of the edges on her path with all other players fairly. It has been shown that the price of stability of any network design game is at most $$H_n$$ , the n-th harmonic number. This bound is tight for directed graphs. For undirected graphs, it has only recently been shown that the price of stability is at most $$H_n \left( 1-\frac{1}{\Theta (n^4)} \right) $$ , while the worst-case known example has price of stability around 2.25. We improve the upper bound considerably by showing that the price of stability is at most $$H_{n/2} + \varepsilon $$ for any $$\varepsilon $$ starting from some suitable $$n \ge n(\varepsilon )$$ . We also study quality measures of different solution concepts for the multicast network design game on a ring topology. We recall from the literature a lower bound of $$\frac{4}{3}$$ and prove a matching upper bound for the price of stability. Therefore, we answer an open question posed by Fanelli et al. (Theor Comput Sci 562:90–100, 2015). We prove an upper bound of 2 for the ratio of the costs of a potential optimizer and of an optimum, provide a construction of a lower bound, and give a computer-assisted argument that it reaches 2 for any precision. We then turn our attention to players arriving one by one and playing myopically their best response. We provide matching lower and upper bounds of 2 for the myopic sequential price of anarchy (achieved for a worst-case order of the arrival of the players). We then initiate the study of myopic sequential price of stability and for the multicast game on the ring we construct a lower bound of $$\frac{4}{3}$$ , and provide an upper bound of $$\frac{26}{19}$$ . To the end, we conjecture and argue that the right answer is $$\frac{4}{3}$$ .

The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view accurately inferring the root location in a phylogenetic tree is notoriously difficult and poor root placement can artificially inflate the hybridization number. To this end we study a number of relaxed variants of this problem. We start by showing that the fundamental problem of determining whether an \emph{unrooted} phylogenetic network displays (i.e. embeds) an \emph{unrooted} phylogenetic tree, is NP-hard. On the positive side we show that this problem is FPT in reticulation number. In the rooted case the corresponding FPT result is trivial, but here we require more subtle argumentation. Next we show that the hybridization number problem for unrooted networks (when given two unrooted trees) is equivalent to the problem of computing the Tree Bisection and Reconnect (TBR) distance of the two unrooted trees. In the third part of the paper we consider the "root uncertain" variant of hybridization number. Here we are free to choose the root location in each of a set of unrooted input trees such that the hybridization number of the resulting rooted trees is minimized. On the negative side we show that this problem is APX-hard. On the positive side, we show that the problem is FPT in the hybridization number, via kernelization, for any number of input trees., 28 pages, 8 Figures

We consider sequential multi-player games with perfect information and with deterministic transitions. The players receive a reward upon termination of the game, which depends on the state where the game was terminated. If the game does not terminate, then the rewards of the players are equal to zero. We prove that, for every game in this class, a subgame perfect $$\varepsilon $$ ε -equilibrium exists, for all $$\varepsilon > 0$$ ε > 0 . The proof is constructive and suggests a finite algorithm to calculate such an equilibrium.

In case of a plan failure, plan-repair is a more promising solution than replanning from scratch. The effectiveness of plan-repair depends on knowledge of which plan action failed and why. Therefore, in this paper, we propose an Extended Spectrum Based Diagnosis approach that efficiently pinpoints failed actions. Unlike Model Based Diagnosis (MBD), it does not require the fault models and behavioral descriptions of actions. Our approach first computes the likelihood of an action being faulty and subsequently proposes optimal probe locations to refine the diagnosis. We also exploit knowledge of plan steps that are instances of the same plan operator to optimize the selection of the most informative diagnostic probes. In this paper, we only focus on diagnostic aspect of plan-repair process.

Human reasoning under uncertainty is conjectured to use Mental Models as a representation format. Each Mental Model characterizes a possible state of the world based on and constrained by the available information. Conclusion about the world must hold in each of these Mental Models. An important task in human reasoning is the construction these Mental Models using the available information. This paper investigates whether it is possible to design a neural network architecture that enables the construction of Mental Model, similarly to the conjectured way that humans reason. The paper investigates different architectures in an incremental way. The final architecture not only produces the correct mental models but also learns correct mental models for intermediate representation without being explicitly trained to do so. This contributes to the explainability of the approach.

The COVID-19 pandemic forces many robotics teachers to rethink their approach to education. Distance rules and the constant threat of a partial or complete lockdown leading to limited access to classroom equipment make it challenging to plan for hands-on education where students experience robotics by experimenting and studying with robotic hardware. On the other hand, this hands-on active learning experience is one of the strengths of robotics education and the ability to handle hardware equipment a substantial learning goal of study programs on robotics. In this paper we present and discuss the approach taken for the course Robotics and Embedded Systems at Maastricht University. The course had been adjusted to meet COVID-19 safety regulations and to allow for a fast seamless transition between onsite education at university and online education where students can work with robotic hardware at home. We share experience, best practice advice as well as educational material to help other teachers benefit from our developments. A key contribution is our custom-made, low-cost, educational modular robotic system for teaching kinematics, locomotion, and PID control that we make publicly available for replication through the website https://www.maastrichtuniversity.nl/edmo.

We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many connections to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows. We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values. We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, maximum degree, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing). We pay special attention to planar graphs. For example, we show that there are planar graphs that can be drawn in 3-space on a lot fewer lines than in the plane., Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)

Harmony in visual compositions is a concept that cannot be defined or easily expressed mathematically, even by humans. The goal of the research described in this paper was to find a numerical representation of artistic compositions with different levels of harmony. We ask humans to rate a collection of grayscale images based on the harmony they convey. To represent the images, a set of special features were designed and extracted. By doing so, it became possible to assign objective measures to subjectively judged compositions. Given the ratings and the extracted features, we utilized machine learning algorithms to evaluate the efficiency of such representations in a harmony classification problem. The best performing model (SVM) achieved 80% accuracy in distinguishing between harmonic and disharmonic images, which reinforces the assumption that concept of harmony can be expressed in a mathematical way that can be assessed by humans., Comment: 9 pages, ICAART 2021

We study the task of gathering k energy-constrained mobile agents in an undirected edge-weighted graph. Each agent is initially placed on an arbitrary node and has a limited amount of energy, which constrains the distance it can move. Since this may render gathering at a single point impossible, we study three variants of near-gathering:the goal is to move the agents into a configuration that minimizes either (i) the radius of a ball containing all agents, (ii) the maximum distance between any two agents, or (iii) the average distance between the agents. We prove that (i) is polynomial-time solvable, (ii) has a polynomial-time 2-approximation with a matching np-hardness lower bound, while (iii) admits a polynomial-time \(2(1-\tfrac{1}{k})\)-approximation, but no fptas, unless \(\text {p}=\text {np}\). We extend some of our results to additive approximation.keywordsmobile agentspower-aware robotslimited batterygatheringgraph algorithmsapproximationcomputational complexity.

Background Flow and mass cytometry are important modern immunology tools for measuring expression levels of multiple proteins on single cells. The goal is to better understand the mechanisms of responses on a single cell basis by studying differential expression of proteins. Most current data analysis tools compare expressions across many computationally discovered cell types. Our goal is to focus on just one cell type. Our narrower field of application allows us to define a more specific statistical model with easier to control statistical guarantees. Results Differential analysis of marker expressions can be difficult due to marker correlations and inter-subject heterogeneity, particularly for studies of human immunology. We address these challenges with two multiple regression strategies: a bootstrapped generalized linear model and a generalized linear mixed model. On simulated datasets, we compare the robustness towards marker correlations and heterogeneity of both strategies. For paired experiments, we find that both strategies maintain the target false discovery rate under medium correlations and that mixed models are statistically more powerful under the correct model specification. For unpaired experiments, our results indicate that much larger patient sample sizes are required to detect differences. We illustrate the R package and workflow for both strategies on a pregnancy dataset. Conclusion Our approach to finding differential proteins in flow and mass cytometry data reduces biases arising from marker correlations and safeguards against false discoveries induced by patient heterogeneity.

Introduction Electrocardiographic imaging (ECGI) has been used to investigate arrhythmia mechanisms in various conditions. Data on normal human subjects, especially in Europe, are scarce. Dynamic characteristics of ventricular activation and recovery during sinus rhythm have not been assessed before. Purpose To examine cardiac electrophysiology and its dynamic aspects in normal subjects using ECGI, in order to provide a range of normal patterns and values for activation (AT) and recovery times (RT), activation-recovery intervals (ARI, a surrogate for action potential duration) and their dynamicity. Methods 11 Subjects (age 57±7 years, 27% male, all normal LVEF) with atypical chest pain who underwent a cardiac CT-scan as part of clinical care but who were negative for any pathology on full examination were included. A validated non-commercial potential-based formulation of ECGI was used to reconstruct unipolar electrograms (EGMs) on the epicardial surface for three sinus beats within minutes from each other, per individual. ATs and RTs were determined as the maximum negative upslope during QRS, and maximum positive upslope during T wave of the local EGMs. Additionally, we determined locations of first and last activation and recovery. Inter- and intra-individual differences were computed. Results Subjects had normal 12-lead characteristics without ST-deviations, and an average QTc interval of 415±18ms. Figure 1, panel A shows ECGI during sinus rhythm for 3 representative subjects, and panel B summarizes all findings on the entire epicardium. The first epicardial activation breakthrough typically occurred on the right ventricle (RV), consistent with the concept that the thinner RV wall accounts for a faster transmural activation. Last activation was mostly on the base of the left ventricle (LV), on the inferior to lateral wall. Earliest recovery occurred predominantly on the anterior surface, while latest recovery occurred on the inferior surface. Complete activation of the epicardial surface (from earliest to latest AT) took 41±8ms, while recovery (earliest AT to latest RT) took 317±24ms and average ARI (local AT to local RT) took 232±23ms. Thus, inter-individual variation of recovery duration was higher than of activation. Intra-individual differences between beats in ATs, RTs and ARIs of distinct sinus beats were small (2.3±3.1ms, 9.7±8.8ms and 9.8±9.1ms, respectively) suggesting that ECGI enables stable reconstruction quality (Figure 1, panel C). Conclusion In this cohort, noninvasive ECGI provides novel insights in ventricular electrophysiology. Electrical recovery is more variable than activation, both intra-individually and inter-individually. Overall, AT, RT and ARI differences between sinus beats were low. ECGI appears suitable to assess dynamic electrical patterns during cardiac pathology. Figure 1 Funding Acknowledgement Type of funding source: None