Discrete dynamical systems are commonly used to model the spread of contagions on real-world networks. Under the PAC framework, existing research has studied the problem of learning the behavior of a system, assuming that the underlying network is known. In this work, we focus on a more challenging setting: to learn both the behavior and the underlying topology of a black-box system. We show that, in general, this learning problem is computationally intractable. On the positive side, we present efficient learning methods under the PAC model when the underlying graph of the dynamical system belongs to certain classes. Further, we examine a relaxed setting where the topology of an unknown system is partially observed. For this case, we develop an efficient PAC learner to infer the system and establish the sample complexity. Lastly, we present a formal analysis of the expressive power of the hypothesis class of dynamical systems where both the topology and behavior are unknown, using the well-known Natarajan dimension formalism. Our results provide a theoretical foundation for learning both the topology and behavior of discrete dynamical systems.

Networked dynamical systems are widely used as formal models of real-world cascading phenomena, such as the spread of diseases and information. Prior research has addressed the problem of learning the behavior of an unknown dynamical system when the underlying network has a single layer. In this work, we study the learnability of dynamical systems over multilayer networks, which are more realistic and challenging. First, we present an efficient PAC learning algorithm with provable guarantees to show that the learner only requires a small number of training examples to infer an unknown system. We further provide a tight analysis of the Natarajan dimension which measures the model complexity. Asymptotically, our bound on the Nararajan dimension is tight for almost all multilayer graphs. The techniques and insights from our work provide the theoretical foundations for future investigations of learning problems for multilayer dynamical systems.

Evolutionary anti-coordination games on networks capture real-world strategic situations such as traffic routing and market competition. Two key problems concerning evolutionary games are the existence of a pure Nash equilibrium (NE) and the convergence time. In this work, we study these two problems for anti-coordination games under sequential and synchronous update schemes. For each update scheme, we examine two decision modes based on whether an agent considers its own previous action (self essential) or not (self non-essential) in choosing its next action. Using a relationship between games and dynamical systems, we show that for both update schemes, finding an NE can be done efficiently under the self non-essential mode but is computationally intractable under the self essential mode. We then identify special cases for which an NE can be obtained efficiently. For convergence time, we show that the dynamics converges in a polynomial number of steps under the synchronous scheme; for the sequential scheme, the convergence time is polynomial only under the self non-essential mode. Through experiments, we empirically examine the convergence time and the equilibria for both synthetic and real-world networks.

Applications such as employees sharing office spaces over a workweek can be modeled as problems where agents are matched to resources over multiple rounds. Agents' requirements limit the set of compatible resources and the rounds in which they want to be matched. Viewing such an application as a multi-round matching problem on a bipartite compatibility graph between agents and resources, we show that a solution (i.e., a set of matchings, with one matching per round) can be found efficiently if one exists. To cope with situations where a solution does not exist, we consider two extensions. In the first extension, a benefit function is defined for each agent and the objective is to find a multi-round matching to maximize the total benefit. For a general class of benefit functions satisfying certain properties (including diminishing returns), we show that this multi-round matching problem is efficiently solvable. This class includes utilitarian and Rawlsian welfare functions. For another benefit function, we show that the maximization problem is NP-hard. In the second extension, the objective is to generate advice to each agent (i.e., a subset of requirements to be relaxed) subject to a budget constraint so that the agent can be matched. We show that this budget-constrained advice generation problem is NP-hard. For this problem, we develop an integer linear programming formulation as well as a heuristic based on local search. We experimentally evaluate our algorithms on synthetic networks and apply them to two real-world situations: shared office spaces and matching courses to classrooms.

Networked discrete dynamical systems are often used to model the spread of contagions and decision-making by agents in coordination games. Fixed points of such dynamical systems represent configurations to which the system converges. In the dissemination of undesirable contagions (such as rumors and misinformation), convergence to fixed points with a small number of affected nodes is a desirable goal. Motivated by such considerations, we formulate a novel optimization problem of finding a nontrivial fixed point of the system with the minimum number of affected nodes. We establish that, unless P = NP, there is no polynomial-time algorithm for approximating a solution to this problem to within the factor n^(1 - epsilon) for any constant epsilon > 0. To cope with this computational intractability, we identify several special cases for which the problem can be solved efficiently. Further, we introduce an integer linear program to address the problem for networks of reasonable sizes. For solving the problem on larger networks, we propose a general heuristic framework along with greedy selection methods. Extensive experimental results on real-world networks demonstrate the effectiveness of the proposed heuristics. A full version of the manuscript, source code and data are available at: https://github.com/bridgelessqiu/NMIN-FPE

