Search

This paper addresses fault pattern diagnosis of discrete event systems, involving fault pattern detection and diagnosability. A fault pattern is modelled as a finite automaton whose accepted language is the objective to be diagnosed, representing the occurrence of complex or composite faults. A verifier for fault pattern detection based on the synchronous product of a system and a fault pattern is proposed. By removing all silent events, a silent closure is calculated based on the synchronous product, which offers computational advantages for systems that have a large number of silent events. An NSC/FSC pair verifier is then computed by taking the product of a normal silent closure and an accepted silent closure. By studying indeterminate cycles of the NSC/FSC pair verifier, necessary and sufficient verification conditions are established, asserting that a system is diagnosable with respect to a fault pattern if and only if there is no indeterminate cycle in the NSC/FSC pair verifier. It is shown that the proposed method requires polynomial time at most. Finally, a case study to illustrate the results is provided. [ABSTRACT FROM AUTHOR]

High-performance computers are used for computation-intensive tasks. It is essential for these systems to simultaneously execute several computation-intensive tasks for efficient and timely system utilization. Since typical tasks have a longer runtime, it is essential to determine the runtime of each task prior to execution and schedule them accordingly. We propose a method for predicting the runtime of MPI-based software. Initially, we analyze the source code of the software by translating the code to finite automata and measuring the state complexity. Next, the runtime of software is trained using a deep neural network (DNN) along with its state complexity. Herein, we propose three models based on DNN, statistics and their hybrid. DNN model is superior in comparison. Additionally, the adaptability of our method is demonstrated by showing that our method can adapt on new environment with 90% accuracy on various software. [ABSTRACT FROM AUTHOR]

We introduce an n-state Game of Life (GoL) on a cellular array (cells indexed by (i, j)), where each state σ = 0, ..., n − 1 has a nominal values vσ ≥ 0. The game involves computing the sum of the state values of the eight cells that surround cell (i, j) and using this sum to determine whether cell (i, j) stays in state σ, progress to state σ + 1, or reverts at state 0. We illustrate examples of this game, identifying still-life, oscillator, glider, and replicator patterns, as well as the long term behavior arising from random and regular starting configurations. Importantly, we provide two freely downloadable application programs that can be used to explore the behavior of the three and four state GoLs discussed in this paper [ABSTRACT FROM AUTHOR]

The Declare process modeling language has been established within the research community for modeling so-called flexible processes. Declare follows the declarative modeling paradigm and therefore guarantees flexible process execution. For several reasons, declarative process models turned out to be hard to read and comprehend. Thus, it is also hard to decide whether two process models are equal with respect to their semantic meaning, whether one model is completely contained in another one or how far two models overlap. In this paper, we follow an automaton-based approach by transforming Declare process models into finite state automatons and applying automata theory for solving this issue. [ABSTRACT FROM AUTHOR]

String constraint solving refers to solving combinatorial problems involving constraints over string variables. String solving approaches have become popular over the past few years given the massive use of strings in different application domains like formal analysis, automated testing, database query processing, and cybersecurity. This article reports a comprehensive survey on string constraint solving by exploring the large number of approaches that have been proposed over the past few decades to solve string constraints. [ABSTRACT FROM AUTHOR]

Sofic shifts are symbolic dynamical systems defined by the set of bi-infinite sequences on an edge-labeled directed graph, called a presentation. We study the computational complexity of an array of natural decision problems about presentations of sofic shifts, such as whether a given graph presents a shift of finite type, or an irreducible shift; whether one graph presents a subshift of another; and whether a given presentation is minimal, or has a synchronizing word. Leveraging connections to automata theory, we first observe that these problems are all decidable in polynomial time when the given presentation is irreducible (strongly connected), via algorithms both known and novel to this work. For the general (reducible) case, however, we show they are all PSPACE -complete. All but one of these problems (subshift) remain polynomial-time solvable when restricting to synchronizing deterministic presentations. We also study the size of synchronizing words and synchronizing deterministic presentations. [ABSTRACT FROM AUTHOR]

Nominal automata are models for recognising languages over infinite alphabets, based on the algebraic notion of nominal set. Motivated by their use in automata theory, we show how to compute efficiently with nominal sets over the so-called total order symmetry , a variant which allows to compare alphabet letters for equality as well as their respective order. We develop an explicit finite representation of such nominal sets and basic constructions thereon. The approach is implemented as the library Ons (Ordered Nominal Sets), enabling programming with infinite sets. Returning to our motivation of nominal automata, we evaluate Ons in two applications: minimisation of automata and active automata learning. In both cases, Ons is competitive compared to existing implementations and outperforms them for certain classes of inputs. [ABSTRACT FROM AUTHOR]

The Nottingham group at 2 is the group of (formal) power series t + a 2 t 2 + a 3 t 3 + ⋯ in the variable t with coefficients a i from the field with two elements, where the group operation is given by composition of power series. The depth of such a series is the largest d ⩾ 1 for which a 2 = ... = a d = 0. Only a handful of power series of finite order (forcedly a power of 2) are explicitly known through a formula for their coefficients. We argue in this paper that it is advantageous to describe such series in closed computational form through automata, based on effective versions of proofs of Christol's theorem identifying algebraic and automatic series. Up to conjugation, there are only finitely many series σ of order 2 n with fixed break sequence (i.e. the sequence of depths of σ ∘ 2 i ). Starting from Witt vector or Carlitz module constructions, we give an explicit automaton-theoretic description of: (a) representatives up to conjugation for all series of order 4 with break sequence (1 , m) for m < 10 ; (b) representatives up to conjugation for all series of order 8 with minimal break sequence (1 , 3 , 11) ; and (c) an embedding of the Klein four-group into the Nottingham group at 2. We study the complexity of the new examples from the algebro-geometric properties of the equations they satisfy. For this, we generalise the theory of sparseness of power series to a four-step hierarchy of complexity, for which we give both Galois-theoretic and combinatorial descriptions. We identify where our different series fit into this hierarchy. We construct sparse representatives for the conjugacy class of elements of order two and depth 2 μ ± 1 (μ ⩾ 1). Series with small state complexity can end up high in the hierarchy. This is true, for example, for a new automaton we found, representing a series of order 4 with 5 states (the minimal possible number for such a series). [ABSTRACT FROM AUTHOR]

We address the following decision problem. Given a numeration system U and a U-recognizable set X ⊆ ℕ , i.e. the set of its greedy U-representations is recognized by a finite automaton, decide whether or not X is ultimately periodic. We prove that this problem is decidable for a large class of numeration systems built on linear recurrence sequences. Based on arithmetical considerations about the recurrence equation and on p-adic methods, the DFA given as input provides a bound on the admissible periods to test. [ABSTRACT FROM AUTHOR]

String constraint solving refers to solving combinatorial problems involving constraints over string variables. String solving approaches have become popular over the past few years given the massive use of strings in different application domains like formal analysis, automated testing, database query processing, and cybersecurity. This article reports a comprehensive survey on string constraint solving by exploring the large number of approaches that have been proposed over the past few decades to solve string constraints. [ABSTRACT FROM AUTHOR]

Venkatachala on the one hand, and Avdispahić & Zejnulahi on the other, both studied integer sequences with an unusual sum property defined in a greedy way, and proved many results about them. However, their proofs were rather lengthy and required numerous cases. In this paper, I provide a different approach, via finite automata, that can prove the same results (and more) in a simple, unified way. Instead of case analysis, we use a decision procedure implemented in the free software Walnut. Using these ideas, we can prove a conjecture of Quet and find connections between Quet's sequence and the "married" functions of Hofstadter. • Uses a new technique, automata theory, to prove properties of some greedily-defined integer sequences. • Finds much simpler proofs of some known results in the literature. • Finds a new connection between Quet's sequence and the Hofstadter married functions. [ABSTRACT FROM AUTHOR]

In the constrained synchronization problem we want to know if a given input automaton admits a synchronizing word contained in a (fixed) regular constraint language. Here we study the computational complexity of the constrained synchronization problem for the class of regular commutative constraint languages and the computational complexity of the problem restricted to commutative input semi-automata. We give a full classification of the computational complexity of the constrained synchronization problem for commutative regular constraints. Depending on the constraint language, our problem becomes PSPACE -complete, NP -complete or polynomial time solvable. In addition, we derive a polynomial time decision procedure for the complexity of the constrained synchronization problem, given a constraint automaton accepting a commutative language as input. Furthermore, for commutative input semi-automata, the problem is decidable in polynomial time, regardless of the regular constraint language. [ABSTRACT FROM AUTHOR]

Afflictions, or predispositions to have particular disorders in an animal are often caused by specific genes. However, some of these conditions could be avoided using genetic alterations during the breeding process. A good example is brachycephaly in dogs, which, in many cases, causes dyspnoea. In this research paper, we focused on using Finite Deterministic Automata for pattern recognition in dog genes in order to improve the breathing problems of French bulldogs, and other brachycephalic breeds. [ABSTRACT FROM AUTHOR]

