Amalgams of finite inverse semigroups and deterministic context-free languages.
type: Item
instance of: scholarly article
title: Amalgams of finite inverse semigroups and deterministic context-free languages.
zbMATH Open document ID: 1275.20066
author: C. Nuccio
author: A. Cherubini
author: Emanuele Rodaro
published in: Semigroup Forum
publication date: 2012-11-08T00:00:00Z
review text: 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.
reviewed by: Jorge Almeida
Mathematics Subject Classification ID: 20M18
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6103704
zbMATH Keywords: finite inverse semigroups
zbMATH Keywords: amalgams of inverse semigroups
zbMATH Keywords: Schützenberger automata
zbMATH Keywords: context-free graphs
zbMATH Keywords: context-free languages
zbMATH Keywords: word problem
zbMATH Keywords: decidability
MaRDI profile type: Publication
full work available at URL: s00233-012-9399-x
OpenAlex ID: W2067396744
cites work: Regularity Problems for Visibly Pushdown Languages
cites work: Amalgamated free products of inverse semigroups
cites work: Amalgams of free inverse semigroups.
cites work: Amalgams of finite inverse semigroups.
cites work: MULTILINEAR EQUATIONS IN AMALGAMS OF FINITE INVERSE SEMIGROUPS
cites work: Amalgams vs Yamamura's HNN-Extensions of Inverse Semigroups
cites work: Free products with amalgamation of inverse semigroups
cites work: Q4198075
cites work: Inverse Monoids, Trees, and Context-Free Languages
cites work: The theory of ends, pushdown automata, and second-order logic
cites work: Free Inverse Semigroups
cites work: Q3337662
cites work: A graph-based regularity test for deterministic context-free languages
cites work: Decidability of the word problem in Yamamura's HNN extensions of finite inverse semigroups.
cites work: BICYCLIC SUBSEMIGROUPS IN AMALGAMS OF FINITE INVERSE SEMIGROUPS
cites work: Presentations of inverse monoids
cites work: FINITE IDEMPOTENT INVERSE MONOID PRESENTATIONS
DOI: 10.1007/S00233-012-9399-X
description: scientific article; zbMATH DE number 6103704