Series parallel digraphs with loops

DOI10.1007/s00224-012-9409-0zbMath1286.68282OpenAlexW17492227MaRDI QIDQ372966

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

regular expressionsdigraphsforbidden subgraphs

Mathematics Subject Classification ID

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

Related Items

Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ On lengths of edge-labeled graph expressions ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems

Uses Software

• LANGAGE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite automata and unary languages
• Complexity measures for regular expressions
• A characterization of Thompson digraphs.
• Characterization of Glushkov automata
• On theories with a combinatorial definition of 'equivalence'
• An Optimal Construction of Finite Automata from Regular Expressions
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Series-Parallel Automata and Short Regular Expressions
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• The Recognition of Series Parallel Digraphs
• Graph Classes: A Survey
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• 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

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