We develop a generic framework to extend the logics LTL, CTL+ and CTL⁎ by automata-based connectives from formal language classes and analyse this framework with regard to regular languages, visibly pushdown languages, deterministic and non-deterministic context-free languages. More precisely, we consider how the use of different automata classes changes the expressive power of the logics and provide algorithms for the satisfiability and model checking problems induced by the use of different classes of automata. For the model checking problem, we treat not only finite Kripke transition systems, but also visibly pushdown systems and pushdown systems. We provide completeness or undecidability results in all cases and show that the extensions we consider can formulate properties not expressible in classical temporal logics or regular extensions thereof. [ABSTRACT FROM AUTHOR]

The idea behind the neutrosophic set is we can connect the concept by dynamics of opposite interacts and its neutral that are uncertain and get common parts. Automata theory is beneficial to solve computational complexity problem and also it is an in uential mathematical modeling tool in computer science. Inspired by the concepts of neutrosophic sets and automata theory, here, we are introducing and discussing the algebraic concept of neutrosophic finite automata based on the paper [10]. Generally, composite machines can be achieved by the output of the one machine that will be used as input for another machines. This paper introduced the concept of composite automata under the environment of the neutrosophic set and also examined the box function between the composite neutrosophic finite automata. [ABSTRACT FROM AUTHOR]

We show how some problems in additive number theory can be attacked in a novel way, using techniques from the theory of finite automata. We start by recalling the relationship between first-order logic and finite automata, and use this relationship to solve several problems involving sums of numbers defined by their base-2 and Fibonacci representations. Next, we turn to harder results. Recently, Cilleruelo, Luca, & Baxter proved, for all bases b ≥ 5, that every natural number is the sum of at most 3 natural numbers whose base-b representation is a palindrome (Cilleruelo et al., Math. Comput. 87, 3023–3055, 2018). However, the cases b = 2, 3, 4 were left unresolved. We prove that every natural number is the sum of at most 4 natural numbers whose base-2 representation is a palindrome. Here the constant 4 is optimal. We obtain similar results for bases 3 and 4, thus completely resolving the problem of palindromes as an additive basis. We consider some other variations on this problem, and prove similar results. We argue that heavily case-based proofs are a good signal that a decision procedure may help to automate the proof. [ABSTRACT FROM AUTHOR]

We exhaustively investigate possible combinations of a Boolean operation together with a catenation. In many cases we prove and improve some conjectures by Brzozowski. For each family of operations, we endeavour to provide a common witness with a small size alphabet. [ABSTRACT FROM AUTHOR]

We define a notion of randomness for individual and collections of formal languages based on automatic martingales acting on sequences of words from some underlying domain. An automatic martingale bets if the incoming word belongs to the target language or not. Then randomness of both single languages and collections of languages is defined as a failure of automatic martingale to gain an unbounded capital by betting on the target language according to an incoming sequence of words, or a text. The randomness of formal languages turned out to be heavily dependent on the text. For very general classes of texts, any nonregular language happens to be random when considered individually. As for collections of languages, very general classes of texts permits nonrandomness of automatic families of languages only. On the other hand, an arbitrary computable language is shown to be nonrandom under certain dynamic texts. [ABSTRACT FROM AUTHOR]

This paper presents a connection between fuzzy sets, biological inheritance and hyperstructures in which we consider the set of phenotypes of the second generation F2 in different types of inheritance, define fuzzy subsets of it and construct a sequence of join spaces associated to each of its types. [ABSTRACT FROM AUTHOR]

The event‐triggered hybrid control is proposed in this study to realise multi‐model switching when the microgrid system is operating in the island mode. The hybrid control includes decentralised control strategy and coordinated control strategy. Firstly, control commands in the hybrid control strategy are triggered by the event triggering mechanism including trigger events and trigger conditions. When a trigger condition is met, the corresponding event is triggered to execute the corresponding control command. Secondly, the microgrid system is divided into an upper control layer and a lower execution layer by using the multi‐agent system theory. For the upper control layer, a coordinated control strategy based on decision tree algorithm is designed, which can not only issue switching control commands to the lower execution layer, but also reduce the number of switching, improve system stability, and enrich the control strategy. For the lower execution layer, a decentralised control strategy is designed to realise distributed operation of the underlying units. Finally, the model of hybrid automata of each unit is established to ensure the smooth switching of working modes of each unit. The simulation results verify the effectiveness of the event‐triggered hybrid control strategy for controlling the microgrid. [ABSTRACT FROM AUTHOR]

