Amalgams of finite inverse semigroups and deterministic context-free languages. (Q1758227): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 05:35, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Amalgams of finite inverse semigroups and deterministic context-free languages. |
scientific article |
Statements
Amalgams of finite inverse semigroups and deterministic context-free languages. (English)
0 references
8 November 2012
0 references
The paper deals with the standard presentation \(\langle X\mid R\rangle\) of an amalgam \(S=[S_1,S_2;U]\) of finite inverse semigroups. Through the investigation of the structure of the Schützenberger graph \(S\Gamma(X,R;w)\) of a representative \(w\in(X\cup X^{-1})^+\) of an element \(s\) of~\(S\), several algorithmic conclusions are drawn. The main ingredient is to show that \(S\Gamma(X,R;w)\) is a context-free graph in the sense of \textit{D. E. Müller} and \textit{P. E. Schupp} [Bull. Am. Math. Soc., New Ser. 4, 331-334 (1981; Zbl 0484.03019)], and whence the transition graph of a pushdown automaton. Thus, the language recognized by the associated Schützenberger automaton, which recognizes the language of all representatives of elements of \(S\) which lie above \(s\) in the natural order, is a context-free language. An explicit construction for a pushdown automaton recognizing this language is also given. As an application, the authors show that the non-uniform word problem for amalgams of finite inverse semigroups is solvable in polynomial time; decidability had previously been established by \textit{A. Cherubini, J. Meakin} and \textit{B. Piochi} [J. Algebra 285, No. 2, 706-725 (2005; Zbl 1069.20052)]. Another application is that it is decidable whether all \(\mathcal D\)-classes in such an amalgam are finite.
0 references
finite inverse semigroups
0 references
amalgams of inverse semigroups
0 references
Schützenberger automata
0 references
context-free graphs
0 references
context-free languages
0 references
word problem
0 references
decidability
0 references