Abstract A pumping lemma for a class of languages $$\varvec{\mathcal {C}}$$ C is often used to show particular languages are not in $$\varvec{\mathcal {C}}$$ C . In contrast, we show that a pumping lemma for a class of languages $$\varvec{\mathcal {C}}$$ C can be used to study the computational complexity of the predicate “ $$\in \varvec{\mathcal {C}}$$ ∈ C ” via highly efficient many-one reductions. In this paper, we use extended regular expressions (EXREGs, introduced in Câmpeanu et al. (Int. J. Foundations Comput. Sci. 14(6), 1007–1018, 2003)) as an example to illustrate the proof technique and establish the complexity of the predicate “is an EXREG language” for several classes of languages. Due to the efficiency of the reductions, both productiveness (a stronger form of non-recursive enumerability) and complexity results can be obtained simultaneously. For example, we show that the predicate “is an EXREG language” is productive (hence, not recursively enumerable) for context-free grammars, and is Co-NEXPTIME-hard for context-free grammars generating bounded languages. The proof technique is easy to use and requires only a few conditions. This suggests that for any class of languages $$\varvec{\mathcal {C}}$$ C having a pumping lemma, the language class comparison problems (e.g., does a given context-free grammar generate a language in $$\varvec{\mathcal {C}}$$ C ?) are almost guaranteed to be hard. So, pumping lemmas sometimes could be “harmful” when studying computational complexity results.

Abstract In Freydenberger (Theory Comput Syst 53(2):159–193, 2013. https://doi.org/10.1007/s00224-012-9389-0 ), Freydenberger shows that the set of invalid computations of an extended Turing machine can be recognized by a synchronized regular expression [as defined in Della Penna et al. (Acta Informatica 39(1):31–70, 2003. https://doi.org/10.1007/s00236-002-0099-y )]. Therefore, the widely discussed predicate “ $$=\{0,1\}^*$$ = { 0 , 1 } ∗ ” is not recursively enumerable for synchronized regular expressions (SRE). In this paper, we employ a stronger form of non-recursive enumerability called productiveness and show that the set of invalid computations of a deterministic Turing machine on a single input can be recognized by a synchronized regular expression. Hence, for a polynomial-time decidable subset of SRE, where each expression generates either $$\{0, 1\}^*$$ { 0 , 1 } ∗ or $$\{0, 1\}^* -\{w\}$$ { 0 , 1 } ∗ - { w } where $$w \in \{0, 1\}^*$$ w ∈ { 0 , 1 } ∗ , the predicate “ $$=\{0,1\}^*$$ = { 0 , 1 } ∗ ” is productive. This result can be easily applied to other classes of language descriptors due to the simplicity of the construction in its proof. This result also implies that many computational problems, especially promise problems, for SRE are productive. These problems include language class comparison problems (e.g., does a given synchronized regular expression generate a context-free language?), and equivalence and containment problems of several types (e.g., does a given synchronized regular expression generate a language equal to a fixed unbounded regular set?). In addition, we study the descriptional complexity of SRE. A generalized method for studying trade-offs between SRE and many classes of language descriptors is established.

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.

We demonstrate how the concepts of algebraic representability and strongly-local reductions developed here and in [20] can be used to characterize the computational complexity/efficient approximability of a number of basic problems and their variants, on various abstract algebraic structures F. These problems include the following:

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).

We prove the #P-hardness of the counting problems associated with various satisfiability, graph, and combinatorial problems, when restricted to planar instances. These problems include 3Sat, 1-3Sat, 1-Ex3Sat, Minimum Vertex Cover, Minimum Dominating Set, Minimum Feedback Vertex Set, X3C, Partition Into Triangles, and Clique Cover. We also prove the NP-completeness of the Ambiguous Satisfiability} problems [J. B. Saxe, Two Papers on Graph Embedding Problems, Tech. Report CMU-CS-80-102, Dept. of Computer Science, Carnegie Mellon Univ., Pittsburgh, PA, 1980] and the D P -completeness (with respect to random polynomial reducibility) of the unique satisfiability problems [L. G. Valiant and V. V. Vazirani, NP is as easy as detecting unique solutions, in Proc. 17th ACM Symp. on Theory of Computing, 1985, pp. 458--463] associated with several of the above problems, when restricted to planar instances. Previously, very few #P}-hardness results, no {\sf NP}-hardness results, and no D P -completeness results were known for counting problems, ambiguous satisfiability problems, and unique satisfiability problems, respectively, when restricted to planar instances. Assuming {\sf P \neq $ NP}, one corollary of the above results is that there are no $\epsilon$-approximation algorithms for the problems of maximizing or minimizing a linear objective function subject to a planar system of linear inequality constraints over the integers.

