Lanczos <Emphasis Type="Italic">τ</Emphasis>-method regularization algorithm and its algebraic-programming implementation

An algebraic algorithm is developed for computing an algebraic polynomial y _n of order n ∈ N in computer algebra systems. This polynomial is the optimal approximation of the solution y = y(x), x ∈ [a,b], to a system of linear differential equations with polynomial coefficients and initial conditions at a regular singular zero point of this equation in a space C_{[ a,b ]}^k C_{\left[ {a,b} \right]}^k .     

A counterexample to a conjecture concerning concatenation hierarchies

We give a counterexample to the conjecture which was originally formulated by Straubing in 1986 concerning a certain algebraic characterization of regular languages of level 2 in the Straubing-Thérien concatenation hierarchy of star-free languages.     

Dispersion Analysis of Discontinuous Galerkin Schemes Applied to Poincaré, Kelvin and Rossby Waves

A technique for analyzing dispersion properties of numerical schemes is proposed. The method is able to deal with both non dispersive or dispersive waves, i.e. waves for which the phase speed varies with wavenumber. It can be applied to unstructured grids and to finite domains with or without periodic boundary conditions. We consider the discrete version L of a linear differential operator ℒ. An eigenvalue analysis of L gives eigenfunctions and eigenvalues (l _i ,λ _i ). The spatially resolved modes are found out using a standard a posteriori error estimation procedure applied to eigenmodes. Resolved eigenfunctions l _i ’s are used to determine numerical wavenumbers k _i ’s. Eigenvalues’ imaginary parts are the wave frequencies ω _i and a discrete dispersion relation ω _i =f(k _i ) is constructed and compared with the exact dispersion relation of the continuous operator ℒ. Real parts of eigenvalues λ _i ’s allow to compute dissipation errors of the scheme for each given class of wave. The method is applied to the discontinuous Galerkin discretization of shallow water equations in a rotating framework with a variable Coriolis force. Such a model exhibits three families of dispersive waves, including the slow Rossby waves that are usually difficult to analyze. In this paper, we present dissipation and dispersion errors for Rossby, Poincaré and Kelvin waves. We exhibit the strong superconvergence of numerical wave numbers issued of discontinuous Galerkin discretizations for all families of waves. In particular, the theoretical superconvergent rates, demonstrated for a one dimensional linear transport equation, for dissipation and dispersion errors are obtained in this two dimensional model with a variable Coriolis parameter for the Kelvin and Poincaré waves.     

Quotient Complexity of Closed Languages

A language L is prefix-closed if, whenever a word w is in L, then every prefix of w is also in L. We define suffix-, factor-, and subword-closed languages in an analogous way, where by factor we mean contiguous subsequence, and by subword we mean scattered subsequence. We study the state complexity (which we prefer to call quotient complexity) of operations on prefix-, suffix-, factor-, and subword-closed languages. We find tight upper bounds on the complexity of the subword-closure of arbitrary languages, and on the complexity of boolean operations, concatenation, star, and reversal in each of the four classes of closed languages. We show that repeated applications of positive closure and complement to a closed language result in at most four distinct languages, while Kleene closure and complement give at most eight.     

Monoïdes syntactiques des langages algébriques

Summary Syntactic monoids have been considered so far almost only for rational (= regular) languages. We start here a systematic study of the syntactic monoids of algebraic (= context-free) languages. We exhibit a whole class of finitely generated monoids, none of which is isomorphic to the syntactic monoid of an algebraic language. We show that if M ₁ and M ₂ are syntactic monoids of algebraic languages L ₁ and L ₂, and if neither M ₁ nor M ₂ has a zero, then there exists an algebraic language L whose syntactic monoid is isomorphic to the direct product M ₂×M₂. We then prove that the algebraic language ¯L ₀ Complement of {n ⁿ yⁿ zⁿ; n1} has a syntactic monoid M ₀ such that M ₀×M ₀ is not isomorphic to the syntactic monoid of any algebraic language, whence follows that any algebraic language L whose syntatic monoid is isomorphic to M ₀ must be non deterministic.     

Minimal equational representations of recognizable tree languages

 A tree language is congruential if it is the union of finitely many classes of a finitely generated congruence on the term algebra. It is well known that congruential tree languages are the same as recognizable tree languages. An equational representation is an ordered pair (E, P) , where E is either a ground term equation system or a ground term rewriting system, and P is a finite set of ground terms. We say that (E, P) represents the congruential tree language L which is the union of those ?^* _E -classes containing an element of P, i.e., for which L=⋃{[p]_? ^* _E ∣p∈P}. We define two sorts of minimality for equational representations. We introduce the cardinality vector (∣E∣, ∣P∣) of an equational representation (E, P). Let ? _l and ? _a denote the lexicographic and antilexicographic orders on the set of ordered pairs of nonnegative integers, respectively. Let L be a congruential tree language. An equational representation (E, P) of L with ? _l -minimal (? _a -minimal) cardinality vector is called ? _l -minimal (? _a -minimal). We compute, for an L given by a deterministic bottom-up tree automaton, both a ? _l -minimal and a ? _a -minimal equational representation of L. Received: 27 July 1994/5 October 1995     