Using a discrete dynamical system model, many papers have addressed the problem of learning the behavior (i.e., the local function at each node) of a networked system through active queries, assuming that the network topology is known. We address the problem of inferring both the topology of the network and the behavior of a discrete dynamical system through active queries. We consider two query models studied in the literature, namely the batch model (where all the queries must be submitted together) and the adaptive model (where responses to previous queries can be used in formulating a new query). Our results are for systems where the state of each node is from {0,1} and the local functions are Boolean. We present algorithms to learn the topology and the behavior under both batch and adaptive query models for several classes of dynamical systems. These algorithms use only a polynomial number of queries. We also present experimental results obtained by running our query generation algorithms on synthetic and real-world networks.

Developing techniques to infer the behavior of networked social systems has attracted a lot of attention in the literature. Using a discrete dynamical system to model a networked social system, the problem of inferring the behavior of the system can be formulated as the problem of learning the local functions of the dynamical system. We investigate the problem assuming an active form of interaction with the system through queries. We consider two classes of local functions (namely, symmetric and threshold functions) and two interaction modes, namely batch (where all the queries must be submitted together) and adaptive (where the set of queries submitted at a stage may rely on the answers to previous queries). We establish bounds on the number of queries under both batch and adaptive query modes using vertex coloring and probabilistic methods. Our results show that a small number of appropriately chosen queries are provably sufficient to correctly learn all the local functions. We develop complexity results which suggest that, in general, the problem of generating query sets of minimum size is computationally intractable. We present efficient heuristics that produce query sets under both batch and adaptive query modes. Also, we present a query compaction algorithm that identifies and removes redundant queries from a given query set. Our algorithms were evaluated through experiments on over 20 well-known networks.

Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Motivated by applications in systems biology, several recent papers have studied algorithmic and complexity aspects of diffusion problems for dynamical systems whose underlying graphs are directed, and may contain directed cycles. Such problems can be regarded as reachability problems in the phase space of the corresponding dynamical system. We show that computational intractability results for reachability problems hold even for dynamical systems on directed acyclic graphs (dags). We also show that for dynamical systems on dags where each local function is monotone, the reachability problem can be solved efficiently.

The problem of inferring unknown parameters of a networked social system is of considerable practical importance. We consider this problem for the independent cascade model using an active query framework. More specifically, given a network whose edge probabilities are unknown, the goal is to infer the probability value on each edge by querying the system. The optimization objective is to use as few queries as possible in carrying out the inference. We present approximation algorithms that provide provably good estimates of edge probabilities. We also present results from an experimental evaluation of our algorithms on several real-world networks.

We develop a graph-theoretic model for service-oriented networks and propose metrics that quantify the resilience of such networks under node and edge failures. These metrics are based on the topological structure of the network and the manner in which services are distributed over the network. We present efficient algorithms to determine the maximum number of node and edge failures that can be tolerated by a given service-oriented network. These algorithms rely on known algorithms for computing minimum cuts in graphs. We also present efficient algorithms for optimally allocating services over a given network so that the resulting service-oriented network can tolerate single node or edge failures. These algorithms are derived through a careful analysis of the decomposition of the underlying network into appropriate types of connected components.

Abstract Time series segmentation is a promising approach to discover temporal patterns from time‐stamped numeric data. A novel approach to apply time series segmentation to discern temporal information from software version repositories is proposed. Data from such repositories, both numeric and non‐numeric, are represented as item‐set time series data. A dynamic programming algorithm for optimal segmentation is presented. The algorithm automatically produces a compacted item‐set time series that can be analyzed to identify temporal patterns. The effectiveness of the approach is illustrated by analyzing version control repositories of several open‐source projects to identify time‐varying patterns of developer activity. The experimental results show that the segmentation algorithm produces segments that capture meaningful information and is superior to the information content obtained by arbitrarily segmenting software history into regular time intervals. Copyright © 2008 John Wiley & Sons, Ltd.

Time series analysis is a promising approach to discover temporal patterns from time stamped, numeric data. A novel approach to apply time series analysis to discern temporal information from software version repositories is proposed. Version logs containing numeric as well as non-numeric data are represented as an item-set time series. A dynamic programming based algorithm to optimally segment an item-set time series is presented. The algorithm automatically produces a compacted item-set time series that can be analyzed to discern temporal patterns. The effectiveness of the approach is illustrated by applying to the Mozilla data set to study the change frequency and developer activity profiles. The experimental results show that the segmentation algorithm produces segments that capture meaningful information and is superior to the information content obtaining by arbitrarily segmenting time period into regular time intervals.

