Skip to content
HALOWERK

Datenvertragswerk

dfa subsequence downward closure

Given one complete binary DFA with1..4states, construct its full subsequence downward-closure language: u is accepted iff u embeds, by deleting any positions, in some originally accepted word. Original language may be infinite. Add silent deletion edges parallel to every original0/1edge, close reachability, and determinize. Return epsilon_masks by original state; canonical reachable subset DFA in breadth-first discovery order, startindex0, exploring0then1; and ALL31binary words of length0..4.

POST https://datenvertrag.halowerk.com/v1/dfa-subsequence-downward-closure

Inputs

Fields of the published input schema
FieldTypeRequiredDescription
dfaSee schemaYes
claimSee schemaYes
Show full input schema
{
  "type": "object",
  "properties": {
    "dfa": {
      "anyOf": [
        {
          "type": "object",
          "properties": {
            "start": {
              "type": "integer",
              "minimum": 0,
              "maximum": 3
            },
            "transitions": {
              "type": "array",
              "items": {
                "type": "array",
                "items": {
                  "type": "integer",
                  "minimum": 0,
                  "maximum": 3
                },
                "minItems": 2,
                "maxItems": 2
              },
              "minItems": 1,
              "maxItems": 4
            },
            "accepting": {
              "type": "array",
              "items": {
                "type": "boolean"
              },
              "minItems": 1,
              "maxItems": 4
            }
          },
          "required": [
            "start",
            "transitions",
            "accepting"
          ],
          "additionalProperties": false
        },
        {
          "type": "null"
        }
      ]
    },
    "claim": {
      "anyOf": [
        {
          "type": "object",
          "properties": {
            "subsets": {
              "type": "array",
              "items": {
                "type": "integer",
                "minimum": 0,
                "maximum": 15
              },
              "minItems": 1,
              "maxItems": 16
            },
            "transitions": {
              "type": "array",
              "items": {
                "type": "array",
                "items": {
                  "type": "integer",
                  "minimum": 0,
                  "maximum": 15
                },
                "minItems": 2,
                "maxItems": 2
              },
              "minItems": 1,
              "maxItems": 16
            },
            "accepting": {
              "type": "array",
              "items": {
                "type": "boolean"
              },
              "minItems": 1,
              "maxItems": 16
            }
          },
          "required": [
            "subsets",
            "transitions",
            "accepting"
          ],
          "additionalProperties": false
        },
        {
          "type": "null"
        }
      ]
    }
  },
  "required": [
    "dfa",
    "claim"
  ],
  "additionalProperties": false
}

Open original schema

Published input example

{
  "dfa": {
    "start": 0,
    "transitions": [
      [
        0,
        0
      ]
    ],
    "accepting": [
      false
    ]
  },
  "claim": {
    "subsets": [
      1
    ],
    "transitions": [
      [
        0,
        0
      ]
    ],
    "accepting": [
      false
    ]
  }
}

Result & documentation

Machine-readable documentation of this hub

Source of this page: the published HALOWERK catalog. Updated: 2026-11-17 UTC.

More endpoints in this hub

All endpoints in this hub โ†’