Publication:3056218

Publication date: 11 November 2010

minimization; polynomial; formal power series; automatic sequence; rational series; rational expression; matrix semigroup; variable-length code; non-commutative rational series; recognizable formal language

Mathematics Subject Classification ID

68Q45: Formal languages and automata

16W60: Valuations, completions, formal power series and related constructions (associative rings and algebras)

68Q70: Algebraic theory of languages and automata

68-02: Research exposition (monographs, survey articles) pertaining to computer science

15A04: Linear transformations, semilinear transformations

12K10: Semifields

16Y60: Semirings

26A12: Rate of growth of functions, orders of infinity, slowly varying functions

94A45: Prefix, length-variable, comma-free codes

15-02: Research exposition (monographs, survey articles) pertaining to linear algebra

Related Items

Linearizing the word problem in (some) free fields, Birecurrent sets, General Framework, First-Order Logic and Numeration Systems, Some Applications of Algebra to Automatic Sequences, Unnamed Item, Unnamed Item, ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES, Unnamed Item, Free (rational) derivation, Singular value automata and approximate minimization, Pebble Weighted Automata and Weighted Logics, A Factorization Theory for some Free Fields, -DEFORMED RATIONALS AND -CONTINUED FRACTIONS, The finiteness problem for monoids of morphisms, Formulae and Asymptotics for Coefficients of Algebraic Functions, The Generalized Rank of Trace Languages, A Final Coalgebra for k-regular Sequences, Stable Noncommutative Polynomials and Their Determinantal Representations, Growth degree classification for finitely generated semigroups of integer matrices, The quaternionic weighted zeta function of a graph, Free iterative and iteration \(K\)-semialgebras, Mutating seeds: types \(\mathbb{A}\) and \(\tilde{\mathbb{A}}\), The quaternionic second weighted zeta function of a graph and the Study determinant, Relations on words, Cayley graphs and automatic sequences, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Free loci of matrix pencils and domains of noncommutative rational functions, Absolute convergence of rational series is semi-decidable, Linear recurrence relations for cluster variables of affine quivers., The set of realizations of a max-plus linear sequence is semi-polyhedral, On domains of noncommutative rational functions, Noncommutative rational functions invariant under the action of a finite solvable group, \(L^2\)-Betti numbers arising from the lamplighter group, Geometry of free loci and factorization of noncommutative polynomials, Matrix coefficient realization theory of noncommutative rational functions, Generalization bounds for learning weighted automata, On the supports of recognizable series over a field and a single letter alphabet, Robustness of Pisot-regular sequences, Noncommutative polynomials describing convex sets, Hopf algebra structure of generalized quasi-symmetric functions in partially commutative variables, Noncommutative rational Pólya series, A standard form in (some) free fields: how to construct minimal linear representations, Determinisability of unary weighted automata over the rational numbers, Regular sequences and synchronized sequences in abstract numeration systems, Scattering in quantum dots via noncommutative rational functions, Decidability and \(k\)-regular sequences, The carry propagation of the successor function, Multipartite rational functions, The Coxeter relations and KP map for non-commuting symbols, Quasi-universal \(k\)-regular sequences, Extension of the Bessmertnyĭ realization theorem for rational functions of several complex variables, A new approach to the 2-regularity of the \(\ell\)-abelian complexity of 2-automatic sequences, Bianalytic free maps between spectrahedra and spectraballs, Local laws for polynomials of Wigner matrices, Context-free coalgebras, Character theory of monoids over an arbitrary field., The inversion height of the free field is infinite., Abelian-square-rich words, Null- and positivstellensätze for rationally resolvable ideals, Composition of quasi-polynomial maps, Farey boat: continued fractions and triangulations, modular group and polygon dissections, On the factorization of non-commutative polynomials (in free associative algebras), Adding pebbles to weighted automata: easy specification \& efficient evaluation, A note on the factorization conjecture, Plurisubharmonic noncommutative rational functions, Rational elements of summation semirings, On the Rademacher Complexity of Weighted Automata, COMPLETELY REDUCIBLE SETS, Conway and iteration hemirings Part 1, Unnamed Item, Partial Conway and Iteration Semiring-Semimodule Pairs, The cyclicity problem for the images of Q-rational series, Evaluating Generating Functions for Periodic Multiple Polylogarithms via Rational Chen–Fliess Series, Mechanical Proofs of Properties of the Tribonacci Word, Absolute Convergence of Rational Series Is Semi-decidable