Measuring the expressive power of practical regular expressions by classical stacking automata models

DOI10.1016/J.IC.2025.105303MaRDI QIDQ6966438zbMATH OpenFDO

Authors Taisei Nogami, Tachio Terauchi

Publication date 27 June 2025

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

Full work available at URL https://doi.org/10.1016/J.IC.2025.105303

zbMATH Keywords

backreferencesexpressive powerlookaheadsregular expressions

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• Characterising REGEX languages by regular languages equipped with factor-referencing
• Deterministic regular expressions with back-references
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• Indexed Grammars—An Extension of Context-Free Grammars
• Intercalation theorems for stack languages
• Nested Stack Automata
• Nonerasing stack automata
• On derivation trees of indexed grammars - an extension of the uvwxy- theorem
• On Extended Regular Expressions
• On lookaheads in regular expressions with backreferences
• On the expressive power of regular expressions with backreferences
• One-way stack automata
• Re-examining regular expressions with backreferences
• Regular expressions with nested levels of back referencing form a hierarchy
• Stack automata and compiling

Cited in

(1)

• Efficient matching of some fundamental regular expressions with backreferences

This page was built for publication: Measuring the expressive power of practical regular expressions by classical stacking automata models

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