#15963 closed enhancement (fixed)
finite_state_machine: New attribute FSMState.color to prohibit merging in simplification
Reported by:  cheuberg  Owned by:  

Priority:  minor  Milestone:  sage6.2 
Component:  combinatorics  Keywords:  finite_state_machine 
Cc:  skropf  Merged in:  
Authors:  Clemens Heuberger  Reviewers:  Daniel Krenn 
Report Upstream:  N/A  Work issues:  
Branch:  2031f53 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  #15841, #15847, #15848, #15849, #15850  Stopgaps: 
Description
In some circumstances, it might be desirable to prohibit merging of states in finite state machine simplification, e.g., if there is some extra distinction between states that is not captured in outgoing transitions. Therefore, the notion of "color" of a state is introduced such that states of different colors are never merged.
Change History (7)
comment:1 Changed 8 years ago by
 Status changed from new to needs_review
comment:2 Changed 8 years ago by
 Cc dkrenn removed
 Reviewers set to Daniel Krenn
 Status changed from needs_review to positive_review
comment:3 Changed 8 years ago by
 Commit changed from 2031f53b78c88ec68b7ff2ffc252362174304601 to d51be51b8299930abc0e6b72700eca79cd978cfc
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
2d43fdd  FiniteStateMachine: add failing doctests: nonhashable colors

547968a  FiniteStateMachine.product_FiniteStateMachine, composition: fix unhashable colors

d51be51  Automaton.determinisation(): docstring on hashable colors

comment:4 followup: ↓ 6 Changed 8 years ago by
The following behaviour is undesired (docstrings says that colors are tuples of the colors of the constituent states, but this is not the case and leads to problems in Automaton.determinisation):
sage: A = Automaton([[0, 0, 0]], initial_states=[0]) sage: B = A.product_FiniteStateMachine(A, ....: lambda t1, t2: (0, None)) sage: B.states()[0].color [None, None] sage: B.determinisation() Traceback (most recent call last): ... TypeError: unhashable type: 'list' sage: A = Automaton([[0, 0, 0]], initial_states=[0]) sage: B = A.composition(A, algorithm='explorative') sage: B.states()[0].color [None, None] sage: B.determinisation() Traceback (most recent call last): ... TypeError: unhashable type: 'list'
I pushed commits correcting this and adding two more docstrings to emphasize that colors have to be hashable in order to be able to use Automaton.determinisation.
comment:5 Changed 8 years ago by
 Branch changed from u/cheuberg/fsm/state_color to d51be51b8299930abc0e6b72700eca79cd978cfc
 Resolution set to fixed
 Status changed from needs_review to closed
comment:6 in reply to: ↑ 4 Changed 8 years ago by
 Commit d51be51b8299930abc0e6b72700eca79cd978cfc deleted
Replying to cheuberg:
The following behaviour is undesired (docstrings says that colors are tuples of the colors of the constituent states, but this is not the case and leads to problems in Automaton.determinisation): ... I pushed commits correcting this and adding two more docstrings to emphasize that colors have to be hashable in order to be able to use Automaton.determinisation.
I've reviewed those > positive_review
comment:7 Changed 7 years ago by
 Branch changed from d51be51b8299930abc0e6b72700eca79cd978cfc to 2031f53b78c88ec68b7ff2ffc252362174304601
The last commit was not merged in this ticket, but at #16128.
code looks fine, doctests pass, docu checked, coverage checked
(also reviewed all its dependencies)