Open-world continual learning (OWCL) adapts to sequential tasks with open samples, learning knowledge incrementally while preventing forgetting. However, existing OWCL still requires a large amount of labeled data for training, which is often impractical in real-world applications. Given that new categories/entities typically come with limited annotations and are in small quantities, a more realistic situation is OWCL with scarce labeled data, i.e., few-shot training samples. Hence, this paper investigates the problem of open-world few-shot continual learning (OFCL), challenging in (i) learning unbounded tasks without forgetting previous knowledge and avoiding overfitting(ii) constructing compact decision boundaries for open detection with limited labeled data, and (iii) transferring knowledge about knowns and unknowns and even update the unknowns to knowns once the labels of open samples are learned. In response, we propose a novel OFCL framework that integrates three key components: (1) an instance-wise token augmentation (ITA) that represents and enriches sample representations with additional knowledge(2) a margin-based open boundary (MOB) that supports open detection with new tasks emerge over time, and (3) an adaptive knowledge space (AKS) that endows unknowns with knowledge for the updating from unknowns to knowns. Finally, extensive experiments show that the proposed OFCL framework outperforms all baselines remarkably with practical importance and reproducibility. The source code is released at https://github.com/liyj1201/OFCL.

Abstract Quantum circuit compilation comprises many computationally hard reasoning tasks that lie inside # $${\textsf{P}}$$ P and its decision counterpart in $${\textsf{PP}}$$ PP . The classical simulation of universal quantum circuits is a core example. We show for the first time that a strong simulation of universal quantum circuits can be efficiently tackled through weighted model counting by providing a linear-length encoding of Clifford+Tcircuits. To achieve this, we exploit the stabilizer formalism by Knill, Gottesmann, and Aaronson by reinterpreting quantum states as a linear combination of stabilizer states. With an open-source simulator implementation, we demonstrate empirically that model counting often outperforms state-of-the-art simulation techniques based on the ZX calculus and decision diagrams. Our work paves the way to apply the existing array of powerful classical reasoning tools to realize efficient quantum circuit compilation; one of the obstacles on the road towards quantum supremacy.

Abstract Verifying equivalence between two quantum circuits is a hard problem, that is nonetheless crucial in compiling and optimizing quantum algorithms for real-world devices. This paper gives a Turing reduction of the (universal) quantum circuits equivalence problem to weighted model counting (WMC). Our starting point is a folklore theorem showing that equivalence checking of quantum circuits can be done in the so-called Pauli-basis. We combine this insight with a WMC encoding of quantum circuit simulation, which we extend with support for the Toffoli gate. Finally, we prove that the weights computed by the model counter indeed realize the reduction. With an open-source implementation, we demonstrate that this novel approach can outperform a state-of-the-art equivalence-checking tool based on ZX calculus and decision diagrams.

Information cascade size prediction is one of the primary challenges for understanding the diffusion of information. Traditional feature-based methods heavily rely on the quality of handcrafted features, requiring extensive domain knowledge and hard to generalize to new domains. Recently, inspired by the success of deep learning in computer vision and natural language processing, researchers have developed neural network-based approaches for tackling this problem. However, existing deep learning-based methods either focused on modeling the temporal characteristics of cascades but ignored the structural information or failed to take the order-scale and position-scale into consideration in modeling structures of information propagation. This paper proposed a novel graph neural network-based model, called MUCas, to learn the latent representations of cascade graphs from a multi-scale perspective, which can make full use of the direction-scale, high-order-scale, position-scale, and dynamic-scale of cascades via a newly designed MUlti-scale Graph Capsule Network (MUG-Caps) and the influence-attention mechanism. Extensive experiments conducted on two real-world data sets demonstrate that our MUCas significantly outperforms the state-of-the-art approaches.

In this paper, we study a subclass of constraint automata with local variables. The fragment denotes an executable subset of constraint automata for which synchronization and data constraints are expressed in an imperative guarded command style, instead of a denotational style as in the coordination language Reo. To demonstrate the executability property, we provide a translation scheme from symbolic constraint automata to Promela, the language of the model checker Spin. As a proof of concept, we model in Reo a software defined network circuit, and use the Spin model checker to verify that our model satisfies some temporal properties.

Abstract In this paper, we provide a formal explanation of symbolic execution in terms of a symbolic transition system and prove its correctness and completeness with respect to an operational semantics which models the execution on concrete values.We first introduce a formalmodel for a basic programming languagewith a statically fixed number of programming variables. This model is extended to a programming language with recursive procedures which are called by a call-by-value parameter mechanism. Finally, we present a more general formal framework for proving the soundness and completeness of the symbolic execution of a basic object-oriented language which features dynamically allocated variables.

