Completions in measure of languages and related combinatorial problems

We consider measures of languages induced by Bernoulli distributions on the letters of a given alphabet. Of particular interest are languages having a measure equal to 1 with respect to all positive Bernoulli distributions (Bernoulli sets). The main object of the paper is to study conditions ensuring that a given language has a finite Bernoulli completion, i.e., it is included in a finite Bernoulli set. Some characterizations of languages having finite Bernoulli completions are given. In the case of a two-letter alphabet it is shown that one can decide whether a finite language has a finite Bernoulli completion or not. Moreover, any finite code over a two-letter alphabet has a finite Bernoulli completion. Finally, we prove that two finite languages have the same measure with respect to all Bernoulli distributions if and only if each of the two languages can be obtained from the other by using a finite number of times three suitable measure-invariant transformations.     

Some results on the generalized star-height problem

We prove some results related to the generalized star-height problem. In this problem, as opposed to the restricted star-height problem, complementation is considered as a basic operator. We first show that the class of languages of star-height ≤ n is closed under certain operations (left and right quotients, inverse alphabetic morphisms, injective star-free substitutions). It is known that languages recognized by a commutative group are of star-height 1. We extend this result to nilpotent groups of class 2 and to the groups that divide a semidirect product of a commutative group by ( /2 )ⁿ. In the same direction, we show that one of the languages that were conjectured to be of star-height 2 during the past ten years is in fact of star-height 1. Next we show that if a rational language L is recognized by a monoid of the variety generated by wreath products of the form M (G N), where M and N are aperiodic monoids, and G is a commutative group, the L is of star-height ≤ 1. Finally we show that every rational language is the inverse image, under some morphism between free monoids, of a language of (resticted) star-height 1.     

Two-way automata and length-preserving homomorphisms

Closure underlength-preserving homomorphisms is interesting because of its similarity tonondeterminism. We give a characterization of NP in terms of length-preserving homomorphisms and present related complexity results. However, we mostly study the case of two-way finite automata: Let l.p.hom[n state 2DFA] denote the class of languages that are length-preserving homomorphic images of languages recognized byn-state 2DFAs. We give a machine characterization of this class. We show that any language accepted by ann-state two-wayalternating finite automaton (2AFA), or by a l-pebble 2NFA, belongs to l.p.hom[O(n ²) state 2DFA]. Moreover, there are languages in l.p.hom[n state 2DFA] whose smallest accepting 2NFA has at leastc ⁿ states (for some constantc > 1). So for two-way finite automata, the closure under length-preserving homomorphisms is much more powerful than nondeterminism. We disprove two conjectures (of Meyer and Fischer, and of Chrobak) about the state-complexity of unary languages. Finally, we show that the equivalence problems for 2AFAs (resp. 1-pebble 2NFAs) are in PSPACE, and that the equivalence problem for 1-pebble 2AFAs is in ExpSPACE (thus answering a question of Jiang and Ravikumar); it was known that these problems are hard in these two classes. We also give a new proof that alternating 1-pebble machines recognize only regular languages (which was first proved by Goralčíket al.). This research was supported in part by N.S.F. Grant DMS 8702019.     

Bi-catenation and shuffle product of languages

The shuffle product of two words consists of all words obtained by inserting one word into another word sparsely. The shuffle product of two languages is the union of all the shuffle products of two words taken one from each of these two languages. The bi-catenation of two languages A andB is the set . A non-empty word which is not a power of any other word is called a primitive word. A language is a prefix code if no word in this language is a prefix of any other word in this language. This paper is devoted to the investigation of the elementary properties of bi-catenation and shuffle product of languages. The families of prefix codes, disjunctive languages and languages consisting of primitive words with respective to these two operations are studied. We characterize languages of which the bi-catenation or the shuffle product with any non-empty word are prefix codes. We also derive that for any bifix code A, both and , , are disjunctive languages, where Q is the set of all primitive words over an alphabet X with more than one letter and . For the shuffle product case, surprisingly is a regular language, where a is a letter of the alphabet X. Received: 22 September 1997 / 7 January 1998     

Distance automata having large finite distance or finite ambiguity

A distance automaton is a (nondeterministic finite) automaton which is equipped with a nonnegative cost function on its transitions. The distance of a word recognized by such a machine quantifies the expenses associated with the recognition of this word. The distance of a distance automaton is the maximal distance of a word recognized by this machine or is infinite, depending on whether or not a maximum exists. We present distance automata havingn states and distance 2 ⁿ – 2. As a by-product we obtain regular languages having exponential finite order. Given a finitely ambiguous distance automaton withn states, we show that either its distance is at most 3 ⁿ – 1, or the growth of the distance in this machine is linear in the input length. The infinite distance problem for these distance automata is NP-hard and solvable in polynomial space. The infinite-order problem for regular languages is PSPACE-complete.A preliminary version of this article appeared in theProceedings of the 15th Symposium on Mathematical Foundations of Computer Science, 1990.     

Schützenberger and Eilenberg theorems for words on linear orderings

