Search

These transactions publish research in computer-based methods of computational collective intelligence (CCI) and their applications in a wide range of fields such as the semantic web, social networks, and multi-agent systems. TCCI strives to cover new methodological, theoretical and practical aspects of CCI understood as the form of intelligence that emerges from the collaboration and competition of many individuals (artificial and/or natural). The application of multiple computational intelligence technologies, such as fuzzy systems, evolutionary computation, neural systems, consensus theory, etc., aims to support human and other collective intelligence and to create new forms of CCI in natural and/or artificial systems. This thirty-second issue presents 5 selected papers in the field of management, economics and computer science.

Ultimate Automizer is a software verifier that implements an automata-based approach for the verification of safety and liveness properties. A central new feature that speeded up the abstraction refinement of the tool is an on-demand construction of Floyd-Hoare automata.

We show how recent results concerning quantitative forms of automata help providing refined understanding of the properties of a system (for instance, a program). In particular, combining the size-change abstraction together with results concerning the asymptotic behavior of tropical automata yields extremely fine complexity analysis of some pieces of code.

Symbolic automata allow transitions to carry predicates over rich alphabet theories, such as linear arithmetic, and therefore extend classic automata to operate over infinite alphabets, such as the set of rational numbers. In this paper, we study the foundational problem of learning symbolic automata. We first present \(\mathrm {\Lambda }^*\), a symbolic automata extension of Angluin’s L\(^*\) algorithm for learning regular languages. Then, we define notions of learnability that are parametric in the alphabet theories of the symbolic automata and show how these notions nicely compose. Specifically, we show that if two alphabet theories are learnable, then the theory accepting the Cartesian product or disjoint union of their alphabets is also learnable. Using these properties, we show how existing algorithms for learning automata over large alphabets nicely fall in our framework. Finally, we implement our algorithm in an open-source library and evaluate it on existing automata learning benchmarks.

Automata, logic and games provide the mathematical theory that underpins the model checking of reactive systems.

Automata-theoretic formal verification approaches the problem of guaranteeing that a program conforms to its specification by reducing conformance to language containment. We can prove conformance by representing both programs and specifications as automata and proving that the specification contains the program. This connection to the theory of automata on infinite words motivated an extensive research program into the algorithmic theory of automata on infinite words, with a focus on algorithms that perform well in practice. The focus on practical performance is important because of the large gap between worst-case complexity and practice for many automata-theoretic algorithms. Unfortunately, there are few benchmark instances of automata in industrial verification. To overcome this challenge, Tabakov and Vardi proposed a model for generating random automata as test cases. The Tabakov-Vardi T-V model, however, is just one random model, based on a specific, rather simple model of random graphs. Other models of random graphs have been studied over the years. While the T-V model has the advantage of simplicity, it is not clear that performance analysis conducted on this model is robust, and an analogous analysis over other random models might yield different conclusions. To address this problem, we introduce three novel models of random automata, yielding automata that are richer in structure than the automata generated by the T-V model. By generating large corpora of random automata and using them to evaluate the performance of universality-checking algorithms, we show that the T-V model is a robust random model for evaluating performance of universality-checking algorithms.

We introduce an efficient complementation technique for semi-deterministic Buchi automata, which are Buchi automata that are deterministic in the limit: from every accepting state onward, their behaviour is deterministic. It is interesting to study semi-deterministic automata, because they play a role in practical applications of automata theory, such as the analysis of Markov decision processes. Our motivation to study their complementation comes from the termination analysis implemented in Ultimate Buchi Automizer, where these automata represent checked runs and have to be complemented to identify runs to be checked. We show that semi-determinism leads to a simpler complementation procedure: an extended breakpoint construction that allows for symbolic implementation. It also leads to significantly improved bounds as the complement of a semi-deterministic automaton with n states has less than $$4^n$$ states. Moreover, the resulting automaton is unambiguous, which again offers new applications, like the analysis of Markov chains. We have evaluated our construction against the semi-deterministic automata produced by the Ultimate Buchi Automizer. The evaluation confirms that our algorithm outperforms the known complementation techniques for general nondeterministic Buchi automata.

We introduce weighted symbolic automata with data storage, which combine and generalize the concepts of automata with storage types, weighted automata, and symbolic automata. By defining two particular data storages, we show that this combination is rich enough to capture symbolic visibly pushdown automata and weighted timed automata. We introduce a weighted MSO-logic and prove a Buchi-Elgot-Trakhtenbrot theorem, i.e., the new logic and the new automaton model are expressively equivalent.