• Nucleotide sequences capable to form combinations of DNA non-canonical structures were detected. • Special software for molecular biologist was developed. • Minimal length of nucleotide sequences with structural polymorphism was revealed. In this study, we develop a program that allows us to reveal DNA receptors, i.e. nucleotide sequences that may form more than one non-canonical structure. The data obtained may be analysed either experimentally or using DNA banks, and refers to the coding, non-coding or promotor region of the gene. These results provide a better understanding of the role that non-canonical structures play in pathological modifications of the genetic apparatus, resulting in tumour formation or inherited disease. They also reveal the effect of single nucleotide polymorphisms on gene expression, indicate so-called "risk regions" in which the substitution of a single nucleotide may lead to increased formation of non-canonical structures, and elucidate the epigenetic mechanisms of microorganism adaptation. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we study the lattice and the Boolean algebra, possibly closed under quotient, generated by the languages of the form u ⁎ , where u is a word. We provide effective equational characterisations of these classes, i.e. one can decide using our descriptions whether a given regular language belongs or not to each of them. [ABSTRACT FROM AUTHOR]

In this study, the authors consider the problem of collision avoidance of ground vehicles. In this framework, they focus on a single vehicle, and they guarantee that a given safe set is not exited during a mission. More specifically, they consider the yaw‐lateral motion of a two‐wheel vehicle subject to a side wind, and they design a state‐feedback controller such that the vehicle follows the nominal trajectory with a given maximum error. For these purposes, they resort to a control system where a supervisor, implemented as a hybrid automata, decides to switch between two controllers, depending on the measured vehicle lateral displacement from the nominal trajectory. The two controllers are designed using an H∞ approach and the input–output finite‐time stability approach, respectively. Some simulation results are included, showing the effectiveness of the proposed architecture. [ABSTRACT FROM AUTHOR]

While structured as an autobiography, this memoir exemplifies ways in which classic contributions to cybernetics (e.g., by Wiener, McCulloch & Pitts, and von Neumann) have fed into a diversity of current research areas, including the mathematical theory of systems and computation, artificial intelligence and robotics, computational neuroscience, linguistics, and cognitive science. The challenges of brain theory receive special emphasis. Action-oriented perception and schema theory complement neural network modeling in analyzing cerebral cortex, cerebellum, hippocampus, and basal ganglia. Comparative studies of frog, rat, monkey, ape and human not only deepen insights into the human brain but also ground an EvoDevoSocio view of “how the brain got language.” The rapprochement between neuroscience and architecture provides a recent challenge. The essay also assesses some of the social and theological implications of this broad perspective. [ABSTRACT FROM AUTHOR]

A set is called recurrent if its minimal automaton is strongly connected and birecurrent if it is recurrent as well as reversal. We prove a series of results concerning birecurrent sets. It is already known that any birecurrent set is completely reducible (that is, such that the minimal representation of its characteristic series is completely reducible). The main result of this paper characterizes completely reducible sets as linear combinations of birecurrent sets [ABSTRACT FROM AUTHOR]

The study of various decision problems for logic fragments has a long history in computer science. This paper is on the membership problem for a fragment of first-order logic over infinite words; the membership problem asks for a given language whether it is definable in some fixed fragment. The alphabetic topology was introduced as part of an effective characterization of the fragment Σ2 over infinite words. Here, Σ2 consists of the first-order formulas with two blocks of quantifiers, starting with an existential quantifier. Its Boolean closure is 픹Σ2. Our first main result is an effective characterization of the Boolean closure of the alphabetic topology, that is, given an ω-regular language L, it is decidable whether L is a Boolean combination of open sets in the alphabetic topology. This is then used for transferring Place and Zeitoun’s recent decidability result for 픹Σ2 from finite to infinite words. [ABSTRACT FROM AUTHOR]

The paper is devoted to the investigation of "linearly realizable" automata, i.e. automata that allow state encodings that lead to implementations with linear Boolean operators. We formulate the criterion of linear realizability and obtain upper and lower bounds on the number of linearly realizable automata. [ABSTRACT FROM AUTHOR]

