Series parallel digraphs with loops

DOI10.1007/S00224-012-9409-0MaRDI QIDQ372966zbMATH OpenOpenAlexFDO

Authors Stefan Gulan

Publication date 21 October 2013

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-012-9409-0

zbMATH Keywords

digraphsforbidden subgraphsregular expressions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Recommendations

• scientific article; zbMATH DE number 5999572
• Series-Parallel Automata and Short Regular Expressions
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• An optimal construction of finite automata from regular expressions
• Provably shorter regular expressions from finite automata

Cites work

• scientific article; zbMATH DE number 5999572 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 2040952 (Why is no real title available?)
• A characterization of Thompson digraphs.
• An optimal construction of finite automata from regular expressions
• Characterization of Glushkov automata
• Complexity measures for regular expressions
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Finite automata and unary languages
• Graph Classes: A Survey
• Graph theory
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• On theories with a combinatorial definition of 'equivalence'
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Parallel algorithms for series parallel graphs and graphs with treewidth two
• Regular expressions: new results and open problems
• Series-Parallel Automata and Short Regular Expressions
• Succinctness of the complement and intersection of regular expressions
• The Recognition of Series Parallel Digraphs
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata

Cited in

(7)

• Constrained synchronization and subset synchronization problems for weakly acyclic automata
• Series parallel linkages
• Improved upper bounds for planarization and series-parallelization of degree-bounded graphs
• On lengths of edge-labeled graph expressions
• Series-Parallel Operations with Alpha-Graphs
• Chronological rectangle digraphs which are two-terminal series-parallel
• Synchronizing series-parallel deterministic finite automata with loops and related problems

Describes a project that uses

Uses Software

• LANGAGE

This page was built for publication: Series parallel digraphs with loops

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q372966)