LaTeX Finite Automata and State Diagrams with Tikz
1–10 of 36 posts
Re: LaTeX Finite Automata and State Diagrams with Tikz
#2I loved using Tikz for my Discrete Math homework. I was so proud of how pretty the DFA's looked :)
Re: LaTeX Finite Automata and State Diagrams with Tikz
#3DFAs and NFAs may seem like academic novelties but they are amazingly powerful for certain problems.
For example, naively searching a string of length N for P different substrings will yield an algorithm that has roughly O(N * P) worst case time complexity.
But implementing that algorithm as a DFA yields an efficient construction that has O(N) worst case time complexity.
This results in considerable speedups for complex pattern recognition tasks on large inputs, and yields other useful properties.
As a real world example, a CSV file can be parsed in parallel on a GPU by using a DFA based algorithm [1].
One downside to DFA representations is that they can be difficult to work with as linear text in your editor. Tikz produces great visualizations but I feel the syntax is a bit cumbersome. I’m still searching for that perfect text based format for DFAs - ideally one that can be visualized but also executed.
[1] ParPaRaw: Massively Parallel Parsing of Delimiter-Separated Raw Data https://arxiv.org/abs/1905.13415
Re: LaTeX Finite Automata and State Diagrams with Tikz
#4On this topic, I recently came across a nice string diagram formalization for automata:
https://arxiv.org/pdf/2009.14576.pdf
Re: LaTeX Finite Automata and State Diagrams with Tikz
#5I find manually laying out graphs and digraphs tedious.
It seems like a problem that should be amenable to machine learning approaches. Basically, training a machine as to what is an aesthetically pleasing layout and what is not.
Are there layout engines that use machine learning for layout, as against being implemented in terms of specific tree or graph layout algorithms?
Re: LaTeX Finite Automata and State Diagrams with Tikz
#6DFAs and NFAs may seem like academic novelties but they are amazingly powerful for certain problems. For example, naively searching a string of length N for P different substrings will yield an algorithm that has roughly O(N * P) worst case time complexity. But implementing that algorithm as a DFA yields an efficient construction that has O(N) worst case time complexity. This results in considerable speedups for comp…
Is that your research? I will have to read up more on it, but I am blown away that it is even possible to do that.
Re: LaTeX Finite Automata and State Diagrams with Tikz
#7I loved using Tikz for my Discrete Math homework. I was so proud of how pretty the DFA's looked :)
I used OmniGraffle and got some pretty fine looking graphs myself, but this is next-level ease. I’m jealous that you knew how to use this.
Re: LaTeX Finite Automata and State Diagrams with Tikz
#8DFAs and NFAs may seem like academic novelties but they are amazingly powerful for certain problems. For example, naively searching a string of length N for P different substrings will yield an algorithm that has roughly O(N * P) worst case time complexity. But implementing that algorithm as a DFA yields an efficient construction that has O(N) worst case time complexity. This results in considerable speedups for comp…
But implementing that algorithm as a DFA yields an efficient construction that has O(N) worst case time complexity.
I think it is worth saying that this is possible because finite state automata have a set of useful, well-understood operations, like concatenation, union, intersection, negation, kleene closure, determinization, and minimization. This makes it possible to generate complex automata from basic building blocks and to make them deterministic and minimal.
Re: LaTeX Finite Automata and State Diagrams with Tikz
#9I always used this website to generate them https://madebyevan.com/fsm/
Re: LaTeX Finite Automata and State Diagrams with Tikz
#10I find manually laying out graphs and digraphs tedious. It seems like a problem that should be amenable to machine learning approaches. Basically, training a machine as to what is an aesthetically pleasing layout and what is not. Are there layout engines that use machine learning for layout, as against being implemented in terms of specific tree or graph layout algorithms?
Arguably a graph layout is performed by a kind of "training" in the sense that it takes many iterations for the parameters (and possibly physical distancing forces) to be evaluated for every node against all of the others. This is a solver, and not entirely unlike something like gradient descent. This is painting a rather broad brush with these terms, however.