Equal matrix languages and Kleene closure

It is shown that the family of equal matrix languages (EML) which intersects the family of context-sensitive and context-free languages is not closed under Kleene closure, intersection and complementation. The family of bounded EML whose generative power lies between that of bounded context-sensitive languages and bounded context-free languages is shown to be a class of unambiguous languages. Operations that preserve unambiguity and certain decidability questions are discussed.     

Classes of regular and context-free languages over countably infinite alphabets

For a countably infinite alphabet Δ, the classes Reg(Δ) of regular languages and CFL(Δ) of context-free languages over Δ are defined by way of an encoding. All the languages contained in these classes are decidable, and these classes do have many properties in common with the class of regular languages Reg(Σ) and the class of context-free languages CFL(Σ), respectively, where Σ is a finite alphabet. In particular, each of these classes can be characterized in a semantical way by a certain type of automata over Δ. Finally, the classes Reg(Δ) and CFL (Δ) are compared to the classes of languages over Δ that are defined by Autebert, Beauquier, and Boasson.     

146号初等元胞自动机的演化语言的复杂性

Symbolic dynamics of cellular automata is introduced by coarse-graining the temporal evolution orbits. Evolution languages are defined. By using the theory of formal languages and automata, the complexity of evolution languages of the elementary cellular automaton of rule 146 is studied and it is proved that its width 1-evolution language is regular, but for every n ≥ 2 its width n-evolution language is not context-free but context-sensitive. Also, the same results hold for the equivalent （under conjugation） elementary cellular automaton of rule 182.     

Regular Component Splittable Languages

Every infinite regular language contains a regular subset of the formuv+w for some words u, v, w, where v is not the empty word. The regularsubsets of the above form are called regular components. Some well-knowncontext-free languages, such as the Dyck language and the balanced language(over an alphabet X with |X| = 2), are decomposed as disjointunions of disjunctive languages. In this paper, we investigate thedecompositions of some of the regular languages and the context-freelanguages as disjoint unions of regular components. An infinite language iscalled regular component splittable if it can be expressed as a disjointunion of regular components and a finite set. We show that the Dycklanguage, the balanced language and some disjunctive context-free splittablelanguages are regular component splittable. We also present an example toshow that there is a disjunctive context-free language which is not regularcomponent splittable.     

Notes on top-down languages

Properties of context-free languages and grammars permitting deterministic top-down recognition with bounded lookahead are discussed. In particular, it is shown that for eachk>1 there are such languages requiring a lookahead of at leastk characters.     

Restorations of punctured languages and similarity of languages

Punctured languages are languages whose words are partial words in the sense that the letters at some positions are unknown. We investigate to which extent restoration of punctured languages is possible if the number of unknown positions or the proportion of unknown positions per word, respectively, is bounded, and we study their relationships for different boundings. The considered restoration classes coincide with similarity classes according to some kind of similarity for languages. Thus all results we can also formulate in the language of similarity. We show some hierarchies of similarity classes for each class from the Chomsky hierarchy and prove the existence of linear languages which are not δ ‐similar to any regular language for any δ < ½. For δ ≥ ½ this is unknown but it could only be possible in the case of non‐slender linear languages. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Linear splicing and syntactic monoid

Splicing systems were introduced by Head in 1987 as a formal counterpart of a biological mechanism of DNA recombination under the action of restriction and ligase enzymes. Despite the intensive studies on linear splicing systems, some elementary questions about their computational power are still open. In particular, in this paper we face the problem of characterizing the proper subclass of regular languages which are generated by finite (Paun) linear splicing systems. We introduce here the class of marker languages L, i.e., regular languages with the form L=L₁[x]₁L₂, where L₁,L₂ are regular languages, [x] is a syntactic congruence class satisfying special conditions and [x]₁ is either equal to [x] or equal to [x]∪{1}, 1 being the empty word. Using classical properties of formal language theory, we give an algorithm which allows us to decide whether a regular language is a marker language. Furthermore, for each marker language L we exhibit a finite Paun linear splicing system and we prove that this system generates L.     

Pure 2D picture grammars and languages

A new syntactic model, called pure two-dimensional (2D) context-free grammar (P2DCFG), is introduced based on the notion of pure context-free string grammar. The rectangular picture generative power of this 2D grammar model is investigated. Certain closure properties are obtained. An analogue of this 2D grammar model called pure 2D hexagonal context-free grammar (P2DHCFG) is also considered to generate hexagonal picture arrays on triangular grids.     

Complete classes of tests for regularly varying distributions

This paper establishes essentially complete class theorems and gives conditions for admissibility of tests for parametric families of distributions having some kinds of regular variation properties. A complete treatment of topologically contiguous one-dimensional bounded and unbounded hypotheses is given. Examples of applications to well known families of distributions are presented.     

Bicomplex holomorphic functional calculus

In this paper we introduce and study a functional calculus for bicomplex linear bounded operators. The study is based on the decomposition of bicomplex numbers and of linear operators using the two nonreal idempotents. We show that, due to the presence of zero divisors in the bicomplex numbers, the spectrum of a bounded operator is unbounded. We therefore introduce a different spectrum (called reduced spectrum) which is bounded and turns out to be the right tool to construct the bicomplex holomorphic functional calculus. Finally we provide some properties of the calculus.     

