On some decidability questions concerning supports of rational series

DOI10.1016/J.IPL.2022.106290MaRDI QIDQ2094367zbMATH OpenOpenAlexFDO

Authors Peter Kostolányi

Publication date 28 October 2022

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2022.106290

zbMATH Keywords

decidabilityformal languagesrational seriesweighted automatonPost's correspondence problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings
• Recognizability of the support of recognizable series over the semiring of the integers is undecidable
• Rational series with coefficients in a commutative ring
• Rational relations and rational series
• What's decidable about weighted automata?

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3458752 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 3633742 (Why is no real title available?)
• scientific article; zbMATH DE number 1970438 (Why is no real title available?)
• An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is Recognizable
• An algebraic characterization of semirings for which the support of every recognizable series is recognizable
• Elements of automata theory. Translated from the French by Reuben Thomas
• Handbook of weighted automata
• Noncommutative rational series with applications
• On the supports of recognizable series over a field and a single letter alphabet
• Rational and Recognisable Power Series
• Recognizability of the support of recognizable series over the semiring of the integers is undecidable
• Sequential?
• Weighted automata
• What's decidable about weighted automata?

Cited in

(3)

• On the decidability of the equivalence problem for partially commutative rational power series
• Absolute Convergence of Rational Series Is Semi-decidable
• Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings

This page was built for publication: On some decidability questions concerning supports of rational series

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