Tight Bounds on the Descriptional Complexity of Regular Expressions
Authors:
- 1 January 2009
- book chapter
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 276-287
Abstract
No abstract availableKeywords
This publication has 17 references indexed in Scilit:
- Succinctness of Regular Expressions with Interleaving, Intersection and CountingLecture Notes in Computer Science, 2008
- Finite Automata, Digraph Connectivity, and Regular Expression Size2008
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity2008
- Provably Shorter Regular Expressions from Deterministic Finite Automata2008
- The treewidth and pathwidth of hypercubesDiscrete Mathematics, 2006
- Algorithms for determining relative star height and star heightInformation and Computation, 1988
- The complexity of the inequivalence problem for regular expressions with intersectionLecture Notes in Computer Science, 1980
- Complexity measures for regular expressionsJournal of Computer and System Sciences, 1976
- Star height of certain families of regular eventsJournal of Computer and System Sciences, 1970
- Transition graphs and the star-height of regular events.The Michigan Mathematical Journal, 1963