This paper contains extensions to words on countable scattered linear orderings of two well-known results of characterization of languages of finite words. We first extend a theorem of Schützenberger establishing that the star-free sets of finite words are exactly the languages recognized by finite aperiodic semigroups. This gives an algebraic characterization of star-free sets of words over countable scattered linear orderings. Contrarily to the case of finite words, first-order definable languages are strictly included into the star-free languages when countable scattered linear orderings are considered. Second, we extend the variety theorem of Eilenberg for finite words: there is a one-to-one correspondence between varieties of languages of words on countable scattered linear orderings and pseudo-varieties of algebras. The star-free sets are an example of such a variety of languages.     

Polynomial closure and unambiguous product

This article is a contribution to the algebraic theory of automata, but it also contains an application to Büchi’s sequential calculus. The polynomial closure of a class of languagesC is the set of languages that are finite unions of languages of the formL ₀ a ₁ L ₁ ···a _nL_n, where thea _i’s are letters and theL _i’s are elements ofC. Our main result is an algebraic characterization, via the syntactic monoid, of the polynomial closure of a variety of languages. We show that the algebraic operation corresponding to the polynomial closure is a certain Mal’cev product of varieties. This result has several consequences. We first study the concatenation hierarchies similar to the dot-depth hierarchy, obtained by counting the number of alternations between boolean operations and concatenation. For instance, we show that level 3/2 of the Straubing hierarchy is decidable and we give a simplified proof of the partial result of Cowan on level 2. We propose a general conjecture for these hierarchies. We also show that if a language and its complement are in the polynomial closure of a variety of languages, then this language can be written as a disjoint union of marked unambiguous products of languages of the variety. This allows us to extend the results of Thomas on quantifier hierarchies of first-order logic.     

The Compatibility of Binary Characters on Phylogenetic Networks: Complexity and Parameterized Algorithms

In a recent article, Nakhleh, Ringe and Warnow introduced perfect phylogenetic networks—a model of language evolution where languages do not evolve via clean speciation—and formulated a set of problems for their accurate reconstruction. Their new methodology assumes networks, rather than trees, as the correct model to capture the evolutionary history of natural languages. They proved the NP-hardness of the problem of testing whether a network is a perfect phylogenetic one for characters exhibiting at least three states, leaving open the case of binary characters, and gave a straightforward brute-force parameterized algorithm for the problem of running time O(3 ^k n), where k is the number of bidirectional edges in the network and n is its size. In this paper, we first establish the NP-hardness of the binary case of the problem. Then we provide a more efficient parameterized algorithm for this case running in time O(2 ^k n ²). The presented algorithm is very simple, and utilizes some structural results and elegant operations developed in this paper that can be useful on their own in the design of heuristic algorithms for the problem. The analysis phase of the algorithm is very elegant using amortized techniques to show that the upper bound on the running time of the algorithm is much tighter than the upper bound obtained under a conservative worst-case scenario assumption. Our results bear significant impact on reconstructing evolutionary histories of languages—particularly from phonological and morphological character data, most of which exhibit at most two states (i.e., are binary), as well as on the design and analysis of parameterized algorithms. Research of I.A. Kanj was supported in part by DePaul University Competitive Research Grant.     

On the Hopcroft’s minimization technique for DFA and DFCA

We show that the absolute worst case time complexity for Hopcroft’s minimization algorithm applied to unary languages is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. A previous paper by Berstel and Carton gave the example of de Bruijn words as a language that requires $O(nlogn)$ steps in the case of deterministic automata by carefully choosing the splitting sets and processing these sets in a FIFO mode for the list of the splitting sets in the algorithm. We refine the previous result by showing that the Berstel/Carton example is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. We show that the same result is valid also for the case of cover automata and an algorithm based on the Hopcroft’s method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list will not achieve the same absolute worst time complexity for the case of unary languages both in the case of regular deterministic finite automata or in the case of the deterministic finite cover automata as defined by S. Yu.     

Space Complexity Vs. Query Complexity

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far” from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity s(n) ≤ log n there is a language with space complexity O(s(n)) and query complexity 2^Ω(s(n)). Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space o(log log n) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space O(log n) that are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space O(log log n) that is not testable with a constant number of queries. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines.      

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.     

Characterizing sets of jobs that admit optimal greedy-like algorithms

The “Priority Algorithm” is a model of computation introduced by Borodin, Nielsen and Rackoff ((Incremental) Priority algorithms, Algorithmica 37(4):295–326, 2003) which formulates a wide class of greedy algorithms. For an arbitrary set \mathbbS\mathbb{S} of jobs, we are interested in whether or not there exists a priority algorithm that gains optimal profit on every subset of \mathbbS\mathbb{S} . In the case where the jobs are all intervals, we characterize such sets \mathbbS\mathbb{S} and give an efficient algorithm (when \mathbbS\mathbb{S} is finite) for determining this. We show that in general, however, the problem is NP-hard.     

Communication complexity of matrix computation over finite fields