Abstract Facility dispersion problems arise in the context of placing obnoxious facilities and retail outlets. In the offline version of such a problem, the input consists of a complete graph on n nodes, a nonnegative weight (distance) for each edge, and the number k ⩽ n of facilities to be placed. The goal is to choose a facility placement consisting of k nodes so as to maximize a given measure of the distances among the facilities. Here, we consider an online version of the problem where the value of k is not known apriori; instead, requests for facilities arrive one at a time. It is also required that previously placed facilities cannot be moved or eliminated. Our main result is that for any objective that satisfies two properties, namely monotonicity and graceful degradation, any offline approximation algorithm with a performance guarantee ρ can be used to develop an algorithm with competitive ratio c ρ for the online version, where c is a constant independent of the problem instance. Objectives for which our result applies include the average edge weight and average weight of a star subgraph. The result holds even when the edge weights do not satisfy the triangle inequality. We also identify dispersion objectives for which the offline and online versions have different behaviors when only one of the above two properties is satisfied. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 206–217 2006

We consider the analysis and optimization of code utilizing operations and functions operating on entire arrays. Models are developed for studying the minimization of the number of materializations of array-valued temporaries in basic blocks, each consisting of a sequence of assignment statements involving array-valued variables. We derive lower bounds on the number of materializations required, and develop several algorithms minimizing the number of materializations, subject to a simple constraint on allowable statement rearrangement. In contrast, we also show that when statement rearrangement is unconstrained, minimizing the number of materializations becomes NP-complete, even for very simple basic blocks.

Constructing time decompositions of time stamped documents is an important first step in extracting temporal information from a document set. Efficient algorithms are described for computing optimal lossy decompositions for a given document set, where the loss of information is constrained to be within a specified bound. A novel and efficient algorithm is proposed for computing information loss values required to construct optimal lossy decompositions. Experimental results are reported comparing optimal lossy decompositions and equal length decompositions in terms of a number of parameters such as information loss. In particular, our results show that optimal lossy decompositions outperform equal length decompositions by preserving more of the information content of the underlying document set. The results also demonstrate that permitting even small amounts of variability in the length of the subintervals of a decomposition results in capturing more of the temporal information content of a document set when compared to equal length decompositions. This paper builds upon our earlier work on time decompositions where the problem of computing optimal lossy decomposition of the time period associated with a document set was first formulated.

Extraction of sequences of events from news and other documents based on the publication times of these documents has been shown to be extremely effective in tracking past events. This paper addresses the issue of constructing an optimal decomposition of the time period associated with a given document set, i.e., a decomposition with the smallest number of subintervals, subject to no or limited loss of information. We introduce the notion of the compressed interval decomposition, where each subinterval consists of consecutive time points having identical information content. We define optimality, and show that any optimal information preserving decomposition of the time period is a refinement of the compressed interval decomposition. We define several special classes of measure functions (functions that compute the significant information from document sets), based on their effect on the information computed as document sets are combined. These classes are used in developing algorithms for computing an optimal information preserving decomposition of the time period of a given document set. We also define the notion of information loss of a time decomposition of a given document set and give an efficient algorithm for computing an optimal lossy decomposition. We discuss the effectiveness of our algorithms on the Reuters-21578, Distribution 1.0 data set and a subset of Medline abstracts.

No abstract available.

Placement of inspection stations is a common task in transportation and communication networks. In this paper, two categories of problems involving placement of inspection stations are studied. The first category deals with the selection of inspection stations along a given path from an origin to a destination. The second considers simultaneous selection of both a path and inspection stations along that path. We formulate these problems under a variety of minimization objectives such as the maximum gap between two consecutive inspection stations, the expected penalty cost of failure along the path, and the total inspection cost. Our results include efficient algorithms for many formulations and complexity results as well as fully polynomial approximation schemes for other formulations. When considering cost objectives, we identify a core problem and show that the complexity of many formulations is directly related to the complexity of the core problem.

We consider path problems in networks where each edge is associated with a vector of weights. One application where such path problems arise is in transporting hazardous materials. In that context, the network is embedded in a cluster of communities (or zones), and it is important to consider the impact of an accident along an edge on the surrounding zones. This impact is modeled as a cost vector for each edge, where each component represents the impact of an accident on a zone. Under this model, we formulate two kinds of path problems, namely, routing and feasibility problems. These formulations utilize various definitions of equity with respect to cost impact on the zones. We present complexity results and pseudopolynomial algorithms for general versions as well as efficient algorithms for special cases. We also carry out a comparative analysis of different routing problems. © 1999 John Wiley & Sons, Inc. Networks 34: 19–35, 1999

We study the complexity and the efficient approximability of graph and satisfiability problems when specified using various kinds of periodic specifications studied previously. We obtain two general results. First, we characterize the complexities of several basic generalized CNF satisfiability problems SAT(S), when instances are specified using various kinds of 1- and 2-dimensional periodic specifications. We outline how this characterization can be used to prove a number of new hardness results for periodically specified problems for various complexity classes. As one corollary, we show that a number of basic NP-hard problems become EXPSPACE-hard when inputs are represented using 1-dimensional infinite periodic wide specifications, thereby answering an open question. Second, we outline a simple yet a general technique to devise approximation algorithms with provable worst case performance guarantees for a number of combinatorial problems specified periodically. Our efficient approximation algorithms and schemes are based on extensions of the previous ideas. They provide the first nontrivial collection of natural NEXPTIME-hard problems that have an /spl epsiv/-approximation (or PTAS).

