This article shows a general result about finite monoids and weight reducing string rewriting systems. As a consequence it proves a long standing conjecture in formal language theory: All regular languages are Church-Rosser congruential. The class of Church-Rosser congruential languages was introduced by McNaughton, Narendran, and Otto in 1988. A language L is Church-Rosser congruential if there exists a finite, confluent, and length-reducing semi-Thue system S such that L is a finite union of congruence classes modulo S . It was known that there are deterministic linear context-free languages which are not Church-Rosser congruential, but the conjecture was that all regular languages are of this form. The article offers a stronger statement: A language is regular if and only if it is strongly Church-Rosser congruential. It is the journal version of the conference abstract which was presented at ICALP 2012.

Many companies and institutions employ packet filter firewalls in order to effectively regulate network traffic. Unfortunately, the constant growth of network bandwidth makes the task of matching packet headers against potentially large rulesets more difficult, and prohibits the sole use of entirely software-based firewalls which cannot cope with such huge amounts of traffic. Instead, high-speed firewalls are often implemented in ASICs which offer a high degree of parallelism, many opportunities for operation pipelining, and low-latency access to network data. However, due to their static nature, ASICs must provide generic filtering circuitry that is hardly able to take full advantage of firewall ruleset properties, thus leading to a waste of hardware resources.

The process of matching the header fields of network packets against a set of rules is a performance critical task of firewalls. Software-based solutions have no chance to keep pace with the ever-growing data rates in high-speed networks. However, specialized filtering hardware is costly because complex logic is required in order to be able to apply arbitrary rulesets to a packet stream. By adapting the implemented logic to the specific firewall ruleset, FPGAs allow for much more specifically tailored and thus more efficient processing than ruleset-independent circuits in an ASIC. We present MPFC, a method to generate customized firewall circuits in the form of synthesizable VHDL code for FPGA configuration. The highly parallel MPFC circuits achieve a deterministic throughput of one packet per clock cycle, can be operated at high clock frequencies, and provide orders of magnitudes shorter processing latencies than previous work in this direction.

We show that in the context of nonuniform complexity, nondeterministic logarithmic space bounded computation can be made unambiguous. An analogous result holds for the class of problems reducible to context-free languages. In terms of complexity classes, this can be stated as NL/poly = UL/poly,\\ LogCFL/poly = UAuxPDA($\log n, n^{O(1)}$)/poly.

We show that the perfect matching problem is in the complexity class SPL (in the nonuniform setting). This provides a better upper bound on the complexity of the matching problem, as well as providing motivation for studying the complexity class SPL. Using similar techniques, we show that the complexity class LogFew coincides with NL in the nonuniform setting. Finally, we provide evidence that our results also hold in the uniform setting.

We show that in the context of nonuniform complexity, nondeterministic logarithmic space bounded computation can be made unambiguous. An analogous result holds for the class of problems reducible to context-free languages. In terms of complexity classes, this can be stated as: NL/poly=UL/poly LogCFL/poly=UAuxPDA(log n, n/sup O(1)/)/poly.