In this study, the author presents a new efficient algorithm for translating linear temporal logic (LTL) formulas to Büchi automata, which are used by LTL model checkers. The general idea of this algorithm is to generate Büchi automata from LTL formulas, using the principle of alternating automata and keeping only the positive transitions without generating the intermediate generalised automata. The LTL translation is the heart of any LTL model checker, which affects its performance. The translation performance is measured in addition to its speed and the size of the produced Büchi automaton (number of states and number of transitions), by correctness of produced Büchi automaton and its level of determinism. The author will show that this method is different from the others and it is very competitive with the most efficient translators to date. [ABSTRACT FROM AUTHOR]

Semiautomatic structures generalise automatic structures in the sense that for some of the relations and functions in the structure one only requires the derived relations and functions are automatic when all but one input are filled with constants. One can also permit that this applies to equality in the structure so that only the sets of representatives equal to a given element of the structure are regular while equality itself is not an automatic relation on the domain of representatives. It is shown that one can find semiautomatic representations for the field of rationals and also for finite algebraic field extensions of it. Furthermore, one can show that infinite algebraic extensions of finite fields have semiautomatic representations in which the addition and equality are both automatic. Further prominent examples of semiautomatic structures are term algebras, any relational structure over a countable domain with a countable signature and any permutation algebra with a countable domain. Furthermore, examples of structures which fail to be semiautomatic are provided. [ABSTRACT FROM AUTHOR]

Higher-order pushdown systems and ground tree rewriting systems can be seen as extensions of suffix word rewriting systems. Both classes generate infinite graphs with interesting logical properties. Indeed, the model-checking problem for monadic second order logic (respectively first order logic with a reachability predicate) is decidable on such graphs. We unify both models by introducing the notion of stack trees, trees whose nodes are labelled by higher-order stacks, and define the corresponding class of higher-order ground tree rewriting systems. We show that these graphs retain the decidability properties of ground tree rewriting graphs while generalising the pushdown hierarchy of graphs. [ABSTRACT FROM AUTHOR]

There exist several methods of computing an automaton recognizing the language denoted by a given regular expression: In the case of words, the position automaton P due to Glushkov, the c-continuation automaton C due to Champarnaud and Ziadi, the follow automaton F due to Ilie and Yu and the equation automaton ε due to Antimirov. It has been shown that P and C are isomorphic and that ε (resp. F) is a quotient of C (resp. of P). In this paper, we define from a given regular tree expression the position tree automaton P and the follow tree automaton F. Using the definition of the equation tree automaton ε of Kuske and Meinecke and our previously defined c-continuation tree automaton C, we show that the previous morphic relations are still valid on tree expressions. [ABSTRACT FROM AUTHOR]

The locality of a graph problem is the smallest distance T such that each node can choose its own part of the solution based on its radius- T neighborhood. In many settings, a graph problem can be solved efficiently with a distributed or parallel algorithm if and only if it has a small locality. In this work we seek to automate the study of solvability and locality: given the description of a graph problem Π, we would like to determine if Π is solvable and what is the asymptotic locality of Π as a function of the size of the graph. Put otherwise, we seek to automatically synthesize efficient distributed and parallel algorithms for solving Π. We focus on locally checkable graph problems; these are problems in which a solution is globally feasible if it looks feasible in all constant-radius neighborhoods. Prior work on such problems has brought primarily bad news: questions related to locality are undecidable in general, and even if we focus on the case of labeled paths and cycles, determining locality is PSPACE -hard (Balliu et al., PODC 2019). We complement prior negative results with efficient algorithms for the cases of unlabeled paths and cycles and, as an extension, for rooted trees. We study locally checkable graph problems from an automata-theoretic perspective by representing a locally checkable problem Π as a nondeterministic finite automaton M over a unary alphabet. We identify polynomial-time-computable properties of the automaton M that near-completely capture the solvability and locality of Π in cycles and paths, with the exception of one specific case that is co- NP -complete. [ABSTRACT FROM AUTHOR]

We present a disambiguation algorithm for weighted automata. The algorithm admits two main stages: a pre-disambiguation stage followed by a transition removal stage. We give a detailed description of the algorithm and the proof of its correctness. The algorithm is not applicable to all weighted automata but we prove sufficient conditions for its applicability in the case of the tropical semiring by introducing the weak twins property . In particular, the algorithm can be used with any weighted automaton over the tropical semiring for which the weighted determinization algorithm terminates and with any acyclic weighted automaton over an arbitrary weakly left divisible cancellative and commutative semiring. While disambiguation can sometimes be achieved using weighted determinization, our disambiguation algorithm in some cases can return a result that is exponentially smaller than any equivalent deterministic automaton. We also present some empirical evidence of the space benefits of disambiguation over determinization in speech recognition and machine translation applications. [ABSTRACT FROM AUTHOR]

