Jiří Koutný Engineering Manager · Lecturer · Pilot
Ph.D. Thesis · Brno University of Technology · 2012

Grammars, reimagined.

How do you make a grammar more powerful without making it harder to use? My doctoral work answers that by restricting the shape of derivation trees — keeping the simplicity of context-free rules while reaching languages they normally can't describe.

View the thesis at FIT BUT ↗
B a b d e S A D c
A derivation tree. Its leaves, left to right, spell the generated word. Reading the highlighted root-to-leaf path top-down gives word(p) = S·A·D·c. These grammars require such a path — or a cut (a frontier of nodes, below) — to belong to a separate control language, while every production stays context-free.
THE PROBLEM

Languages — human or machine — are built from rules, and grammars formalize those rules. Context-free grammars have long been the workhorse: simple enough to parse efficiently, expressive enough for most programming languages.

But real structure often escapes them. Cross-serial dependencies in natural language and RNA pseudoknots in biology have shapes a context-free grammar cannot capture. Context-sensitive grammars are more powerful, but their complexity and undecidability make them impractical.

The question driving this thesis: can we keep the structural clarity of context-free rules while expanding what they express — not by rewriting the rules, but by regulating how and when they apply? That is the domain of regulated rewriting through grammars with restricted derivation trees.

BACKGROUND

Regulating derivations is a decades-old idea. Several models set the stage:

Matrix & vector grammars

Govern fixed sequences of productions — synchronized, but purely linear, with no regard for tree structure.

Programmed & controlled grammars

Add explicit control over the order productions fire, but likewise ignore the derivation tree.

Tree-controlled (level) grammars

Introduced by Culik & Maurer: restrict which productions may appear at each level of the tree — foundational, but often either too weak or jumping straight to recursively enumerable power.

Path-controlled grammars

Regulate root-to-leaf paths for finer control — but early formulations leaned on erasing rules, lacked normal forms, and left their true generative power unclear.

What was still open
—

Tree-level restrictions were either too rigid or computationally impractical.

—

Linear models ignored hierarchical derivation structure entirely.

—

Path-based grammars lacked formal rigor, normal forms, and parsing insight.

—

No model used derivation cuts to modularize control, or regulated several paths at once.

THREE CONTRIBUTIONS

The thesis extends regulated rewriting in three original directions — each adds power while preserving context-free productions.

Cuts
A frontier of nodes; their labels spell word(c).
Paths
One root-to-leaf path; its labels spell word(p).
Multiple paths
Several paths, each spelling a controlled word.
01

Cut-based restrictions

A new model. Cuts are horizontal slices through a derivation tree where rewriting is frozen or resumed under defined constraints, allowing modular, staged derivation.

Result

Generates the recursively enumerable languages while keeping context-free rules — and opens a research line on ordered cuts and cut languages.

02

Path-based restrictions, refined

Revisits and corrects the existing path-controlled model: analyzes the impact of erasing (ε) productions and introduces two normal forms that remove the dependence on them.

Result

Formally corrects an overestimated prior claim about generative power, and draws a new link between path control and RNA pseudoknots — connecting formal language theory to structural bioinformatics.

03

Multi-path restrictions

Generalizes path control to several paths at once — n-path-controlled grammars — including an all-paths restriction that regulates every path in the tree.

Result

Establishes pumping and closure properties tied to the number of controlled paths, approximates generative power across levels of control, and keeps parsing tractable.

Across all three models
—

Tailored pumping lemmas for class separation and language analysis.

—

Closure under union, concatenation, and intersection with regular languages.

—

Parsing directions emphasizing tractability and polynomial-time potential for restricted subclasses.

RECEPTION

“His thesis contains original, valuable contributions. I fully recommended it for defense.”

Prof. Alexander Meduna · Supervisor

“A leading-edge topic. The thesis introduces new models, fixes flaws in prior work, and extends the theory significantly. Recommended without hesitation.”

doc. Ing. Jan Janoušek, Ph.D. · Opponent · CTU in Prague

“Cut-controlled grammars are introduced for the first time; the path-grammar theory was clarified and improved. The thesis meets PhD standards. Recommended for acceptance.”

Prof. Ing. Tomáš Vojnar, Ph.D. · Opponent · Brno University of Technology
THE DEFENSE

Defended on 18 September 2012 at the Faculty of Information Technology, Brno University of Technology, before a five-member committee chaired by Prof. Ing. Tomáš Hruška, CSc.

Unanimous approval — 5 of 5 — passed (prospěl).

PUBLICATIONS
  1. Tree-controlled grammars with restrictions placed upon cuts and paths Kybernetika · 2012
  2. Normal forms and erasure-free path-controlled grammars Schedae Informaticae
  3. Parsing strategies for multi-path grammars Theoretical and Applied Informatics · 2012
  4. On n-language hierarchies and structural regulation Acta Cybernetica
RECOGNITION
—

First place at the EEICT student conference (2009, 2010, 2012); second place (2008, 2011).

—

FRVŠ research grant FR2581/2010/G1.

—

Talks on syntax analysis, pumping lemmas, and pseudoknot modeling; co-organized DMTI 2010 and LTA 2011.

—

Taught Formal Languages & Compilers and Compiler Construction.

WHERE IT CAN GO
—

Ordered cuts — sequential constraints across multiple cuts.

—

Cut languages governing the placement and rules of cuts.

—

Probabilistic and weighted path-based grammars.

—

Minimal path-set optimization for multi-path coverage.

—

Deeper application to RNA and other structured biomolecules.

—

Tooling for grammar analysis and verification.

CITATION

