Search

Plants are capable of a range of complex interactions with the environment. Over the last decade, some authors have used this as evidence to argue that plants are cognitive agents. While there is no consensus on this view, it is certainly interesting to approach the debate from a comparative perspective, trying to understand whether different lineages of plants show different degrees of responsiveness to environmental cues, and how their responses compare with those of animals or humans. In this paper, I suggest that a potentially fruitful approach to these comparative studies is provided by automata theory. Accordingly, I shall present a possible application of this theory to plant communication. Two tentative results will emerge. First, that different lineages may exhibit different levels of complexity in response to similar stimuli. Second, that current evidence does not allow to infer great cognitive sophistication in plants. [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]

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]

The linked governance set has presently been introduced as an attractive scheme to the region analysis in wireless sensor networks (WSNs). Therefore the key issue bothering the behavior of the prevailing Minimal sized Governing Set (MGS) based analysis standards is that they are focused on increasing the count of sleep nodes to safeguard the energy. It makes the lively sensors to feel immense loads for handling voluminous adjacencies. The quicker depletion of the lively sensors might detach the network standard and discards the region explored. Hence for offering an improved transmission of the network association analysis and lifespan, a precise count of sensors must be triggered. The intention is based on the angle restricted minimal load allowance of the MGS issues termed as Angle Restricted minimal load MGS (ARGS) to design the region analysis in WSNs. The precise decision of the angle restriction of ARGS equalizes the load within the network on the lively sensors enhances the network analysis and lifespan. The knowledge automation-based heuristics termed as Automata Theory-based Energy Efficient Area algorithm (ATEEA) is designed for locating a close optimal solution to the substitution identical ARGS issues in WSN. The analysis difficulties of the designed scheme to locate the optimal solution of the region analysis issue are estimated. Diverse experiments are performed to depict the supremacy of the designed analysis standards over the prevailing MGS-based schemes in terms of rate of coverage region, remaining energy, number of lively nodes and the lifetime of the networks. [ABSTRACT FROM AUTHOR]

The main contribution of this paper is oriented towards system modeling with resource conflicts, in which a set of tasks must be completed at the earliest. Mutual exclusion between tasks with underlying resource conflicts is modeled as subsystems through local tropical automata. Parallel task execution is explored through a new framework for a synchronous product of tropical automata directly minimizing the global completion time of a set of tasks. A dater-based analysis is proposed to determine an optimal qualitative schedule and relies on proposed definitions of global, private, and synchronizing daters. This approach drastically narrows the solution spectrum, and allows finding the optimal task schedule. The approach is applied to a flow network as a case study, but can be applied to systems of different nature. [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]

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]

We introduce Visibly Linear Temporal Logic ( VLTL), a linear-time temporal logic that captures the full class of Visibly Pushdown Languages over infinite words. The novel logic avoids fix points and instead provides natural temporal operators with simple and intuitive semantics. We prove that the complexities of the satisfiability and visibly pushdown model checking problems are the same as for other well known logics, like CaRet and the nested word temporal logic NWTL, which in contrast are strictly more limited in expressive power than VLTL. Moreover, formulas of CaRet and NWTL can be translated inductively and in linear-time into VLTL. [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]

We prove completeness for some language-theoretic models of the full Lambek calculus and its various fragments. First we consider syntactic concepts and syntactic concepts over regular languages, which provide a complete semantics for the full Lambek calculus $${\mathbf {FL}}_\perp $$ . We present a new semantics we call automata-theoretic, which combines languages and relations via closure operators which are based on automaton transitions. We establish the completeness of this semantics for the full Lambek calculus via an isomorphism theorem for the syntactic concepts lattice of a language and a construction for the universal automaton recognizing the same language. Finally, we use automata-theoretic semantics to prove completeness of relation models of binary relations and finite relation models for the Lambek calculus without and with empty antecedents (henceforth: $$\mathbf L $$ and $$\mathbf L1 $$ ), thus solving a problem left open by Pentus (Ann Pure Appl Log 75:179-213, 1995). [ABSTRACT FROM AUTHOR]

We present a new algorithm to construct a (generalized) deterministic Rabin automaton for an LTL formula $$\varphi $$ . The automaton is the product of a co-Büchi automaton for $$\varphi $$ and an array of Rabin automata, one for each $${\mathbf {G}}$$ -subformula of $$\varphi $$ . The Rabin automaton for $${\mathbf {G}}\psi $$ is in charge of recognizing whether $${\mathbf {F}}{\mathbf {G}}\psi $$ holds. This information is passed to the co-Büchi automaton that decides on acceptance. As opposed to standard procedures based on Safra's determinization, the states of all our automata have a clear logical structure, which allows for various optimizations. Experimental results show improvement in the sizes of the resulting automata compared to existing methods. [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]