On the Complexity of Universality for Partially Ordered NFAs

DOI10.4230/LIPICS.MFCS.2016.62MaRDI QIDQ4608625zbMATH OpenOpenAlexFDO

Authors Orna Kupferman, Gal Vardi

Publication date 21 March 2018

Full work available at URL https://inria.hal.science/hal-01334958

zbMATH Keywords

Eulerian pathsregular languages

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• Acyclic orientations with path constraints
• Curvature-constrained directional-cost paths in the plane
• Constrained rough paths
• Rectilinear paths among rectilinear obstacles
• Polygonal path approximation with angle constraints
• On minimum-time paths of bounded curvature with position-dependent constraints
• Polygon-constrained motion planning problems
• scientific article; zbMATH DE number 1696623
• On a constrained variational problem and the space of horizontal paths
• Finding curvature-constrained paths that avoid polygonal obstacles

Cited in

(4)

• Minimal Eulerian Circuit in a Labeled Digraph
• Engineering label-constrained shortest-path algorithms
• Formal-Language-Constrained Path Problems
• When is string reconstruction using de Bruijn graphs hard?

This page was built for publication: On the Complexity of Universality for Partially Ordered NFAs

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