Logical characterization of recognizable sets of polynomials over a finite field

DOI10.1142/S0129054111008878MaRDI QIDQ2909094zbMATH OpenFDO

Authors Laurent Waxweiler, Michel Rigo

Publication date 29 August 2012

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054111008878

zbMATH Keywords

Cobham's theoremdecidabilityfirst-order logicfirst-order theorypolynomial over a finite fieldrecognizable set

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Polynomials over finite fields (11T06) Decidability (number-theoretic aspects) (11U05)

Recommendations

• Syntactical and automatic properties of sets of polynomials over finite fields
• Recursively enumerable sets of polynomials over a finite field
• A theorem on sets of polynomials over a finite field
• On value sets of polynomials over a finite field
• scientific article; zbMATH DE number 1866863
• Value Sets of Polynomials Over Finite Fields
• Polynomial spaces over finite fields
• Polynomials over finite fields with a given value set
• Decidability of sub-theories of polynomials over a finite field
• Polynomial multiplicities over finite fields and intersection sets

Cites work

• Automatic Sequences
• Decidability of sub-theories of polynomials over a finite field
• Elimination theory for addition and the frobenius map in polynomial rings
• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• Independent numeration systems and syndeticity
• On an exponential predicate in polynomials over finite fields
• On the base-dependence of sets of numbers recognizable by finite automata
• Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
• Syntactical and automatic properties of sets of polynomials over finite fields
• The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
• Unrecognizable Sets of Numbers
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(6)

• Recognizable sets of power series over finite fields
• Syntactical and automatic properties of sets of polynomials over finite fields
• Uniform families of polynomial equations over a finite field and structures admitting an Euler characteristic of definable sets.
• Defining multiplication in some additive expansions of polynomial rings
• Generalized hex and logical characterizations of polynomial space
• Rational digit systems over finite fields and Christol's theorem

This page was built for publication: Logical characterization of recognizable sets of polynomials over a finite field

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