Polynomially ambiguous probabilistic automata on restricted languages

DOI10.1016/j.jcss.2022.02.002zbMath1483.68156arXiv1902.09407OpenAlexW2915637607MaRDI QIDQ2121470

Paul C. Bell

Publication date: 4 April 2022

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1902.09407

zbMATH Keywords

undecidabilityambiguitybounded languageprobabilistic finite automataformal language theory

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Finite ambiguity and finite sequentiality in weighted automata over fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unbounded-error quantum computation with small space bounds
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Probabilistic automata
• On the degree of ambiguity of finite automata
• On the equal-subset-sum problem
• Undecidable problems for probabilistic automata of fixed dimension
• Homogenization and the polynomial calculus
• The boundedness of all products of a pair of matrices is undecidable
• The freeness problem over matrix semigroups and bounded languages
• On Post correspondence problem for letter monotonic languages
• Scalar Ambiguity and Freeness in Matrix Semigroups over Bounded Languages
• Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
• On the Complexity of the Orbit Problem
• Polynomial-time algorithm for the orbit problem
• Probabilistic Automata on Finite Words: Decidable and Undecidable Problems
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Decision Problems for Probabilistic Finite Automata on Bounded Languages
• Polynomially Ambiguous Probabilistic Automata on Restricted Languages
• Probabilistic Automata of Bounded Ambiguity
• Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages
• Probabilistic automata
• Generalized Automata and Stochastic Languages
• A survey of computational complexity results in systems and control

This page was built for publication: Polynomially ambiguous probabilistic automata on restricted languages