LOGICAL CHARACTERIZATION OF RECOGNIZABLE SETS OF POLYNOMIALS OVER A FINITE FIELD

DOI10.1142/S0129054111008878zbMath1252.03022MaRDI QIDQ2909094

Laurent Waxweiler, Michel Rigo

Publication date: 29 August 2012

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

zbMATH Keywords

first-order theoryfirst-order logicdecidabilityrecognizable setCobham's theorempolynomial over a finite field

Mathematics Subject Classification ID

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

Related Items (3)

Rational digit systems over finite fields and Christol's theorem ⋮ Recognizable sets of power series over finite fields ⋮ Defining Multiplication in Some Additive Expansions of Polynomial Rings

Cites Work

• Unnamed Item
• Unnamed Item
• The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
• Independent numeration systems and syndeticity
• 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
• Weak Second‐Order Arithmetic and Finite Automata
• On an exponential predicate in polynomials over finite fields
• Decidability of Sub-theories of Polynomials over a Finite Field
• Automatic Sequences
• Elimination theory for addition and the frobenius map in polynomial rings
• Unrecognizable Sets of Numbers
• On the base-dependence of sets of numbers recognizable by finite automata

This page was built for publication: LOGICAL CHARACTERIZATION OF RECOGNIZABLE SETS OF POLYNOMIALS OVER A FINITE FIELD