Commercial distributed database systems generally support an optional protocol that provides loose consistency of replicas, allowing replicas to be inconsistent for some time. In such a protocol, each replicated data item is assigned a primary copy site. Typically, a transaction updates only the primary copies of data items, with updates to other copies deferred until after the transaction commits. After a transaction commits, its updates to primary copies are sent transactionally to the other sites containing secondary copies. We investigate the transaction model underlying the above protocol. We show that global serializability in such a system is a property of the placement of primary and secondary copies of replicated data items. We present a polynomial time algorithm to assign primary sites to data items so that the resulting topology ensures serializability.

No abstract available.

We study the problem of finding small trees. Classical network design problems are considered with the additional constraint that only a specified number k of nodes are required to be connected in the solution. A prototypical example is the kMST problem in which we require a tree of minimum weight spanning at least k nodes in an edge-weighted graph. We show that the kMST problem is NP-hard even for points in the Euclidean plane. We provide approximation algorithms with performance ratio $2\sqrt{k} $ for the general edge-weighted case and $O(k^{1/4} )$ for the case of points in the plane. Polynomial-time exact solutions are also presented for the class of treewidth-bounded graphs, which includes trees, series-parallel graphs, and bounded bandwidth graphs, and for points on the boundary of a convex region in the Euclidean plane. We also investigate the problem of finding short trees and, more generally, that of finding networks with minimum diameter. A simple technique is used to provide a polynomial-time solution for finding k-trees of minimum diameter. We identify easy and hard problems arising in finding short networks using a framework due to T. C. Hu.

No abstract available.

Abstract Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP‐hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring, and minimum dominating set. We also present an on‐line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representation of unit disk graphs. Geometric representations are used only in establishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of circles of arbitrary radii in the plane, intersection graphs of regular polygons, and intersection graphs of higher dimensional regular objects.

Algorithm-based fault tolerance (ABFT) is a popular approach to achieve fault and error detection in multiprocessor systems. The design problem for ABFT is concerned with the construction of a check set of minimum cardinality that detects a specified number of errors or faults. Previous work on this problem has assumed an a priori bound on the size of a check. We motivate and carry out an investigation of the problem without the bounded check size assumption. We establish upper and lower bounds on the number of checks needed to detect a given number of errors. The upper bounds are obtained through new schemes which are easy to implement, and the lower bounds are established using new types of arguments. These bounds are sharply different from those previously established under the bounded check size model. We also show that unlike error detection, the design problem for fault detection is NP-hard even for detecting only one fault.>

An efficient scheme to store and reconstruct versions of sequential files is presented. The reconstruction scheme involves building a data structure representing a complete version, and then successively modifying this data structure by applying a sequence of specially formatted differential files to it. Each application of a differential file produces a representation of an intermediate version, with the final data structure representing the requested version. The scheme uses a linked list to represent an intermediate version, instead of a sequential array, as is used traditionally. A new format for differential files specifying changes to this linked list data structure is presented. The specification of each change points directly to where the change is to take place, thereby obviating a search. Algorithms are presented for using such a new format differential file to transform the representation of a version, and for reconstructing a requested version. Algorithms are also presented for generating the new format differential files, both for the case of a forward differential specifying how to transform the representation of an old version to the representation of a new version, and for the case of a reverse differential specifying how to transform the representation of a new version to the representation of an old version. The new version reconstruction scheme takes time linear in the sum of the size of the initial complete version and the sizes of the file differences involved in reconstructing the requested version. In contrast, the classical scheme for reconstructing versions takes time proportional to the sum of the sizes of the sequence of versions involved in the reconstruction, and therefore has a worst-case time that is quadratic in the sum of the size of the initial complete version and the sizes of the file differences. The time cost of the new differential file generation scheme is comparable to the time cost of the classical differential file generation scheme.

Considers a strategy for dealing with communication conflicts in omega networks. Specifically, the authors consider the problem of partitioning a set of conflicting messages into a minimum number of subsets, called rounds, each free of communication conflicts. In addition to standard omega networks, they consider this problem for a more general class of networks called bundled omega networks, where interconnection links in the network are replaced by bundles of wires. Although the partitioning problem has previously been considered in the literature, its computational complexity has remained open. The authors show that for a number of cases, the problem is NP-complete, but for certain special cases, it is solvable in polynomial time. In addition, they present a class of distributed, on-line heuristics for the problem. Finally, they give a lower bound of /spl Omega/(log N) on the performance ratio for one of these heuristics.>

