An efficient null-free procedure for deciding regular language membership

DOI10.1016/S0304-3975(99)00019-5MaRDI QIDQ1575893zbMATH OpenOpenAlexFDO

Authors Jean-Luc Ponty

Publication date 23 August 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(99)00019-5

zbMATH Keywords

Glushkov automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• A Four Russians algorithm for regular expression pattern matching
• Regular expressions into finite automata
• Space-efficient representations for Glushkov automata
• Compressed membership problems for regular expressions and hierarchical automata

Cites work

• scientific article; zbMATH DE number 48095 (Why is no real title available?)
• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• scientific article; zbMATH DE number 194974 (Why is no real title available?)
• scientific article; zbMATH DE number 5254145 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Automata Studies. (AM-34)
• Deterministic regular languages
• Efficient string matching
• Fast Pattern Matching in Strings
• From regular expressions to deterministic automata
• On Simon's string searching algorithm
• Partial derivatives of regular expressions and finite automaton constructions
• Programming Techniques: Regular expression search algorithm
• Regular expressions into finite automata
• THE ABSTRACT THEORY OF AUTOMATA
• The passing of a rational expression to a nondeterministic finite automaton
• Translating regular expressions into small \(\epsilon \)-free nondeterministic finite automata

Cited in

(5)

• Compact and fast algorithms for safe regular expression search
• Principles and Practice of Constraint Programming – CP 2004
• Efficient algorithms for membership in Boolean hierarchies of regular languages
• Regular expression order-sorted unification and matching
• Subset construction complexity for homogeneous automata, position automata and ZPC-structures

Describes a project that uses

Uses Software

• AMoRE

This page was built for publication: An efficient null-free procedure for deciding regular language membership

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1575893)