Opened 5 years ago
Closed 5 years ago
#18089 closed enhancement (fixed)
Automaton.shannon_parry_markov_chain: New method
Reported by:  cheuberg  Owned by:  

Priority:  major  Milestone:  sage6.7 
Component:  finite state machines  Keywords:  regular language, automaton, probabilities 
Cc:  skropf, dkrenn  Merged in:  
Authors:  Clemens Heuberger, Sara Kropf  Reviewers:  Sara Kropf, Clemens Heuberger 
Report Upstream:  N/A  Work issues:  
Branch:  5dc24ac (Commits)  Commit:  5dc24acb8f51ad82879e9ec5120be0dbd8a72c79 
Dependencies:  #18114, #18331  Stopgaps: 
Description (last modified by )
Given an automaton, define transition probabilities such that all paths weighted with these probabilities have the same weight. The transition probabilities are the Parry measure.
Change History (16)
comment:1 Changed 5 years ago by
 Branch set to u/cheuberg/fsm/transition_probabilities
 Commit set to 3e756cab6dd4f2e51e12eee081ba43f4593e91e5
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
Hello,
The probabilities that you can define on the edges of a graph are far from being unique... having such method called transition_probabilities
is really vague (not mentioning that it does return another graph and not probabilities).
The definition should be precise and is quite standard: it is simply the Parry measure.
Vincent
comment:3 Changed 5 years ago by
 Status changed from needs_review to needs_work
 Work issues set to merge #18114; name; refer to Perry measure
Vincent, thank you for your remarks which will be taken into account. Apart from that, #18114 needs to be merged in order to avoid a merge conflict.
comment:4 Changed 5 years ago by
 Commit changed from 3e756cab6dd4f2e51e12eee081ba43f4593e91e5 to 8b165ddfd0b1a879cf4be8388256e6caf11a175a
Branch pushed to git repo; I updated commit sha1. New commits:
66a0612  method for extending an automaton to a transducer

ebe8c7b  added tests to check that A.transducer(...).input_projection gives A

b604319  improve docstring according to comments on trac

f209b0f  rename Automaton.transducer to Automaton.with_output

06842f6  additional doctests/examples

cdcd3c0  seealsoblocks

8b165dd  Merge branch 't/18114/fsm/automatontotransducer' into fsm/transition_probabilities

comment:5 Changed 5 years ago by
 Dependencies set to #18114
 Work issues changed from merge #18114; name; refer to Perry measure to name; refer to Perry measure
comment:6 Changed 5 years ago by
 Branch changed from u/cheuberg/fsm/transition_probabilities to u/skropf/fsm/transition_probabilities
comment:7 Changed 5 years ago by
 Commit changed from 8b165ddfd0b1a879cf4be8388256e6caf11a175a to 4767f8aa6757e058b8818e21304b17f8b3b6ad36
 Dependencies changed from #18114 to #18114, #18331
 Description modified (diff)
 Status changed from needs_work to needs_review
 Summary changed from Automaton.transition_probabilities: New method to Automaton.shannon_parry_markov_chain: New method
 Work issues name; refer to Perry measure deleted
I changed the name, referred to Parry and Shannon and included the stationary distribution.
comment:8 Changed 5 years ago by
 Description modified (diff)
 Milestone changed from sage6.6 to sage6.7
comment:9 Changed 5 years ago by
 Branch changed from u/skropf/fsm/transition_probabilities to u/cheuberg/fsm/transition_probabilities
comment:10 Changed 5 years ago by
 Commit changed from 4767f8aa6757e058b8818e21304b17f8b3b6ad36 to 58d21a6849344dd2493a03d305468f690dc09298
Branch pushed to git repo; I updated commit sha1. New commits:
9dffe20  Trac #18089: Reword docstring

51d5898  Trac #18089: enforce deterministic transducer, doctests for aperiodic and strongly connected

70cc536  Trac #18089: All states must be final

58d21a6  Trac #18089: list all assumptions in docstring

comment:11 Changed 5 years ago by
comment:12 Changed 5 years ago by
 Commit changed from 58d21a6849344dd2493a03d305468f690dc09298 to 24b789ee0c9678949bc04d4cfcc7022ad9402eb7
Branch pushed to git repo; I updated commit sha1. New commits:
9fcae9e  Trac #18331: import FSMState

ce5d3bb  Trac #18331: Minor rewordings of documentation

2c31e70  Trac #18331: Iterate over iter_states() instead of .states()

435d8f6  Trac #18331: adapt doctest/sources due to ignored doctests in new attribute

24b789e  Trac #18089: Merge #18331 to fix failing doctest

comment:13 Changed 5 years ago by
 Branch changed from u/cheuberg/fsm/transition_probabilities to u/skropf/fsm/transition_probabilities
comment:14 followup: ↓ 15 Changed 5 years ago by
 Commit changed from 24b789ee0c9678949bc04d4cfcc7022ad9402eb7 to 5dc24acb8f51ad82879e9ec5120be0dbd8a72c79
comment:15 in reply to: ↑ 14 Changed 5 years ago by
 Reviewers set to Sara Kropf, Clemens Heuberger
 Status changed from needs_review to positive_review
comment:16 Changed 5 years ago by
 Branch changed from u/skropf/fsm/transition_probabilities to 5dc24acb8f51ad82879e9ec5120be0dbd8a72c79
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Trac #18089: Automaton.transition_probabilities