The continuous Skolem-Pisot problem

We study decidability and complexity questions related to a continuous analogue of the Skolem-Pisot problem concerning the zeros and nonnegativity of a linear recurrent sequence. In particular, we show that the continuous version of the nonnegativity problem is NP-hard in general and we show that the presence of a zero is decidable for several subcases, including instances of depth two or less, although the decidability in general is left open. The problems may also be stated as reachability problems related to real zeros of exponential polynomials or solutions to initial value problems of linear differential equations, which are interesting problems in their own right.     

Computational classification of cellular automata

We discuss attempts at the classification of cellular automata, in particular with a view towards decidability. We will see that a large variety of properties relating to the short-term evolution of configurations are decidable in principle, but questions relating to the long-term evolution are typically undecidable. Even in the decidable case, computational hardness poses a major obstacle for the automatic analysis of cellular automata.     

A Decidability Result for the Model Checking of Infinite-State Systems

We present a decidability result for the model checking of a certain class of properties that can be conveniently expressed as ground formulae of a first-order temporal fragment. The decidability result is obtained by importing into the context of model-checking problems some techniques developed for the combination of decision procedures for the satisfiability of constraints. The general decidability result is then specialized for checking properties of particular interest, such as liveness and safety, and, for the latter case, a more optimized algorithm has been proposed.     

Independent agents in a globalized world modelled by tissue P systems

For modelling the interactions of independent agents (only interacting via a common environment, but not depending on any direct physical interactions with other agents) in the globalized world, we here consider so-called agent tissue P systems (ATP systems). Based on the model of tissue P systems, such ATP systems consist of cells (independent agents) with specific programs which allow for changing the objects inside the agent or for exchanging objects from inside the agent with objects from the environment through the cell membrane. We investigate the computational power of specific variants of ATP systems, and also discuss the special decidability problem whether or not a given ATP system of a specific type from its initial contents can ever reach a configuration where all objects in the system are contained in a specific subset of the set of objects.     

Decidable First-Order Theories of One-Step Rewriting in Trace Monoids

We prove that the first-order theory of the one-step rewriting relation associated with a trace rewriting system is decidable but in general not elementary. This extends known results on semi-Thue systems but our proofs use new methods; these new methods yield the decidability of local properties expressed in first-order logic augmented by modulo-counting quantifiers. Using the main decidability result, we define several subclasses of trace rewriting systems for which the confluence problem is decidable.     

O-Minimal Hybrid Systems

An important approach to decidability questions for verification algorithms of hybrid systems has been the construction of a bisimulation. Bisimulations are finite state quotients whose reachability properties are equivalent to those of the original infinite state hybrid system. In this paper we introduce the notion of o-minimal hybrid systems, which are initialized hybrid systems whose relevant sets and flows are definable in an o-minimal theory. We prove that o-minimal hybrid systems always admit finite bisimulations. We then present specific examples of hybrid systems with complex continuous dynamics for which finite bisimulations exist. Date received: June 9, 1998. Date revised: June 28, 1999.     

On images of D0L and DT0L power series

The D0L and DT0L power series are generalizations of D0L and DT0L languages. We continue the study of these series by investigating various decidability questions concerning the images of D0L and DT0L power series.     

Non-Interference Control Synthesis for Security Timed Automata

In this paper, the problem of synthesizing controllers that ensures non interference for multilevel security dense timed discrete event systems modeled by an extension of Timed Automata, is addressed for the first time. We first discuss a notion of non interference for dense real-time systems that refines notions existing in the literature and investigate decidability issues raised by the verification problem for dense time properties. We then prove the decidability of the problem of synthesis of the timed controller for some of these timed non interference properties, providing so a symbolic method to synthesize a controller that ensures them.     

On decidability and closure properties of language classes with respect to bio-operations

We present general results that are useful in showing closure and decidable properties of large classes of languages with respect to biologically-inspired operations. We use these results to prove new decidability results and closure properties of some classes of languages under bio-operations such hairpin-inversion, the recently studied operation of pseudo-inversion, and other bio-operations. We also provide techniques for proving undecidability results. In particular, we give a new approach for proving the undecidability of problems for which the usual method of reduction to the undecidability of the Post Correspondence Problem seems hard to apply. Our closure and decidability results strengthen or generalize previous results.     