KOUTNÝ, Jiří. Grammars with Restricted Derivation Trees. Ph.D. Thesis. Brno University of Technology, Faculty of Information Technology, 18 September 2012. Supervised by Prof. Alexander Meduna.

@phdthesis{FITPT355,
  author = {Jiří Koutný},
  title  = {Grammars with Restricted Derivation Trees},
  school = {Brno University of Technology, Faculty of Information Technology},
  year   = {2012},
  type   = {Ph.D. thesis},
  url    = {https://www.fit.vut.cz/study/phd-thesis/355/}
}
View the thesis at FIT BUT ↗

By inventing and refining ways to restrict how derivation trees grow — through cuts and paths — this thesis expands the power of grammars, opens new theoretical possibilities, and provides practical pathways for handling complex languages.

Jiří Koutný {{ navTagline }}
{{ t.hero.kicker }}

{{ t.hero.titleA }} {{ t.hero.titleB }}

{{ t.hero.lead }}

{{ p.kicker }}

{{ p.title }}

{{ p.teaser }}

{{ p.stat }}
{{ p.cta }} {{ p.arrow }}
{{ labels.posts }}

{{ t.posts.title }}

{{ t.posts.all }} →
{{ post.category }}
{{ post.date }} · {{ post.readLabel }}

{{ post.title }}

{{ post.excerpt }}
{{ labels.contact }}

{{ t.contact.title }}

{{ t.contact.lead }}

{{ d.label }}
{{ d.value }}
{{ t.about.label }}

{{ t.about.title }}

{{ t.about.lead }}

{{ t.about.achievementsLabel }}

{{ ac.stat }}
{{ ac.label }}
{{ ac.text }}
{{ aboutBaseLabel }}
{{ aboutBaseValue }}

{{ para }}

{{ t.about.expLabel }}

{{ job.tenure }}
{{ job.place }}

{{ job.org }}

{{ r.title }} {{ r.period }}

{{ pt }}

{{ t.about.teachingLabel }}

{{ job.tenure }}
{{ job.place }}

{{ job.org }}

{{ r.title }} {{ r.period }}

{{ pt }}

{{ t.about.earlierLabel }}

{{ t.about.earlierText }}

{{ t.about.eduLabel }}

{{ ed.period }}
{{ ed.school }}
{{ ed.degree }}

{{ ed.note }}

{{ t.about.staysLabel }}

{{ t.about.staysIntro }}

{{ grp.year }}
{{ s.period }}
{{ s.inst }} · {{ s.place }}
{{ s.what }}
{{ t.aviation.label }}

{{ t.aviation.title }}

{{ t.aviation.lead }}

{{ s.label }}
{{ s.value }}
{{ a.title }}
{{ a.body }}
{{ t.aviation.project.tag }}

{{ t.aviation.project.name }}

{{ t.aviation.project.tagline }}

{{ t.aviation.project.body }}

{{ t.aviation.project.cta }} ↗
{{ p }}
{{ t.aviation.flyWithMe.kicker }}

{{ t.aviation.flyWithMe.title }}

{{ t.aviation.flyWithMe.body }}

{{ t.aviation.flyWithMe.cta }} →
{{ t.grammars.kicker }}

{{ t.grammars.title }}

{{ t.grammars.lead }}

{{ t.grammars.thesisLinkLabel }} ↗
B a b d e S A D c
A derivation tree. Its leaves, left to right, spell the generated word. Reading the highlighted root-to-leaf path top-down gives word(p) = S·A·D·c. These grammars require such a path — or a cut (a frontier of nodes, below) — to belong to a separate control language, while every production stays context-free.
{{ t.grammars.problemLabel }}

{{ para }}
{{ t.grammars.bgLabel }}

{{ t.grammars.bgIntro }}

{{ m.name }}

{{ m.text }}
{{ t.grammars.limitsLabel }}
—

{{ lim }}
{{ t.grammars.contribLabel }}

{{ t.grammars.contribIntro }}

Cuts
A frontier of nodes; their labels spell word(c).
Paths
One root-to-leaf path; its labels spell word(p).
Multiple paths
Several paths, each spelling a controlled word.
{{ c.n }}

{{ c.name }}

{{ c.what }}

{{ t.grammars.resultWord }}

{{ c.result }}
{{ t.grammars.acrossLabel }}
—

{{ a }}
{{ t.grammars.receptionLabel }}

“{{ r.quote }}”

{{ r.who }} · {{ r.role }}
{{ t.grammars.defenseLabel }}

{{ t.grammars.defenseText }}

{{ t.grammars.defenseResult }}

{{ t.grammars.pubsLabel }}
  1. {{ p.title }} {{ p.venue }}
{{ t.grammars.recognitionLabel }}
—

{{ r }}
{{ t.grammars.futureLabel }}
—

{{ f }}
{{ t.grammars.citationLabel }}

{{ t.grammars.citation }}

{{ t.grammars.bibtex }}
{{ t.grammars.thesisLinkLabel }} ↗

{{ t.grammars.oneLine }}
{{ labels.posts }}

{{ t.posts.title }}

{{ leadPost.category }}·{{ leadPost.date }}·{{ leadPost.readLabel }}

{{ leadPost.title }}

{{ leadPost.excerpt }}

{{ t.posts.readMore }} →
{{ post.category }}
{{ post.date }} · {{ post.readLabel }}

{{ post.title }}

{{ post.excerpt }}
← {{ t.posts.all }}
{{ currentPost.category }}·{{ currentPost.date }}·{{ currentPost.readLabel }}

{{ currentPost.title }}
404

{{ notFound.title }}

{{ notFound.body }}