Some decision problems concerning semilinearity and commutation.
type: Item
instance of: scholarly article
title: Some decision problems concerning semilinearity and commutation.
zbMATH Open document ID: 1059.68061
author: Tero Harju
author: Oscar H. Ibarra
author: Arto Salomaa
author: Juhani Karhumäki
published in: Journal of Computer and System Sciences
publication date: 2003-05-14T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 1910836
zbMATH Keywords: reversal-bounded counters
zbMATH Keywords: context-free languages
zbMATH Keywords: combinatorics on words
zbMATH Keywords: commutation of languages
zbMATH Keywords: morphisms.
MaRDI profile type: Publication
full work available at URL: jcss.2002.1836
OpenAlex ID: W1973654289
cites work: MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS
cites work: Q4714446
cites work: Q4510794
cites work: On the decidability of homomorphism equivalence for languages
cites work: Q5576254
cites work: Checking automata and one-way stack languages
cites work: The complexity of decision problems for finite-turn multicounter machines
cites work: Q4265634
cites work: Q4198075
cites work: Q3773369
cites work: Reversal-Bounded Multicounter Machines and Their Decision Problems
cites work: Q4536602
cites work: New Decidability Results Concerning Two-Way Counter Machines
cites work: A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\)
cites work: Q3659988
cites work: On Context-Free Languages
cites work: Q5678435
cites work: \(L(A)=L(B)\)? decidability results from complete formal systems
cites work: Decidability of DPDA equivalence
DOI: 10.1006/JCSS.2002.1836
Recommended article: A decision problem for varieties of commutative semigroups
Recommended article: Q3123871
Recommended article: Q3824386
Recommended article: Some decision problems on integer matrices
Recommended article: Q4706072
Recommended article: Q4535049
Recommended article: DECISION AND SEPARABILITY PROBLEMS FOR BAUMSLAG–SOLITAR SEMIGROUPS
Recommended article: On confluent semi-commutations: Decidability and complexity results
Recommended article: DECISION PROBLEMS FOR FINITELY PRESENTED AND ONE-RELATION SEMIGROUPS AND MONOIDS
Recommended article: Q4362736
description: scientific article; zbMATH DE number 1910836