Trees,grids, and MSO decidability: From graphs to matroids

Monadic second order (MSO) logic has proved to be a useful tool in many areas of application, reaching from decidability and complexity to picture processing, correctness of programs and parallel processes. To characterize the structural borderline between decidability and undecidability is a classical research problem here. This problem is related to questions in computational complexity, especially to the model checking problem, for which many tools developed in the area of decidability have proved to be useful. For more than two decades it was conjectured in [D. Seese, The structure of the models of decidable monadic theories of graphs, Ann. Pure Appl. Logic 53 (1991) 169–195] that decidability of monadic theories of countable structures implies that the theory can be reduced via interpretability to a theory of trees.     

Sequent calculi and decidability for intuitionistic hybrid logic

In this paper we study the proof theory of the first constructive version of hybrid logic called Intuitionistic Hybrid Logic (IHL) in order to prove its decidability. In this perspective we propose a sequent-style natural deduction system and then the first sequent calculus for this logic. We prove its main properties like soundness, completeness and also the cut-elimination property. Finally we provide, from our calculus, the first decision procedure for IHL and then prove its decidability.     

Combining static analysis and state transition graphs for verification of event-condition-action systems in the RERS 2012 and 2013 challenges

We present a combination of approaches for the verification of event-condition-action (ECA) systems. The analyzed ECA systems range from structurally simple to structurally complex systems. We address the verification of reachability properties and behavioral properties. Reachability properties are represented by assertions in the program and we determine statically whether an assertion holds for all execution paths. Behavioral properties are represented as linear temporal logic formulas specifying the input/output behavior of the program. Our approach assumes a finite state space. We compare a symbolic analysis with an exhaustive state space exploration and discuss the trade-offs between the approaches in terms of the number of computed states and run-time behavior. All variants compute a state transition graph which can also be passed to an LTL verifier. The variants have a different impact on the number of computed states in the state transition graph which in turn impacts the run-time and memory consumption of subsequent phases. We evaluate the different analysis variants with the RERS benchmarks.     

Decidability Equivalence between the Star Problem and the Finite Power Problem in Trace Monoids

In the last decade, research on the star problem in trace monoids (is the iteration of a recognizable language also recognizable?) has pointed out the importance of the finite power property to achieve partial solutions to this problem. We prove that the star problem is decidable in some trace monoid if and only if, in the same monoid, it is decidable whether a recognizable language has the finite power property. Intermediate results allow us to give a shorter proof for the decidability of the two previous problems in every trace monoid without a C4 submonoid. We also deal with some earlier ideas, conjectures, and questions which have been raised in the research on the star problem and the finite power property, e.g., we show the decidability of these problems for recognizable languages which contain at most one non-connected trace. Received April 29, 1999, and in revised form November 8, 2000 and in final form November 24, 2000. Online publication February 26, 2001.     

Regular Language Representations in the Constructive Type Theory of Coq

We explore the theory of regular language representations in the constructive type theory of Coq. We cover various forms of automata (deterministic, nondeterministic, one-way, two-way), regular expressions, and the logic WS1S. We give translations between all representations, show decidability results, and provide operations for various closure properties. Our results include a constructive decidability proof for the logic WS1S, a constructive refinement of the Myhill-Nerode characterization of regularity, and translations from two-way automata to one-way automata with verified upper bounds for the increase in size. All results are verified with an accompanying Coq development of about 3000 lines.     

Polytopic uncertainty for linear systems: New and old complexity results

We survey the problem of deciding the stability or stabilizability of uncertain linear systems whose region of uncertainty is a polytope. This natural setting has applications in many fields of applied science, from control theory to systems engineering to biology. We focus on the algorithmic decidability of this property when one is given a particular polytope. This setting gives rise to several different algorithmic questions, depending on the nature of time (discrete/continuous), the property asked (stability/stabilizability), or the type of uncertainty (fixed/switching). Several of these questions have been answered in the literature in the last thirty years. We point out the ones that have remained open, and we answer all of them, except one which we raise as an open question. In all the cases, the results are negative in the sense that the questions are NP-hard. As a byproduct, we obtain complexity results for several other matrix problems in systems and control.     

