𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of languages of type UM

✍ Scribed by R.G. Nigmatullin

Publisher
Elsevier Science
Year
1977
Weight
553 KB
Volume
17
Category
Article
ISSN
0041-5553

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The counting complexity of group-definab
The counting complexity of group-definable languages
✍ V. Arvind; N.V. Vinodchandran πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 166 KB

A group family is a countable family B = {Bn}nΒΏ0 of ΓΏnite black-box groups, i.e., the elements of each group Bn are uniquely encoded as strings of uniform length (polynomial in n) and for each Bn the group operations are computable in time polynomial in n. In this paper we study the complexity of NP

On computational complexity of contextua
On computational complexity of contextual languages
✍ Lucian Ilie πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 726 KB

We consider the following restriction of internal contextual grammars, called local: in any derivation in a grammar, after applying a context, further contexts can be added only inside of or at most adjacent to the previous ones. We further consider a natural restriction of this derivation mode by r

The complexity of countable categoricity
The complexity of countable categoricity in finite languages
✍ Aleksander Ivanov πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 139 KB

## Abstract We study complexity of the index set of countably categorical theories and Ehrenfeucht theories in finite languages.

The complexity of existential quantifica
The complexity of existential quantification in concept languages
✍ Francesco M. Donini; Maurizio Lenzerini; Daniele Nardi; Bernhard Hollunder; Wern πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 965 KB

Much of the research on concept languages, which also are called terminological languages, has focused on the computational complexity of subsumption. The intractability results can be divided into two groups. First, it has been shown that extending the basic language ,~Sfwith constructs containing

On the context-free production complexit
On the context-free production complexity of finite languages
✍ Zsolt Tuza πŸ“‚ Article πŸ“… 1987 πŸ› Elsevier Science 🌐 English βš– 696 KB

The following problem is investigated. Let L be a given finite language, LcL,= {ub: I ~o,bsn, of/~}. Determine the minimal natural number c(L) such that L can be generated by c(L) context-free productions. Among others, max c(L) = O(n'/log n) is proved, and languages satisfying c(L) = IL) are charac