An algorithmic representation of fractional powers of positive operators

We are concerned with a new representation of fractional powers of operators by a series using exclusively contractive operators or operators with uniformly bounded powers. This representation is suitable for the construction of efficient approximations for which the error estimates are given and the convergence is investigated. The rate of convergence turns out to be exponential for bounded operators and polynomial for unbounded operators     

2 ω-finite automata and sets of obstructions of their languages

Nondeterministic finite Rabin-Scott’s automata without initial and final states (2ω-FA) are considered. In this paper, they are used to define so called sets of obstructions, used also in various algebraic systems, and to consider similar problems for the formal languages theory. Thus, we define sets of obstructions of languages (or, rather, 2ω-languages) of such automata. We obtain that each 2ω-language defined by 2 ω-FA has the set of obstruction being a regular language. And, vice versa, for each regular languageL (containing no proper subword of its another word), there exists a 2ω-FA havingL as the set of obstructions.     

Colored operads,series on colored operads,and combinatorial generating systems

We introduce bud generating systems, which are used for combinatorial generation. They specify sets of various kinds of combinatorial objects, called languages. They can emulate context-free grammars, regular tree grammars, and synchronous grammars, allowing us to work with all these generating systems in a unified way. The theory of bud generating systems uses colored operads. Indeed, an object is generated by a bud generating system if it satisfies a certain equation in a colored operad. To compute the generating series of the languages of bud generating systems, we introduce formal power series on colored operads and several operations on these. Series on colored operads are crucial to express the languages specified by bud generating systems and allow us to enumerate combinatorial objects with respect to some statistics. Some examples of bud generating systems are constructed; in particular to specify some sorts of balanced trees and to obtain recursive formulas enumerating these.     

Solution of Parabolic Equations by Means of Lyapunov Functionals

We propose a new approach to defining the notion of a solution to linear and nonlinear parabolic equations. The main idea consists in studying connections between solutions to dynamic problems in the variational shape and the properties of the corresponding Lyapunov functionals which are strictly decreasing along the trajectories of the above-mentioned dynamic equations except for the equilibrium points. It turns out that the families of Lyapunov functionals constructed by T. I. Zelenyak enable us to propose a new approach to defining solutions to both linear and nonlinear parabolic problems. All results are given in the case of smooth solutions. Note that the Lyapunov functionals can be used for studying solutions with unbounded gradients.     

Hamiltonian Pontryagin's Principles for Control Problems Governed by Semilinear Parabolic Equations

In this paper we study optimal control problems governed by semilinear parabolic equations. We obtain necessary optimality conditions in the form of an exact Pontryagin's minimum principle for distributed and boundary controls (which can be unbounded) and bounded initial controls. These optimality conditions are obtained thanks to new regularity results for linear and nonlinear parabolic equations. Accepted 17 March 1997     

On the boundedness of outer polyhedral estimates for reachable sets of linear systems

New properties of outer polyhedral (parallelepipedal) estimates for reachable sets of linear differential systems are studied. For systems with a stable matrix, it is determined what the orientation matrices are for which the estimates possessing the generalized semigroup property are bounded/unbounded on an infinite time interval. In particular, criteria are found (formulated in terms of the eigenvalues of the system’s matrix and the properties of bounding sets) that guarantee for previously mentioned tangent estimates and estimates with a constant orientation matrix that either there are initial orientation matrices for which the corresponding estimate tubes are bounded or all these tubes are unbounded. For linear stationary systems, a system of ordinary differential equations and algebraic relations is derived that determines estimates with constant orientation matrices for reachable sets that have no generalized semigroup property but are tangent and also bounded if the matrix of the system is stable.     

A note on morphic characterization of languages

It is noted, by using ideas of Culik, Fich and Salomaa [3], that for each language L and each regular language R the language L ∩ R is obtained from L# by applying the operation ‘a morphism followed by an inverse morphism' twice. As a consequence new purely morphic characterizations, based on the Dyck language D₂ and the twin-shuffle language L₂, are derived for the families of context-free and recursively enumerable languages, respectively. Also a morphic representation result for rational transductions follows.     

Some more on the finite automata

Some new problems of the theory of the finite automata are considered. Applying the finite automata in various tasks of the formal languages theory is observed. Special proof of Kleene’s theorem is obtained. This proof is used for the defining the star-height of the finite automaton. The properties of the last object are considered. The star-height of the finite automaton is used for reformulating the star-height problem of regular expressions for finite automata. The method of the reduction of the star-height problem to the task of making special finite automaton is obtained. This reformulating can help to solve the star-height problem by new way.     

Facing linear difference equations through hypergroup methods

We investigate a class of second-order linear difference equations by applying results of harmonic analysis on polynomial hypergroups. For the scalar case we show that the solutions are either bounded by the modulus of the initial value or are unbounded. For the Hilbert space-valued case we establish a concrete representation of the solutions whenever they are bounded and stationary. Among various examples we discuss those corresponding to Jacobi polynomials.