We study network-design problems with multiple design objectives.In particular, we look at two cost NY 12222.

Hierarchical object descriptions consisting of a set of module descriptions are considered, where each module is either a primitive module or has a body that is an interconnection of submodules. The description represents a flattened object, whose size can be exponential in the size of the description. The complexity of processing and/or analyzing such hierarchically specified objects is considered. The simulation of hierarchically specified circuits is emphasized, but the results are applicable to other kinds of hierarchically specified objects. It is shown that hierarchically specified acyclic circuits can be simulated deterministically in space linear in the size of the description, even when the description is not explicitly acyclic. $\Theta (n^2 )$-size-bounded reductions are given from the languages in ${\operatorname{DSPACE}}(n)$ to the problem of simulating hierarchically specified acyclic monotone circuits. This implies that this simulation problem is PSPACE-complete and that any algorithm for it that operates faster than $2^{O(\sqrt n )} $ deterministic time could be used to recognize all ${\operatorname{DSPACE}}(n)$ languages in less than $2^{O(n)} $ deterministic time. It is then shown that the simulation problem for hierarchically specified acyclic circuits (not necessarily monotone) can indeed be solved in $2^{O(\sqrt n )} $ deterministic time. Moreover, every hierarchically specified acyclic circuit is shown to have an equivalent flat circuit of size $2^{O(\sqrt n )} $. For binary circuits the size of the equivalent flat circuit is $O(n^{{3 / 2}} 2^{1.53\sqrt n } )$. It is also shown that the problem of simulating hierarchically specified circuits is EXPSPACE-complete for cyclic circuits.

Lower and upper bounds are established for the combinatorial problem of constructing minimal test sets for error detection in multiprocessor systems. The construction for detecting two errors produces minimal test sets, while that for three errors produces test sets whose size exceeds the lower bound by at most one. Also presented is a divide-and-conquer construction scheme for four or more errors.>

A paradigm is proposed for representing hierarchically specified design data in CAD database systems in which there are alternate expansions of hierarchically specified modules. The paradigm uses an ancestor-based scheme to control which instances of submodules are to be placed in the expansion of each instance of a given module and is formalized using a versioned directed acyclic multigraph (VDAG). The approach is aimed at reducing storage space in engineering design database systems and at providing a means for designers to specify alternate expansions of a module. The VDAG model is defined, and a mechanism by which a VDAG generates an exploded forest of design trees is described. Algorithms are provided to generate a design forest from a given VDAG, determine whether one module is contained by a larger module, extract a version from a VDAG, test whether two VDAGs are equivalent, and try to reduce the size of a VDAG. The problems of module containment and VDAG inequivalence are shown to be NP-complete, and the problem of finding a minimum sized VDAG equivalent to a given VDAG is shown to be NP-hard.>

A simple model, called a VDAG, is proposed for succinctly representing hierarchically specified design data in CAD database systems where there are to be alternate expansions of hierarchical modules. The model uses an ancestor-based expansion scheme to control which instances of submodules are to be placed within each instance of a given module.The approach is aimed at reducing storage space in engineering design database systems and providing a means for designers to specify alternate expansions of a module. The expressive power of the VDAG model is investigated, and the set of design forests that are VDAG-generable is characterized. It is shown that there are designs whose representation via VDAGs is exponentially more succinct than is possible when expansion is uncontrolled. The problem of determining whether a given design forest is VDAG-generable is shown to be $NP$-complete, even when the height of the forest is bounded. However, it is shown that determining whether a given forest is VDAG-generable and producing such a VDAG if it exists, can be partitioned into a number of simpler subproblems, each of which may not be too computationally difficult in practice. Furthermore, for forests in a special natural class that has broad applicability, a polynomial time algorithm is provided that determines whether a given forest is VDAG-generable, and produces such a VDAG if it exists. However, the paper shows that it is $NP$-hard to produce a minimum-sized such VDAG for forests in this special class, even when the height of the forest is bounded.

A strategy for dealing with communication conflicts that occur in omega networks is presented. The strategy operates by implementing the dual path property of omega networks, which allows the source and destination processors to reverse roles for some of the messages that are being transmitted. For certain message patterns, such a reversal produces a modified message pattern for which the network routes are disjoint. For a circuit switching mode in which the network links and switches are bidirectional, the disjoint set of routes for modified message pattern can be used to achieve conflict-free message transmission for the original message pattern. This strategy is investigated, and an efficient algorithm to determine whether it can be successfully applied to a given message pattern is presented.>

A simple model, called a VDAG, is proposed for representing hierarchically specified design data in CAD database systems where there are to be alternate expansions of hierarchically specified modules. The model uses an ancestor-based expansion scheme to control which instances of submodules are to be placed within each instance of a given module. The approach is aimed at reducing storage space in engineering design database systems, and providing a means for designers to specify alternate expansions of a module.

