Polynomially ambiguous unary weighted automata over fields

DOI10.1007/S00224-022-10107-7MaRDI QIDQ6038711zbMATH OpenOpenAlexFDO

Authors Peter Kostolányi

Publication date 2 May 2023

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-022-10107-7

zbMATH Keywords

difference equationfieldformal power serieslinear recurrencepolynomial ambiguityweighted automaton

Mathematics Subject Classification ID

Computer science (68-XX) Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Determinisability of unary weighted automata over the rational numbers
• On finite and polynomial ambiguity of weighted tree automata
• On determinism and unambiguity of weighted two-way automata
• Noncommutative rational Pólya series
• Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata

Cites work

• A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
• Ambiguity hierarchies for weighted tree automata
• Copyless cost-register automata: structure, expressiveness, and closure properties
• Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
• Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata
• Elements of automata theory. Translated from the French by Reuben Thomas
• Field Theory
• Finite automata
• Handbook of weighted automata
• scientific article; zbMATH DE number 193132 (Why is no real title available?)
• scientific article; zbMATH DE number 3458752 (Why is no real title available?)
• scientific article; zbMATH DE number 2171469 (Why is no real title available?)
• scientific article; zbMATH DE number 7561720 (Why is no real title available?)
• scientific article; zbMATH DE number 7407779 (Why is no real title available?)
• scientific article; zbMATH DE number 7650822 (Why is no real title available?)
• Noncommutative rational Pólya series
• Noncommutative rational series with applications
• On finite and polynomial ambiguity of weighted tree automata
• On the definition of a family of automata
• On the degree of ambiguity of finite automata
• Polynomially Ambiguous Probabilistic Automata on Restricted Languages
• Rational and Recognisable Power Series
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Semirings and Formal Power Series
• Sequential?
• The Generalized Vandermonde Matrix
• Weighted automata

Cited in

(2)

• Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
• Finitely ambiguous and finitely sequential weighted automata over fields

This page was built for publication: Polynomially ambiguous unary weighted automata over fields

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