On computing Boolean connectives of characteristic functions

This paper is a study of the existence of polynomial time Boolean connective functions for languages. A languageL has an AND function if there is a polynomial timef such thatf(x,y) L x L andy L. L has an OR function if there is a polynomial timeg such thatg(x,y) xL oryL. While all NP complete sets have these functions, Graph Isomorphism, which is probably not complete, is also shown to have both AND and OR functions. The results in this paper characterize the complete sets for the classes D^p and p^SAT[O(logn)] in terms of AND and OR and relate these functions to the structure of the Boolean hierarchy and the query hierarchies. Also, this paper shows that the complete sets for the levels of the Boolean hierarchy above the second level cannot have AND or OR unless the polynomial hierarchy collapses. Finally, most of the structural properties of the Boolean hierarchy and query hierarchies are shown to depend only on the existence of AND and OR functions for the NP complete sets.The first author was supported in part by NSF Research Grants DCR-8520597 and CCR-88-23053, and by an IBM Graduate Fellowship.     

On bounded lattices satisfying Elkan’s law

In this short paper we shall prove that every bounded lattice L with the conditions: (c1) 1′ =  0 and (EL): (a · b′)′ =  b +  a′ · b′ for all a, b ∈ L is a Boolean algebra. This is a more general result than that of Renedo et al. (Proceedings NAFIPS’04, 2004), in which it is proved that every orthocomplemented lattice with (EL) is a Boolean algebra.     

A note on autodense related languages

In this paper, some algebraic properties of autodense languages and pure autodense languages are studied. We also investigate the algebraic properties concerning anti-autodense languages. The family of anti-autodense languages contains infix codes, comma-free codes, and some subfamilies of new codes which are anti-autodense prefix codes, anti-autodense suffix codes and anti-autodense codes. The relationships among these subfamilies of new codes are investigated. The characterization of L ⁿ , n ≥ 2, which are anti-autodense is studied.     

Hierarchies of polynomially solvable satisfiability problems

In this paper, we introduce general techniques for extending classes of polynomially solvable SAT instances. We generalize the approach of Gallo and Scutellà, who defined the hierarchy { _i }, where _l corresponds to the Generalized Horn class. We propose a family of polynomial hierarchies, where a polynomial hierarchy { _i } is a sequence of polynomially solvable classes that cover the whole set of CNF formulas, and such that _{i i+1} fori0. Following a different approach, based on a new decomposition technique, we define the class of Split-Horn formulas, which is an extension of _l. We discuss and compare the basic properties of the proposed classes; polynomial time algorithms for recognition and solution are provided.     

On the decidability of sparse univariate polynomial interpolation

We consider the problem of determining whether or not there exists a sparse univariate polynomial that interpolates a given setS={(x _i ,y _i )} of points. Several important cases are resolved, e.g., the case when thex _i's are all positive rational numbers. But the general problem remains open.     

Abstract families of context-free grammars

An abstract family of grammars (AFG) may be defined as a class of grammars for which the corresponding class of languages forms an abstract family of languages (AFL) as defined by Ginsburg and Greibach. The derivation bounded grammars of Ginsburg and Spanier is an example of an AFG which is properly included in the class of all context-free grammars (also AFG). The main result is that there exist two distinct infinite hierarchies of AFG which exhaust the derivation bounded AFG such that the AFL associated with the kth member of one of these AFG hierarchies is properly included in the AFL associated with the k-lst member of that same hierarchy. Each hierarchy is shown to be strongly incomparable to the other; that is, the first member of each generates some language not generated by a fixed but arbitrary member of the other. We designate these hierarchies as the hierarchies of left and right dominant grammars (languages)     

Homomorphic characterizations of recursively enumerable languages with very small language classes

In this paper, we attempt to characterize the class of recursively enumerable languages with much smaller language classes than that of linear languages. Language classes, and , of (i,j) linear languages and (i,j) minimal linear languages are defined by posing restrictions on the form of production rules and the number of nonterminals. Then the homomorphic characterizations of the class of recursively enumerable languages are obtained using these classes and a class, , of minimal linear languages. That is, for any recursively enumerable language L over Σ, an alphabet Δ, a homomorphism h : Δ^*→Σ^* and two languages L₁ and L₂ over Δ in some classes mentioned above can be found such that L = h(L₁∩L₂). The membership relations of L₁ and L₂ of the main results are as follows:(I) For posing restrictions on the forms of production rules, the following result is obtained:(1) and .This result is the best one and cannot be improved using . However, with posing more restriction on L₂, this result can be improved and the follwing statement is obtained.(2) and .(II) For posing restrictions on the numbers of nonterminals, the follwing result is obtained.(3) and .We believe this result is also the best.     

Indian parallelism on unary ol systems

