On regular realizability problems

We consider the class of regular realizability problems. Any of such problems is specified by some language (filter) and consists in verifying that the intersection of a given regular language and the filter is nonempty. The main question is diversity of the computational complexity of such problems. We show that any regular realizability problem with an infinite filter is hard for a class of problems decidable in logarithmic space with respect to logarithmic reductions. We give examples of NP-complete and PSPACE-complete regular realizability problems.     

On regular realizability problems for context-free languages

We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance relation of CF languages. However, as we prove, it is more rough. We also give examples of both P-complete and NL-complete regular realizability problems for CF filters. Furthermore, we give an example of a subclass of CF languages for filters of which the regular realizability problems can have an intermediate complexity. These are languages with polynomially bounded rational indices.     

On the expressive power of schemes

We present a calculus, called the scheme-calculus, that permits to express natural deduction proofs in various theories. Unlike λ-calculus, the syntax of this calculus sticks closely to the syntax of proofs, in particular, no names are introduced for the hypotheses. We show that despite its non-determinism, some typed scheme-calculi have the same expressivity as the corresponding typed λ-calculi.     

On the expressive power of data dependencies

Summary The class of data dependencies is a class of first-order sentences that seem to be suitable to express semantic constraints for relational databases. We deal with the question of which classes of databases are axiomatizable by data dependencies. (A class of databases is said to be axiomatizable by sentences of a certain kind if there exists a set of sentences of that kind such that is the class of all models of that set.) Our results characterize, by algebraic closure conditions, classes of databases that are axiomatizable by dependencies of different kinds. Our technique is model-theoretic, and the characterization easily entails all previously known results on axiomatizability by dependencies.Research partially supported by Swiss National Science Foundation Grant No. 82.820.0.80 (1980–1982), revision of the paper was done while visiting the Mathematisches Forschungsinstitut at the Swiss Federal Institute of Technology (Summer 1985)Part of the research reported here was done while the author was at Stanford University and supported by a Weizmann Post-Doctoral Fellowship and AFOSR grant 80-0212     

On the expressive power of behavioral profiles

Behavioral profiles have been proposed as a behavioral abstraction of dynamic systems, specifically in the context of business process modeling. A behavioral profile can be seen as a complete graph over a set of task labels, where each edge is annotated with one relation from a given set of binary behavioral relations. Since their introduction, behavioral profiles were argued to provide a convenient way for comparing pairs of process models with respect to their behavior or computing behavioral similarity between process models. Still, as of today, there is little understanding of the expressive power of behavioral profiles. Via counter-examples, several authors have shown that behavioral profiles over various sets of behavioral relations cannot distinguish certain systems up to trace equivalence, even for restricted classes of systems represented as safe workflow nets. This paper studies the expressive power of behavioral profiles from two angles. Firstly, the paper investigates the expressive power of behavioral profiles and systems captured as acyclic workflow nets. It is shown that for unlabeled acyclic workflow net systems, behavioral profiles over a simple set of behavioral relations are expressive up to configuration equivalence. When systems are labeled, this result does not hold for any of several previously proposed sets of behavioral relations. Secondly, the paper compares the expressive power of behavioral profiles and regular languages. It is shown that for any set of behavioral relations, behavioral profiles are strictly less expressive than regular languages, entailing that behavioral profiles cannot be used to decide trace equivalence of finite automata and thus Petri nets.     

On the expressive power of CSP refinement

We show that wide-ranging classes of predicates on the failures-divergences model for CSP can be represented by refinement checks in a general form. These are predicates of a process P expressible as F(P)⊏G(P), where F and G are CSP contexts and ⊏ is refinement. We use ideas similar to full abstraction, but achieve a stronger property than that. Our main result is that topologically-closed predicates are precisely those representable when F and G are both uniformly continuous. We show that sub-classes of predicates such as refinement-closed and distributive ones are represented by special forms of this check.Received November 2003Revised July 2004Accepted December 2004 by M. Leuschel and D. J. Cooke     

On the generative power of regular pattern grammars

Acta Informatica - It is shown that for every recursively enumerable language L $$ \subseteq $$ ∑* there exists a selective substitution grammar with a regular selector over a binary alphabet...     

On the realizability of collaborative services

This paper considers compositional specifications of services using UML 2 collaborations, activity and interaction diagrams, and addresses the realizability problem for such specifications: given a global specification, can we construct a set of communicating system components whose joint behavior is precisely the specified global behavior? We approach the problem by looking at how the sequencing of collaborations and local actions may be described using UML activity diagrams. We identify the realizability problems for each of the sequencing operators, such as strong and weak sequence, choice of alternatives, loops, and concurrency. The nature of these realizability problems and possible solutions are discussed. This brings a new look at already known problems: we show that given some conditions, certain problems can already be detected at an abstract level, without looking at the detailed interactions of the collaborations, provided that we know the components that initiate and terminate the different collaborations.     

On the expressive power of the relational algebra with partially ordered domains

