A hitchhiker's guide to descriptional complexity through analytic combinatorics

DOI10.1016/j.tcs.2014.02.013zbMath1308.68070OpenAlexW2063199724MaRDI QIDQ2437857

António Machiavelo, Sabine Broda, Rogério Reis, Nelma Moreira

Publication date: 13 March 2014

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

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

zbMATH Keywords

regular expressionsfinite automataanalytic combinatoricsaverage-case complexitydescriptional complexity

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Formal languages and automata (68Q45)

Related Items

Local limit laws for symbol statistics in bicomponent rational models ⋮ Automata for regular expressions with shuffle ⋮ On the average complexity of partial derivative transducers ⋮ On the Average State Complexity of Partial Derivative Transducers ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ On Average Behaviour of Regular Expressions in Strong Star Normal Form ⋮ On the size of partial derivatives and the word membership problem ⋮ On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• Enumeration and random generation of accessible automata
• Follow automata.
• Average case analysis of Moore's state minimization algorithm
• Enumeration and generation with a string automata representation
• On the average state and transition complexity of finite languages
• THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS
• ON THE AVERAGE STATE COMPLEXITY OF PARTIAL DERIVATIVE AUTOMATA: AN ANALYTIC COMBINATORICS APPROACH
• In Search of Most Complex Regular Languages
• An Optimal Construction of Finite Automata from Regular Expressions
• Simplifying Regular Expressions
• The Complexity of Regular(-Like) Expressions
• THE AVERAGE STATE COMPLEXITY OF RATIONAL OPERATIONS ON FINITE LANGUAGES
• On the Average Size of Glushkov’s Automata
• ON THE AVERAGE SIZE OF GLUSHKOV AND PARTIAL DERIVATIVE AUTOMATA
• State Complexity Research and Approximation
• Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata
• Implementation and Application of Automata
• Programming Techniques: Regular expression search algorithm

This page was built for publication: A hitchhiker's guide to descriptional complexity through analytic combinatorics