A characterization of Thompson digraphs.

DOI10.1016/S0166-218X(03)00299-3zbMath1074.68031OpenAlexW2010443277MaRDI QIDQ1421476

Dora Giammarresi, Djelloul Ziadi, Jean-Luc Ponty, Derick Wood

Publication date: 26 January 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00299-3

zbMATH Keywords

Regular expressionsDyck stringsThompson machine

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

How to settle the ReDoS problem: back to the classical automata theory ⋮ Obtaining shorter regular expressions from finite-state automata ⋮ Series parallel digraphs with loops ⋮ Smaller representation of compiled regular expressions ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity

Uses Software

• LANGAGE

Cites Work

• Unnamed Item
• Unnamed Item
• The validation of SGML content models
• Characterization of Glushkov automata
• Optimization of LR(k) parsers
• Programming Techniques: Regular expression search algorithm

This page was built for publication: A characterization of Thompson digraphs.