Decision problems for convex languages

We examine decision problems for various classes of convex languages, previously studied by Ang and Brzozowski, originally under the name “continuous languages”. We can decide whether a language L is prefix-, suffix-, factor-, or subword-convex in polynomial time if L is represented by a DFA, but these problems become PSPACE-complete if L is represented by an NFA. If a regular language is not convex, we find tight upper bounds on the length of the shortest words demonstrating this fact, in terms of the number of states of an accepting DFA. Similar results are proved for some subclasses of convex languages: the prefix-, suffix-, factor-, and subword-closed languages, and the prefix-, suffix-, factor-, and subword-free languages. Finally, we briefly examine these questions where L is represented by a context-free grammar.     

Leaf languages and string compression

Tight connections between leaf languages and strings compressed by straight-line programs (SLPs) are established. It is shown that the compressed membership problem for a language L is complete for the leaf language class defined by L via logspace machines. A more difficult variant of the compressed membership problem for L is shown to be complete for the leaf language class defined by L via polynomial time machines. As a corollary, it is shown that there exists a fixed linear visibly pushdown language for which the compressed membership problem is PSPACE-complete. For XML languages, it is shown that the compressed membership problem is coNP-complete.Furthermore it is shown that the embedding problem for SLP-compressed strings is hard for PP (probabilistic polynomial time).     

Constants and label-equivalence: A decision procedure for reflexive regular splicing languages

A structural characterization of reflexive splicing languages has been recently given in [P. Bonizzoni, C. De Felice, R. Zizza, The structure of reflexive regular splicing languages via Schützenberger constants, Theoretical Computer Science 334 (2005) 71-98] and [P. Bonizzoni, G. Mauri, Regular splicing languages and subclasses, Theoretical Computer Science 340 (2005) 349-363] showing surprising connections between long standing notions in formal language theory, the syntactic monoid and Schützenberger constant and the splicing operation.In this paper, we provide a procedure to decide whether a regular language is a reflexive splicing language, based on the above-mentioned characterization that is given in terms of a finite set of constants for the language. The procedure relies on the notion of label-equivalence that induces a finite refinement of the syntactic monoid of a regular language L. A finite set of representatives for label-equivalent classes of constant words in L is defined and it is proved that such a finite set provides the splice sites of splicing rules generating language L.     

Undecidable problems of decentralized observation and control on regular languages

We introduce a decentralized observation problem, where the system under observation is modeled as a regular language L over a finite alphabet Σ and n subsets of Σ model distributed observation points. A regular language K⊆L models a set of distinguished behaviors, say, correct behaviors of the system. The objective is to check the existence of a function which, given the n observations corresponding to a behavior ρ∈L, decides whether ρ is in K or not. We prove that checking the existence of such a function is undecidable. We then use this result to show undecidability of a decentralized supervisory control problem in the discrete event system framework.     

Algebraic properties of LA-languages

In this study, we introduce the concepts of L-valued regular substitution (LA-substitution), deterministic L-valued regular substitution (DLA-substitution), L-valued fuzzy homomorphism and its inverse images, homomorphism and its inverse images for a lattice-ordered monoid L. We also study the properties of LA-languages and DLA-languages under the above-mentioned algebraic operations. The algebraic characterization of the L-valued regular language is given.     

Compositional synthesis of asynchronous automata

Asynchronous automata are a model of communication processes with a control structure distributed on a set P of processes, global initializations and global accepting conditions. The well-known theorem of Zielonka states that they recognize exactly the class of regular Mazurkiewicz trace languages. The corresponding synthesis problem is, given a global specification A of any regular trace language L, to build an asynchronous automaton that recognizes L, automatically. Yet, all such existing constructions are quite involved and yield an explosion of the number of states in each process, which is exponential in both the sizes of A and P. In this paper, we introduce the particular case of distributed asynchronous automata, which require that the initializations and the accepting conditions are distributed as well. We present an original technique based on simple compositions/decompositions of these distributed asynchronous automata that results in the construction of smaller non-deterministic asynchronous automata: now, the number of states in each process is only polynomial in the size of A, but is still exponential in the size of P.     

On languages specified by relative acceptance

For any language A, the class NP(A) of languages accepted in polynomial time by nondeterministic oracle machines with A as oracle set is characterized in terms of the regular sets and the operations of homomorphic replication and intersection. A similar characterization is obtained for the class EXRUD(A) of languages that are extended rudimentary in A. Other classes which can be similarly characterized are described.     

A theoretical limit for safety verification techniques with regular fix-point computations