The state assignment problem for the programmable logic array (PLA) implementation of finite state machines is considered. It is pointed out that the number of PLA columns can be reduced by using state assignments leading to logic that is unate in the state variables. Half-hot state assignments are proposed, where each state has an encoding in which exactly half the state variables are equal to 1.>

The authors show that the problem of obtaining a minimum complete test set is NP-complete for monotone PLAs even when each product term of the PLA contains at most two literals. Using the ideas developed in the proof of this result, they resolve an open question due to B. Krishnamurthy and S.B. Akers (1984). The authors also show that given a complete test set T, the problem of obtaining a minimum test set contained in T is NP-complete even for two-level monotone circuits.>

We introduce the concept of a version graph to model the problem of minimising the space and version regeneration cost for database version control. We show that, in general, this problem and several of its variations are NP-complete. Motivated by the practical importance of these problems, we develop several heuristics and obtain worst-case guarantees on their performance. We also present linear time algorithms for problems characterized by special classes of version graphs.

We study the computational complexity of equivalence and minimization problems for expressions on many different lattices including each finite lattice and each distributive lattice. A general efficient expressibility condition C on a lattice is presented such that 1. The equivalence problem is co$NP$ hard for constant-free expressions on any lattice with at least two elements that satisfies condition C. Each finite or distributive lattice is shown to satisfy condition C. Moreover, if a lattice $\mathcal{L}$ satisfies condition C and $ \equiv $ is a congruence relation on $\mathcal{L}$, then ${\mathcal{L} / \equiv }$ also satisfies condition C. Several additional results are also presented. These results include the following: 2. In contrast to 1, the equivalence and operator minimization problems are solvable deterministically in polynomial time for disjunctive normal form and conjunctive normal form expressions on any lattice and for constant-free expressions on any free lattice with at least three generators: 3. Let $\mathcal{L}$ be a lattice. Then, the operator minimization problem and various approximate operator minimization problems for expressions on $\mathcal{L}$ are as hard as the problem of determining, for expressions F and G on $\mathcal{L}$, if $F \leqq G$.

Several computational problems about grammars are studied. Efficient algorithms are presented for the problems of (1) determining, for a given semantic grammar, if there exists a related parsing grammar in some specified grammar class, and (2) finding such a related parsing grammar when one exists. The two grammars are to be related by mergers of nonterminals and/or terminals. Efficient algorithms are presented for most of the grammar classes used in compilers. We also study the problem of (3) determining which terminals of a grammar are good candidates for merger into common lexical tokens of the corresponding parsing grammar.

Deterministic exponential lower time bounds are presented for analyzing recursion schemes and recursive programs. The lower bounds for recursion schemes hold for any interpretation with a nontrivial predicate, i.e. a predicate that is neither identically true nor identically false. The lower bounds for recursive programs hold for very simple programs in any recursive programming language with a nontrivial predicate. These lower time bounds hold for the executability, computational identity, totality, divergence, partial correctness, and total correctness problems.

The relationship between the setting in which an algebraic problem is posed and the complexity of solving the problem is considered.The problems stud~ed are equivalence, minimization, and approximate mimmlzatlon problems for formulas revolving variables, parentheses, operators, and (optionally) constants.General suffioent condmons on an algebraic structure Y for these problems to be NP-or coNP-hard are presented.Apphcations are gwen to a number of specific algebraic structures of independent interest including lattices, semirings, regular algebras, finite fields, rings 7/k, and Boolean nngs.Apphcations are also gwen to systems of rewrite rules and to several simple programming languages.

The main results of this paper show that serialization is both necessary and sufficient for consistency in concurrent database systems. This is true for both the final database and the views of the database seen by individual transactions. The model of a transaction includes both read and write operations which may be performed in any order (except an entity must be read before being written). The main results are presented in terms of an information flow model describing the source of each value read and the use of each value written. Since the model does not involve any concept of the “time” a value was read or written, it models any concurrency system producing information flow among transactions. There is a section discussing the effect of changing the model to include write operations without preceding reads, and a section discussing the restriction to straight-line programs.

Associated with the write of a database entity is both the or old value, and the after or new value. Concurrency can be increased by allowing other transactions to read the before values of a given transaction. The ramifications of allowing this, particularly on a distributed system in which limited communications is desirable, are investigated. A careful distinction is made between design decisions concerning communications and design decisions concerning the responses to read/write requests. Two schemes for producing such controls are given, one scheme for systems where processes are committed on termination, and the other for systems where committment is made later.