Assuming data domains are partially ordered, we define the partially ordered relational algebra (PORA) by allowing the ordering predicate ? to be used in formulae of the selection operator σ. We apply Paredaens and Bancilhon's Theorem to examine the expressiveness of the PORA, and show that the PORA expresses exactly the set of all possible relations which are invariant under order-preserving automorphisms of databases. The extension is consistent with the two important extreme cases of unordered and linearly ordered domains. We also investigate the three hierarchies of: (1) computable queries, (2) query languages and (3) partially ordered domains, and show that there is a one-to-one correspondence between them.     

On the expressive power of movement and restriction in pure mobile ambients

Pure mobile ambients is a process calculus suitable to focus on issues related to mobility, abstracting away from aspects concerning process communication. However, it incorporates name restriction (i.e. the (νn) binder) and ambient movement (i.e. the in and out capabilities) that can be seen as characteristics adapted, or directly borrowed, from the tradition of communication-based process calculi. For this reason, we retain that it is worth to investigate whether or not these features can be removed from pure mobile ambients without losing expressive power.To this aim, we consider two variants of pure mobile ambients which differ in the way infinite processes can be defined; the former exploits process replication, while the latter is more general and permits recursive process definition. We analyse whether or not the elimination of ambient movement and/or name restriction reduces the expressive power of these two calculi, using the decidability of process termination as a yardstick. We prove that name restriction can be removed from both calculi without reducing the expressive power. On the other hand, the elimination of both ambient movement and name restriction strictly reduces the expressive power of both calculi. As far as the elimination of only ambient movement is concerned, we prove an interesting discrimination result: process termination is undecidable under recursive process definition, while it turns out to be decidable under process replication.     

Enriching the expressive power of security labels

Common security models such as Bell-LaPadula focus on the control of access to sensitive data but leave some important systems issues unspecified, such as the implementation of read-only objects, garbage collection, and object upgrade and downgrade paths. Consequently, different implementations of the same security model may have conflicting operational and security semantics. We propose the use of more expressive security labels for specifying these system issues within the security model, so that the semantics of a system design are precisely understood and are independent of implementation details     

The expressive power of the shuffle product

There is an increasing interest in the shuffle product on formal languages, mainly because it is a standard tool for modeling process algebras. It still remains a mysterious operation on regular languages.Antonio Restivo proposed as a challenge to characterize the smallest class of languages containing the singletons and closed under Boolean operations, product and shuffle. This problem is still widely open, but we present some partial results on it. We also study some other smaller classes, including the smallest class containing the languages composed of a single word of length 2 which is closed under Boolean operations and shuffle by a letter (resp. shuffle by a letter and by the star of a letter). The proof techniques have both an algebraic and a combinatorial flavor.     

The expressive power of the bounded-iteration construct

The bounded-iteration constructforeach x in R/p do t od is very commonly used in database programming, due to the fact that database programs are dominated by data retrieval and manipulation tasks rather than by complex computations. Hence in database programming language design, it is important to understand the expressive power of the bounded-iteration construct and its relationship with other language constructs. We study the bounded-iteration construct within the context of a simple database programming language called theiterative transaction language. The language is shown to have NPTIME expressive power, and the deterministic subclass of it has PTIME expressive power, without any extra machineries or restrictions. We show that the bounded-iteration construct is essential for achieving this expressiveness, by characterizing its relationship with other constructs in the language. We also identify another natural subclass of iterative transactions calledfirst-order transactions with exactly first-order expressive power. The complexity of first-order transactions in terms of nested iterations and intermediate states is connected further to the complexity of first-order updates in terms of quantification depth.This work was supported in part by the Defense Advanced Research Projects Agency under Contract N39-84-C-0211 for Knowledge Based Management Systems and by Rome Air Development Center under Contract 30602-86-C-0026 for Knowledge-Based Software AssistantAn extended abstract of this work appeared in the Proceedings of the Second International Workshop on Database Programming Languages, 1989, 411–421     

The expressive power of side effects in prolog

This paper presents a rigorous framework for studying the influence of side effects in logic programming. We exemplify this framework by analyzing the power of assert and retract restricted to ground clauses. The same model can be used to analyze the exact behavior of reconsult and other constructs which modify the underlying database.     

The expressive power of delay operators in SCCS

Summary We investigate the relative expressive power of finite delay operators in SCCS. These were introduced by Milner and by Hennessy to study fairness properties of processes in the context of SCCS. We show that the context sensitive delay operator introduced by Hennessy is more expressive than the finite delay operator introduced by Milner. This result is closely related to recent results by Pananagden and Stark on the expressive power of fair merge in asynchronous dataflow (Kahn) networks. It indicates that the expressiveness results obtained there are not sensitive to the precise computational model since SCCS, unlike Kahn networks, is synchronous and permits expansion of recursively defined processes.This research was supported in part by NSF grant CCR-8818979. Present address: School of Computer Science, 3480 Rue University, McGill University, Montreal, Quebec, Canada H3A 2A7