We consider finite and polynomial ambiguity of weighted tree automata. Concerning finite ambiguity, we show that a finitely ambiguous weighted tree automaton can be decomposed into a sum of unambiguous automata. For polynomial ambiguity, we show how to decompose a polynomially ambiguous weighted tree automaton into simpler polynomially ambiguous automata and then analyze the structure of these simpler automata. We also outline how these results can be used to capture the ambiguity of weighted tree automata with weighted logics.

We introduce tree stack automata as a new class of automata with storage and identify a restricted form of tree stack automata that recognises exactly the multiple context-free languages.

This paper explores the language classes that arise with respect to the head count of a finite ultrametric automaton. First we prove that in the one-way setting there is a language that can be recognized by a one-head ultrametric finite automaton and cannot be recognized by any k-head non-deterministic finite automaton. Then we prove that in the two-way setting the class of languages recognized by ultrametric finite k-head automata is a proper subclass of the class of languages recognized by (k + 1)-head automata. Ultrametric finite automata are similar to probabilistic and quantum automata and have only just recently been introduced by Freivalds. We introduce ultrametric Turing machines and ultrametric multi-register machines to assist in proving the results.

We consider the model checking problem of infinite state systems given in the form of parameterized discrete timed networks with multiple clocks. We show that this problem is decidable with respect to specifications given by B- or S-automata. Such specifications are very expressive they strictly subsume $$\omega $$-regular specifications, and easily express complex liveness and safety properties. Our results are obtained by modeling the passage of time using symmetric broadcast, and by solving the model checking problem of parameterized systems of untimed processes communicating using k-wise rendezvous and symmetric broadcast. Our decidability proof makes use of automata theory, rational linear programming, and geometric reasoning for solving certain reachability questions in vector addition systems; we believe these proof techniques will be useful in solving related problems.

Petri obtained his doctorate in 1962 at the Technical University of Darmstadt, with the thesis Kommunikation mit Automaten (Communication with Automata) that he had submitted the year before.

This piece is not a paper reporting on original research, but rather a slightly expanded write-up of some notes for a concluding discussion at the 2012 Workshop on ‘Modeling Strategic Reasoning’ at the Lorentz Center in Leiden, an interdisciplinary meeting on the importance of strategies in many fields, from game theory to linguistics, computer science, and cognitive science, that was the incubator for the present volume on the logic-based analysis of strategies and how we reason with, and about them. My modest purpose here is to highlight a few general, somewhat unresolved, decision points about this proposed program that seemed to resonate with the audience at the Workshop, but that may also present food for thought to a more general reader of this book. The emphasis in the presentation that follows is on logic, a view of strategies that figures prominently in my own work on logic and games, cf. [9]. Still, there are certainly other equally viable and illuminating formal viewpoints on the study of strategies, coming, for instance, from automata theory or dynamical systems, cf. [16, 31].

In the following years, Petri generalizes the insights from his thesis, always closely guided by the requirements of physical compatibility. The ultimate goal he strives for, is to find a common denominator for automata theory, switching circuits, geometry, and physics.

The traditional model-driven developing methods in requirement engineering (RE) have met challenges. Under the dropback of big data, we propose a new framework of software design method based on requirement data. Given a set of requirement data, which are usually acquired directly from users’ intuitive descriptions about systems, we consider the method to analyze them and extract useful information from them in order to build the formal specifications of systems. Here the ‘data’ could be any form and could describe any prospect of functionalities of systems, the ‘model’ could be any types of formal models like process algebra, automata, or some forms of state-diagrams. We limit the scope of our discussion in this paper to a special type of data and formal models. We first use some simple examples to clarify the general idea of ‘data-driven’ we propose. Then as a case study, we apply this idea to the requirement specification of a special type of systems—spatial-temporal systems by proposing a special formal model in order to capture the spatial-time features of them.

We introduce a general method for proving measurability of topologically complex sets by establishing a correspondence between the notion of game tree languages from automata theory and the σ-algebra of \(\mathcal{R}\)-sets, introduced by A. Kolmogorov as a foundation for measure theory. We apply the method to answer positively to an open problem regarding the game interpretation of the probabilistic μ-calculus.

