Languages, Decidability, and Complexity

DOI10.1007/978-1-4471-4276-8_2MaRDI QIDQ5496920zbMATH OpenOpenAlexFDO

Authors Stefan Haar, Tomáš Masopust

Publication date 29 January 2015

Published in Lecture Notes in Control and Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-1-4471-4276-8_2

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)

Cites work

• A Second Course in Formal Languages and Automata Theory
• Complexity in union-free regular languages
• Elements of automata theory. Translated from the French by Reuben Thomas
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3902039 (Why is no real title available?)
• scientific article; zbMATH DE number 3509706 (Why is no real title available?)
• scientific article; zbMATH DE number 1339873 (Why is no real title available?)
• scientific article; zbMATH DE number 1033559 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• The classical decision problem.
• Turing machines with sublogarithmic space

Cited in

(9)

• Algorithmic problems and hierarchies of first-order languages
• Decidability problems in grammar systems
• Modern aspects of complexity within formal languages
• scientific article; zbMATH DE number 58306 (Why is no real title available?)
• scientific article; zbMATH DE number 1869614 (Why is no real title available?)
• scientific article; zbMATH DE number 6309316 (Why is no real title available?)
• SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS
• Some Decision Questions Concerning the Time Complexity of Language Acceptors
• On the complexity of decidable cases of the commutation problem of languages

This page was built for publication: Languages, Decidability, and Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5496920)