Local languages and the Berry-Sethi algorithm

DOI10.1016/0304-3975(95)00104-2MaRDI QIDQ672153zbMATH OpenOpenAlexFDO

Authors Jean Berstel, Jean-Éric Pin

Publication date 27 February 1997

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

Full work available at URL https://doi.org/10.1016/0304-3975(95)00104-2

zbMATH Keywords

local languagesBerry-Sethi algorithmconstruction of a finite automaton from a (regular) expression

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 2040915
• Locally finite languages
• On locally reversible languages
• Local periods and binary partial words: an algorithm
• A characterization of local regular languages
• Lattices of local two-dimensional languages
• Local search in coding theory
• Local decodability of the Burrows-Wheeler transform
• On Languages Reducible to Algorithmically Random Languages
• Locality and the complexity of minimalist derivation tree languages

Cites work

• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3251424 (Why is no real title available?)
• A taxonomy of sublinear multiple keyword pattern matching algorithms
• An optimal parallel algorithm to convert a regular expression into its Glushkov automaton
• Deterministic regular languages
• From regular expressions to deterministic automata
• THE ABSTRACT THEORY OF AUTOMATA
• The passing of a rational expression to a nondeterministic finite automaton
• Transductions des langages de Chomsky

Cited in

(20)

• One-unambiguous regular languages
• Extended to multi-tilde-bar regular expressions and efficient finite automata constructions
• From regular to strictly locally testable languages
• Language operations with regular expressions of polynomial size
• Characterization of Glushkov automata
• A deterministic parsing algorithm for ambiguous regular expressions
• Families of locally testable languages
• From ambiguous regular expressions to deterministic parsing automata
• Two-Sided Strictly Locally Testable Languages
• scientific article; zbMATH DE number 7317445 (Why is no real title available?)
• From regular expressions to finite automata^∗
• One-unambiguous regular languages
• Shuffle on positive varieties of languages
• Traces of Control-Flow Graphs
• From regular expressions to smaller NFAs
• Automata and rational expressions
• One-unambiguity of regular expressions with numeric occurrence indicators
• Infinite Arrays and Domino Systems
• Efficient recognition of trace languages defined by repeat-until loops
• How expressions can code for automata

This page was built for publication: Local languages and the Berry-Sethi algorithm

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