Papers for

automata theory engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Complexity limits of simple semi conditional grammars revealed

Non-Terminal Complexity of Simple Semi-Conditional Grammars

Abstract: We study the complexity of simple semi-conditional grammars (SSCGs) in terms of the number of their terminals and non-terminals. We show that SSCGs with three non-terminals can generate all RE languages; two non-terminals suffice for linear languages; and one suffices for unary regular languages. We also determine both upper bounds and fundamental limitations of SSCGs: while certain one-non-terminal SSCGs can generate non-context-free languages, every language generated by a one-non-terminal SSCG is in non-deterministic linear space. We also prove that there exists a regular language of alphabet size at least 3 which cannot be generated by any one-non-terminal SSCG. Finally, we prove that membership testing for SSCGs of two non-terminals is already NP-hard.

Sat 12 SeptFormal Languages and Automata Theory

The gist

This paper looks at a special kind of grammar called simple semi-conditional grammars (SSCGs), which are rules that describe how languages form. The authors find out how many building blocks (called non-terminals) these grammars need to create different types of languages, from very simple to very complicated ones. They also show that some SSCGs with only one non-terminal can still make languages that are tricky to recognize, but there are limits to this power. Finally, the paper finds that checking whether a word belongs to a language described by an SSCG with two non-terminals is already a tough problem for computers.

Open → 2609.14181v1