Series parallel digraphs with loops

DOI10.1007/S00224-012-9409-0zbMATH Open1286.68282OpenAlexW17492227MaRDI QIDQ372966FDOQ372966

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

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

zbMATH Keywords

digraphsforbidden subgraphsregular expressions

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Complexity measures for regular expressions
• Title not available (Why is that?)
• Graph Classes: A Survey
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• On theories with a combinatorial definition of 'equivalence'
• The Recognition of Series Parallel Digraphs
• Regular expressions: new results and open problems
• Title not available (Why is that?)
• Finite automata and unary languages
• A characterization of Thompson digraphs.
• Characterization of Glushkov automata
• Title not available (Why is that?)
• An optimal construction of finite automata from regular expressions
• Series-Parallel Automata and Short Regular Expressions
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Succinctness of the complement and intersection of regular expressions
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Parallel algorithms for series parallel graphs and graphs with treewidth two
• 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

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)