The (n,k)-bounded emptiness-problem for probabilistic acceptors and related problems

DOI10.1007/BF00261257zbMath0449.03010MaRDI QIDQ1147116

Volker Claus

Publication date: 1981

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00261257

zbMATH Keywords

rational power series; emptiness-problem; limit between decidability and undecidability; probabilistic acceptors; restricted Post correspondence problem

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

03B25: Decidability of theories and sets of sentences

13F25: Formal power series rings

03D10: Turing machines and related notions

68Q99: Theory of computing