Computation is classically studied in terms of automata, formal languages and algorithms; yet, the relation between neural dynamics and symbolic representations and operations is still unclear in traditional eliminative connectionism. Therefore, we suggest a unique perspective on this central issue, to which we would like to refer as transparent connectionism, by proposing accounts of how symbolic computation can be implemented in neural substrates. In this study we first introduce a new model of dynamics on a symbolic space, the versatile shift, showing that it supports the real-time simulation of a range of automata. We then show that the Gödelization of versatile shifts defines nonlinear dynamical automata, dynamical systems evolving on a vectorial space. Finally, we present a mapping between nonlinear dynamical automata and recurrent artificial neural networks. The mapping defines an architecture characterized by its granular modularity, where data, symbolic operations and their control are not only distinguishable in activation space, but also spatially localizable in the network itself, while maintaining a distributed encoding of symbolic representations. The resulting networks simulate automata in real-time and are programmed directly, in the absence of network training. To discuss the unique characteristics of the architecture and their consequences, we present two examples: (i) the design of a Central Pattern Generator from a finite-state locomotive controller, and (ii) the creation of a network simulating a system of interactive automata that supports the parsing of garden-path sentences as investigated in psycholinguistics experiments. [ABSTRACT FROM AUTHOR]

We examine the effects of supplying increasing amounts of trusted advice to a finite automaton. Previous work has shown that allowing such automata with a single advice tape to make a single pass over their input renders them unable to recognize the palindromes language, whereas both two-way machines reading advice from a single tape and one-way machines with multiple advice tapes can recognize all languages with exponentially bounded amounts of advice. We study several architectural variants and demonstrate the existence of language hierarchies based on increased advice length, runtime (measured in terms of the number of allowed left-to-right passes on the input), and number of advice tapes. We also prove some lower bounds for recognizing certain concrete languages. [ABSTRACT FROM AUTHOR]

This paper establishes a framework based on logic and automata theory in which to model and automatically verify systems of multiple mobile agents moving in environments with partially-known topologies, i.e., ones which are not completely known at design time. Examples include physical agents designed to be used in many spatial environments and not tailored for a specific one, robots in environments not reachable by humans, and software exploring partially-mapped networks. We model spatial environments as graphs whose edges are labelled with directions. We model agents as finite-state machines that move on the graphs by issuing commands of the form "go in direction X", that can communicate their internal state to other agents, and that can sense agent positions (including current and visited positions). We treat the incomplete information about the spatial environment by studying the decision problem that asks whether a given collection of agents achieve their tasks on all graphs from a class of graphs — this is called the parameterised verification problem. The framework also introduces a new logical language based on Linear Temporal Logic that is tailored for expressing agent navigation tasks in such environments. Although the parameterised verification problem is undecidable, we identify two key dimensions that need to be limited in order to regain decidability, namely, the set of graph-environments and the amount of sensing and communication between agents. In particular, one should limit the families of graphs to exclude grids, and there should be a bound on the number of times an agent senses the position of another agent or communicates its own state to another agent. We prove that dropping either of these assumptions results in undecidability, even for agents with severe restrictions on their abilities (e.g., with very limited sensing abilities and no communication abilities). The importance of this work is that a) it provides a general computational model for mobile multi-agent systems in environments with partially-known topologies, b) it identifies, for the first time, the precise causes of undecidability of these systems and presents minimal restrictions to alleviate this problem, and c) it provides a generic sound and complete procedure for solving the parameterised verification problem over a broad range of spatial-environments and for agents with very powerful sensing and communication abilities. [ABSTRACT FROM AUTHOR]

We study the descriptional complexity of regular languages that are definable by deterministic regular expressions, i.e., we examine worst-case blow-ups in size when translating between different representations for such languages. As representations of languages, we consider regular expressions, deterministic regular expressions, and deterministic finite automata. Our results show that exponential blow-ups between these representations cannot be avoided. Furthermore, we study the descriptional complexity of these representations when applying boolean operations. Here, we start by investigating the closure properties of such languages under various language-theoretic operations such as union, intersection, concatenation, Kleene star, and reversal. Our results show that languages that are definable by deterministic regular expressions are not closed under any of these operations. Finally, we show that for all these operations except the Kleene star an exponential blow-up in the size of deterministic regular expressions cannot be avoided. [ABSTRACT FROM AUTHOR]

