Superelliptic curve

2014-02-03T00:05:55Z

173.13.181.233: /* Ramification */ Minor fix

[[File:Matrix Signal-Flow Graph.png|thumb|A multi-input, multi-output system represented as a noncommutative matrix signal-flow graph.]]

In [[automata theory]] and [[control theory]], branches of [[mathematics]], [[theoretical computer science]] and [[systems engineering]], a '''noncommutative signal-flow graph''' is a tool for modeling{{sfn|Lorens|1964}} interconnected systems and state machines by mapping the edges of a [[directed graph]] to a [[ring (mathematics)|ring]] or [[semiring]].

A single edge '''weight''' might represent an array of [[impulse response]]s of a complex system (see figure to the right),{{sfn|Riegle|Lin|1972}} or a character from an [[Alphabet (computer science)|alphabet]] picked off the [[Finite state transducer|input tape]] of a finite automaton,{{sfn|Brzozowski|McCluskey|1963}} while the graph might represent the flow of information or state transitions.

As diverse as these applications are, they share much of the same underlying theory.{{sfn|Book|Even|Greibach|Ott|1971}}{{sfn|Pliam|Lee|1995}}

==Definition==
[[File:Signal-Flow Graph Fragment.png|thumb|Signal-flow graph fragment.]]

Consider ''n'' equations involving ''n''+1 variables {''x''0, ''x''1,...,''x''n}.

:<math>x_i = \sum_{j=0}^n a_{ij}x_j, \;\;\; 1\leq i \leq n,</math>

with ''a''ij elements in a ring or semiring ''R''. The free variable ''x''0 corresponds to a source vertex ''v''0, thus having no defining equation. Each equation corresponds to a fragment of a [[directed graph]] ''G''=(''V'',''E'') as show in the figure.

The edge weights define a function ''f'' from ''E'' to ''R''. Finally fix an output vertex ''vm''. A signal-flow graph is the collection of this data ''S'' = (''G''=(''V'',''E''), ''v0'',''vm'' <math>\in</math> ''V'', ''f'' : ''E'' → ''R''). The equations may not have a solution, but when they do,

:<math>x_m = T x_0,</math>

with ''T'' an element of ''R'' called the '''gain'''.

==Successive Elimination==
{{expand section|date=May 2012}}

