\(Q\)-grammars and wall polyominoes (Q1306603): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf01608790 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2092841585 / rank | |||
Normal rank |
Latest revision as of 10:29, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(Q\)-grammars and wall polyominoes |
scientific article |
Statements
\(Q\)-grammars and wall polyominoes (English)
0 references
5 October 1999
0 references
A wall polyomino (or bar-graph polygon or solid-on-solid walk) is defined as a vertically convex polyomino in which all columns have their lowest cell at the same level. The upper path of such a polyomino can be bijectively coded with words using letters \(x\), \(y\), \(\overline y\) (corresponding to east, north and south steps). The language of nonempty words coding such polyominoes is algebraic and is generated by an unambiguous grammar. A slightly different grammar corresponds to coding directed positive words. The grammars lead to functional equations for generating functions for the polyominoes. The form of these equations, and some simple singularity computations, are used to prove that the area of wall polyominoes of perimeter \(2n\) has the Airy distribution as a limit law.
0 references
asymptotic enumeration
0 references
polyomino
0 references
words
0 references
coding
0 references
grammar
0 references
generating functions
0 references
0 references
0 references