We present a new game-based abstraction technique for probabilistic automata (PA). The key idea is to use distribution-based abstraction – preserving novel distribution-based (alternating) simulation relations – rather than classical state-based abstraction. These abstractions yield (simple) probabilistic game automata (PGA), turn-based 2 player stochastic games in which moves of both players – as opposed to classical stochastic games – yield distributions over states. As distribution-based (alternating) simulation relations are pre-congruences for composite PGA, abstraction can be done compositionally. Our abstraction yields tighter upper and lower bounds on (extremal) reachability probabilities than state-based abstraction. This shows the potential superiority over state-based abstraction of PA and Markov decision processes.

An important direction of computational and formal linguistics is to find good (mathematical and computational) models to describe linguistic phenomena. These models can also help to understand language acquisition, thinking and other mental activities. In this paper we consider finite automata with translucent letters. These models do not read their input strictly from left to right as traditional finite automata, but for each internal state of such a device, certain letters are translucent, that is, in this state the automaton cannot see them. We solve the parsing problem of these automata, both in the deterministic and in the nondeterministic cases. By introducing the permutation operator the class of regular languages is extended. It is shown that this extended class inside the class of languages that can be accepted by nondeterministic finite automata with translucent letters. Some interesting examples from the formal language theory and from a segment of the Hungarian language are shown presenting the applicability of finite automata with translucent letters both in formal and natural languages.

We review our recent efforts in building atom-scale quantum-dot cellular automata circuits on a silicon surface. Our building block consists of silicon dangling bond on a H-Si(001) surface, which has been shown to act as a quantum dot. First the fabrication, experimental imaging, and charging character of the dangling bond are discussed. We then show how precise assemblies of such dots can be created to form artificial molecules. Such complex structures can be used as systems with custom optical properties, circuit elements for quantum-dot cellular automata, and quantum computing. Considerations on macro-to-atom connections are discussed., 2013 Workshop on Field-Coupled Nanocomputing (FCN 2013), February 7-8, 2013, Tampa, Florida, USA, Series: Lecture Notes in Computer Science; no. 8280

Process calculi for service-oriented computing often feature generation of fresh resources. So-called nominal automata have been studied both as semantic models for such calculi, and as acceptors of languages of finite words over infinite alphabets. In this paper we investigate nominal automata that accept infinite words. These automata are a generalisation of deterministic Muller automata to the setting of nominal sets. We prove decidability of complement, union, intersection, emptiness and equivalence, and determinacy by ultimately periodic words. The key to obtain such results is to use finite representations of the (otherwise infinite-state) defined class of automata. The definition of such operations enables model checking of process calculi featuring infinite behaviours, and resource allocation, to be implemented using classical automata-theoretic methods.

The historically second elementary grammar formalism was published in 1936 by the American logician Emil Post (1897–1957). Known as rewrite systems or Post production systems, they originated in the mathematical context of recursion theory and are closely related to automata theory and computational complexity theory.

We introduce a method of applying Myhill-Nerode methods from formal language theory to hypergraphs and show how this method can be used to obtain the following parameterized complexity results.

We present a new technique for verifying Weighted Metric Temporal Logic (WMTL) properties of Weighted Timed Automata. Our approach relies on Statistical Model Checking combined with a new monitoring algorithm based on rewriting rules. Contrary to existing monitoring approaches for WMTL ours is exact. The technique has been implemented in the statistical model checking engine of Uppaal and experiments indicate that the technique performs faster than existing approaches and leads to more accurate results.

Many software systems are naturally modeled as networks of interacting elements such as computing nodes, input devices, and output devices. In this paper, we present a notion of robustness for a networked system when the underlying network is prone to errors. We model such a system $\mathcal{N}$ as a set of processes that communicate with each other over a set of internal channels, and interact with the outside world through a fixed set of input and output channels. We focus on network errors that arise from channel perturbations, and assume that we are given a worst-case bound i¾? on the number of errors that can occur in the internal channels of $\mathcal{N}$. We say that the system $\mathcal{N}$ is i¾?, e-robust if the deviation of the output of the perturbed system from the output of the unperturbed system is bounded by e. We study a specific instance of this problem when each process is a Mealy machine, and the distance metric used to quantify the deviation from the desired output is either the L1-norm or the Levenshtein distance also known as the edit distance. For the former, we present a decision procedure for i¾?, e-robustness that is polynomial in the size of the network. For the latter, we present a decision procedure that is polynomial in the size of the network and exponential in the error bound on the output channel. Our solution draws upon techniques from automata theory, essentially reducing the problem of checking i¾?,e-robustness to the problem of checking emptiness for a certain class of reversal-bounded counter automata.