Runtime analysis of probabilistic programs with unbounded recursion
Copyright policy )Runtime analysis of probabilistic programs with unbounded recursion
We study termination time and recurrence time in programs with unbounded recursion, which are either randomized or operate on some statistically quantified inputs. As the underlying formal model for such programs we use probabilistic pushdown automata (pPDA) which are equivalent to probabilistic recursive state machines. We obtain tail bounds for the distribution of termination time for pPDA. We also study the recurrence time for probabilistic recursive programs that are not supposed to terminate (such as system daemons, network servers, etc.). Typically, such programs react to certain requests generated by their environment, and hence operate in finite request-service cycles. We obtain bounds for the frequency of long request-service cycles.
- Department of Computer Science University of Oxford United Kingdom
- University of Oxford United Kingdom
- Masaryk University Czech Republic
FOS: Computer and information sciences, Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.), Computer Science - Logic in Computer Science, Probability in computer science (algorithm analysis, random structures, phase transitions, etc.), Formal Languages and Automata Theory (cs.FL), Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.), Analysis of algorithms and problem complexity, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), recursive Markov chains, Computer Science - Formal Languages and Automata Theory, Formal languages and automata, Automata and formal grammars in connection with logical questions, Logic in Computer Science (cs.LO), termination time, probabilistic pushdown automata, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
FOS: Computer and information sciences, Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.), Computer Science - Logic in Computer Science, Probability in computer science (algorithm analysis, random structures, phase transitions, etc.), Formal Languages and Automata Theory (cs.FL), Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.), Analysis of algorithms and problem complexity, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), recursive Markov chains, Computer Science - Formal Languages and Automata Theory, Formal languages and automata, Automata and formal grammars in connection with logical questions, Logic in Computer Science (cs.LO), termination time, probabilistic pushdown automata, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).21 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!