{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T03:19:06Z","timestamp":1773717546094,"version":"3.50.1"},"reference-count":53,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2017,2,5]],"date-time":"2017-02-05T00:00:00Z","timestamp":1486252800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We study several classical decision problems on finite automata under the (Strong) Exponential Time Hypothesis. We focus on three types of problems: universality, equivalence, and emptiness of intersection. All these problems are known to be CoNP-hard for nondeterministic finite automata, even when restricted to unary input alphabets. A different type of problems on finite automata relates to aperiodicity and to synchronizing words. We also consider finite automata that work on commutative alphabets and those working on two-dimensional words.<\/jats:p>","DOI":"10.3390\/a10010024","type":"journal-article","created":{"date-parts":[[2017,2,6]],"date-time":"2017-02-06T11:29:27Z","timestamp":1486380567000},"page":"24","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Problems on Finite Automata and the Exponential Time Hypothesis"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4444-3220","authenticated-orcid":false,"given":"Henning","family":"Fernau","sequence":"first","affiliation":[{"name":"FB 4, Informatikwissenschaften, University of Trier, Universit\u00e4tsring, 54286 Trier, Germany"}]},{"given":"Andreas","family":"Krebs","sequence":"additional","affiliation":[{"name":"Wilhelm-Schickard-Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, Sand 13, 72076 T\u00fcbingen, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2017,2,5]]},"reference":[{"key":"ref_1","first-page":"41","article-title":"Lower bounds based on the Exponential Time Hypothesis","volume":"105","author":"Lokshtanov","year":"2011","journal-title":"EATCS Bull."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","article-title":"Which Problems Have Strongly Exponential Complexity?","volume":"63","author":"Impagliazzo","year":"2001","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_3","unstructured":"Calabro, C., Impagliazzo, R., and Paturi, R. (2006, January 16\u201320). A Duality between Clause Width and Clause Density for SAT. Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC), Prague, Czech Republic."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., and Kratsch, D. (2010). Exact Exponential Algorithms, Springer. Texts in Theoretical Computer Science.","DOI":"10.1007\/978-3-642-16533-7"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (2013). Fundamentals of Parameterized Complexity, Springer. Texts in Computer Science.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1016\/j.ic.2010.11.013","article-title":"Descriptional and computational complexity of finite automata\u2014A survey","volume":"209","author":"Holzer","year":"2011","journal-title":"Inf. Comput."},{"key":"ref_8","first-page":"89","article-title":"Problems on Finite Automata and the Exponential Time Hypothesis. Implementation and Application of Automata","volume":"Volume 9705","author":"Han","year":"2016","journal-title":"Proceedings of the 21st International Conference CIAA 2016, Seoul, South Korea, 19\u201322 July 2016"},{"key":"ref_9","unstructured":"Aho, A.V., Borodin, A., Constable, R.L., Floyd, R.W., Harrison, M.A., Karp, R.M., and Strong, H.R. (May, January 30). Word Problems Requiring Exponential Time: Preliminary Report. Proceedings of the 5th Annual ACM Symposium on Theory of Computing, STOC, Austin, TX, USA."},{"key":"ref_10","unstructured":"Landau, E. (1909). Handbuch der Lehre von der Verteilung der Primzahlen, Teubner."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","article-title":"Finite automata and unary languages","volume":"47","author":"Chrobak","year":"1986","journal-title":"Theor. Comput. Sci."},{"key":"ref_12","first-page":"17","article-title":"Antichains: A New Algorithm for Checking Universality of Finite Automata","volume":"Volume 4144","author":"Ball","year":"2006","journal-title":"Proceedings of the 18th International Conference CAV 2006, Seattle, WA, USA, 17\u201320 August 2006"},{"key":"ref_13","first-page":"346","article-title":"The Emptiness Problem for Intersections of Regular Languages","volume":"Volume 629","author":"Havel","year":"1992","journal-title":"Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, MFCS\u201992, Prague, Czech Republic, 24\u201328 August 1992"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF00263744","article-title":"Hierarchies of Complete Problems","volume":"6","author":"Galil","year":"1976","journal-title":"Acta Inf."},{"key":"ref_15","first-page":"302","article-title":"The parameterized complexity of intersection and composition operations on sets of finite-state automata","volume":"Volume 2088","author":"Yu","year":"2001","journal-title":"Proceedings of the 5th International Conference on Implementation and Application of Automata, CIAA 2000, Ontario, Canada, 24\u201325 July 2000"},{"key":"ref_16","unstructured":"Dusart, P. (2010). Estimates of Some Functions Over Primes without R.H."},{"key":"ref_17","unstructured":"Kozen, D. (November, January 31). Lower Bounds for Natural Proof Systems. Proceedings of the 18th Annual Symposium on Foundations of Computer Science, FOCS, Providence, RI, USA."},{"key":"ref_18","first-page":"287","article-title":"Polynomial Kernels for Weighted Problems","volume":"Volume 9235","author":"Italiano","year":"2015","journal-title":"Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015, Milan, Italy, 24\u201328 August 2015"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0304-3975(02)00830-7","article-title":"On the complexity of intersecting finite state automata and NLversus NP","volume":"302","author":"Karakostas","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_20","first-page":"354","article-title":"Hardness Results for Intersection Non-Emptiness","volume":"Volume 8573","author":"Esparza","year":"2014","journal-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming\u2014ICALP 2014, Copenhagen, Denmark, 8\u201311 July 2014"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","article-title":"On finite monoids having only trivial subgroups","volume":"8","year":"1965","journal-title":"Inf. Control (Inf. Comput.)"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0304-3975(91)90075-D","article-title":"Finite-Automaton Aperiodicity is PSPACE-Complete","volume":"88","author":"Cho","year":"1991","journal-title":"Theor. Comput. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/S0019-9958(85)80058-9","article-title":"Complexity of Some Problems from the Theory of Automata","volume":"66","author":"Stern","year":"1985","journal-title":"Inf. Control (Inf. Comput.)"},{"key":"ref_24","first-page":"49","article-title":"Fast FAST","volume":"Volume 5555","author":"Albers","year":"2009","journal-title":"Proceedings of the 36th International Colloquium on Automata, Languages and Programming\u2014ICALP 2009, Rhodes, Greece, 5\u201312 July 2009"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1109\/TST.2014.6867519","article-title":"Social Choice Meets Graph Drawing: How to Get Subexponential Time Algorithms for Ranking and Drawing Problems","volume":"19","author":"Fernau","year":"2014","journal-title":"Tsinghua Sci. Technol."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1145\/146637.146661","article-title":"The Membership Problem in Aperiodic Transformation Monoids","volume":"39","author":"Beaudry","year":"1992","journal-title":"J. ACM"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/j.ic.2010.11.009","article-title":"Decision problems for convex languages","volume":"209","author":"Brzozowski","year":"2011","journal-title":"Inf. Comput."},{"key":"ref_28","first-page":"208","article-title":"Pozn\u00e1mka k homog\u00e9nnym experimentom s kone\u010dn\u00fdmi automatmi","volume":"14","year":"1964","journal-title":"Matematicko-fyzik\u00e1lny \u010dasopis"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1016\/j.jcss.2014.12.027","article-title":"A multi-parameter analysis of hard problems on deterministic finite automata","volume":"81","author":"Fernau","year":"2015","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/11498490_2","article-title":"Homing and Synchronizing Sequences","volume":"Volume 3472","author":"Broy","year":"2005","journal-title":"Model-Based Testing of Reactive Systems"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(83)90067-4","article-title":"Polynomial Complete Problems in Automata Theory","volume":"16","author":"Rystsov","year":"1983","journal-title":"Inf. Process. Lett."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(92)90002-W","article-title":"The Parallel Complexity of Finite-State Automata Problems","volume":"97","author":"Cho","year":"1992","journal-title":"Inf. Comput."},{"key":"ref_33","unstructured":"Stockmeyer, L.J. (1974). The complexity of decision problems in automata theory and logic. [Ph.D. Thesis, Massachusetts Institute of Technology]."},{"key":"ref_34","unstructured":"Shmoys, D.B. (June, January 31). Analytical approach to parallel repetition. Proceedings of the 46th Annual ACM Symposium on Theory of Computing\u2014STOC 2014, New York, NY, USA."},{"key":"ref_35","first-page":"202","article-title":"Scanning Pictures the Boustrophedon Way","volume":"Volume 9448","author":"Barneva","year":"2015","journal-title":"Proceedings of the International Workshop on Combinatorial Image Analysis\u2014IWCIA 2015, Kolkata, India, 24\u201327 November 2015"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1555","DOI":"10.1142\/S0129054112500244","article-title":"Jumping Finite Automata","volume":"23","author":"Meduna","year":"2012","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_37","unstructured":"Fernau, H., Paramasivan, M., Schmid, M.L., and Vorel, V. (2015). Characterization and Complexity Results on Jumping Finite Automata."},{"key":"ref_38","unstructured":"Haase, C., and Hofman, P. (2015). Tightening the Complexity of Equivalence Problems for Commutative Grammars."},{"key":"ref_39","first-page":"291","article-title":"The complexity of semilinear sets","volume":"18","author":"Huynh","year":"1982","journal-title":"Elektronische Informationsverarbeitung und Kybernetik (jetzt J. Inf. Process. Cybern. EIK)"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0019-9958(83)80022-9","article-title":"Commutative grammars: The complexity of uniform word problems","volume":"57","author":"Huynh","year":"1983","journal-title":"Inf. Control"},{"key":"ref_41","first-page":"1","article-title":"Complexity of Problems of Commutative Grammars","volume":"11","year":"2015","journal-title":"Log. Methods Comput. Sci."},{"key":"ref_42","first-page":"191","article-title":"Closure Properties of Multiset Language Families","volume":"49","author":"Kudlek","year":"2002","journal-title":"Fundam. Inf."},{"key":"ref_43","first-page":"215","article-title":"Two-dimensional languages","volume":"Volume III","author":"Rozenberg","year":"1997","journal-title":"Handbook of Formal Languages"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/978-3-642-24897-9_9","article-title":"A Survey on Picture-Walking Automata","volume":"Volume 7020","author":"Kuich","year":"2011","journal-title":"Algebraic Foundations in Computer Science"},{"key":"ref_45","first-page":"112","article-title":"Recognizable vs. Regular Picture Languages","volume":"Volume 4728","author":"Bozapalidis","year":"2007","journal-title":"Proceedings of the Second International Conference on Algebraic Informatics\u2014CAI 2007, Thessaloniki, Greece, 21\u201325 May 2007"},{"key":"ref_46","first-page":"134","article-title":"Rectangles and Squares Recognized by Two-Dimensional Automata","volume":"Volume 3113","author":"Maurer","year":"2004","journal-title":"Theory Is Forever, Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday"},{"key":"ref_47","first-page":"374","article-title":"Some Results Concerning Two-Dimensional Turing Machines and Finite Automata","volume":"Volume 965","author":"Reichel","year":"1995","journal-title":"Proceedings of the 10th International Symposium on Fundamentals of Computation Theory\u2014FCT \u201995, Dresden, Germany, 22\u201325 August 1995"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"1278","DOI":"10.1016\/j.jcss.2015.03.005","article-title":"Regular expressions for data words","volume":"81","author":"Libkin","year":"2015","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/S0304-3975(99)00105-X","article-title":"Intractability of decision problems for finite-memory automata","volume":"231","author":"Sakamoto","year":"2000","journal-title":"Theor. Comput. Sci."},{"key":"ref_50","unstructured":"Charikar, M. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, USA, 17\u201319 January 2010."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Chen, J., Huang, X., Kanj, I.A., and Xia, G. (2004, January 13\u201316). Linear FPT reductions and computational lower bounds. Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA.","DOI":"10.1145\/1007352.1007391"},{"key":"ref_52","first-page":"414","article-title":"On the Complexity of Intersecting Regular, Context-Free, and Tree Languages","volume":"Volume 9135","author":"Iwama","year":"2015","journal-title":"Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015, Kyoto, Japan, 6\u201310 July 2015"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.tcs.2015.07.032","article-title":"Boundary sets of regular and context-free languages","volume":"610","author":"Holzer","year":"2016","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/1\/24\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:27:29Z","timestamp":1760207249000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/1\/24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,5]]},"references-count":53,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2017,3]]}},"alternative-id":["a10010024"],"URL":"https:\/\/doi.org\/10.3390\/a10010024","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,5]]}}}