We study the efficient approximability of basic graph and logic problems in the literature when instances are specified hierarchically as in [T. Lengauer, J. Assoc. Comput. Mach., 36(1989), pp. 474--509] or are specified by one-dimensional finite narrow periodic specifications as in [E. Wanke, Paths and cycles in finite periodic graphs, in Lecture Notes in Comp. Sci. 711, Springer-Verlag, New York, 1993, pp. 751--760]. We show that, for most of the problems $\Pi$ considered when specified using k-level-restricted hierarchical specifications or k-narrow periodic specifications, the following hold. Let $\rho$ be any performance guarantee of a polynomial time approximation algorithm for $\Pi$, when instances are specified using standard specifications. Then $\forall \epsilon > 0$, $ \Pi$ has a polynomial time approximation algorithm with performance guarantee $(1 + \epsilon) \rho$. $\Pi$ has a polynomial time approximation scheme when restricted to planar instances. These are the first polynomial time approximation schemes for PSPACE-hard hierarchically or periodically specified problems. Since several of the problems considered are PSPACE-hard, our results provide the first examples of natural PSPACE-hard optimization problems that have polynomial time approximation schemes. This answers an open question in Condon et al. [Chicago J. Theoret. Comput. Sci., 1995, Article 4].

No abstract available.

A new algebraic model, called the generalized satisfiability problem (GSP) model, is introduced for representing and solving combinatorial problems. The GSP model is an alternative to the common method in the literature of representing such problems as language-recognition problems. In the GSP model, a problem instance is represented by a set of variables together with a set of terms, and the computational objective is to find a certain sum of products of terms over a commutative semiring. The model is general enough to express all the standard problems about sets of clauses and generalized clauses, all nonserial optimization problems, and all $\{ 0,1\} $-linear programming problems. The model can also describe many graph problems, often in a very direct structure-preserving way. Two important properties of the model are the following;1. In the GSP model, one can naturally discuss the structure of individual problem instances. The structure of a GSP instance is displayed in a “structure tree.” The smaller the “weighted depth” or “channelwidth” of the structure tree for a GSP instance, the faster the instance can be solved by any one of several generic algorithms. 2. The GSP model extends easily so as to apply to hierarchically specified problems and enables solutions to instances of such problems to be found directly from the specification rather than from the (often exponentially) larger specified object.

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.

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.

The concepts of $\textbf{SAT}$-hardness and $\textbf{SAT}$-completeness modulo npolylogn time and linear size reducibility, denoted by $\textbf{SAT}$-hard (npolylogn, n) and $\textbf{SAT}$-complete (npolylogn, n), respectively, are introduced. Regardless of whether $\textbf{P} = \textbf{NP}$ or $\textbf{P} \neq \textbf{NP}$, it is shown that intuitively Each $\textbf{SAT}$-hard (npolylogn, n) problem requires essentially at least as much deterministic time as, and Each $\textbf{SAT}$-complete (npolylogn, n) problem requires essentially the same deterministic time as the satisfiability problem for 3CNF formulas. It is proved that the $\leqq$, satisfiability, tautology, unique satisfiability, equivalence, and minimization problems are already $\textbf{SAT}$-complete (npolylogn, n), for very simple Boolean formulas and for very simple systems of Boolean equations. These completeness results are used to characterize the deterministic time complexities of a number of problems for lattices, propositional calculi, combinatorial circuits, finite fields, rings ${\bf Z}_{k}(k \geqq 2)$, binary decision diagrams, and monadic single variable program schemes. A number of these hardness results are “best” possible.

Algorithms for the following two problems are presented: (1) computing detection probability of stuck-at faults (CDP), and (2) computing signal probability (CSP). These problems arise in the context of random testing, pseudorandom testing, and testability analysis of combinational circuits. The algorithm for CDP combines the notion of supergates and a refinement of th algorithm for CDP presented in the work of S. Chakravarty and H.B. Hunt, III (1986). The algorithm for CDP can be used to compute the exact value of detection probability of multiple stuck-at faults in circuits with multiple outputs. Single-input, single-output pseudo gates are inserted to model stuck-at faults and derive an equivalent single-output circuit. CDP is thus reduced to the problem of computing the probability distribution of the output over the set of four logic values (0, 1d, d). The algorithm for CDP uses an efficient enumeration algorithm. The authors show how the enumeration algorithm can be used to refine the algorithm for CSP.>

