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

Priority:  major  Milestone:  sage6.7 
Component:  finite state machines  Keywords:  regular language, automaton, probabilities 
Cc:  Sara Kropf, Daniel Krenn  Merged in:  
Authors:  Clemens Heuberger, Sara Kropf  Reviewers:  Sara Kropf, Clemens Heuberger 
Report Upstream:  N/A  Work issues:  
Branch:  5dc24ac (Commits, GitHub, GitLab)  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 7 years ago by
Branch:  → u/cheuberg/fsm/transition_probabilities 

Commit:  → 3e756cab6dd4f2e51e12eee081ba43f4593e91e5 
Status:  new → needs_review 
comment:2 Changed 7 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 7 years ago by
Status:  needs_review → needs_work 

Work issues:  → 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 7 years ago by
Commit:  3e756cab6dd4f2e51e12eee081ba43f4593e91e5 → 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 7 years ago by
Dependencies:  → #18114 

Work issues:  merge #18114; name; refer to Perry measure → name; refer to Perry measure 
comment:6 Changed 7 years ago by
Branch:  u/cheuberg/fsm/transition_probabilities → u/skropf/fsm/transition_probabilities 

comment:7 Changed 7 years ago by
Commit:  8b165ddfd0b1a879cf4be8388256e6caf11a175a → 4767f8aa6757e058b8818e21304b17f8b3b6ad36 

Dependencies:  #18114 → #18114, #18331 
Description:  modified (diff) 
Status:  needs_work → needs_review 
Summary:  Automaton.transition_probabilities: New method → Automaton.shannon_parry_markov_chain: New method 
Work issues:  name; refer to Perry measure 
I changed the name, referred to Parry and Shannon and included the stationary distribution.
comment:8 Changed 7 years ago by
Description:  modified (diff) 

Milestone:  sage6.6 → sage6.7 
comment:9 Changed 7 years ago by
Branch:  u/skropf/fsm/transition_probabilities → u/cheuberg/fsm/transition_probabilities 

comment:10 Changed 7 years ago by
Commit:  4767f8aa6757e058b8818e21304b17f8b3b6ad36 → 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 7 years ago by
Authors:  Clemens Heuberger → Clemens Heuberger, Sara Kropf 

comment:12 Changed 7 years ago by
Commit:  58d21a6849344dd2493a03d305468f690dc09298 → 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 7 years ago by
Branch:  u/cheuberg/fsm/transition_probabilities → u/skropf/fsm/transition_probabilities 

comment:14 followup: 15 Changed 7 years ago by
Commit:  24b789ee0c9678949bc04d4cfcc7022ad9402eb7 → 5dc24acb8f51ad82879e9ec5120be0dbd8a72c79 

comment:15 Changed 7 years ago by
Reviewers:  → Sara Kropf, Clemens Heuberger 

Status:  needs_review → positive_review 
comment:16 Changed 7 years ago by
Branch:  u/skropf/fsm/transition_probabilities → 5dc24acb8f51ad82879e9ec5120be0dbd8a72c79 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
Trac #18089: Automaton.transition_probabilities