On the Average State Complexity of Partial Derivative Transducers

DOI10.1007/978-3-030-38919-2_15zbMath1440.68156OpenAlexW2999592416MaRDI QIDQ3297766

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

Publication date: 20 July 2020

Published in: SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-38919-2_15

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (3)

Average complexity of partial derivatives for synchronised shuffle expressions ⋮ On the average complexity of partial derivative transducers ⋮ On the size of partial derivatives and the word membership problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partial derivatives of regular expressions and finite automaton constructions
• Regular expressions and transducers over alphabet-invariant and user-defined labels
• 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 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
• Partial derivatives of regular expressions over alphabet-invariant and user-defined labels

This page was built for publication: On the Average State Complexity of Partial Derivative Transducers