✦ LIBER ✦

A predicative and decidable characterization of the polynomial classes of languages

✍ Scribed by S. Caporaso; M. Zito; N. Galesi

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 149 KB
Volume: 250
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(99)00116-4

No coin nor oath required. For personal study only.

✦ Synopsis

Characterizations of PTIME, PSPACE, the polynomial hierarchy and its elements are given, which are decidable (membership can be decided by syntactic inspection to the constructions), predicative (according to points of view by Leivant and others), and are obtained by means of increasing restrictions to course-of-values recursion on trees (represented in a dialect of Lisp).

📜 SIMILAR VOLUMES

A characterization of two-way determinis

A characterization of two-way deterministic classes of languages

✍ A.V. Aho; J.D. Ullman 📂 Article 📅 1970 🏛 Elsevier Science 🌐 English ⚖ 731 KB

It is shown that a class of languages is defined by a class of two-way deterministic balloon automata if and only if that class is closed under marked union, marked Kleene closure and the inverse mappings performed by deterministic GSMs that move two ways on the input. Hence, the context sensitive l

A characterization of the leaf language

A characterization of the leaf language classes

✍ Bernd Borchert; Riccardo Silvestri 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 602 KB

Bovet, Crescenzi, and Silvestri ( 1992 , 1995 ), and independently Vereshchagin ( 1994) , showed that many complexity classes in the polynomial time setting are leaf language classes, i.e. classes which are determined by two disjoint languages. They gave many examples but they did not characteriz

Closure and decidability properties of s

Closure and decidability properties of some language classes with respect to ciliate bio-operations

✍ Mark Daley; Oscar H. Ibarra; Lila Kari 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 285 KB

The process of gene unscrambling in ciliates (a type of unicellular protozoa), which accomplishes the di cult task of re-arranging gene segments in the correct order and deleting non-coding sequences from an "encrypted" version of a DNA strand, has been modeled and studied so far from the point of v

The Polynomial Method and Restricted Sum

The Polynomial Method and Restricted Sums of Congruence Classes

✍ Noga Alon; Melvyn B. Nathanson; Imre Ruzsa 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 432 KB

We present a simple and general algebraic technique for obtaining results in Additive Number Theory, and apply it to derive various new extensions of the Cauchy Davenport Theorem. In particular we obtain, for subsets A 0 , A 1 , ..., A k of the finite field Z p , a tight lower bound on the minimum p

Determination of the residue classes of

Determination of the residue classes of a polynomial at integral arguments

✍ Wen-Ch'ing Winnie Li 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 550 KB

Properties and Applications of a Class o

Properties and Applications of a Class of Polynomials

✍ S.D. Bedrosian 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 373 KB

A study of c+z.&&x away8 have led ua to examina t?~ Fibonach po&nomid and a tree enumeration polynomial F,,(x) and T"(m), r@vdy. T,,(m) b for lirmw iterative celhhr arrays of n Zeus with a wmmon edge !x+?we~ ao&ctmt m-cyck dia. The we&&mta of T,,(m) huve the 8ame absolude vaha 08 tha8e of F, (x) but