We investigate the communication complexity of singularity testing in a finite field, where the problem is to determine whether a given square matrixM is singular. We show that, forn×n matrices whose entries are elements of a finite field of sizep, the communication complexity of this problem is (n ² logp). Our results imply tight bounds for several other problems likedetermining the rank andcomputing the determinant.This research was supported in part by NSF Grant CCR-8805978 and AFOSR Grant 87-0-400.     

On iterated hairpin completion

(Bounded) hairpin completion and its iterated versions are operations on formal languages which have been inspired by hairpin formation in DNA biochemistry. The paper answers two questions asked in the literature about iterated hairpin completion.The first question is whether the class of regular languages is closed under iterated bounded hairpin completion. Here we show that this is true by providing a more general result which applies to all classes of languages which are closed under finite union, intersection with regular sets, and concatenation with regular sets. In particular, all Chomsky classes and all standard complexity classes are closed under iterated bounded hairpin completion.In the second part of the paper we address the question whether the iterated hairpin completion of a singleton is always regular. In contrast to the first question, this one has a negative answer. We exhibit an example of a singleton language whose iterated hairpin completion is not regular: actually, it is not context-free, but context-sensitive.     

Unavoidable Sets of Words of Uniform Length

A set of words X over a finite alphabet A is said to be unavoidable if all but finitely many words in A* have a factor in X. We examine the problem of calculating the cardinality of minimal unavoidable sets of words of uniform length; we correct an error in [8], state a conjecture offering a formula for the minimum size of these so called n-good sets for all values of n, and show that the conjecture is correct in an infinite number of cases.     

Accepting Networks of Evolutionary Processors with Subregular Filters

We propose a new variant of Accepting Networks of Evolutionary Processors, in which the operations are applied at arbitrary positions to the processed words (rather than at the ends of words only) and where the filters are languages from several special classes of regular sets. More precisely, we show that the use of filters from the class of non-counting, ordered, power-separating, suffix-closed regular, union-free, definite and combinational languages is as powerful as the use of arbitrary regular languages and yields networks that can accept all the recursively enumerable languages. On the other hand, by using filters that are only finite languages, monoids, nilpotent languages, commutative regular languages, or circular regular languages, one cannot generate all recursively enumerable languages. These results seem interesting as they provide both upper and lower bounds on the classes of languages that one can use as filters in an accepting network of evolutionary processors in order to obtain a complete computational model.     

Unknown malcode detection and the imbalance problem

The recent growth in network usage has motivated the creation of new malicious code for various purposes. Today’s signature-based antiviruses are very accurate for known malicious code, but can not detect new malicious code. Recently, classification algorithms were used successfully for the detection of unknown malicious code. But, these studies involved a test collection with a limited size and the same malicious: benign file ratio in both the training and test sets, a situation which does not reflect real-life conditions. We present a methodology for the detection of unknown malicious code, which examines concepts from text categorization, based on n-grams extraction from the binary code and feature selection. We performed an extensive evaluation, consisting of a test collection of more than 30,000 files, in which we investigated the class imbalance problem. In real-life scenarios, the malicious file content is expected to be low, about 10% of the total files. For practical purposes, it is unclear as to what the corresponding percentage in the training set should be. Our results indicate that greater than 95% accuracy can be achieved through the use of a training set that has a malicious file content of less than 33.3%.     

Star-Free Sets of Words on Ordinals

Let n be a fixed integer; we extend the theorem of Schützenberger, McNaughton, and Papert on star-free sets of finite words to languages of words of length less than ωⁿ.     

Approximations in <Emphasis Type="Italic">n</Emphasis>-ary algebraic systems

Algebraic systems have many applications in the theory of sequential machines, formal languages, computer arithmetics, design of fast adders and error-correcting codes. The theory of rough sets has emerged as another major mathematical approach for managing uncertainty that arises from inexact, noisy, or incomplete information. This paper is devoted to the discussion of the relationship between algebraic systems, rough sets and fuzzy rough set models. We shall restrict ourselves to algebraic systems with one n-ary operation and we investigate some properties of approximations of n-ary semigroups. We introduce the notion of rough system in an n-ary semigroup. Fuzzy sets, a generalization of classical sets, are considered as mathematical tools to model the vagueness present in rough systems.     

Supporting SAT based BMC on Finite Path Models

The standard translation of a Bounded Model Checking (BMC) instance into a satisfiability problem, (a.k.a SAT), might produce misleading results in the case when the model under verification contains finite paths. Models with finite paths might be produced unknowingly when using modern verification languages such as PSL-Sugar [Property Specification Language: Reference Manual. Version 1.1, Accellera, June 2004]. Specifically, the use of language constructs such as restrict, assume etc. might lead to such models. Thus the user may receive misleading results from SAT based tools.In this paper we describe in what circumstances the finite path problem occurs and present an improved translation of the BMC problem into a SAT instance. The new translation does not suffer from the discussed shortcoming. Our translation is only slightly longer then the usual one introducing one extra Boolean variable in the model.We also show that this translation may improve the SAT solver runtime even for models without finite paths.