PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA

DOI10.1142/S0129054113500330zbMath1291.68230OpenAlexW2113629662MaRDI QIDQ5168416

Hermann Gruber, Markus Holzer

Publication date: 4 July 2014

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054113500330

zbMATH Keywords

interleavingintersectionregular expressionstate eliminationcycle rank

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (max. 100)

From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ Descriptional complexity of regular languages

Cites Work

• Graph minors. III. Planar tree-width
• Obtaining shorter regular expressions from finite-state automata
• Succinctness of regular expressions with interleaving, intersection and counting
• Large induced degenerate subgraphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Complexity measures for regular expressions
• S-functions for graphs
• Follow automata.
• Ordered colourings
• Planarization and fragmentability of some classes of graphs
• Tree-depth, subgraph coloring and homomorphism bounds
• Transition graphs and the star-height of regular events
• Succinctness of the Complement and Intersection of Regular Expressions
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• A Separator Theorem for Planar Graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Rankings of Graphs
• Derivatives of Regular Expressions

This page was built for publication: PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA