ASD-STE100 and Controlled Natural Languages (CNLs)

Sushma Akoju, Oct 2, 2026 (Fully Human-generated content)

Dedicating this post to an inspiring post from @karpathy and for the love of languages - controlled, constructed, formal and also everything natural and various other languages :)

https://x.com/karpathy/status/2105819303471976479

Controlled Natural Languages like ASD-STE100 written in Definite Clause Grammar (DCG) are designed to translate declarative and interrogative sentences into First Order Logic notations "discourse representation structures". DCG resolves anaphoric references, only after discourse representation structure is constructed, but Processable English (PENG) resolves anaphoric references during parsing when the discourse representation structures are being built up. PENG is a CNL. There are Human-oriented and Machine-oriented CNLs. PENG is also demonstrated by rewriting a TPTP problem from NL to PENG (which is a CNL). Computer Processable Language (CPL) is yet another controlled language developed by BOEING. ACE uses a small set of interpretation rules and in contrast to PENG that relies on predictive editor resolving references as it parses and constructs discourse representation. But CPL interpreter resolves various types of ambiguities using heuristic rules for prepositional phrase attachment, word sense disambiguation, semantic role labeling etc. CPL accepts ground facts, questions and rules while using different but restricted forms of sentences for each one of the three types of accepted sentences. For rules, CPL uses conventional "If this then that" with optional AND connectors. A parsed set of sentences that end up using logical forms to generate "Knowledge Machine (KM) assertions". The KM interpreter employs sophisticated machinery for reasoning using a situation calculus for actions. CPL relies on heuristics.

Regarding expressivity and complexity of CNLs, E2V is a decidable two-variable fragment of FOL(L^2). If a formula in that L^2 is satisfiable it is satisfiable in a finite model. (refer Schwitter, R. (2010, August)). Also ACE is an alternative to Semantic Web languages like OWL (which I worked briefly during Fall 2022 just to learn) and there are variations to OWL's syntax that uses bidirectional translation which uses PENG.

Interestingly, Lite NL is a CNL based on Categorical Grammar with the same expressivity as description logic DL-Lite. DL-Lite is a tractable fragment of OWL and has p-time complexity for main reasoning tasks. There are also "writing support" techniques for predictive feedback. CNLs are evaluated using task-based, paraphrase-based experiments, and graph based experiments.

Springer Berlin Heidelberg 2009 paper on properties and prospects of CNLs suggests that CNLs enable casual users to use SQL/SPARQL . CNLs facilitate human-human and human-machine communication. There are CNLs defined for English, Japanese, Mandarin and so on. CNLs derived from NL, a wider range of speakers find it easier to learn, use, read and write than formal languages like programming languages.

Kuhn, T. (2014)- supplies great insights into formal definitions and surveys along with expressiveness, naturalness alongside complexity up until 2014. Under expressiveness - imprecise languages, less imprecise/other variations of languages - Interpretable, Inexpressible and variations of a) precision P, b) expressiveness E, c) naturalness N and d) simplicity S in languages - with five classes for each P^1 to P^5, E^1 to E^5, N^1 to N^5 and S^1 to S^5 respectively. But it is the PENS classification that describes expressiveness features: because classifications generally need to "cover" for beyond NL uses, such as declarative formal/informal and procedural ones which make expressiveness needed to be weaker, not stricter. Interestingly fictional languages are not in scope such as Newspeak and also maybe Elvish/N'avi. There are many English-based CNLs such as Sowa's syllogisms, Basic English, E-prime and E', CFE, FAA, AirSpeak and ASD-STE where ASD-STE classified as P^2 E^5 N^5 S^1 which disallows "reliable automatic interpretation". Not CNLS - English, Propositional Logic, FOL, COBOL, Manchester OWL syntax. Figure 1 in Kuhn, T. (2014) provides a pairwise comparison to PENS classification and Table 3 provides properties required and Figure 2 with a timelines of the evolution of controlled English. AECMA-SE (processor for ASD-STE) is found to make communication precise and more effective.

An account of constructions in ASD-STE100 (2020) for formalizing non-propositional meanings, language is regulated to write procedural writing "instructions", descriptive writing for "giving information", and rules for "safety instructions". Uses COREL scheme for writing L-1, L-2 and L-3 constructions with various types of ordering types.

INSTRUCTCTG (2023) paper (Instruction-based Controlled Text Generation) - a simple controlled text generation framework that incorporates different constraints by verbalizing them as natural language instructions.Figure 1 in this paper provides examples. This work utilizes meta-in context learning, with fewer constraint-text pairs as demonstration examples and gives access to models to the constraints before decoding. Table 1 provides how INSTRUCTCTG is designed.

Back when I wrote down a proposed thesis proposal draft in 2022-2023 - I was aiming for a subset of NL that was controlled yet is "constructed" to eventually translate to FOL. In 2023, LLMs are capable of translating to FOL though not deterministically which requires additional rules depending on type of task, domain etc. The restrictions of CNLs are in terms of lexicon, syntax and semantics.

Is there a CNL/ACE/PENG/other decidable format of subset of NL for Lean?

References

Abbreviations