In this paper, we pioneer a study of parameterized automata constructions for languages related to the design of parameterized algorithms. We focus on the k - Distinct language L k ( Σ ) ⊆ Σ k , defined as the set of words of length k over an alphabet Σ whose symbols are all distinct. This language is implicitly related to several breakthrough techniques developed during the last two decades, to design parameterized algorithms for fundamental problems such as k - Path and r - Dimensional k - Matching . Building upon the color coding, divide-and-color and narrow sieves techniques, we obtain the following automata constructions for L k ( Σ ) . We develop non-deterministic automata (NFAs) of sizes 4 k + o ( k ) ⋅ n O ( 1 ) and ( 2 e ) k + o ( k ) ⋅ n O ( 1 ) , where the latter satisfies a ‘bounded ambiguity’ property relevant to approximate counting, as well as a non-deterministic xor automaton (NXA) of size 2 k ⋅ n O ( 1 ) , where n = | Σ | . We show that our constructions can be used to develop both deterministic and randomized algorithms for k - Path , r - Dimensional k -Matching and Module Motif in a natural manner, considering also their approximate counting variants. Our framework is modular and consists of two parts: designing an automaton for k - Distinct , and designing a problem specific automaton, as well as an algorithm for deciding whether the intersection automaton's language is empty, or for counting the number of accepting paths in it. [ABSTRACT FROM AUTHOR]

Ehrenfeucht, Parikh and Rozenberg gave an interesting characterisation of the regular languages called the block pumping property. When requiring this property only with respect to members of the language but not with respect to nonmembers, one gets the notion of block pumpable languages. It is shown that these block pumpable are a more general concept than regular languages and that they are an interesting notion of their own: they are closed under intersection, union and homomorphism by transducers; they admit multiple pumping; they have either polynomial or exponential growth. [ABSTRACT FROM AUTHOR]

One aspect of DNA Computing is the possibility of using DNA molecules for solving some “complicated” computational problems. In this context, the DNA code word design problem assumes a fundamental role: given a problem encoded in DNA strands and biochemical processes, the final computation is a concatenation of the input DNA strands that must allow us to recover the solution of the given problem in terms of the input (unique decipherability). Thus the initial set of DNA strands must be a code. In addition, it should satisfy some restrictions, called here DNA properties, in order to prevent them from interacting in undesirable ways. So a new interest towards the design of efficient algorithms for testing whether a language X is a code, has arisen from (wet) DNA Computing, but, as far as we know, only when X is a finite set. In this paper we provide an algorithm for testing whether an infinite but regular set of words is a code that avoids some DNA properties among unwanted intermolecular and intramolecular hybridizations. [ABSTRACT FROM AUTHOR]

We give an analog of the Myhill-Nerode theorem from formal language theory for hypergraphs and use it to derive the following results for two NP-hard hypergraph problems. (1) We provide an algorithm for testing whether a hypergraph has cutwidth at most $$k$$ that runs in linear time for constant $$k$$ . In terms of parameterized complexity theory, the problem is fixed-parameter linear parameterized by $$k$$ . (2) We show that it is not expressible in monadic second-order logic whether a hypergraph has bounded (fractional, generalized) hypertree width. The proof leads us to conjecture that, in terms of parameterized complexity theory, these problems are W[1]-hard parameterized by the incidence treewidth (the treewidth of the incidence graph). Thus, in the form of the Myhill-Nerode theorem for hypergraphs, we obtain a method to derive linear-time algorithms and to obtain indicators for intractability for hypergraph problems parameterized by incidence treewidth. [ABSTRACT FROM AUTHOR]

The determinization of Büchi automata is a celebrated problem, with applications in synthesis, probabilistic verification, and multi-agent systems. Since the 1960s, there has been a steady progress of constructions: by McNaughton, Safra, Piterman, Schewe, and others. Despite the proliferation of solutions, they are all essentially ad-hoc constructions, with little theory behind them other than proofs of correctness. Since Safra, all optimal constructions employ trees as states of the deterministic automaton, and transitions between states are defined operationally over these trees. The operational nature of these constructions complicates understanding, implementing, and reasoning about them, and should be contrasted with complementation, where a solid theory in terms of automata run dag s underlies modern constructions. In 2010, we described a profile -based approach to Büchi complementation, where a profile is simply the history of visits to accepting states. We developed a structural theory of profiles and used it to describe a complementation construction that is deterministic in the limit. Here we extend the theory of profiles to prove that every run dag contains a profile tree with at most a finite number of infinite branches. We then show that this property provides a theoretical grounding for a new determinization construction where macrostates are doubly preordered sets of states. In contrast to extant determinization constructions, transitions in the new construction are described declaratively rather than operationally. [ABSTRACT FROM AUTHOR]

