Finite automata and algebraic extensions of functions fields
From MaRDI portal
(Redirected from Publication:873839)
Formal languages and automata (68Q45) (p)-adic and power series fields (11D88) Algebraic theory of languages and automata (68Q70) Automata sequences (11B85) Formal power series rings (13F25) Valuations, completions, formal power series and related constructions (associative rings and algebras) (16W60)
Abstract: We give an automata-theoretic description of the algebraic closure of the rational function field F_q(t) over a finite field, generalizing a result of Christol. The description takes place within the Hahn-Mal'cev-Neumann field of "generalized power series" over F_q. Our approach includes a characterization of well-ordered sets of rational numbers whose base p expansions are generated by a finite automaton, as well as some techniques for computing in the algebraic closure; these include an adaptation to positive characteristic of Newton's algorithm for finding local expansions of plane curves. We also conjecture a generalization of our results to several variables.
Recommendations
- Automata and algebraicity
- scientific article; zbMATH DE number 1120300
- Automata algebras
- Automata on algebraic structures
- scientific article; zbMATH DE number 3390671
- Automata in algebra
- scientific article; zbMATH DE number 3250570
- Algebraic structures of automata
- On a class of automaton algebras
- The \(p\)-adic theory of automata functions
Cites work
- scientific article; zbMATH DE number 418886 (Why is no real title available?)
- scientific article; zbMATH DE number 4021221 (Why is no real title available?)
- scientific article; zbMATH DE number 4065109 (Why is no real title available?)
- scientific article; zbMATH DE number 3657912 (Why is no real title available?)
- scientific article; zbMATH DE number 3574054 (Why is no real title available?)
- scientific article; zbMATH DE number 3070524 (Why is no real title available?)
- Algebraic Functions Over a Field of Positive Characteristic and Hadamard Products
- Algebraic functions over finite fields
- Automatic Sequences
- Ensembles presque périodiques \(k\)-reconnaissables. (Almost periodic \(k\)-recognizable sets)
- Intégration sur un cycle évanescent
- Maximal fields with valuations. I, II
- Power series and \(p\)-adic algebraic closures
- Suites algébriques, automates et substitutions
- The algebraic closure of the power series field in positive characteristic
- The theory of well-quasi-ordering: a frequently discovered concept
- Two Notes on Formal Power Series
Cited in
(20)- An analogue of Cobham’s theorem for fractals
- Automatic sequences and generalised polynomials
- Transcendence of generating functions whose coefficients are multiplicative
- Function fields in positive characteristic: expansions and Cobham's theorem
- A refinement of Christol's theorem for algebraic power series
- scientific article; zbMATH DE number 4071020 (Why is no real title available?)
- scientific article; zbMATH DE number 1109815 (Why is no real title available?)
- On the algebraicity of generalized power series
- Rational approximations to algebraic Laurent series with coefficients in a finite field
- scientific article; zbMATH DE number 1594296 (Why is no real title available?)
- Automata methods in transcendence
- Quantitative estimates for the size of an intersection of sparse automatic sets
- Substitutive systems and a finitary version of Cobham's theorem
- Rational digit systems over finite fields and Christol's theorem
- Decidability via the tilting correspondence
- Orbits of automorphism groups of fields
- Cobham's theorem and its extensions
- On vanishing coefficients of algebraic power series over fields of positive characteristic
- Semi-Galois categories. II: An arithmetic analogue of Christol's theorem
- Automatic sequences and curves over finite fields
This page was built for publication: Finite automata and algebraic extensions of functions fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q873839)
