2 papers
cs.LO2009
Degrees of Undecidability in Rewriting
Joerg Endrullis, Herman Geuvers, Hans Zantema
Undecidability of various properties of first order term rewriting systems is well-known. An undecidable property can be classified by the complexity of the formula defining it. Th…
math.CO2006
Minimum Mean Cycle Problem in Bidirected and Skew-Symmetric Graphs
Maxim A. Babenko, Alexander V. Karzanov
The problem of finding, in an edge-weighted bidirected graph , a cycle with minimum mean weight of its edges generalizes similar problems for both directed and undirected…