-1

I'm looking for a notation that is familiar to modern developers and can supersede s-Notation. (additional insight into Rivest's proposal of s-Expression is here)

Is there any Swagger, JSON or other notation that is very intuitive for ACL control?

Improve this question
9

1 Answer 1

Reset to default
0

There is a JSON schema for state machines in the SJOT project:

{
  "$schema": "http://json-schema.org/draft-04/schema#",
  "$ref": "#/definitions/0",
  "definitions": {
    "0": {
      "type": "object",
      "properties": {
        "a": { "$ref": "#/definitions/1" },
        "x": { "type": "boolean" }
      },
      "additionalProperties": false
    },
"<DEF>": {
      "type": "object",
      "properties": {
        "a": { "$ref": "#/definitions/<DEF>+1" },
        "b": {
          "anyOf": [
            { "$ref": "#/definitions/0" },
            { "$ref": "#/definitions/<DEF>" }
          ]
        }
      },
      "additionalProperties": false
    },

The JSON Schema has N definitions. The "words" we validate with the schema are defined by the regular expression (a{N}|a(a|b+){0,N-1}b)*x that describes a sequence of a and b ending in x. The word abbx is represented by the JSON pointer a/b/b/x which is {"a":{"b":{"b":{"x":true}}}}.

Then we add N-1 definitions <DEF> to the schema enumerated "1", "2", "3", ... "N-1" where "<DEF>+1" wraps back to "0" when <DEF> is equal to N-1.

This "NFA" on a two-letter alphabet has N states, only one initial and one final state. Its equivalent minimal DFA has 2^N (2 to the power N) states.

In the worst case, a validator that uses this JSON schema either takes 2^N time or uses 2^N memory "cells" to validate the input.

References

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.