Deterministic exponential lower time bounds are obtained for analyzing monadic recursion schemes, multi-variable recursion schemes, and recursive programs. The lower bound for multivariable recursion schemes holds for any domain of interpretation with at least two elements. The lower bound for recursive programs holds for any recursive programming language with a nontrivial predicate test (i.e. a predicate test that is neither identically true nor identically false). Exponential lower bounds on depth of nesting of recursive function calls play an important role in the proofs of these bounds. In contrast, polynomial upper bounds on depth of nesting are obtained for total and linear monadic recursion schemes. As corollaries, several decision problems for these scheme classes are shown to have nondeterministic polynomially time-bounded algorithms.

Efficient algorithms are presented for several grammar problems relevant to compiler construction. These problems include(i) testing, for a reduced context-free grammar G and an LL(k), uniquely invertible, or BRC(m,n) grammar H, if G is structurally contained by H, and(ii) testing, for a reduced context-free grammar G and a structurally unambiguous grammar H, if G is Reynolds covered by H or if there is an on to homomorphisem from G to H.Related complexity results are presented for several problems for the regular grammars, program schemes, and monadic program schemes.

The problem of testing predicates for satisfiability arises in several aspects of database systems such as the use of predicate locks in concurrency control [7]. Such problems are NP-complete even for "simple predicates", i.e. predicates consisting of Boolean combinations of comparisons between a field of a tuple and a constant. However, when the relations referred to by the predicates are of fixed degree, there is an algorithm whose runtime is bounded by a polynomial in the length of the predicate. This is true not only for "simple predicates" but also for predicates containing comparisons between a field and another field, possibly offset by a constant. The proofs involve showing that if a predicate is satisfiable, then it is satisfiable by a tuple whose field values are related to constants occurring in the predicate.

Several methods are studied for dynamically creating a dump copy of a database while the database is on-line and being updated by user transactions. The methods can be characterized by whether the dump represents the database that existed at the beginning of the dump creation, at the end, or sometime in the middle. The methods are analyzed to understand the performance tradeoffs between alternate methods. The methods vary in the time required to create the dump and the amount of extra storage needed. A key parameter of a given system is shown to be the ratio of the rate at which database entities are copied into the dump to the rate at which database entities are updated. For certain methods to work, the ratio must exceed one. However, by combining two methods into a hybrid scheme, the ratio need only exceed one half.

Several sufficient conditions are presented for a regular set or context-free language problem to be as hard as testing for emptiness or testing for equivalence to the language $\{ 0,1\} ^ * $. These sufficient conditions provide a unified method for proving undecidability or complexity results and apply to a large number of language problems studied in the literature. Many new nonpolynomial lower complexity bounds and undecidability results follow easily. The techniques used to prove these sufficient conditions involve reducibilities utilizing simple and efficient encodings by homomorphisms.

An algorithm is presented for converting a deterministic pushdown automaton (dpda) of size n into an equivalent dpda that always halts. The dpda produced is of size $O(n)$. The algorithm operates in linear time on a random access machine (but may require the allocation of $O(n^2 )$ storage), and in time $O(n^2 )$ on a multi-tape Turing machine. Related results on polynomial time algorithms for dpda equivalence problems and for two-way pushdown automata language recognition problems are discussed.

Sufficient but general conditions on a family of formal languages ~ and a language L~ m ~ are given such that (l) "'= L0" is as hard as "= {0, 1}*" for,~', (2) "_~ Lo" is as hard as "= {0, 1}*" for if', and (3) "= L0" and "C_ Lo" are as hard as "= ~" lor ~: For many interesting families such as the regular sets and contextfree languages, a sufficient condmon for (1) is that Lo has an unbounded regular subset; a sufficient condinon for (2) is that Lo has an unbounded context-free subset, and a sufficient condition for (3) is that L0 has no unbounded regular subsets Numerous applications of these results to specific families of languages are hsted Many context-free languages are shown to contain unbounded regular subsets KEY WORDS AND PHRASES equivalence, containment, language, grammar, context-free CR CATEGORIES 5 22, 5 23, 5 25 IntroducttonFor a family of languages and a fixed language L0 m the family, a deoston problem of mterest is: Given a description of a language m the family, does that language equal L0 Two other related problems are: Does the language contain Lo, and is the language contained in Lo We abbrevtate the above three problems as "= L0," "_~ Lo," and "C L0," respectively.In this paper we show that for many interesting famdies of languages and fixed languages L0 in ~,~, "= L0'" ts as hard as "= {0, 1}*" or "= {0, 1} +'' for ~, whenever Lo has an unbounded regular subset.Slmdarly "~ L0" is as hard as "= {0, 1}*" or "= {0, 1}+, '' whenever L0 has an unbounded context-free subset.Finally "= Lo" and "_CL0" are as hard as "= ~" for if, whenever Lo has no unbounded regular subsets This ts true for famdles with deodable "= {0, 1}*" and "= Q" problems as well as families for which these problems are undecldable.To mvestlgate the complexity of these predicates for general classes of languages, we mtroduce the concept of an effective famdy of languages over {0, 1}.In Sections 2 and 3 we show that for all effectwe famdies of languages that are "efficiently" closed under several simple language operations these results hold, In Section 4 examples are gtven where these general results apply In

