Results 1 to 2 of 2

Math Help - Number of path in Kripke Structure

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    Singapore
    Posts
    2

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: January 22nd 2013, 05:54 PM
  2. Class Number / Structure
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 25th 2010, 04:36 AM
  3. Clarify the number of path compnents...
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: November 8th 2009, 12:26 PM
  4. degree of a path, path homotopy.
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: March 19th 2009, 05:37 PM
  5. group structure?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 3rd 2008, 09:08 AM

Search Tags


/mathhelpforum @mathhelpforum