In computer aided verification, the reachability problem is particularly relevant for safety analyses. Given a regular tree language L, a term t and a relation R, the reachability problem consists in deciding whether there exist a positive integer n and terms t₀,t₁,…,tn such that t₀∈L, tn=t and for every 0?i<n, (ti,ti+1)∈R. In this case, the term t is said to be reachable, otherwise it is said unreachable. This problem is decidable for particular kinds of relations, but it is known to be undecidable in general, even if L is finite. Several approaches to tackle the unreachability problem are based on the computation of an R-closed regular language containing L. In this paper we show a theoretical limit to this kind of approaches for this problem.     

A characterization of (regular) circular languages generated by monotone complete splicing systems

Circular splicing systems are a formal model of a generative mechanism of circular words, inspired by a recombinant behaviour of circular DNA. Some unanswered questions are related to the computational power of such systems, and finding a characterization of the class of circular languages generated by circular splicing systems is still an open problem. In this paper we solve this problem for monotone complete systems, which are finite circular splicing systems with rules of a simpler form. We show that a circular language L is generated by a monotone complete system if and only if the set Lin(L) of all words corresponding to L is a pure unitary language generated by a set closed under the conjugacy relation. The class of pure unitary languages was introduced by A. Ehrenfeucht, D. Haussler, G. Rozenberg in 1983, as a subclass of the class of context-free languages, together with a characterization of regular pure unitary languages by means of a decidable property. As a direct consequence, we characterize (regular) circular languages generated by monotone complete systems. We can also decide whether the language generated by a monotone complete system is regular. Finally, we point out that monotone complete systems have the same computational power as finite simple systems, an easy type of circular splicing system defined in the literature from the very beginning, when only one rule of a specific type is allowed. From our results on monotone complete systems, it follows that finite simple systems generate a class of languages containing non-regular languages, showing the incorrectness of a longstanding result on simple systems.     

Minimax regret p-center location on a network with demand uncertainty

We consider the weighted p-center problem on a transportation network with uncertain weights of nodes. Specifically, for each node, an interval estimate of its weight is known. The objective is to find the ‘minimax regret’ solution i.e. to minimize the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. We discuss properties of the problem and show that the problem can be solved by means of solving (n + 1) regular weighted p-center problems. This leads to polynomial algorithms for the cases where the regular weighted p-center problem can be solved in polynomial time, e.g. for the case of a tree network, and for the case of a general network with p = 1.     

Robust optimal control of regular languages

This paper presents an algorithm for robust optimal control of regular languages under specified uncertainty bounds on the event cost parameters of the language measure that has been recently reported in literature. The performance index for the proposed robust optimal policy is obtained by combining the measure of the supervised plant language with uncertainty. The performance of a controller is represented by the language measure of the supervised plant and is minimized over the given range of event cost uncertainties. Synthesis of the robust optimal supervisory control policy requires at most n iterations, where n is the number of states of the deterministic finite-state automaton (DFSA) model, generated from the regular language of the unsupervised plant behavior. The computational complexity of the control synthesis method is polynomial in n.     

Inverse star, borders, and palstars

A language L is closed if L=L^?. We consider an operation on closed languages, L−?, that is an inverse to Kleene closure. It is known that if L is closed and regular, then L−? is also regular. We show that the analogous result fails to hold for the context-free languages. Along the way we find a new relationship between the unbordered words and the prime palstars of Knuth, Morris, and Pratt. We use this relationship to enumerate the prime palstars, and we prove that neither the language of all unbordered words nor the language of all prime palstars is context-free.     

The copying power of one-state tree transducers

One-state deterministic top-down tree transducers (or, tree homomorphisms) cannot handle “prime copying,” i.e., their class of output (string) languages is not closed under the operation L → {$(w$)^f(n) ∥ w?L, f(n) ? 1}, where f is any integer function whose range contains numbers with arbitrarily large prime factors (such as a polynomial). The exact amount of nonclosure under these copying operations is established for several classes of input (tree) languages. These results are relevant to the extended definable (or, restricted parallel level) languages, to the syntax-directed translation of context-free languages, and to the tree transducer hierarchy.     

2DST mappings on languages and related problems

