Opened 5 years ago

Closed 4 years ago

#18089 closed enhancement (fixed)

Automaton.shannon_parry_markov_chain: New method

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

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 cheuberg

  • Branch set to u/cheuberg/fsm/transition_probabilities
  • Commit set to 3e756cab6dd4f2e51e12eee081ba43f4593e91e5
  • Status changed from new to needs_review

New commits:

3e756caTrac #18089: Automaton.transition_probabilities

comment:2 Changed 5 years ago by vdelecroix

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 cheuberg

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

  • Commit changed from 3e756cab6dd4f2e51e12eee081ba43f4593e91e5 to 8b165ddfd0b1a879cf4be8388256e6caf11a175a

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 5 years ago by cheuberg

  • Dependencies set to #18114
  • Work issues changed from merge #18114; name; refer to Perry measure to name; refer to Perry measure

comment:6 Changed 4 years ago by skropf

  • Branch changed from u/cheuberg/fsm/transition_probabilities to u/skropf/fsm/transition_probabilities

comment:7 Changed 4 years ago by skropf

  • 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 4 years ago by cheuberg

  • Description modified (diff)
  • Milestone changed from sage-6.6 to sage-6.7

comment:9 Changed 4 years ago by cheuberg

  • Branch changed from u/skropf/fsm/transition_probabilities to u/cheuberg/fsm/transition_probabilities

comment:10 Changed 4 years ago by git

  • Commit changed from 4767f8aa6757e058b8818e21304b17f8b3b6ad36 to 58d21a6849344dd2493a03d305468f690dc09298

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 4 years ago by cheuberg

  • Authors changed from Clemens Heuberger to Clemens Heuberger, Sara Kropf

comment:12 Changed 4 years ago by git

  • Commit changed from 58d21a6849344dd2493a03d305468f690dc09298 to 24b789ee0c9678949bc04d4cfcc7022ad9402eb7

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 4 years ago by skropf

  • Branch changed from u/cheuberg/fsm/transition_probabilities to u/skropf/fsm/transition_probabilities

comment:14 follow-up: Changed 4 years ago by skropf

  • Commit changed from 24b789ee0c9678949bc04d4cfcc7022ad9402eb7 to 5dc24acb8f51ad82879e9ec5120be0dbd8a72c79

For me, these changes are ok.


New commits:

5dc24acTrac 18089: Changes in the citation

comment:15 in reply to: ↑ 14 Changed 4 years ago by cheuberg

  • Reviewers set to Sara Kropf, Clemens Heuberger
  • Status changed from needs_review to positive_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 4 years ago by vbraun

  • Branch changed from u/skropf/fsm/transition_probabilities to 5dc24acb8f51ad82879e9ec5120be0dbd8a72c79
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.