eratommsd / moore_machine_filter

An experimental implementation of Moore machine filter for timed and untimed pattern matching

Moore Machine Filter

An experimental implementation of Moore machine filter for timed and untimed pattern matching. This implementation is tested on Ubuntu (18.04 and 20.04) and macOS 10.15 Catalina.

Getting Started

Requirements

• C++ compiler supporting C++17 and the corresponding libraries.
• Boost (>= 1.59)
• Eigen
• CMake

Building

mkdir build
cd build && cmake -DCMAKE_BUILD_TYPE=Release -DBUFFER_SIZE=10 .. && make

Configuration

BUFFER_SIZE : The size of buffer in the Moore machine (default: 10).

Usage

Synopsis

filt [OPTIONS] -f FILE

Options

-h, --help Print a help message.
-V, --version Print the version.
-f file, --automaton file Read a (timed) automaton from file.
-u, --untimed (default) Untimed filtering mode.
-t, --timed Timed filtering mode.

Syntax of Timed Automata

You can use DOT language to represent a timed automaton or a NFA. For the timing constraints and other information, you can use the following custom attributes.

	attribute	value	description
vertex	init	0 or 1	init=1 if the state is initial
vertex	match	0 or 1	match=1 if the state is accepting
edge	label	[a-z], [A-Z]	the value represents the event on the transition
edge	reset	a list of integers	the set of variables reset after the transition
edge	guard	a list of inequality constraints	the guard of the transition

References

• Waga, Masaki, and Ichiro Hasuo. "Moore-machine filtering for timed and untimed pattern matching." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 37.11 (2018): 2649-2660.