The problem of detecting sneak paths in transistor networks arises in the minimization of transistor networks. It is shown that the problem of detecting consistent sneak paths in very simple transistor networks is co-NP-complete.>

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 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 general ${\textbf{NP}}$- or ${\textbf{coNP}}$-hardness results are presented for nonlinear algebraic and optimization problems on rings. These results include the following: (1) The problem of determining if a system of nonlinear equations on a ring has a solution is ${\textbf{NP}}$-hard for virtually all of the rings studied in mathematics or computer science. (2) Let S be any nondegenerate ring with a multiplicative identity, and let $ \leqq $ be any linear order on S. Then, the problems of maximizing or of minimizing a linear function on S subject to quadratic constraints are both ${\textbf{NP}}$- and ${\textbf{coNP}}$-hard. (3) Let S be any ordered ring, and let be the associated order. Then, the problems of maximizing or of minimizing a quadratic multiple variable polynomial on S subject to constraints of the form $a \leqq x \leqq b$ are both ${\textbf{NP}}$- and ${\textbf{coNP}}$-hard. Several additional related nonlinear problems for such rings are shown to be ${\textbf{NP}}$-, ${\textbf{coNP}}$-, or #${\textbf{P}}$-hard. In particular, the following variant of Hilbert’s Tenth Problem is shown to be ${\textbf{NP}}$-complete: (4) The problem of determining, for a quadratic multiple variable polynomial f with integer coefficients over the reals, if there is an assignment v of values from $\{ 0,1\} $ to the variables of f such that f takes on the value 0 under v.

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 known proofs that the equivalence and containment problems for regular expressions, regular grammars and nondeterministic finite automata are PSPACE-complete [SM] depend upon consideration of highly unambiguous expressions, grammars and automata. Here, we prove that such dependence is inherent. Deterministic polynomial-time algorithms are presented for the equivalence and containment problems for unambiguous regular expressions, unambiguous regular grammars and unambiguous finite automata. The algorithms are then extended to ambiguity bounded by a fixed k. Our algorithms depend upon several elementary observations on the solutions of systems of homogeneous linear difference equations with constant coefficients and their relationship with the number of derivations of strings of a given length n by a regular grammar.

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.

Three natural decision problems are presented: one for correspondence problems and linear context-free grammars, one for arbitrary context-free grammars, and one for program schemes.Each of these three decismn problems, although decidable, is shown to be of nonrecursive complexity.The complexities of these three decision problems are shown to easdy imply nonrecursive lower bounds on the complexities of wide classes of decision problems for their respective structures.As corollaries, a number of new nonrecursive lower complexity bounds, undecidabdRy results, and relative economy of descnptmn results are obtained for these structures.In addition, several decidable decision problems and effective procedures in the literature are shown to be of nonrecursive complexity.

Umform NP-hard and PSPACE-hard lower bounds are presented for problems for various classes of flowchart and loop program schemes and programming languages These lower bounds hold for the isomorphism, strong equivalence, containment, weak equivalence, totality, divergence, and executabthty problems.These lower bounds hold for any reasonably nontrivial flowchart and loop programming language.

AaSaat^CT The decidability of context-free grammar and language problems in general, especially problems about separabthty and context, grammar and language class membership, and grammatical similarity relauons, is studied.The results are based upon efficient reductions of membership problems for always-halting Turmg machines and the following fundamental property of s-grammars and s-languages:The emptiness-of-intersection problem for pa,rs of s-grammars that generate languages without arbitrarily long common prefixes is decidable but ~s not recorsively time-bounded.

