On the average complexity of partial derivative transducers

DOI10.1016/j.tcs.2023.113830OpenAlexW4328105802MaRDI QIDQ2699218

Nelma Moreira, Stavros Konstantinidis, António Machiavelo, Rogério Reis

Publication date: 26 April 2023

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.113830

zbMATH Keywords

average case complexitytransducerspartial derivativesanalytic combinatoricsrational expressions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• FAdo

Cites Work

• Partial derivatives of regular expressions and finite automaton constructions
• Automata for regular expressions with shuffle
• Derivatives of rational expressions with multiplicity
• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• ON THE AVERAGE STATE COMPLEXITY OF PARTIAL DERIVATIVE AUTOMATA: AN ANALYTIC COMBINATORICS APPROACH
• On the Average State Complexity of Partial Derivative Transducers
• On the Average Size of Glushkov’s Automata
• Derived-Term Automata of Multitape Expressions with Composition
• On Average Behaviour of Regular Expressions in Strong Star Normal Form
• A Singular Mathematical Promenade
• Regular Expressions and Transducers Over Alphabet-Invariant and User-Defined Labels
• Partial derivatives of regular expressions over alphabet-invariant and user-defined labels
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item