Some decision problems concerning semilinearity and commutation.

DOI10.1006/jcss.2002.1836zbMath1059.68061OpenAlexW1973654289MaRDI QIDQ1872706

Oscar H. Ibarra, Tero J.Harju, Arto Salomaa, Juhani Karhumäki

Publication date: 14 May 2003

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2002.1836

zbMATH Keywords

context-free languagescombinatorics on wordsreversal-bounded counterscommutation of languagesmorphisms.

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items (34)

On the solvability of a class of Diophantine equations and applications ⋮ The effect of end-markers on counter machines and commutativity ⋮ Subword histories and Parikh matrices ⋮ Playing with Conway's problem ⋮ Visit-bounded stack automata ⋮ Families of languages defined by ciliate bio-operations ⋮ On the computational complexity of membrane systems ⋮ Visibly pushdown transducers ⋮ Deletion operations on deterministic families of automata ⋮ On store languages and applications ⋮ On counting functions and slenderness of languages ⋮ On sets of numbers accepted by P/T systems composed by join ⋮ Input-Position-Restricted Models of Language Acceptors ⋮ On the complexity and decidability of some problems involving shuffle ⋮ Bounded underapproximations ⋮ On spiking neural P systems and partially blind counter machines ⋮ Accepting runs in a two-way finite automaton ⋮ Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity ⋮ On the Boundedness Property of Semilinear Sets ⋮ On the complexity of decidable cases of the commutation problem of languages ⋮ Visit-bounded stack automata ⋮ One-reversal counter machines and multihead automata: revisited ⋮ On membrane hierarchy in P systems ⋮ Variations of checking stack automata: obtaining unexpected decidability properties ⋮ On store languages of language acceptors ⋮ On spiking neural P systems ⋮ One-Reversal Counter Machines and Multihead Automata: Revisited ⋮ On Families of Full Trios Containing Counter Machine Languages ⋮ On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L ⋮ Characterizations of some classes of spiking neural P systems ⋮ On composition and lookahead delegation of \(e\)-services modeled by automata ⋮ On families of full trios containing counter machine languages ⋮ Semilinearity of Families of Languages ⋮ A sharpening of the Parikh mapping

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of decision problems for finite-turn multicounter machines
• On the decidability of homomorphism equivalence for languages
• \(L(A)=L(B)\)? decidability results from complete formal systems
• A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\)
• Checking automata and one-way stack languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• New Decidability Results Concerning Two-Way Counter Machines
• On Context-Free Languages
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS
• Decidability of DPDA equivalence

This page was built for publication: Some decision problems concerning semilinearity and commutation.