# Math Help - Number of path in Kripke Structure

1. ## Number of path in Kripke Structure

Given an acyclic kripke structure (Kripke structure (model checking) - Wikipedia, the free encyclopedia), is the number of possible paths (path that start from initial state and ends in final state) exponential to the number of states? If yes, what is the simple argument for it (just few sentences), or is there any references that mentioned this?

2. ## Re: Number of path in Kripke Structure

The finite Kripke structure defined in that Wikipedia page cannot be acyclic because the transition relation is left-total.

Try searching for "number of paths in a directed acyclic graph" (DAG). For example, the graph shown in this answer has the number of paths exponential in the number of vertices.