Comments (10)
Automata#minimize
should do the trick, or if you don't need the original automaton anymore, Automata#invasiveMinimize
. The Automata
class is part of the automata-util
module.
from automatalib.
Hi, @mtf90
Thanks for your reply. I'm new to automatalib
so I'm not familiar with the APIs and their capabilities.
I tried Automata#invasiveMinimize
using the following code:
public static void main(String[] args) throws IOException {
Alphabet<Character> alphabet = Alphabets.characters('a', 'b');
CompactMealy<Character, Integer> mealy = AutomatonBuilders.<Character, Integer>newMealy(alphabet)
.withInitial(0)
.from(0).on('a').withOutput(1).to(1)
.from(1).on('b').withOutput(2).to(2)
.from(2).on('a').withOutput(1).to(3).from(3).on('b').withOutput(2).to(4)
.create();
StringBuilder b = new StringBuilder();
GraphDOT.write(mealy, mealy.getInputAlphabet(), b);
System.out.println(b.toString());
CompactMealy<Character, Integer> mealy_minimized = Automata.invasiveMinimize(mealy, mealy.getInputAlphabet());
GraphDOT.write(mealy_minimized, mealy_minimized.getInputAlphabet(), b);
System.out.println(b.toString());
}
The output is
digraph g {
s0 [shape="circle" label="0"];
s1 [shape="circle" label="1"];
s2 [shape="circle" label="2"];
s3 [shape="circle" label="3"];
s4 [shape="circle" label="4"];
s0 -> s1 [label="a / 1"];
s1 -> s2 [label="b / 2"];
s2 -> s3 [label="a / 1"];
s3 -> s4 [label="b / 2"];
__start0 [label="" shape="none" width="0" height="0"];
__start0 -> s0;
}
digraph g {
s0 [shape="circle" label="0"];
s1 [shape="circle" label="1"];
s2 [shape="circle" label="2"];
s3 [shape="circle" label="3"];
s4 [shape="circle" label="4"];
s1 -> s3 [label="a / 1"];
s2 -> s1 [label="b / 2"];
s3 -> s0 [label="b / 2"];
s4 -> s2 [label="a / 1"];
__start0 [label="" shape="none" width="0" height="0"];
__start0 -> s4;
}
The mealy automata was not minimized. Did I use it wrong? Thanks.
from automatalib.
Sorry, I should have looked at the automaton models more closely. Your two models are not equivalent. Your first model only supports translating the input sequence "abab" (there are no successors to state 4) whereas your expected model supports translating alternations of "a" and "b" of indefinite length. You probably want to change the last .to(4)
to .to(0)
.
As a result, the minimization essentially reconstructs the original automaton and only renames the existing nodes.
from automatalib.
Got it! Thank you for your time and expertise.
My goal is to infer the protocol state machine based on the protocol session. For instance, consider the TCP session below:
C -- SYN --> S
S -- SYN/ACK --> C
C -- SYN --> S
S -- PUSH --> C
C -- SYN --> S
S -- PUSH --> C
C -- SYN --> S
S -- PUSH --> C
By modeling each tuple of request and response, we can generate the following chained Mealy machine:
digraph g {
s0 [shape="circle" label="0"];
s1 [shape="circle" label="1"];
s2 [shape="circle" label="2"];
s3 [shape="circle" label="3"];
s4 [shape="circle" label="4"];
s0 -> s1 [label="SYN / SYN/ACK"];
s1 -> s2 [label="SYN / PUSH"];
s2 -> s3 [label="SYN / PUSH"];
s3 -> s4 [label="SYN / PUSH"];
__start0 [label="" shape="none" width="0" height="0"];
__start0 -> s0;
}
Since the protocol session has a limited length, it is impossible to construct a chained Mealy machine of indefinite length. However, based on the insight, we can infer that the protocol state machine should be:
digraph g {
s0 [shape="circle" label="0"];
s1 [shape="circle" label="1"];
s0 -> s1 [label="SYN / SYN/ACK"];
s1 -> s1 [label="SYN / PUSH"];
__start0 [label="" shape="none" width="0" height="0"];
__start0 -> s0;
}
I wonder if there is any tool that can help me minimize the chained Mealy machine generated from a protocol session and can be used as the protocol state machine.
from automatalib.
Your description sounds exactly like the problem that automata learning is trying to solve: based on a finite set of observations, try to generalize the observed behavior to a finite state machine. Depending on how you can provide the observations either passive automata learning or active automata learning may be better suited. Conveniently, LearnLib offers solutions for both use-cases 😆.
If it is of any help, there also has been some research on applying automata learning to TCP implementations in the recent past (https://doi.org/10.1007/978-3-319-10702-8_6, https://doi.org/10.1007/978-3-319-67113-0_12). However, the register automata stuff is not yet implemented in LearnLib.
from automatalib.
@mtf90 Thanks for your helpful guidance! As my task involves inferring a protocol model based on a set of traffic observations, I believe that passive automata learning is the way to go. However, I have been unsuccessful in finding any examples or tutorials on how to accomplish this in LearnLib. LearnLib is a powerful tool, but there are relatively few tutorials available for it. Could you please let me know which class/function can help me achieve this? Thanks so much for your time and expertise.
from automatalib.
There exists an examples
module which contains some exemplary setups to get you going. The module also contains an example for setting up a passive learning process. Unfortunately, LearnLib mainly focuses on active automata learning, so there is a somewhat restricted support for passive learning algorithms. While we have an RPNI implementation for Mealy systems, I can't really comment on its practical performance.
from automatalib.
@mtf90 Thanks for your helpful guidance! I'll try it 😆.
from automatalib.
@grandnew are there any question left to this particular issue, or can it be closed?
from automatalib.
I'm closing this issue for now since the problem seems to be solved. Feel free to open it again, if you find an actual problem within AutomataLib.
from automatalib.
Related Issues (20)
- CompactMealyTransition does not extend MealyTransition HOT 5
- Error testing serilaization-dot HOT 10
- Substract current automaton size to Wp-method's maxDepth HOT 2
- Replace JSR305 annotations
- Write a parser for LTSmin formulae
- Incorrect characterizing set for Mealy machine HOT 3
- TAF writer does not enquote outputs of mealy machines
- DOTParsers.mealy() not parsing all transitions HOT 13
- Minimizer.minimize overload without start states is broken HOT 2
- CompactMoore HOT 9
- Deviation in the BBC functionality between (at least) LearnLib 0.14.0 and 0.16.0 HOT 2
- PaigeTarjanMinimization.minimizeDFA does not guarantee minimal result HOT 2
- Add support for Java 17 (LTS) to CI pipeline
- AUTParser only adds states with outgoing transitions
- M3C does not run on M1 MacBooks HOT 1
- Fail on javadoc warnings and improve documentation
- M3CParser fails when ID is a formula token
- IndexOutOfBoundsException in IncrementalMealyDAGBuilder when input word is longer than output word HOT 6
- IncrementalDAGBuilder fails for traces with cyclic repetitions longer than 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from automatalib.