Let $\text{l}$ be a family of languages effectively closed under inverse homomorphism and intersection with regular sets and such that the languages have effectively constructible semilinear Parikh maps. We show that there is an algorithm to decide given a language L in $\text{L}$ and a language R accepted by a one-way nondeterministic multicounter machine, where each counter makes exactly one reversal, whether L∩R is empty. This result has many applications. In particular, it can be used to show that there is an algorithm to decide given a language L in $\text{L}$ and two-way deterministic sequential transducers (2DST's) S₁ and S₂ whether S₁ and S₂ are equivalent on L.     

Application of formal languages in polynomial transformations of instances between NP-complete problems

We propose the usage of formal languages for expressing instances of NP-complete problems for their application in polynomial transformations. The proposed approach, which consists of using formal language theory for polynomial transformations, is more robust, more practical, and faster to apply to real problems than the theory of polynomial transformations. In this paper we propose a methodology for transforming instances between NP-complete problems, which differs from Garey and Johnson’s. Unlike most transformations which are used for proving that a problem is NP-complete based on the NP-completeness of another problem, the proposed approach is intended for extrapolating some known characteristics, phenomena, or behaviors from a problem A to another problem B. This extrapolation could be useful for predicting the performance of an algorithm for solving B based on its known performance for problem A, or for taking an algorithm that solves A and adapting it to solve B.     

Regular autodense languages

A regular component is either autodense or anti-autodense. Characterizations of a regular component being a pure autodense language and being a pure autodense code are obtained. A relationship between intercodes and anti-autodense languages is that for an intercode L of index m, L ⁿ is an anti-autodense language for every n > m.     

Subtractive reductions and complete problems for counting complexity classes

We introduce and investigate a new type of reductions between counting problems, which we call subtractive reductions. We show that the main counting complexity classes #P, #NP, as well as all higher counting complexity classes $\#·{\Pi }_k\mathrm{P},k⩾2$, are closed under subtractive reductions. We then pursue problems that are complete for these classes via subtractive reductions. We focus on the class #NP (which is the same as the class $\#·\mathrm{coNP}$) and show that it contains natural complete problems via subtractive reductions, such as the problem of counting the minimal models of a Boolean formula in conjunctive normal form and the problem of counting the cardinality of the set of minimal solutions of a homogeneous system of linear Diophantine inequalities.     

Succinct Representation, Leaf Languages, and Projection Reductions

In this article, the following results are shown: 1. For succinctly encoded problemss(A), completeness under polynomial time reductions is equivalent to completeness under projection reductions, an extremely weak reduction defined by a quantifier-free projective formula. 2. The succinct versions(Aof a computational problemAis complete under projection reductions for the class of problems characterizable with leaf languageA, but not complete undermonotoneprojections. 3. A strong conversion lemma: IfAis reducible toBin polylogarithmic time, then the succinct version ofAis monotone projection reducible to the succinct version ofB. This result strengthens previous results by Papadimitriou and Yannakakis, and Balcázar and Lozano. It allows iterated application for multiple succinct problems. 4. For all syntactic complexity classes there exist complete problems undermonotoneprojection reductions. This positively answers a question by Stewart for a large number of complexity classes.     

On log-tape isomorphisms of complete sets

In this paper we study log n-tape computable reductions between sets and investigate conditions under which log n-tape reductions between sets can be extended to log n-tape computable isomorphisms of these sets. As an application of these results we obtain easy to check necessary and sufficient conditions that sets complete under log n-tape reductions in NL, CSL, P, NP, PTAPE, etc. are log n-tape isomorphic to the previously known complete sets in the respective classes. As a matter of fact, all the “known” complete sets for NL, CSL, P, NP, PTAPE, etc. are now easily seen to be, respectively, log n-tape isomorphic. These results strengthen and extend substantially the previously known results about polynomial time computable reductions and isomorphisms of NP and PTAPE complete sets. Furthermore, we show that any set complete in CSL, PTAPE, etc. must be dense and therefore, for example, cannot be over a single letter alphabet.     

Subcomplete generalizations of graph isomorphism

We present eight group-theoretic problems in NP one of which is a reformulation of graph isomorphism. We give technical evidence that none of the problems is NP-complete, and give polynomial time reductions among the problems. There is a good possibility that seven of these problems are harder than graph isomorphism (relative to polynomial time reduction), so that they might be examples of natural problems of intermediate difficulty, situated properly between the class of NP-complete problems and the class P of problems decidable in deterministic polynomial time. Because of strong structural similarity, two of the apparently harder problems can be interpreted as generalized isomorphism and generalized automorphism, respectively. Whether these problems ultimately prove to be harder than graph isomorphism seems to depend, in part, on the open problem whether every permutation group of degree n arises as the automorphism group of a combinatorial structure of size polynomial in n. Finally, we give an O(n² · k) algorithm for constructing the centralizer of a permutation group of degree n presented by a generating set of k permutations. Note that we may assume that k is O(n · log n), without loss of generality. This problem is a special case of one of the harder group-theoretic problems. From the method of constructing the centralizer, we recover results about the group-theoretic structure of the centralizer. Furthermore, applying our algorithm for intersecting with a normalizing permutation group, we show how to find the center of a permutation group of degree n in O(n⁶) steps, having constructed the centralizer of the group first.