In the literature, there exist several interesting hybrid models of quantum finite automata (QFA) which have both quantum and classical states. This paper describes these models in a uniform way: a hybrid QFA can be seen as a two-component communication system consisting of a quantum component and a classical one, and the existing hybrid QFA differ from each other mainly in the specific communication pattern: classical-quantum, or quantum-classical, or two-way. We clarify the relationship between these hybrid QFA and some other models; in particular, it is shown that hybrid QFA can be simulated exactly by QFA with general quantum operations. As corollaries, some results in the literature concerning the language recognition power and the equivalence problem of hybrid QFA follow directly from these relationships clarified in this paper. [ABSTRACT FROM AUTHOR]

The state complexity of basic operations on regular languages considering complete deterministic finite automata (DFA) has been extensively studied in the literature. But, if incomplete DFAs are considered, transition complexity is also a significant measure. In this paper we study the incomplete (deterministic) state and transition complexity of some operations for regular and finite languages. For regular languages we give a new tight upper bound for the transition complexity of the union, which refutes the conjecture presented by Y. Gao et al. For finite languages, we correct the published state complexity of concatenation for complete DFAs and provide a tight upper bound for the case when the right operand is larger than the left one. We also present some experimental results to test the behavior of those operations on the average case, and we conjecture that for many operations and in practical applications the worst-case complexity is seldom reached. [ABSTRACT FROM AUTHOR]

In this article, we provide a coalgebraic account of parts of the mathematical theory underlying context-free languages. We characterize context-free languages, and power series and streams generalizing or corresponding to the context-free languages, by means of systems of behavioural differential equations; and prove a number of results, some of which are new, and some of which are new proofs of existing theorems, using the techniques of bisimulation and bisimulation up to linear combinations. Furthermore, we establish a link between automatic sequences and these systems of equations, allowing us to, given an automaton generating an automatic sequence, easily construct a system of behavioural differential equations yielding this sequence as a context-free stream. [ABSTRACT FROM AUTHOR]

Self‐assembly (SA) is the preferred growth mechanism in the natural world, on scales ranging from the molecular to the macro‐scale. It involves the assembling of components, which governed by a set of local interaction rules, lead to the formation of a global minimum energy structure. In this survey, the authors explore the extensive research conducted to exploit SA in three domains; first, as a bottom‐up approach to fabricate semiconductor heterostructures and nano‐scale devices composed of carbon nanotubes and nanowires; second, for meso‐scale assembly to build systems such as three‐dimensional electrical networks and microelectromechanical systems by utilising capillary force, external magnetic field and so on as the binding force; and third, as an emerging means to achieve computing via tiling, biomolecular automata and logic gates. DNA, in particular, has been a molecule of choice because of its easy availability, biological importance and high programmability as a result of its highly specific component bases. [ABSTRACT FROM AUTHOR]

We present an extension of Eilenberg's variety theorem, a well-known result connecting algebra to formal languages. We prove that there is a bijective correspondence between formations of finite monoids and certain classes of languages, the formations of languages. Our result permits to treat classes of finite monoids which are not necessarily closed under taking submonoids, contrary to the original theory. We also prove a similar result for ordered monoids. [ABSTRACT FROM AUTHOR]

For almost all variations of the firing squad synchronization problem for elementary geometric figures such as lines, rings, squares, rectangles, and cubes, minimal-time solutions are known. However, in 2012 Umeo and Kubo introduced a very simple variation of this type and pointed out that its minimal-time solutions are unknown. In that variation, a problem instance is a square array of n columns and n rows and the position of the general is arbitrary. For this variation they constructed a solution that fires at time 2n-2 for any position of the general and wrote that it is not known whether this solution is minimal-time or not. We determine the exact value of the minimum firing time of this variation. For some problem instances this value is smaller than 2n-2 and hence the 2n-2 time solution is not minimal-time. Our result does not solve the problem of existence or non-existence of minimal-time solutions of the variation. However the result gives one necessary condition for solutions to be minimal-time. [ABSTRACT FROM AUTHOR]