The (n,k)-bounded emptiness-problem for probabilistic acceptors and related problems
From MaRDI portal
Publication:1147116
DOI10.1007/BF00261257zbMath0449.03010MaRDI QIDQ1147116
Publication date: 1981
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00261257
rational power series; emptiness-problem; limit between decidability and undecidability; probabilistic acceptors; restricted Post correspondence problem
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