Regular D-length: a tool for improved prefix-stable forward Ramsey factorisations

DOI10.1016/J.IPL.2024.106497MaRDI QIDQ6602314zbMATH OpenFDO

Authors Théodore Lopez, Benjamin Monmege, Jean-Marc Talbot

Publication date 11 September 2024

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2024.106497

zbMATH Keywords

fast infix query evaluationformal languagesGreen's relationsRamsey factorisation

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Recommendations

• The prefix automaton
• The factorisation forest theorem
• On deterministic finite automata and syntactic monoid size
• Prefix and Right-Partial Derivative Automata
• Regular expression length via arithmetic formula complexity

Cites work

• A Combinatorial Theorem for Trees
• Classical finite transformation semigroups. An introduction.
• Efficient evaluation of nondeterministic automata using factorization forests
• Enumeration of monadic second-order queries on trees
• Factorization Forests
• Factorization forests of finite height
• Green's relations and their use in automata theory
• The factorisation forest theorem

This page was built for publication: Regular \(\mathcal{D}\)-length: a tool for improved prefix-stable forward Ramsey factorisations

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