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: sage-6.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:

Status badges

Description (last modified by Clemens Heuberger)

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 Clemens Heuberger

Branch: u/cheuberg/fsm/transition_probabilities
Commit: 3e756cab6dd4f2e51e12eee081ba43f4593e91e5
Status: newneeds_review

New commits:

3e756caTrac #18089: Automaton.transition_probabilities

comment:2 Changed 7 years ago by Vincent Delecroix

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 Clemens Heuberger

Status: needs_reviewneeds_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 git

Commit: 3e756cab6dd4f2e51e12eee081ba43f4593e91e58b165ddfd0b1a879cf4be8388256e6caf11a175a

Branch pushed to git repo; I updated commit sha1. New commits:

66a0612method for extending an automaton to a transducer
ebe8c7badded tests to check that A.transducer(...).input_projection gives A
b604319improve docstring according to comments on trac
f209b0frename Automaton.transducer to Automaton.with_output
06842f6additional doctests/examples
cdcd3c0seealso-blocks
8b165ddMerge branch 't/18114/fsm/automaton-to-transducer' into fsm/transition_probabilities

comment:5 Changed 7 years ago by Clemens Heuberger

Dependencies: #18114
Work issues: merge #18114; name; refer to Perry measurename; refer to Perry measure

comment:6 Changed 7 years ago by Sara Kropf

Branch: u/cheuberg/fsm/transition_probabilitiesu/skropf/fsm/transition_probabilities

comment:7 Changed 7 years ago by Sara Kropf

Commit: 8b165ddfd0b1a879cf4be8388256e6caf11a175a4767f8aa6757e058b8818e21304b17f8b3b6ad36
Dependencies: #18114#18114, #18331
Description: modified (diff)
Status: needs_workneeds_review
Summary: Automaton.transition_probabilities: New methodAutomaton.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 Clemens Heuberger

Description: modified (diff)
Milestone: sage-6.6sage-6.7

comment:9 Changed 7 years ago by Clemens Heuberger

Branch: u/skropf/fsm/transition_probabilitiesu/cheuberg/fsm/transition_probabilities

comment:10 Changed 7 years ago by git

Commit: 4767f8aa6757e058b8818e21304b17f8b3b6ad3658d21a6849344dd2493a03d305468f690dc09298

Branch pushed to git repo; I updated commit sha1. New commits:

9dffe20Trac #18089: Reword docstring
51d5898Trac #18089: enforce deterministic transducer, doctests for aperiodic and strongly connected
70cc536Trac #18089: All states must be final
58d21a6Trac #18089: list all assumptions in docstring

comment:11 Changed 7 years ago by Clemens Heuberger

Authors: Clemens HeubergerClemens Heuberger, Sara Kropf

comment:12 Changed 7 years ago by git

Commit: 58d21a6849344dd2493a03d305468f690dc0929824b789ee0c9678949bc04d4cfcc7022ad9402eb7

Branch pushed to git repo; I updated commit sha1. New commits:

9fcae9eTrac #18331: import FSMState
ce5d3bbTrac #18331: Minor rewordings of documentation
2c31e70Trac #18331: Iterate over iter_states() instead of .states()
435d8f6Trac #18331: adapt doctest/sources due to ignored doctests in new attribute
24b789eTrac #18089: Merge #18331 to fix failing doctest

comment:13 Changed 7 years ago by Sara Kropf

Branch: u/cheuberg/fsm/transition_probabilitiesu/skropf/fsm/transition_probabilities

comment:14 Changed 7 years ago by Sara Kropf

Commit: 24b789ee0c9678949bc04d4cfcc7022ad9402eb75dc24acb8f51ad82879e9ec5120be0dbd8a72c79

For me, these changes are ok.


New commits:

5dc24acTrac 18089: Changes in the citation

comment:15 in reply to:  14 Changed 7 years ago by Clemens Heuberger

Reviewers: Sara Kropf, Clemens Heuberger
Status: needs_reviewpositive_review

Replying to skropf:

New commits:

5dc24acTrac 18089: Changes in the citation

Fine, thank you.

Trac's automerge fails for unknown reasons. I checked that this branch merges cleanly with 6.9.beta0.

comment:16 Changed 7 years ago by Volker Braun

Branch: u/skropf/fsm/transition_probabilities5dc24acb8f51ad82879e9ec5120be0dbd8a72c79
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.