Risk Assessment for One-Counter Threads

Threads as contained in a thread algebra are used for the modeling of sequential program behavior. A thread that may use a counter to control its execution is called a ‘one-counter thread’. In this paper the decidability of risk assessment (a certain form of action forecasting) for one-counter threads is proved. This relates to Cohen’s impossibility result on virus detection (Comput. Secur. 6(1), 22–35, 1984). Our decidability result follows from a general property of the traces of one-counter threads: if a state is reachable from some initial state, then it is also reachable along a path in which all counter values stay below a fixed bound that depends only on the initial and final counter value. A further consequence is that the reachability of a state is decidable. These properties are based on a result for ω-one counter machines by Rosier and Yen (SIAM J. Comput. 16(5), 779–807, 1987).     

Decidability of performance equivalence for basic parallel processes

We study an extension of the class of Basic Parallel Processes (BPP), in which actions are durational and urgent and parallel components have independent local clocks. The main result is decidability of strong bisimilarity, known also as performance equivalence, in this class. This extends the earlier decidability result for plain BPP by Christensen et al. Our decision procedure is based on decidability of the validity problem for Presburger arithmetic. We prove also polynomial complexity in positive-duration fragment, thus properly extending a previous result by Bérard et al. Both ill-timed and well-timed semantics are treated.     

An effectively given initial semigroup

Summary The notion of effectively given domains is extended to semigroups. We show that the initial algebra for the semigroups with finite generators is effectively given. The initial algebra we describe uses expressions and trees of symbols of generators and the partial order in the algebra is defined using a formal system on expressions. The main body of the paper lies in the demonstration of the decidability of this formal system.This research was supported in part by University of Kansas General Research allocation 3530-20-0038     

Model checking for process rewrite systems and a class of action-based regular properties

We consider the model checking problem for Process Rewrite Systems (PRS), an infinite-state formalism (non Turing-powerful) which subsumes many common models such as Pushdown Processes and Petri Nets. PRS can be adopted as a formal model for programs with dynamic creation and synchronization of concurrent processes, and with recursive procedures. The model-checking problem of PRS against action-based linear temporal logic (ALTL) is undecidable. However, decidability for some interesting fragment of ALTL remains an open question. In this paper, we state decidability results concerning generalized acceptance properties about infinite derivations (infinite term rewriting) in PRS. As a consequence, we obtain decidability of the model-checking problem (restricted to infinite runs) of PRS against a meaningful fragment of ALTL.     

Model checking Petri nets with names using data-centric dynamic systems

Petri nets with name creation and management (\({\nu}\)-PNs) have been recently introduced as an expressive model for dynamic (distributed) systems, whose dynamics are determined not only by how tokens flow in the system, but also by the pure names they carry. On the one hand, this extension makes the resulting nets strictly more expressive than P/T nets: they can be exploited to capture a plethora of interesting systems, such as distributed systems enriched with channels and name passing, service interaction with correlation mechanisms, and resource-constrained workflow nets that explicitly account for process instances. On the other hand, fundamental properties like coverability, termination and boundedness are decidable for \({\nu}\)-PNs. In this work, we go one step beyond the verification of such general properties, and provide decidability and undecidability results of model checking \({\nu}\)-PNs against variants of first-order \({\mu}\)-calculus, recently proposed in the area of data-aware process analysis. While this model checking problem is undecidable in the general case, decidability can be obtained by considering different forms of boundedness, which still give raise to an infinite-state transition system. We then ground our framework to tackle the problem of soundness checking over workflow nets enriched with explicit process instances and resources. Notably, our decidability results are obtained via a translation to data-centric dynamic systems, a recently devised framework for the formal specification and verification of data-aware business processes working over full-fledged relational databases with constraints. In this light, our results contribute to the cross-fertilization between the area of formal methods for concurrent systems and that of foundations of data-aware processes, which has not been extensively investigated so far.