Researchers have exerted tremendous effort in designing ways to detect and identify rumors automatically. Traditional approaches focus on feature engineering, which requires extensive manual efforts and are difficult to generalize to different domains. Recently, deep learning solutions have emerged as the de facto methods which detect online rumors in an end-to-end manner. However, they still fail to fully capture the dissemination patterns of rumors. In this study, we propose a novel diffusion-based rumor detection model, called Macroscopic and Microscopic-aware Rumor Detection, to explore the full-scale diffusion patterns of information. It leverages graph neural networks to learn the macroscopic diffusion of rumor propagation and capture microscopic diffusion patterns using bidirectional recurrent neural networks while taking into account the user-time series. Moreover, it leverages knowledge distillation technique to create a more informative student model and further improve the model performance. Experiments conducted on two real-world data sets demonstrate that our method achieves significant accuracy improvements over the state-of-the-art baseline models on rumor detection.

A k-testable machine is a finite automaton which recognizes a language L by only seeing a window of size k of each string in L. In this paper we use k-testable machines to recognize probabilistic languages and propose a novel algorithm to learn them. We work in the context of passive learning as our algorithm is based on a finite sample of strings belonging to the target language equipped with frequencies. Because our algorithm learns a probabilistic automaton, the resulting language is less sensitive to noise threshold than García's algorithm. When compared with the ALERGIA learning algorithm, our method provides a better result in the case of the target language being a k-testable language. In fact, in this case, for the given window k we can learn at the limit the target language exactly.

We present a systematic study of bisimulation-up-to techniques for coalgebras. This enhances the bisimulation proof method for a large class of state based systems, including labelled transition systems but also stream systems and weighted automata. Our approach allows for compositional reasoning about the soundness of enhancements. Applications include the soundness of bisimulation up to bisimilarity, up to equivalence and up to congruence. All in all, this gives a powerful and modular framework for simplified coinductive proofs of equivalence.

In the concurrency theory, various semantic equivalences on transition systems are based on traces decorated with some additional observations, generally referred to as decorated traces. Using the generalized powerset construction, recently introduced by a subset of the authors (Silva et al.2010 FSTTCS. LIPIcs8 272–283), we give a coalgebraic presentation of decorated trace semantics. The latter include ready, failure, (complete) trace, possible futures, ready trace and failure trace semantics for labelled transition systems, and ready, (maximal) failure and (maximal) trace semantics for generative probabilistic systems. This yields a uniform notion of minimal representatives for the various decorated trace equivalences, in terms of final Moore automata. As a consequence, proofs of decorated trace equivalence can be given by coinduction, using different types of (Moore-) bisimulation (up-to context).

Although Agile methodologies have grown very popular, there is a limited amount of literature that combines Agile software methodologies and testing, especially on how testing is integrated with Scrum.In this paper we present an analysis of problem based on case study performed at the IT department of KLM regarding testing in a Scrum team.After having triangulated our results with several interviews with external topical experts and existing literature we propose a visual model that integrates testing activities in Scrum.

We give a new presentation of Brzozowski's algorithm to minimize finite automata using elementary facts from universal algebra and coalgebra and building on earlier work by Arbib and Manes on a categorical presentation of Kalman duality between reachability and observability. This leads to a simple proof of its correctness and opens the door to further generalizations. Notably, we derive algorithms to obtain minimal language equivalent automata from Moore nondeterministic and weighted automata.

Coalgebras provide a uniform framework for studying dynamical systems, including several types of automata. In this article, we make use of the coalgebraic view on systems to investigate, in a uniform way, under which conditions calculi that are sound and complete with respect to behavioral equivalence can be extended to a coarser coalgebraic language equivalence, which arises from a generalized powerset construction that determinizes coalgebras. We show that soundness and completeness are established by proving that expressions modulo axioms of a calculus form the rational fixpoint of the given type functor. Our main result is that the rational fixpoint of the functor FT , where T is a monad describing the branching of the systems (e.g., non-determinism, weights, probability, etc.), has as a quotient the rational fixpoint of the determinized type functor F , a lifting of F to the category of T -algebras. We apply our framework to the concrete example of weighted automata, for which we present a new sound and complete calculus for weighted language equivalence. As a special case, we obtain nondeterministic automata in which we recover Rabinovich’s sound and complete calculus for language equivalence.

Reo is an exogenous coordination language for component connectors extending data flow networks with synchronization and context-dependent behavior. The first proposed formalism to capture the operational semantics of Reo is called constraint automaton. In this paper, we propose another operational model of Reo based on Büchi automata in which port synchronization is modeled by records labeling the transitions, whereas context dependencies are stored in the states. It is shown that constraint automata can be recast into our proposed Büchi automata of records. Also, we provide a composition operator which models the joining of two connectors and show that it can be obtained by using two standard operators: alphabet extension and automata product. Our semantics has the advantage over previous models in that it is based on standard automata theory, so that existing theories and tools can be easily reused. Moreover, it is the first formal model addressing all of Reo’s features: synchronization, mutual exclusion, hiding, and context-dependency.