The known proofs that the equivalence and containment problems for the regular and for the linear context-free grammars are PSPACE-complete and undecidable, respecitvely, depend upon consideration of ambiguous grammars. We prove that this dependence is inherent. Deterministic polynomial time algorithms are presented for; (1) the equivalence and containment problems for the unambiguous regular grammars; (2) for all k ≥ 2, the equivalence and containment problems for the regular grammars of degree of ambiguity ≤ k; and (3) the problems of determining if an unambiguous linear context-free grammar is equivalent to or contains an arbitrary regular set. Simple extensions of the grammar classes in (1), (2), and (3) are shown to yield problems that are NP-hard or undecidable. Several new results on the relative economy of description of ambiguous versus unambiguous regular and linear contextfree grammars are also obtained. These results depend upon several observations on the solutions of systems of homogeneous linear difference equations and their relationship with the number of strings of a given length generated by an unambiguous regular or linear context-free grammar.

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 computatiional complexity of several decidable problems about program schemes, recursion schemes, and simple programming languages is considered. The strong equivalence, weak equivalence, containment, halting, and divergence problems for the single variable program schemes and the linear monadic recursion schemes are shown to be $NP$-complete. The equivalence problem for the Loop 1 programming language is also shown to be $NP$-complete. Sufficient conditions for a program scheme problem to be $NP$-hard are presented. The strong equivalence problem for a subset of the single variable program schemes, the strongly free schemes, is shown to be decidable deterministically in polynomial time.

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.

AESTRA~ r Many parsing techniques are parameterlzed by the amount of context allowed in making parsmg decisions (e g the LR(k), LL(k), and SLR(k) hierarchies).The best-known algorithms for testing membership in these classes depend exponentially on k when the test is performed determinlsttcally, and polynomlally on k when the test IS done nondetermmistically This paper shows that the deterministic complexity of any uniform algorithm for, say, LR(k) testing is a polynommi function of k if and only if P = NP.We then provide a lower bound on the growth rate with respect to k As to the relationships between the various classes, it is shown that the time needed for testing the LL(k) property ~s a lower bound on the time needed for testing membership in any subset of the LR(k) grammars that includes all the LL(k) grammars These results suggest that the complexity of LL(I) testing is a lower bound on the complexity of testing membership m most useful classes of grammars Finally, some relative decision problems are mvesUgated, that is, problems of testing whether a given member of some class is also a member of some other specified class A polynomial time algorithm ts given for determining for an LR(k) grammar whether there exists a k' for which the grammar is LL(k').Slmdar results are shown for the SLR(k) and strong LL(k) hierarchies KEY WORDS AND eHRAS~S: computational complexity, lower bounds, context-free grammars, LR(k) and LL(k) parsing

No abstract available.

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

The close relationship between programming language syntax, context-free grammars (abbreviated cfgs), parsing, and compiling is well-known and is extensively discussed in [1]. Unfortunately, many of the problems about programming languages, one might wish to solve, are equivalent to undecidable grammar problems. Two especially important such problems are

We present several techniques for proving lower bounds that can be applied to problems about grammars, formal languages, program schemes, simple programming languages, and automata. These techniques include dichotomization, extensions of dichotomization to certain classes of relational problems, recursive analogues of the Post Correspondence Problem, and the reachability problem. These techniques provide many new lower bounds and provide a unified framework for viewing much of the work on the complexity of problems about grammars, languages, schemes, and automata. We show how to prove the undecidability of a problem by efficiently reducing the membership problem for Tms that always halt to it. We also introduce the forbidden subgraph problem.

It is shown that there is a sequence of languages E1, E2,... such that every correct prefix parser (one which detects errors at the earliest possible moment, e.g., LR or LL parsers) for En has size 2cn, yet a deterministic PDA recognizing En exists and has size O(n2). There is another easily described sequence of languages N1,N2,... for which Nn has a nondeterministic PDA of size O(n2) but no deterministic PDA of size less than 2cn. It is shown moreover, that this latter exponential gap can be made arbitrarily large for different sequences of languages.

In this paper we derive upper bounds on the complexity of LR(k) testing both when k is considered to be a fixed integer and also when k is considered to be a parameter of the problem. In the latter case, we show that the lower bounds on the running time of such algorithms depend very strongly on the representation chosen for k. Thus LR(k) testing is NP-complete when k is expressed in unary and complete for nondeterministic exponential time when k is expressed in binary.These results carry over to many other parameterized classes of grammars, such as the LL(k), strong LL(k), SLR(k), LC(k), strong LC(k), BRC(l,k), BC(l,k) and extended precedence (l,k) grammars.

In [1] and [2] a complexity theory for formal languages and automata was developed. This theory implies most of the previously known results and yields many new results as well. Here we develop an analogous theory for several classes of more practically motivated problems. Two such classes, both closely related to formal language and automata theory, suggest themselves - grammar problems and program scheme problems. Here, our primary emphasis is on grammar problems of interest in parsing and compiling. Other problems considered include -

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.

We investigate the following: