---
title: "Decidability and shortest strings in formal languages"
authors:
  - "Levent Alpoge"
  - "Thomas Ang"
  - "Luke Schaeffer"
  - "Jeffrey Shallit"
year: 2011
venue: "Descriptional Complexity of Formal Systems (LNCS 6808)"
arxiv: "1103.1622"
doi: "10.1007/978-3-642-22600-7_5"
source: "https://arxiv.org/abs/1103.1622"
topics:
  - "number-theory"
seed_rank: 1218
seed_batch: "alpoge-math-2026-08-24"
reviewed: "2026-08-24"
pool: "maths-foundations"
relevance_score: 7
lineage: arithmetic-geometry
cites:
  []
see:
  []
---

# Decidability and shortest strings in formal languages

## One-sentence takeaway

Given a language specified in various ways, decide emptiness and bound the shortest word — high-school / early-college work with Shallit, before the number-theory turn.

## Why it's lovely

The formal-languages fossil in an otherwise arithmetic-geometry corpus. Real paper, LNCS, Shallit.

## Problem

Emptiness and shortest-word length for languages under several presentations.

## Design

Automata / descriptional-complexity arguments; upper and lower bounds.

## Evidence

DCFS 2011, LNCS 6808, 55-67. DOI 10.1007/978-3-642-22600-7_5. arXiv:1103.1622.

## Limitations

Not number theory. Included because it is a sourced research paper on the homepage.

## Implications for Broadside

Corpus completeness. Not a Broadside engine paper.

## Bottom line

Mint 1103.1622.

## Links

- arXiv: [1103.1622](https://arxiv.org/abs/1103.1622)
- DOI: [10.1007/978-3-642-22600-7_5](https://doi.org/10.1007/978-3-642-22600-7_5)