apengell@axion.bt.co.uk (alan pengelly) (03/04/91)
I've come across the need for the concept of a `quotient automata' or quotient finite-state machine. That is given two machines A and B, what does A/B look like. Does anyone know of any work done in this area? thanks Alan
pipkinsj@cpqhou.uucp (Jeff Pipkins @Adv Dev@SE hou ) (03/06/91)
In article <1991Mar4.083941@axion.bt.co.uk> apengell@axion.bt.co.uk (alan pengelly) writes: > >I've come across the need for the concept of a `quotient automata' >or quotient finite-state machine. That is given two machines A >and B, what does A/B look like. Does anyone know of any work >done in this area? Peculiar notion. No, I've never heard of that. I would be interested in hearing why this is important; I'm really interested in FSMs. Anyway, the definition of a FSM has to do with accepting a regular set. There is a one-to-one correspondence between regular sets and FSMs. So if you're looking for operations on FSMs, first have a look at set theory. (If you can "add" two sets, you can "add" two FSMs). I don't know of any concept of a quotient of two sets. -- Jeff D. Pipkins (uunet!cpqhou!pipkinsj) My disclaimer: My opinions do not necessarily reflect those of my employer. Papaw's disclaimer: I've already told you more than I know.
zeleny@zariski.harvard.edu (Michael zeleny) (03/06/91)
In article <1991Mar05.183438.1760@cpqhou.uucp> pipkinsj@cpqhou.UUCP (Jeff Pipkins @Adv Dev@SE hou ) writes: >In article <1991Mar4.083941@axion.bt.co.uk> apengell@axion.bt.co.uk (alan pengelly) writes: >> >>I've come across the need for the concept of a `quotient automata' >>or quotient finite-state machine. That is given two machines A >>and B, what does A/B look like. Does anyone know of any work >>done in this area? > >Peculiar notion. No, I've never heard of that. I would be interested in >hearing why this is important; I'm really interested in FSMs. > >Anyway, the definition of a FSM has to do with accepting a regular set. >There is a one-to-one correspondence between regular sets and FSMs. >So if you're looking for operations on FSMs, first have a look at set >theory. (If you can "add" two sets, you can "add" two FSMs). I don't >know of any concept of a quotient of two sets. > >-- >Jeff D. Pipkins (uunet!cpqhou!pipkinsj) > >My disclaimer: My opinions do not necessarily reflect those of my employer. >Papaw's disclaimer: I've already told you more than I know. Given an equivalence relation $R$ on a set $X$, we define the equivalence class under $R$ to be the set $$\epsilon_R x = \{y: y \in X {\bf .} R(y,x) \}$$ of those elements of $X$ which are equivalent to $x$ under the relation $R$. The set of all possible equivalence classes is called the quotient set of $X$ by $R$: $$X \slash R = \{E: E \subset X {\bf .} [(\exists x)(x \in X {\bf .} E = \epsilon_R x)]\}.$$ Not a quotient of two sets, though widely used in set theory and algebra. Cheers, Michael Zeleny zeleny@math.harvard.edu P.S. Pardon my TeX
jeff@ics.uci.edu (Jeff Erickson) (03/06/91)
apengell@axion.bt.co.uk (alan pengelly) writes: | I've come across the need for the concept of a `quotient automata' | or quotient finite-state machine. That is given two machines A | and B, what does A/B look like. Does anyone know of any work | done in this area? | thanks | Alan A/B is defined as the language {x | for some y in B, xy is in A}. If A is a regular language (ie, it's accepted by a finite automaton), A/B is also a regular language. If B is also regular, it is fairly easy to construct an FA that accepts A/B. See pp.62-23 of Hopcroft and Ullman's _Introduction to Automata Theory, Languages, and Computation_ for details. They credit the proof that A/B is regular to this paper: Ginsberg, S., and E. H. Spanier [1963]. "Quotients of context free languages", Journal of the ACM, V. 10, No. 4, pp. 487-492. -- Jeff Erickson \ How much Zen would a Zen master master if a Zen master jeff@ics.uci.edu \ could master Zen? A Zen master would master what a Zen jeff@128.195.1.1 \ master could master if a Zen master could master Zen.
nico@cs.ruu.nl (Nico Verwer) (03/06/91)
In <27D4066E.23857@ics.uci.edu> jeff@ics.uci.edu (Jeff Erickson) writes: >apengell@axion.bt.co.uk (alan pengelly) writes: > >| I've come across the need for the concept of a `quotient automata' >| or quotient finite-state machine. That is given two machines A >| and B, what does A/B look like. Does anyone know of any work >| done in this area? > >A/B is defined as the language {x | for some y in B, xy is in A}. > >If A is a regular language (ie, it's accepted by a finite automaton), >A/B is also a regular language. If B is also regular, it is fairly >easy to construct an FA that accepts A/B. I've come across something similar in categorial grammars. There, string concatenation, o is interpreted as a (tensor) product. So AoB is the language { xy | x in A, y in B }. There are two quotients, a "left quotient", A\B = { y | for some x in A, xy is in B } and a "right quotient", A/B = { x | for some y in B, xy is in A }. This gives a categorial interpretation of non-commutative cancellative linear logic; The concatenation operator o is non-commutative, which gives you two quotients. A reference to categorial grammars is J. Lambek, "Categorial and Categorical Grammars", in Oehrle, Bach & wheeler (eds.), "Categorial Grammars and Natural Language Structures". I didn't read it myself, but the following reference is probably hard to find: M. Moortgat, "Categorial Logics: A Computational Perspective", in proceedings of "Computing Science in the Netherlands" 1990. There are some interesting properties of o, \ and /. Since o,\ and o,/ are adjoint functors, there are embeddings Ao(A\B) --> B and (A/B)oB --> A . Also, A\(B/C) = (A\B)/C . It shouldn't be too difficult to develop similar operators on FSM's, but I leave this as an exercise to the reader :-) . -- Nico Verwer | nico@cs.ruu.nl Dept. of Computer Science, University of Utrecht | phone: +31 30 533921 p.o. box 80.089, 3508 TB Utrecht, The Netherlands | fax: +31 30 513791
hsiang@sbhsiang.cs.sunysb.edu (J. Hsiang) (03/08/91)
In <27D4066E.23857@ics.uci.edu> jeff@ics.uci.edu (Jeff Erickson) writes: >apengell@axion.bt.co.uk (alan pengelly) writes: > >| I've come across the need for the concept of a `quotient automata' >| or quotient finite-state machine. That is given two machines A >| and B, what does A/B look like. Does anyone know of any work >| done in this area? > >A/B is defined as the language {x | for some y in B, xy is in A}. > >If A is a regular language (ie, it's accepted by a finite automaton), >A/B is also a regular language. If B is also regular, it is fairly >easy to construct an FA that accepts A/B. I thought someone should point out the following, which is well-known... It is in fact not difficult to prove that as long as A is regular, A/B is regular REGARDLESS of what B is. Take the simple case when B is regular. Let M be a DFA which accepts A. Let qi be a state of M. We denote Mi as the FA which is identical to M except that qi is the starting state of Mi. The machine M' which accepts A/B can be constructed as follows: M' is identical to M except that for each qi, qi is a final state of M' iff the intersection of L(Mi) and B is not empty. When B is any language (not even necessarily computable), the same "construction" given above can be used to obtain the appropriate M'. Of course, since the intersection may not be decidable, the proof is no longer constructive. However, one of the 2^n candidates of M', where n is the number of states of M, will accept A/B. Jieh Hsiang Department of Computer Science SUNY Stony Brook