Automata techniques for query inference machines
type: Item
instance of: scholarly article
title: Automata techniques for query inference machines
zbMATH Open document ID: 1013.03009
DOI: 10.1016/S0168-0072(01)00115-4
author: William Gasarch
author: Geoffrey R. Hird
published in: Annals of Pure and Applied Logic
publication date: 2002-12-02T00:00:00Z
review text: Expressiveness of the languages \([+,<]\) of the first-order monadic predicate logic with addition, the relation ``less than'', and some additional fixed predicates, as well as the second-order monadic predicate language \([S,<]^2\) with some fixed additional predicates, both on the set of natural numbers, are considered, where \(S(x) = x+1\). The query language \(L\) is the set of formulas of the considered logic. A query over \(L\) is a formula \(F(X)\) of \(L\) with the unique free set variable \(X\). Every Turing machine \(M\) (the total variant of \(M\) is called inductive inference machine) is coded into a natural number \(e\), which is called a program (for \(M\)). A query inference machine is a total Turing machine that can ask queries in a particular query language about a computable set \(A\) to learn about \(A\) and magically gets the answers. Theorem. The set of computable sets cannot be learned by Turing machines with queries to the language \([+,<,\text{Pow}_a]\), where \(\text{Pow}_a\) is the predicate that tests if a number is a power of \(a\). The theorem is proved by transforming queries in \([+,<,\text{Pow}_a]\) into queries in \([S,<,\text{Pow}_a]^2\), which can be processed with the help of Büchi automata. Open question: Whether the first-order monadic predicate logic \([S,<,\text{Pow}_2,\text{Pow}_3]\) is quasi-cardinality decidable or not.
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 68Q32
Mathematics Subject Classification ID: 03D10
zbMATH DE Number: 1838860
zbMATH Keywords: decidability
zbMATH Keywords: computable set
zbMATH Keywords: query language
zbMATH Keywords: inductive inference
zbMATH Keywords: query inference machine
zbMATH Keywords: Büchi automata
zbMATH Keywords: second-order monadic predicate logic
zbMATH Keywords: Turing machine
zbMATH Keywords: first-order monadic predicate logic
MaRDI profile type: Publication
cites work: Weak Second‐Order Arithmetic and Finite Automata
cites work: Q5525343
cites work: Comparison of identification criteria for machine inductive inference
cites work: Theories of automata on \(\omega\)-tapes: a simplified approach
cites work: Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
cites work: Q5596785
cites work: Trade-off among parameters affecting inductive inference
cites work: Q4835903
cites work: Inferring answers to queries
cites work: Learning via queries in [+, <]
cites work: Learning via queries
cites work: Q4349576
cites work: Testing and generating infinite sequences by a finite automaton
cites work: Aggregating inductive expertise
cites work: Q5638297
cites work: ON CERTAIN EXTENSIONS OF THE ARITHMETIC OF ADDITION OF NATURAL NUMBERS
cites work: The Power of Pluralism for Automatic Program Synthesis
cites work: Learning via queries and oracles
cites work: Q3998976
full work available at URL: s0168-0072(01)00115-4
OpenAlex ID: W2085222986
Recommended article: Query automata over finite trees
Recommended article: Q4336266
Recommended article: Q4035346
Recommended article: Learning Grammars and Automata with Queries
Recommended article: Learning finite cover automata from queries
Recommended article: GRAMMARS AND AUTOMATA TO OPTIMIZE CHAIN LOGIC QUERIES
Recommended article: Automated inferencing
Recommended article: Inferring Symbolic Automata
Recommended article: Automata and Answer Set Programming
description: scientific article; zbMATH DE number 1838860