Search

Pushdown automata may contain transitions that are never used in any accepting run of the automaton. We present an algorithm for detecting such useless transitions. A finite automaton that captures the possible stack content during runs of the pushdown automaton, is first constructed in a forward procedure to determine which transitions are reachable, and then employed in a backward procedure to determine which of these transitions can lead to a final state. An implementation of the algorithm is shown to exhibit a favorable performance.

Phylogenetic networks are used to represent evolutionary scenarios in biology and linguistics. To find the most probable scenario, it may be necessary to compare candidate networks, to distinguish different networks, and to see when one network is embedded in another. Here, we consider the Network Containment problem, which asks whether a given network is contained in another network. We give a linear-time algorithm to this problem for the class of tree-child networks using the recently introduced tree-child sequences by Linz and Semple. We implement this algorithm in Python and show that the linear-time theoretical bound on the input size is achievable in practice.

Phylogenetic networks are important for the study of evolution. The number of methods to find such networks is increasing, but most such methods can only reconstruct small networks. To find bigger networks, one can attempt to combine small networks. In this paper, we study the {\sc Network Hybridization} problem, a problem of combining networks into another network with low complexity. We characterize this complexity via a restricted problem, {\sc Tree-child Network Hybridization}, and we present an FPT algorithm to efficiently solve this restricted problem.

In this paper the notion of network reification is introduced: a construction by which a given (base) network is extended by adding explicit states representing the characteristics defining the base network’s structure. Having the network structure represented in an explicit manner within the extended network enhances expressiveness and enables to model adaptation of the base network by dynamics within the reified network. It is shown how the approach provides a unified modeling perspective on representing network adaptation principles across different domains. This is illustrated by a number of known network adaptation principles such as for Hebbian learning in Mental Networks and for network evolution based on homophily in Social Networks.

In this paper it is analysed how emerging behaviour of an adaptive network can be related to characteristics of the adaptive network’s structure (which includes the adaptation structure). In particular, this is addressed for mental networks based on Hebbian learning. To this end relevant properties of the network and the adaptation that have been identified are discussed. As a result it has been found that in an achieved equilibrium state the value of a connection weight has a functional relation to the values of the connected states.

In this paper a computational model of a therapy for post-traumatic stress disorder by medicines is presented. The considered therapy has as a goal to decrease the stress level of a stressed individual by injections. Several medicines have been used to decrease the stress level. The presented temporal-causal network model aims at integrative modeling a medicine-based therapy where the relevant biological, cognitive and affective factors are modeled in a dynamic manner. In the first phase a strong stress-inducing stimulus causes the individual to develop an (affective) extreme stressful emotion. In the second phase, the individual makes the (cognitive) decision to apply an injection as a medicine with a goal shown to make the stressed individual relaxed. The third phase (biologically) models how the injection reduces the stress level.

In this paper the interaction of joint decision making, Hebbian learning of mirroring and bonding is analysed. An adaptive network model is designed, and scenarios are explored using this computational model. The results show that Hebbian learning of mirroring connections plays an important role in decision making, and that bonding can be necessary to make a joint decision, but also that conversely joint decisions strengthen the bonding and the mirroring connections.

It was conjectured by Černý in 1964 that a synchronizing DFA on n states always has a shortest synchronizing word of length at most (n−1) 2 (n−1)2, and he gave a sequence of DFAs for which this bound is reached. In 2006 Trahtman conjectured that apart from Černý’s sequence only 8 DFAs exist attaining the bound. He gave an investigation of all DFAs up to certain size for which the bound is reached, and which do not contain other synchronizing DFAs. Here we extend this analysis in two ways: we drop this latter condition, and we drop limits on alphabet size. For n≤4 n≤4 we do the full analysis yielding 19 new DFAs with smallest synchronizing word length (n−1) 2 (n−1)2, refuting Trahtman’s conjecture. All these new DFAs are extensions of DFAs that were known before. For n≥5 n≥5 we prove that none of the DFAs in Trahtman’s analysis can be extended similarly. In particular, as a main result we prove that the Černý examples C n Cn do not admit non-trivial extensions keeping the same smallest synchronizing word length (n−1) 2 (n−1)2.

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 \left( n^2 d^2 \left| \Sigma \right| \right) \), 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 \(\left| \Sigma \right| \) 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.

In this contribution, prototype-based systems and relevance learning are presented and discussed in the context of biomedical data analysis. Learning Vector Quantization and Matrix Relevance Learning serve as the main examples. After introducing basic concepts and related approaches, example applications of Generalized Matrix Relevance Learning are reviewed, including the classification of adrenal tumors based on steroid metabolomics data, the analysis of cytokine expression in the context of Rheumatoid Arthritis, and the prediction of recurrence risk in renal tumors based on gene expression.