On the open problem of Ginsburg concerning semilinear sets and related problems

DOI10.1016/J.TCS.2013.07.025zbMath1296.68094OpenAlexW2034018160MaRDI QIDQ391304

Shinnosuke Seki, Oscar H. Ibarra

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.07.025

zbMATH Keywords

decidabilitystratifiedsynchronizabilitysemilinear set1-reversal countersmultitape automatareversal-bounded counters

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Related Items (1)

On the Ambiguity and Finite-Valuedness Problems in Acceptors and Transducers

Cites Work

• Unnamed Item
• Logically defined subsets of \(\mathbb{N}{}^ k\)
• Weak Synchronization and Synchronizability of Multitape Pushdown Automata and Turing Machines
• Multitape NFA: Weak Synchronization of the Input Heads
• How to Synchronize the Heads of a Multitape Automaton
• RELATIONAL STRING VERIFICATION USING MULTI-TRACK AUTOMATA
• Deciding whether a relation defined in Presburger logic can be defined in weaker logics
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Bounded Regular Sets
• On Context-Free Languages

This page was built for publication: On the open problem of Ginsburg concerning semilinear sets and related problems