In this paper we impose the Indian parallelism restriction on the unary developmental system, i. e. on UOL system. We observe that corresponding to any P_aUL language we can get a unary language of Restricted parallel content free language (RP_aCLUL).

Section 1 deals with definitions and Section 2 deals with some propoerties of P_aUL systems. In Section 3, we compare P_aUL language with unary languages of parallel content free grammars and also characterize some subfamilies of P_aUL languages. In the last section, we state a few hierarchial and closure properties.     

Composition and orbits of language operations: finiteness and upper bounds

We consider a set of eight natural operations on formal languages (Kleene closure, positive closure, complement, prefix, suffix, factor, subword, and reversal), and compositions of them. If x and y are compositions, we say x is equivalent to y if they have the same effect on all languages L. We prove that the number of equivalence classes of these eight operations is finite. This implies that the orbit of any language L under the elements of the monoid is finite and bounded, independent of L. This generalizes previous results about complement, Kleene closure, and positive closure. We also estimate the number of distinct languages generated by various subsets of these operations.     

Batch scheduling of step deteriorating jobs

In this paper we consider the problem of scheduling n jobs on a single machine, where the jobs are processed in batches and the processing time of each job is a step function depending on its waiting time, which is the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. For job i, if its waiting time is less than a given threshold value D, then it requires a basic processing time a _i ; otherwise, it requires an extended processing time a _i +b _i . The objective is to minimize the completion time of the last job. We first show that the problem is NP-hard in the strong sense even if all b _i are equal, it is NP-hard even if b _i =a _i for all i, and it is non-approximable in polynomial time with a constant performance guarantee Δ<3/2, unless . We then present O(nlog n) and O(n ^3F−1log n/F ^F ) algorithms for the case where all a _i are equal and for the case where there are F, F≥2, distinct values of a _i , respectively. We further propose an O(n ²log n) approximation algorithm with a performance guarantee for the general problem, where m ^* is the number of batches in an optimal schedule. All the above results apply or can be easily modified for the corresponding open-end bin packing problem.     

Truncations of infinite matrices and algebraic series associated with some of grammars

We consider an algebraic system over $\text{R}$[x] of the form X = a₀(x)X^k+ a_k1(x)X+a_k(x), where a₀(x) and a_k(x) are in x$\text{R}$[x] and a_k?1(x) is in x$\text{R}$. Let A be the infinite incidence matrix associated with the algebraic system. Then we prove that the eigenvalues of northwest corner truncations of A are dense in some algebraic curves.Using this we get a result on positive algebraic series. We consider the case that the coefficients of a₁(x)(i = 0,…,k?1, k) are positive. The algebraic series generated by the algebraic system may be viewed as a function in the complex variable x. Then by the above fact we prove that the radius of convergence of the function equals the least positive zero of the modified discriminant of the system.As an application to context free languages we show a procedure for calculating the entropy of some one counter languages. Other applications to Dyck languages and the Lukasiewicz language are also described.     

Calculating optimal addition chains

An addition chain is a finite sequence of positive integers 1 = a ₀ ≤ a ₁ ≤ · · · ≤ a _r = n with the property that for all i > 0 there exists a j, k with a _i = a _j + a _k and r ≥ i > j ≥ k ≥ 0. An optimal addition chain is one of shortest possible length r denoted l(n). A new algorithm for calculating optimal addition chains is described. This algorithm is far faster than the best known methods when used to calculate ranges of optimal addition chains. When used for single values the algorithm is slower than the best known methods but does not require the use of tables of pre-computed values. Hence it is suitable for calculating optimal addition chains for point values above currently calculated chain limits. The lengths of all optimal addition chains for n ≤ 2³² were calculated and the conjecture that l(2n) ≥ l(n) was disproved. Exact equality in the Scholz–Brauer conjecture l(2 ⁿ − 1) = l(n) + n − 1 was confirmed for many new values.     

Shuffle languages are in P

In this paper we show that shuffle languages are contained in one-way-NSPACE(log n) thus in P. We consider the class of shuffle languages which emerges from the class of finite languages through regular operations (union, concatenation, Kleene star) and shuffle operations (shuffle and shuffle closure). For every shuffle expression E we construct a shuffle automaton which accepts the language generated by E and we show that the automaton can be simulated by a one-way nondeterministic Turing machine in logarithmic space.     

On computing derivatives forC 1 interpolating schemes: an optimization

The application of Powell-Sabin’s or Clough-Tocher’s schemes to scattered data problems, as known requires the knowledge of the partial derivatives of first order at the vertices of an underlying triangulation. We study alocal method for generating partial derivatives based on the minimization of the energy functional on the star of triangles sharing a node that we called acell. The functional is associated to some piecewise polynomial function interpolating the points. The proposed method combines theglobal Method II by Renka and Cline (cf. [16, pp. 230–231]) with the variational approach suggested by Alfeld (cf. [2]) with care to efficiency in the computations. The locality together with some implementation strategies produces a method well suited for the treatment of a big amount of data. An improvement of the estimates is also proposed.