Finite turns and the regular closure of linear context-free languages

Turn bounded pushdown automata with different conditions for beginning a new turn are investigated. Their relationships with closures of the linear context-free languages under regular operations are studied. For example, automata with an unbounded number of turns that have to empty their pushdown store up to the initial symbol in order to start a new turn are characterized by the regular closure of the linear languages. Automata that additionally have to re-enter the initial state are (almost) characterized by the Kleene star closure of the linear languages. For both a bounded and an unbounded number of turns, requiring to empty the pushdown store is a strictly stronger condition than requiring to re-enter the initial state. Several new language families are obtained which form a double-stranded hierarchy. Closure properties of these families under AFL operations are derived. The regular closure of the linear languages share the strong closure properties of the context-free languages, i.e., the family is a full AFL. Interestingly, three natural new language families are not closed under intersection with regular languages and inverse homomorphism. Finally, an algorithm is presented parsing languages from the new families in quadratic time.     

Iterated Kleene computability

Dedicated to the memory of A. I. Mal'tsev.     

On commutative Kleene monoids

Commutative Kleene monoids are rational     

Kleene代数及相关半模结构

Kleene代数在理论计算机科学中具有基础而特殊的重要性,Kleene模、布尔模和动态代数等与Kleene代数密切相关的半模结构在程序的语义逻辑及推理中发挥着十分重要的作用.将半环和半模等代数系统作为基本构架,研究了理论计算机科学中的Kleene代数、Kleene模和归纳~*-半环等重要概念,并将这些对象统一为序~*-半环上称为归纳半模的代数结构.进一步,提出并讨论了弱归纳半模、伪归纳半模以及伪弱归纳半模等相关概念.     

Non-Complementedness and Non-Distributivity of Kleene Degrees

In this note, we study the complementedness and the distributivity of upper semilattices of Kleene degrees assuming V = L. K denotes the upper semilattice of all Kleene degrees. We prove that if V = L, then some sub upper semilattices of K are non-complemented and some are non-distributive.     

Affine completeness of Kleene algebras

An algebra is called affine complete if all its compatible (i.e. congruence-preserving) functions are polynomial functions. In this paper we characterize affine complete members in the variety of Kleene algebras. We also characterize local polynomial functions of Kleene algebras and use this result to describe locally affine complete Kleene algebras. Received December 20, 1996; accepted in final form March 24, 1997.     

Kleene algebras with implication

Inspired by an old construction due to J. Kalman that relates distributive lattices and centered Kleene algebras, in this paper we study an equivalence for certain categories whose objects are algebras with implication \({(H, \bigwedge, \bigvee, \rightarrow, 0,1)}\) which satisfy the following property for every \({a,b,c\, \in\, H}\): if \({a \leq b \rightarrow c}\), then \({a \bigwedge b \leq c}\).     

On a Conjecture of Kleene and Post

A proof is given that 0 ′ (the argest Turing degree containing a computably enumerable set) is definable in the structure of the degrees of unsolvability. This answers a long‐standing question of Kleene and Post, and has a number of corollaries including the definability of the jump operator.     

Congruence-preserving functions on Stone and Kleene algebras

We investigate local polynomial functions on Stone algebras and on Kleene algebras. We find a generating set for the clone of all local polynomial functions. We also represent local polynomial functions on a given algebra by polynomial functions of some canonical extension of this algebra.     

Local Density of Kleene Degrees

Concerning Post's problem for Kleene degrees and its relativization, Hrbacek showed in [1] and [2] that if V = L, then Kleene degrees of coanalytic sets are dense, and then for all K ?^ωω, there are N₁ sets which are Kleene semirecursive in K and not Kleene recursive in each other and K. But the density of Kleene semirecursive in K Kleene degrees is not obtained from these theorems. In this note, we extend these theorems by showing that if V = L, then for all K ? ^ωω, Kleene semirecursive in K Kleene degrees are dense above K.     

Endomorphisms of finite regular Kleene lattices

The class of regular Kleene lattices is the least strict quasi-variety of De Morgan lattices. In this paper we give necessary and sufficient conditions for two finite regular Kleene lattices to share the same monoid of endomorphisms.     

Unification and Projectivity in De Morgan and Kleene Algebras

We provide a complete classification of solvable instances of the equational unification problem over De Morgan and Kleene algebras with respect to unification type. The key tool is a combinatorial characterization of finitely generated projective De Morgan and Kleene algebras.     

A note on minimal matrix representation of closure operations

A matrixM withn columns represents a closure operationF(A), (A⊂X, |X|=n) if for anyA, any two rows equal in the columns corresponding toA are also equal inF(A). Letm(F) be the minimum number of rows of the matrices representingF. Lower and upper estimates on maxm(F) are given where max runs over the set of all closure operations onn elements.     

Kleene代数的诱导子代数及理想

由于逻辑学研究的需要 ,Kleene代数理论的重要性已越来越明显 .本文主要研究了Kleene代数的子代数及理想的一些性质 ,得到了一些比较好的结果 .