search

coli-saar / alto

Alto, the Algebraic Language Toolkit
Other
16 stars 2 forks source link

isCyclic is very inefficient and only works correctly when applied to concrete automata #16

Closed akoehn closed 8 years ago

akoehn commented 8 years ago

Original report by Christoph Teichmann (Bitbucket: cteichmann, GitHub: CTNLP).

isCyclic may revisit states again that it has already explored, which makes it very inefficient. It also uses a fixed array to keep track of the states which have been seen on the current path down towards a terminal, which is initialized at the beginning for the size of the states known at that point, which means that the code does not work for lazy automata.

akoehn commented 8 years ago

Original comment by Christoph Teichmann (Bitbucket: cteichmann, GitHub: CTNLP).

Fixed in commit: (https://bitbucket.org/tclup/alto/commits/6c91aef6ad2fb3a9c362dd45bdf8adaf19951953). Replaced the array of nodes seen on the current exploration path with a map from seen nodes to their descendants. When a cycle exists a node will find itself as its descendant, then isCyclic returns true.

akoehn commented 8 years ago

Original changes by Christoph Teichmann (Bitbucket: cteichmann, GitHub: CTNLP).

set assignee_account_id to "557058:bb4f9100-7c0a-40a8-9758-25ab89d7e1c4"; set assignee to "cteichmann"

akoehn commented 8 years ago

Original changes by Christoph Teichmann (Bitbucket: cteichmann, GitHub: CTNLP).

changed state from "new" to "resolved"