Opened 8 years ago

Closed 8 years ago

Last modified 7 years ago

#15963 closed enhancement (fixed)

finite_state_machine: New attribute FSMState.color to prohibit merging in simplification

Reported by: cheuberg Owned by:
Priority: minor Milestone: sage-6.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:

Status badges

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 cheuberg

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by dkrenn

  • Cc dkrenn removed
  • Reviewers set to Daniel Krenn
  • Status changed from needs_review to positive_review

code looks fine, doctests pass, docu checked, coverage checked

(also reviewed all its dependencies)

comment:3 Changed 8 years ago by git

  • 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:

2d43fddFiniteStateMachine: add failing doctests: non-hashable colors
547968aFiniteStateMachine.product_FiniteStateMachine, composition: fix unhashable colors
d51be51Automaton.determinisation(): docstring on hashable colors

comment:4 follow-up: Changed 8 years ago by 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):

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 vbraun

  • 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 dkrenn

  • 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 cheuberg

  • Branch changed from d51be51b8299930abc0e6b72700eca79cd978cfc to 2031f53b78c88ec68b7ff2ffc252362174304601

The last commit was not merged in this ticket, but at #16128.

Note: See TracTickets for help on using tickets.