NDLI: Efficient concise deterministic pattern-matching automata for ambiguous patterns

Content Provider	ACM Digital Library
Author	de Macedo Mourelle, Luiza Nedjah, Nadia
Abstract	Pattern-matching is a fundamental feature in many applications such as functional programming, logic programming, theorem proving, term rewriting and rule-based expert systems. Usually, patterns are pre-processed into a deterministic finite automaton. Using such an automaton allows one to determine the matched pattern(s) by a single scan of the input term. The matching automaton is typically based on left-to-right traversal of patterns. With ambiguous patterns a subject term may be an instance of more than one pattern. To select the pattern to use, a priority rule is usually engaged. The pre-processing of the patterns adds new patterns which are instances of the original ones. When the original patterns are ambiguous, some of the instances supplied may be irrelevant for the matching process. They may cause an unnecessary increase in the space requirements of the automaton and may also reduce the time efficiency of the matching process. Here, we devise a new pre-processing operation that recognises and avoids such irrelevant instances and hence improves space and time requirements for the matching automaton.
Starting Page	57
Ending Page	67
Page Count	11
File Format	PDF
ISSN	03621340 15581160
DOI	10.1145/568600.568612
Journal	ACM SIGPLAN Notices (SIGP)
Volume Number	37
Issue Number	2
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1983-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Compilation Closure Pattern-matching Patterns Ambiguous Tree automaton
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Minimal deterministic left-to-right pattern-matching automata

Compiling regular patterns

Post-compilation optimization for multiple gains with pattern matching

Polymorphic regular tree types and patterns

ACME:adaptive compilation made efficient

Open pattern matching for C++

Regular expression patterns

Exploring different automata representations for efficient regular expression matching on GPUs

Fast and flexible instruction selection with on-demand tree-parsing automata

Efficient concise deterministic pattern-matching automata for ambiguous patterns

Similar Documents

Minimal deterministic left-to-right pattern-matching automata

Compiling regular patterns

Post-compilation optimization for multiple gains with pattern matching

Polymorphic regular tree types and patterns

ACME:adaptive compilation made efficient

Open pattern matching for C++

Regular expression patterns

Exploring different automata representations for efficient regular expression matching on GPUs

Fast and flexible instruction selection with on-demand tree-parsing automata

Efficient concise deterministic pattern-matching automata for ambiguous patterns