Coalgebra is an abstract framework for the uniform study of different kinds of dynamical systems. An endofunctor $F$ determines both the type of systems ($F$-coalgebras) and a notion of behavioral equivalence ($\sim_F$) amongst them. Many types of transition systems and their equivalences can be captured by a functor $F$. For example, for deterministic automata the derived equivalence is language equivalence, while for non-deterministic automata it is ordinary bisimilarity. The powerset construction is a standard method for converting a nondeterministic automaton into an equivalent deterministic one as far as language is concerned. In this paper, we lift the powerset construction on automata to the more general framework of coalgebras with structured state spaces. Examples of applications include partial Mealy machines, (structured) Moore automata, and Rabin probabilistic automata.

Several dynamical systems, such as deterministic automata and labelled transition systems, can be described as coalgebras of so-called Kripke polynomial functors, built up from constants and identities, using product, coproduct and powerset. Locally finite Kripke polynomial coalgebras can be characterized up to bisimulation by a specification language that generalizes Kleene's regular expressions for finite automata. In this paper we equip this specification language with an axiomatization and prove it sound and complete with respect to bisimulation, using a purely coalgebraic argument. We demonstrate the usefulness of our framework by providing a finite equational system for (non-)deterministic finite automata, labelled transition systems with explicit termination and automata on guarded strings. © 2009 IEEE.

Reo is an exogenous coordination language for component connectors extending data flow networks with synchronization and context-dependent behavior. We propose an operational model of Reo based on Buchi automata in which port synchronization is modeled by records labeling the transitions, whereas context dependencies are stored in the states. We provide a composition operator which models the joining of two connectors, and show that it can be obtained by using two standard operators: alphabet extension and automata product. Our semantics has the advantage over previous models in that it is based on standard automata theory, so that existing theories and tools can be easily reused. Moreover, it is the first formal model addressing all of Reo's features: synchronization, mutual exclusion, hiding, and context-ependency.

Abramsky's logical formulation of domain theory is extended to encompass the domain theoretic model for pi-calculus processes of Stark and of Fiore, Moggi and Sangiorgi. This is done by defining a logical counterpart of categorical constructions including dynamic name allocation and name exponentiation, and showing that they are dual to standard constructs in functor categories. We show that initial algebras of functors defined in terms of these constructs give rise to a logic that is sound, complete, and characterises bisimilarity. The approach is modular, and we apply it to derive a logical formulation of pi-calculus. The resulting logic is a modal calculus with primitives for input, free output and bound output.

A coherent description of enterprise architecture provides insight, enables communication among stakeholders and guides complicated change processes. Unfortunately, so far no enterprise architecture description language exists that fully enables integrated enterprise modeling, because for each architectural domain, architects use their own modeling techniques and concepts, tool support, visualization techniques, etc. In this paper, we outline such an integrated language and we identify and study concepts that relate architectural domains. In our language, concepts for describing the relationships between architecture descriptions at the business, application, and technology levels play a central role, related to the ubiquitous problem of business-ICT alignment, whereas for each architectural domain we conform to existing languages or standards such as UML. In particular, usage of services offered by one layer to another plays an important role in relating the behaviour aspects of the layers. The structural aspects of the layers are linked through the interface concept, and the information aspects through realization relations.

A coherent description of architectures provides insight, enables communication among different stakeholders and guides complicated (business and ICT) change processes. Unfortunately, so far no architecture description language exists that fully enables integrated enterprise modeling. In this paper we focus on the requirements and design of such a language. This language defines generic, organization-independent concepts that can be specialized or composed to obtain more specific concepts to be used within a particular organisation. It is not our intention to re-invent the wheel for each architectural domain: wherever possible we conform to existing languages or standards such as UML. We complement them with missing concepts, focusing on concepts to model the relationships among architectural domains. The concepts should also make it possible to define links between models in other languages. The relationship between architecture descriptions at the business layer and at the application layer (business-IT alignment) plays a central role.

MoCha is a middleware for distributed communication and collaboration using mobile channels as its medium. Channels allow directed, anonymous, and peer-to-peer communication among entities, while mobility ensures that the structure of their connections can change over time in arbitrary ways. MoCha provides communication mechanisms without requiring central servers or fixed network infrastructures, and it allows exogenous coordination between processes. In this paper we briefly introduce MoCha and discuss the implementation of an important channel type: the asynchronous FIFO mobile channel.

Abstract An extension of Dijkstra's guarded command language is studied, including unbounded demonic choice and a backtrack operator. We consider three orderings on this language: a refinement ordering defined by Back, a new deadlock ordering, and an approximation ordering of Nelson. The deadlock ordering is in between the two other orderings. All operators are monotonic in Nelson's ordering, but backtracking is not monotonic in Back's ordering and sequential composition is not monotonic for the deadlock ordering. At first sight recursion can only be added using Nelson's ordering. We show that, under certain circumstances, least fixed points for non-monotonic functions can be obtained by iteration from the least element. This permits the addition of recursion even using Back's ordering or the deadlock ordering in a fully compositional way. In order to give a semantic characterization of the three orderings that relates initial states to possible outcomes of the computation, the relation between predicate transformers and discrete power domains is studied. We consider (two versions of) the Smyth power domain and the Egli-Milner power domain.