==Return Loop Method==
There exist several{{sfn|Riegle|Lin|1972}} noncommutative generalizations of [[Mason's rule]]. The most common is the '''return loop method''' (sometimes called the '''forward return loop method (FRL)''', having a dual '''backward return loop method (BRL)'''). The first rigorous proof is attributed to Riegle,{{sfn|Riegle|Lin|1972}} so it is sometimes called '''Riegle's rule'''.{{sfn|Andaloussi|Chalh|Sueur|2006|pp=2962}}

As with Mason's rule, these gain expressions combine terms in a graph-theoretic manner (loop-gains, path products, etc). They are known to hold over an arbitrary noncommutative ring and over the semiring of regular expressions.{{sfn|Pliam|Lee|1995}}

===Formal Description===
The method starts by enumerating all paths from input to output, indexed by ''j'' <math>\in</math> ''J''. We use the following definitions:

* The ''j''-th '''path product''' is (by abuse of notation) a tuple of ''kj'' edge weights along it:

::::<math>p_j = (w^{(j)}_{k_j},\ldots, w^{(j)}_2, w^{(j)}_1).</math>

* To '''split''' a vertex ''v'' is to replace it with a source and sink respecting the original incidence and weights (this is the inverse of the graph morphism taking source and sink to ''v'').
* The '''loop gain''' of a vertex ''v'' w.r.t. a subgraph ''H'' is the gain from source to sink of the signal-flow graph split at ''v'' after removing all vertices not in ''H''.
* Each path defines an ordering of vertices along it. The along path ''j'', the ''i''-th '''FRL (BRL) node factor''' is (1-''Si(j)'')−1 where ''Si(j)'' is the loop gain of the ''i''-th vertex along the ''j''-th w.r.t. the subgraph obtained by removing ''v''0 and all vertices ahead of (behind) it.

The contribution of the ''j''-th path to the gain is the product along the path, alternating between the path product weights
and the node factors:

:<math>T_j = \prod_{i=k_j}^1 (1-S^{(j)}_i)^{-1} w^{(j)}_i,</math>

so the total gain is

:<math>T = \sum_{j\in J} T_j.</math>

===An Example===
[[File:FRL BRL Example.png|thumb|A noncommutative signal-flow graph from ''x'' to ''z'']]

Consider the signal-flow graph shown. From ''x'' to ''z'', there are two path products: (''d'') and (''e,a''). Along (''d''), the FRL and BRL contributions coincide as both share same loop gain (whose split reappears in the upper right of the table below):

:<math>f+e(1-b)^{-1}c,</math>

Multiplying its node factor and path weight, its gain contribution is

:<math>T_d = \left[1 - f - e(1-b)^{-1}c \right]^{-1}d.</math>

Along path (''e,a''), FRL and BRL differ slightly, each having distinct splits of vertices ''y'' and ''z'' as shown in the following table.

:[[File:Return Loop Split Table.png|540px]]

Adding to ''Td'', the alternating product of node factors and path weights, we obtain two gain expressions:

:<math>T^{(FRL)} = \left[1 - f - e(1-b)^{-1}c \right]^{-1}d + \left[1 - f - e(1-b)^{-1}c \right]^{-1}e(1-b)^{-1}a,</math>

and

:<math>T^{(BRL)} = \left[1 - f - e(1-b)^{-1}c \right]^{-1}d + (1-f)^{-1}e\left[1 - b - c(1-f)^e\right]^{-1}a,</math>

These values are easily seen to be the same using identities (''ab'')−1 = ''b''−1''a''−1 and ''a''(1-''ba'')−1=(1-''ab'')−1''a''.

==Applications==

===Matrix Signal-Flow Graphs===
Consider equations

:<math>y_i=\sum_{j=1}^2 a_{ij} x_j + \sum_{j=1}^2 b_{ij}y_j</math>

and

:<math>z_i=\sum_{j=1}^2 c_{ij} y_j,</math>

This system could be modeled as scalar signal-flow graph with multiple inputs and outputs. But, the variables naturally fall into layers, which can be collected into vectors
''x''=(''x''1,''x''2)''t''
''y''=(''y''1,''y''2)''t'' and
''z''=(''z''1,''z''2)''t''.
This results in much simpler '''matrix signal-flow graph''' as shown in the figure at the top of the article.

Applying the forward return loop method is trivial as there's a single path product (''C'',''A'') with a single loop-gain ''B'' at ''y''. Thus as a matrix, this system has a very compact representation of its input-output map

:<math>T = C(1-B)^{-1}A.</math>

===Finite Automata===
[[File:Automaton as Signal-Flow Graph.png|thumb|Representation of a finite automaton as a (noncommutative) signal flow graph over a semiring.]]

An important kind of noncommutative signal-flow graph is a finite state [[automaton]] over an alphabet <math>\Sigma</math>.{{sfn|Brzozowski|McCluskey|1963}}{{sfn|Book|Even|Greibach|Ott|1971}}

Serial connections correspond to the concatenation of words, which can be extended to subsets of the [[free monoid]] <math>\Sigma^*</math>. For ''A'', ''B'' <math>\subseteq\Sigma^*</math>

:<math>A \cdot B = \{ab \mid a\in A, b\in B\}.</math>

Parallel connections correspond to [[set union]], which in this context is often written ''A''+''B''.

Finally, self-loops naturally correspond to the [[Kleene closure]]

:<math>A^* = \{\lambda\} + A + AA + AAA + \cdots,</math>

where <math>\lambda</math> is the [[empty word]]. The similarity to the infinite geometric series

:<math>(1-x)^{-1} = 1 + x + x^2 + x^3 \cdots,</math>

is more than superficial, as expressions of this form serve as 'inversion' in this [[semiring]].{{sfn|Kuich|Salomaa|1985}}

In this way, the subsets of <math>\Sigma^*</math> built of from finitely many of these three operations can be identified with the [[semiring]] of [[regular expressions]]. Similarly, finite graphs whose edges are weighted by subsets of <math>\Sigma^*</math> can be identified with finite automata, though generally that theory starts with [[Singleton (mathematics)|singleton]] sets as in the figure.

This automaton is deterministic so we can unambiguously enumerate paths via words. Using the return loop method, path contributions are:

* path ''ab'', has node factors (''c''*, <math>\lambda</math>), yielding gain contribution

::<math>ac^*b,</math>

* path ''ada'', has node factors (''c''*, ''c''*, <math>\lambda</math>), yielding gain contribution

::<math>ac^*dc^*a,</math>

* path ''ba'', has node factors (''c''*, <math>\lambda</math>), yielding gain contribution

::<math>bc^*a.</math>

Thus the [[Formal language|language]] accepted by this automaton (the gain of its signal-flow graph) is the sum of these terms

:<math>L = ac^*b+ac^*dc^*a+bc^*a.</math>

==Historical Notes==
{{expand section|date=May 2012}}

==See also==
*[[Signal-flow graph]]
*[[Mason's rule]]
*[[Finite automata]]
*[[Regular expressions]]

==Notes==
{{reflist}}

== References ==
*{{cite conference
| ref=harv
| title=Infinite zero of linear time varying bond-graph models: Graphical rules
| last1=Andaloussi
| first1=C.
| last2=Chalh
| first2=Z.
| last3=Sueur
| first3=C.
| booktitle=Computer Aided Control System Design, 2006 IEEE International Conference on Control Applications
| pages=2962–2967
| year=2006
| url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4777109
}}
*{{cite journal
| ref=harv
| last1=Book
| first1=Ronald
| last2= Even
| first2=Shimon
| last3= Greibach
| first3=Sheila
| last4= Ott
| first4=Gene
| title=Ambiguity in graphs and expressions
| journal=IEEE Transactions on Computers
| volume=100
| number=2
| pages=149–153
| year=1971
| publisher=IEEE
| url=http://www.diku.dk/hjemmesider/ansatte/henglein/papers/book1971.pdf
}}
*{{cite journal
| ref=harv
| last1=Brzozowski
| first1=J.A.
| last2=McCluskey Jr.
| first2= E.J.
| title=Signal flow graph techniques for sequential circuit state diagrams
| journal=IEEE Transactions on Electronic Computers
| publisher=IEEE
| number=2
| pages=67–76
| year=1963
| url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4037802
}}
*{{cite journal
| ref=harv
| title=A new normal-form theorem for context-free phrase structure grammars
| last=Greibach
| first=Sheila
| journal=Journal of the ACM
| volume=12
| number=1
| pages=42–52
| year=1965
| publisher=ACM
| url=http://dl.acm.org/citation.cfm?id=321254
}}
*{{cite book
| ref=harv
| last1=Kuich
| first1=Werner
| last2=Salomaa
| first2=Arto
| title=Semirings, automata and languages
| year=1985
| publisher=Springer-Verlag
}}
*{{cite book
| ref=harv
| last=Lorens
| first=Charles S.
| title=Flowgraphs: For the Modeling and Analysis of Linear Systems
| year=1964
| publisher=McGraw-Hill
}}
*{{cite journal
| ref=harv
| last1=Pliam
| first1=John
| last2=Lee
| first2=E. Bruce
| title=On the global properties of interconnected systems
| journal=IEEE Transactions on Circuits and Systems I: Fund. Theory and Apps
| volume=42
| number=12
| pages=1013–1017
| year=1995
| publisher=IEEE
| url=http://www.atbash.com/node/8
}}
*{{cite journal
| ref=harv
| last1=Riegle
| first1=Daryle
| last2=Lin
| first2=P.M.
| title=Matrix signal flow graphs and an optimum topological method for evaluating their gains
| journal=IEEE Transactions on Circuit Theory
| volume=19
| number=5
| pages=427–435
| year=1972
| publisher=IEEE
| url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1083542
}}

[[Category:Control theory]]
[[Category:Automata theory]]

formulasearchengine - User contributions [en]

Superelliptic curve