Derivatives of Regular Expressions
From MaRDI portal
Publication:5632482
DOI10.1145/321239.321249zbMath0225.94044OpenAlexW2156429182WikidataQ59595167 ScholiaQ59595167MaRDI QIDQ5632482
Publication date: 1964
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321239.321249
Related Items
A set automaton to locate all pattern matches in a term, Varieties and covarieties of languages (extended abstract), Rational operational models, Bisimilar and logically equivalent programs in PDL with parallel operator, Simplifying regular expressions further, Generalized language equations with multiple solutions, An SMT solver for regular expressions and linear arithmetic over string length, Behavioural differential equations: a coinductive calculus of streams, automata, and power series, The full quotient and its closure property for regular languages, One-unambiguity of regular expressions with numeric occurrence indicators, Factor theory and the unity of opposites, Compositional verification of concurrent systems by combining bisimulations, A matrix-linguistic method of analyzing finite discrete dynamic systems, Super-pattern matching, Proof Pearl: regular expression equivalence and relation algebra, On the computation of quotients and factors of regular languages, Manipulation of regular expressions using derivatives: an overview, The validation of SGML content models, Regular language representations in the constructive type theory of Coq, Quotient complexity of closed languages, Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking, Fairness and communication-based semantics for session-typed languages, From regular expressions to DFA's using compressed NFA's, Derivatives and partial derivatives for regular shuffle expressions, Deadlock and fairness in parallel schemas: A set-theoretic characterization and decision problems, Well-abstracted transition systems: Application to FIFO automata., Proving language inclusion and equivalence by coinduction, On generalized language equations, Symbolic execution of Reo circuits using constraint automata, Follow automata., Learning regular languages using RFSAs., Derivatives of rational expressions and related theorems., Reducing NFAs by invariant equivalences., A description based on languages of the final non-deterministic automaton, Extension of Brzozowski's derivation calculus of rational expressions to series over the free partially commutative monoids, Complete systems of \(\mathcal B\)-rational identities, On series-parallel pomset languages: rationality, context-freeness and automata, Location based automata for expressions with shuffle, Context-free grammars with lookahead, Hidden protocols: modifying our expectations in an evolving world, Extended to multi-tilde-bar regular expressions and efficient finite automata constructions, Nondeterministic syntactic complexity, Partial derivatives of regular expressions and finite automaton constructions, The dual equivalence of equations and coequations for automata, Compilation of the ELECTRE reactive language into finite transition systems, Rewriting extended regular expressions, Compiling and verifying SC-SystemJ programs for safety-critical reactive systems, Applying string-rewriting to sequence-based specification, Verification and enforcement of access control policies, A general account of coinduction up-to, The inclusion problem for regular expressions, Quantitative Kleene coalgebras, Functional dependencies on extended relations defined by regular languages, Construction of fuzzy automata from fuzzy regular expressions, Almost event-rate independent monitoring, CTRL: extension of CTL with regular expressions and fairness operators to verify genetic regulatory networks, A coalgebraic approach to Kleene algebra with tests, Derivatives of rational expressions with multiplicity, Some properties of inclusions of multisets and contractive Boolean operators, State-complexity hierarchies of uniform languages of alphabet-size length, Language operations with regular expressions of polynomial size, A mesh of automata, Multi-tilde-bar expressions and their automata, From regular expressions to deterministic automata, Boolean operations and inclusion test for attribute-element constraints, Properties of code events and homomorphisms over regular events, A type checking algorithm for concurrent object protocols, Computers in semigroups, Derivatives for Regular Shuffle Expressions, From $$\omega $$-Regular Expressions to Büchi Automata via Partial Derivatives, From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity, A specification of parallel problems, Lambek calculus with conjugates, Closures which preserve finiteness in families of languages, Position Automaton Construction for Regular Expressions with Intersection, POSIX Lexing with Derivatives of Regular Expressions (Proof Pearl), Dot-depth of star-free events, On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection, Derived-Term Automata of Multitape Rational Expressions, Derivative-Based Diagnosis of Regular Expression Ambiguity, Derivatives for Enhanced Regular Expressions, Adapting functional programs to higher order logic, Types from Frames as Finite Automata, General properties of star height of regular events, Star height of certain families of regular events, Automata and rational expressions, Learning algorithms, Alternating finite automata and star-free languages, Solvable classes of discrete dynamic programming, An axiom system for sequence-based specification, Finite-state \(\omega\)-languages, A formally verified, optimized monitor for metric first-order dynamic logic, Canonical derivatives, partial derivatives and finite automaton constructions., Context-free coalgebras, Regular expressions into finite automata, Deciding Kleene algebra terms equivalence in Coq, A goal-directed decision procedure for hybrid PDL, A formalisation of the Myhill-Nerode theorem based on regular expressions, Operads, quasiorders, and regular languages, On the hierarchy of generalizations of one-unambiguous regular languages, FROM C-CONTINUATIONS TO NEW QUADRATIC ALGORITHMS FOR AUTOMATON SYNTHESIS, Derivatives of Regular Expressions and an Application, Unnamed Item, On regular expressions and regular canonical systems, Construction of a Deterministicω-Automaton Using Derivatives, OVERLAP-FREE LANGUAGES AND SOLID CODES, Rewriting regular inequalities, A Computational Interpretation of Context-Free Expressions, State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach, Static Trace-Based Deadlock Analysis for Synchronous Mini-Go, Derived-Term Automata for Extended Weighted Rational Expressions, THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS, ON THE AVERAGE STATE COMPLEXITY OF PARTIAL DERIVATIVE AUTOMATA: AN ANALYTIC COMBINATORICS APPROACH, Deriving Syntax and Axioms for Quantitative Regular Behaviours, A Propositional Dynamic Logic for Concurrent Programs Based on the π-Calculus, Prolog infinite trees and automata, Deciding Regular Expressions (In-)Equivalence in Coq, A separation theorem for discrete-time interval temporal logic, Tree pattern matching from regular tree expressions, Implementation of Deadlock Analysis in Data Flow Graphs, Techniques for establishing star height of regular sets, Efficient Program Transformers for Translating LCC to PDL, Equations and regular-like expressions for afa, Deterministic regular languages, Solving Linear Equations in *-continuous Action Lattices, Unnamed Item, POSIX lexing with derivatives of regular expressions, Better automata through process algebra, Unnamed Item, Unnamed Item, Unnamed Item, Completeness and the finite model property for Kleene algebra, reconsidered, Location automata for regular expressions with shuffle and intersection, Verified verifying: SMT-LIB for strings in Isabelle, Verified decision procedures for MSO on words based on derivatives of regular expressions, Unnamed Item, Unnamed Item, A CONCURRENT SPECIFICATION OF BRZOZOWSKI'S DFA CONSTRUCTION ALGORITHM, EFFICIENT AUTOMATA CONSTRUCTIONS AND APPROXIMATE AUTOMATA, Provably Shorter Regular Expressions from Deterministic Finite Automata, Construction of Tree Automata from Regular Expressions, Unnamed Item, Unnamed Item, Conversion of fuzzy automata into fuzzy regular expressions using transitive closure, Equational Theories of Abnormal Termination Based on Kleene Algebra, Partial Derivatives for Context-Free Languages, Computation Tree Regular Logic for Genetic Regulatory Networks, Unnamed Item, On the Coalgebraic Theory of Kleene Algebra with Tests, Reordering Derivatives of Trace Closures of Regular Languages., Calculational design of a regular model checker by abstract interpretation, ON THE AVERAGE SIZE OF GLUSHKOV AND PARTIAL DERIVATIVE AUTOMATA, From Grammars and Automata to Algebras and Coalgebras, Elements of Stream Calculus, COMPOSITIONAL VERIFICATION OF THE GENERALIZED NONBLOCKING PROPERTY USING ABSTRACTION AND CANONICAL AUTOMATA, PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA, Verification of the correctness of compiler optimization using co-induction, Derivatives and Finite Automata of Expressions in Star Normal Form, Realization of Coinductive Types, Product Rules and Distributive Laws, One-unambiguous regular languages, One-unambiguous regular languages, How expressions can code for automata, From regular expressions to finite automata∗, Antimirov and Mosses’s Rewrite System Revisited, Bidirectional grammars for machine-code decoding and encoding, Unnamed Item, Enumerated BSP Automata, Corrigendum to our paper: How Expressions Can Code for Automata, Normal form algorithms for extended context-free grammars, Minimal and Hyper-Minimal Biautomata, Regular-expression derivatives re-examined, Unnamed Item, A Kleene Theorem for Polynomial Coalgebras, Partial derivatives of regular expressions over alphabet-invariant and user-defined labels, Partial Derivative Automata Formalized in Coq, Unnamed Item, A Formalisation of the Myhill-Nerode Theorem Based on Regular Expressions (Proof Pearl), Hedge Pattern Partial Derivative, Construction of tree automata from regular expressions, ANTIMIROV AND MOSSES'S REWRITE SYSTEM REVISITED, A Decision Procedure for Regular Expression Equivalence in Type Theory, ON REGULAR EXPRESSION HASHING TO REDUCE FA SIZE, Inclusion Test Algorithms for One-Unambiguous Regular Expressions, Unnamed Item, Construction of recognition devices for regular languages from their Backus Normal Form definition, Inference of tree automata from sample set of trees, Bottom-Up derivatives of tree expressions, Kleene Theorems for Synchronous Products with Matching, Computing with relational machines, A category theory for programming languages, Discussion on: ``Supervisory control of discrete event systems with flexible marking, Integration in semirings
