Boolean satisfiability

Abstract

An apparatus includes a state machine engine. The state machine engine may also include an automaton, whereby the automaton is configured to analyze data from a beginning of an input data stream until a point when an end of data signal is seen. The automaton may further be configured to report an event representative of a satisfaction of a Boolean clause of a conjunctive normal form (CNF) Boolean expression representative of a Boolean Satisfiability problem (SAT) by a portion of the input data stream.

Description

CROSS REFERENCE TO RELATED APPLICATIONS[0001]This application is a Non-Provisional application claiming priority to U.S. Provisional Patent Application No. 62 / 410,722, entitled “Boolean Satisfiability”, filed Oct. 20, 2016, which is herein incorporated by reference.BACKGROUNDField of Invention[0002]Embodiments relate generally to electronic devices and, more specifically, in certain embodiments, to electronic devices with parallel devices for data analysis.Description of Related Art[0003]Complex pattern recognition can be inefficient to perform on a conventional von Neumann based computer. A biological brain, in particular a human brain, however, is adept at performing pattern recognition. Current research suggests that a human brain performs pattern recognition using a series of hierarchically organized neuron layers in the neocortex. Neurons in the lower layers of the hierarchy analyze “raw signals” from, for example, sensory organs, while neurons in higher layers analyze signal o...

AI Technical Summary

Benefits of technology

The patent text describes a system that can perform pattern recognition, similar to how a human brain does it, using a processor-based system. The system uses a state machine engine to search a data stream for specific patterns. The engine is designed to efficiently analyze large amounts of data and detect patterns in real-time. The technical effect of this system is that it can effectively perform pattern recognition in a way that is more comparable to the human brain, which can be useful in various applications such as data analysis and security.

Problems solved by technology

Complex pattern recognition can be inefficient to perform on a conventional von Neumann based computer.

In the field of computing, pattern recognition tasks are increasingly challenging.

Searching a data stream for each of these patterns can form a computing bottleneck.

The delay before the system is ready to search the next portion of the data stream increases with the number of patterns.

Thus, pattern recognition may slow the receipt of data.

Hardware has been designed to search a data stream for patterns, but this hardware often is unable to process adequate amounts of data in an amount of time given.

These “intermediate results”, however, can be larger than the original input data, which may pose issues for the system.

However, there has not been a system that effectively allows for performing pattern recognition in a manner more comparable to that of a biological brain.

Images