Several polynomial time algorithms finding “good,” but not necessarily optimal, tours for the traveling salesman problem are considered. We measure the closeness of a tour by the ratio of the obtained tour length to the minimal tour length. For the nearest neighbor method, we show the ratio is bounded above by a logarithmic function of the number of nodes. We also provide a logarithmic lower bound on the worst case. A class of approximation methods we call insertion methods are studied, and these are also shown to have a logarithmic upper bound. For two specific insertion methods, which we call nearest insertion and cheapest insertion, the ratio is shown to have a constant upper bound of 2, and examples are provided that come arbitrarily close to this upper bound. It is also shown that for any $n\geqq 8$, there are traveling salesman problems with n nodes having tours which cannot be improved by making $n/4$ edge changes, but for which the ratio is $2(1-1/n)$.

This paper presents a complexity theory of formal languages. The main technique used is that of embedding “={0,1}*”, “=0*”, and “=φ” into other linguistic predicates. In Section 2, the undecidability of “={0,1}*” for cfl's is exploited to provide sufficient conditions for the undecidability of predicates on the cfl's. In Section 3, the same techniques are applied to regular sets. Predicates satisfying conditions similar to those of Section 2 are shown to be hard, where how hard depends on the descriptors used to enumerate the regular sets. Section 4 concentrates on the equivalence and containment problems for cfl's. For cfl's, regular sets, and linear cfl's, the complexity of determining equivalence to a fixed language is linked to whether the fixed language is finite, infinite but bounded, or unbounded. In Section 5, the ability of cfg's to generate finite languages whose strings are exponential in the size of the grammar is used to obtain exponential lower bounds on several decidable problems for cfg's generating finite sets. In Section 6, all nontrivial predicates for certain specific classes of languages are shown to be hard. In Section 7, we show that a dpda can always be converted in polynomial time into an equivalent dpda that always halts. Therefore the predicate “={0,1}*” is in P for dpda's, and embedding this problem into other predicates on the dpda's will not yield nonpolynomial lower bounds. In Section 8, some of the preceding results are generalized to other families of languages.

Attributed translations are a means of specifying the input-output relation of a language processing device, such as for example the lexical or syntax box of a compiler. Considered as a mathematical object, an attributed translation is a mapping of certain strings of attributed “input symbols” into strings of attributed “action symbols”. Under the interpretation that action symbols represent the act of emitting an attributed output or the performing of some other “semantic actions”, and the attributes represent “semantic” information associated with the symbols, the model can be applied in depth to practical compiling problems. Theorems are proved giving conditions under which an attributed translation can be performed by an augmented pushdown machine while it is parsing top down or bottom up.

The class of context free grammars that can be deterministically parsed in a top down manner with a fixed amount of look-ahead is investigated. These grammars, called LL(k) grammars where k is the amount of look-ahead are first defined and a procedure is given for determining if a context free grammar is LL(k) for a given value of k. It is shown that e-rules can be eliminated from an LL(k) grammar, at the cost of increasing the value of k by one, and a description is given of a canonical pushdown machine for recognizing LL(k) languages. It is shown that for each value of k there are LL(k+l) languages that are not LL(k) languages. It is shown that the equivalence problem is decidable for LL(k) grammars. Additional properties are also given.

article Free Access Share on Programmed Grammars and Classes of Formal Languages Author: Daniel J. Rosenkrantz View Profile Authors Info & Claims Journal of the ACMVolume 16Issue 1pp 107–131https://doi.org/10.1145/321495.321504Published:01 January 1969Publication History 192citation797DownloadsMetricsTotal Citations192Total Downloads797Last 12 Months48Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The relationship between the set of productions of a context-free grammar and the corresponding set of defining equations is first pointed out. The closure operation on a matrix of strings is defined and this concept is used to formalize the solution to a set of linear equations. A procedure is then given for rewriting a context-free grammar in Greibach normal form, where the replacements string of each production begins with a terminal symbol. An additional procedure is given for rewriting the grammar so that each replacement string both begins and ends with a terminal symbol. Neither procedure requires the evaluation of regular begins and ends with a terminal symbol. Neither procedure requires the evaluation of regular expressions over the total vocabulary of the grammar, as is required by Greibach's procedure.

This paper presents a synthesis method of ternary digital systems by means of a threshold algebra. The method is based on the fact that the K operations of any ternary function can be expressed as threshold operations on a set of functions called midterms. Such midterms can be easily generated from the outputs of the ternary multivibrators described by the authors in a previous paper [4].