𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On bounded query machines

✍ Scribed by Jose L. Balcázar; Ronald V. Book; Uwe Schöning

Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
452 KB
Volume
40
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Bounded Arity Datalog(≠) Queries on Grap
Bounded Arity Datalog(≠) Queries on Graphs
✍ Foto N. Afrati 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 627 KB

We show that there are Datalog({) queries on graphs (i.e., the extensional database contains a single binary relation) that require recursively defined predicates of arbitrarily large width. More specifically, we prove that fixed subgraph homeomorphism queries require width of recursively defined pr

Automata techniques for query inference
Automata techniques for query inference machines
✍ William Gasarch; Geoffrey R. Hird 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 248 KB

In prior papers the following question was considered: which classes of computable sets can be learned if queries about those sets can be asked by the learner? The answer depended on the query language chosen. In this paper we develop a framework (reductions) for studying this question. Essentially,

Reversal-bounded multipushdown machines
Reversal-bounded multipushdown machines
✍ Brenda S. Baker; Ronald V. Book 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 1001 KB

Several representations of the recursively enumerable (r.e.) sets are presented. The first states that every r.e. set is the homomorphic image of the intersection of two linear context-free languages. The second states that every r.e. set is accepted by an on-line Turing acceptor with two pushdown s