Databases
StackOverflow2013
Postsdbo
POUsing finite automata as keys to a container
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POUsing finite automata as keys to a container
    primarykey
    data
    text
    <p>I have a problem where I really need to be able to use finite automata as the keys to an associative container. Each key should actually represent an equivalence class of automata, so that when I search, I will find an equivalent automaton (if such a key exists), even if that automaton isn't structurally identical.</p> <p>An obvious last-resort approach is of course to use linear search with an equivalence test for each key checked. I'm hoping it's possible to do a lot better than this.</p> <p>I've been thinking in terms of trying to impose an arbitrary but consistent ordering, and deriving an ordered comparison algorithm. First principles involve the sets of strings that the automata represent. Evaluate the set of possible first tokens for each automaton, and apply an ordering based on those two sets. If necessary, continue to the sets of possible second tokens, third tokens etc. The obvious problem with doing this naively is that there's an infinite number of token-sets to check before you can prove equivalence.</p> <p>I've been considering a few vague ideas - minimising the input automata first and using some kind of closure algorithm, or converting back to a regular grammar, some ideas involving spanning trees. I've come to the conclusion that I need to abandon the set-of-tokens lexical ordering, but the most significant conclusion I've reached so far is that this isn't trivial, and I'm probably better off reading up on someone elses solution.</p> <p>I've downloaded a paper from CiteSeerX - <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.7310" rel="nofollow noreferrer">Total Ordering on Subgroups and Cosets</a> - but my abstract algebra isn't even good enough to know if this is relevant yet.</p> <p>It also occurred to me that there might be some way to derive a hash from an automaton, but I haven't given this much thought yet.</p> <p>Can anyone suggest a good paper to read? - or at least let me know if the one I've downloaded is a red herring or not?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USSteve314
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POUsing finite automata as keys to a container
      1. USDavid R Tribble
      1. VTFavorite
    2. VO
      singulars
      1. POUsing finite automata as keys to a container
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POUsing finite automata as keys to a container
      1. USuser179400
      1. VTFavorite
    1. COWikipedia tells me that DFA's can be reduced to a minimal canonical form and tested for equivalence. Perhaps this minimal canonical form can be lexicographically ordered, by listing the states in a specific order based on the alphabetical order of the symbols triggering each transition, like a BFS on the graph of states? It doesn't tell me how to get to canonical form, at least not in terms I fully understand since I never studied language theory. But I think you should be hitting the textbooks on regular languages to find the algorithms.
      singulars
      1. POUsing finite automata as keys to a container
      1. USSteve Jessop
    2. COThere are certainly textbook algorithms for equivalence and minimisation, and that's the basis of my last resort linear search approach. AFAIK, there is no standard algorithm for lexical ordering. That said... probably answer coming shortly...
      singulars
      1. POUsing finite automata as keys to a container
      1. USSteve314
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload