Automata techniques for query inference machines

DOI10.1016/S0168-0072(01)00115-4MaRDI QIDQ1849855zbMATH OpenOpenAlexFDO

Authors William Gasarch, Geoffrey R. Hird

Publication date 2 December 2002

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0168-0072(01)00115-4

zbMATH Keywords

Büchi automatacomputable setdecidabilityfirst-order monadic predicate logicinductive inferencequery inference machinequery languagesecond-order monadic predicate logicTuring machine

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10) Computational learning theory (68Q32)

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.

Recommendations

• Query automata over finite trees
• scientific article; zbMATH DE number 1008506
• scientific article; zbMATH DE number 176242
• Learning grammars and automata with queries
• Learning finite cover automata from queries
• Grammars and automata to optimize chain logic queries
• Automated inferencing
• Inferring Symbolic Automata
• Automata and Answer Set Programming

Cites work

• Aggregating inductive expertise
• Comparison of identification criteria for machine inductive inference
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• scientific article; zbMATH DE number 47903 (Why is no real title available?)
• scientific article; zbMATH DE number 1051236 (Why is no real title available?)
• scientific article; zbMATH DE number 762059 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• scientific article; zbMATH DE number 3316928 (Why is no real title available?)
• scientific article; zbMATH DE number 3365234 (Why is no real title available?)
• Inferring answers to queries
• Learning via queries
• Learning via queries and oracles
• Learning via queries in [+, <]
• ON CERTAIN EXTENSIONS OF THE ARITHMETIC OF ADDITION OF NATURAL NUMBERS
• Testing and generating infinite sequences by a finite automaton
• The Power of Pluralism for Automatic Program Synthesis
• Theories of automata on \(\omega\)-tapes: a simplified approach
• Trade-off among parameters affecting inductive inference
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(2)

• Learning via queries in [+, <]
• Learning via finitely many queries

This page was built for publication: Automata techniques for query inference machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1849855)