Publication:1426009

DOI10.1016/S0890-5401(03)00090-7zbMATH Open1059.68063OpenAlexW2912608078MaRDI QIDQ1426009FDOQ1426009

Lucian Ilie, Sheng Yu

Publication date: 14 March 2004

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00090-7

zbMATH Keywords

Nondeterministic finite automataPartial derivativesRegular expressions\(\varepsilon\)-EliminationQuotientsRight-invariant equivalences

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Formal languages and automata (68Q45) Nonnumerical algorithms (68W05) Algebraic theory of languages and automata (68Q70) Descriptive complexity and finite models (68Q19)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• THE ABSTRACT THEORY OF AUTOMATA
• Derivatives of Regular Expressions
• Partial derivatives of regular expressions and finite automaton constructions
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
• Programming Techniques: Regular expression search algorithm
• Regular expressions into finite automata
• Computingϵ-Free NFA from Regular Expressions inO(nlog²(n)) Time
• From regular expressions to deterministic automata
• From regular expressions to DFA's using compressed NFA's

Cited In (57)

• Space-Efficient Representations for Glushkov Automata
• The Bottom-Up Position Tree Automaton and the Father Automaton
• Algorithms for checking intersection non-emptiness of regular expressions
• Location automata for regular expressions with shuffle and intersection
• From Hadamard expressions to weighted rotating automata and back
• The complexity of regular(-like) expressions
• Left is Better Than Right for Reducing Nondeterminism of NFAs
• Small Extended Expressions for Acyclic Automata
• On typical hesitant fuzzy automata
• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• Computing with relational machines
• Multi-tilde-bar expressions and their automata
• An Efficient Algorithm for the Construction of the Equation Tree Automaton
• An Evaluation of Automata Algorithms for String Analysis
• Derivatives of Regular Expressions and an Application
• On the average state complexity of partial derivative automata: an analytic combinatorics approach
• Analysis of an efficient reduction algorithm for random regular expressions based on universality detection
• Title not available (Why is that?)
• PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA
• NORMALIZED EXPRESSIONS AND FINITE AUTOMATA
• Derivatives and Finite Automata of Expressions in Star Normal Form
• On the Hopcroft's minimization technique for DFA and DFCA
• Reduction of fuzzy automata by means of fuzzy quasi-orders
• Obtaining shorter regular expressions from finite-state automata
• Fuzzy relation equations and reduction of fuzzy automata
• Acyclic automata and small expressions using multi-tilde-bar operators
• Compact representations of automata for regular expression matching
• Prefix and Right-Partial Derivative Automata
• Reducing NFAs by invariant equivalences.
• Descriptional and Computational Complexity of Finite Automata
• Conversion of fuzzy automata into fuzzy regular expressions using transitive closure
• Construction of fuzzy automata from fuzzy regular expressions
• From Hadamard expressions to weighted rotating automata and back
• A mesh of automata
• On Average Behaviour of Regular Expressions in Strong Star Normal Form
• Postfix automata
• Location based automata for expressions with shuffle
• From regular expressions to smaller NFAs
• Minimizing nfa's and regular expressions
• An extended framework for passive asynchronous testing
• Deciding Kleene algebra terms equivalence in Coq
• From finite automata to regular expressions and back -- a summary on descriptional complexity
• Descriptional and computational complexity of finite automata -- a survey
• Extended to multi-tilde-bar regular expressions and efficient finite automata constructions
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Language operations with regular expressions of polynomial size
• Automata and rational expressions
• Descriptional complexity of regular languages
• Enumerating regular expressions and their languages
• A New Family of Regular Operators Fitting with the Position Automaton Computation
• Multi-tilde Operators and Their Glushkov Automata
• Position Automaton Construction for Regular Expressions with Intersection
• ANTIMIROV AND MOSSES'S REWRITE SYSTEM REVISITED
• Hopcroft’s Minimization Technique: Queues or Stacks?
• Antimirov and Mosses’s Rewrite System Revisited
• A faster algorithm for finding shortest substring matches of a regular expression
• Provably Shorter Regular Expressions from Deterministic Finite Automata

This page was built for publication: Follow automata.

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