Intersecting Dense Automata

Dmitry Chistikov; Neha Rino

arxiv: 2605.20421 · v1 · pith:52I5OWJOnew · submitted 2026-05-19 · 💻 cs.FL · cs.LO

Intersecting Dense Automata

Dmitry Chistikov , Neha Rino This is my paper

Pith reviewed 2026-05-21 06:25 UTC · model grok-4.3

classification 💻 cs.FL cs.LO

keywords NFA intersectionemptiness problemdense automataproduct constructionclique detectioncombinatorial algorithmsfinite automata

0 comments

The pith

NFA intersection can be constructed with O(m n) transitions instead of quadratic blowup.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that the classical product construction for intersecting the languages of nondeterministic finite automata creates too many transitions when the input automata have many edges. It gives new constructions that produce an intersection automaton with only O(m n) transitions for two automata or O(m n^{k-1}) transitions for a fixed number k of automata. These constructions immediately yield a faster algorithm for deciding whether the intersection language is empty. A reader would care because the improvement is substantial for dense automata and the resulting emptiness test is shown to be optimal unless a major advance occurs in detecting cliques in graphs.

Core claim

The authors present alternative constructions for the intersection of k nondeterministic finite automata that use O(m n^{k-1}) transitions, where n is the maximum number of states and m the maximum number of transitions across the input automata. This improves on the classical Cartesian product, which can require Theta(m^k) transitions in the worst case. The new automata support a faster decision procedure for emptiness of the intersection and also give a more efficient way to certify that the intersection is empty.

What carries the argument

The alternative transition-sparse product construction for dense NFAs, which iterates over the transitions of one automaton while tracking reachable states in the others to keep the total number of edges linear in m times a polynomial in n.

If this is right

Emptiness of the intersection of a fixed number k of NFAs can be decided faster than by building the full product automaton.
The same constructions supply a more efficient certificate that the intersection language is empty.
The reduction from clique detection to NFA intersection emptiness shows that any substantial improvement to the emptiness algorithm would yield a corresponding improvement for clique detection.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same style of construction may apply to other decision problems on NFAs whose complexity is currently dominated by the size of the product automaton.
If the transition bound can be tightened further for specific alphabets or automaton classes, the emptiness test would become practical for larger instances.

Load-bearing premise

The optimality of the new algorithm rests on the premise that no combinatorial algorithm for detecting (k+1)-cliques in undirected graphs improves substantially on the best known bounds.

What would settle it

A combinatorial algorithm that solves (k+1)-clique detection in time asymptotically better than the time bound implied by the new NFA emptiness procedure would falsify the optimality claim.

Figures

Figures reproduced from arXiv: 2605.20421 by Dmitry Chistikov, Neha Rino.

**Figure 1.** Figure 1: Nodding product automaton 3.1 Nodding product automaton Idea of the construction. The nodding product automaton Anodding is an ε-NFA that recognises ∩ i∈[k] L(Ai), while being sparser than the direct product automaton. The idea is to use Observation 1. Take the standard NFA for the interleaving of k languages, then intersect it with (a k 0 + a k 1 + · · · + a k ℓ−1 ) ∗ , and finally apply the 0 mod k restr… view at source ↗

**Figure 2.** Figure 2: A run of Anodding • recognises ∩ i∈[k] L(Ai), • has at most (kℓ − ℓ + 1) · n k states and at most k · mnk−1 transitions, • and has accessible part which can be constructed in O(k · mnk−1 ) time. Proof (sketch). Every accepting run of Anodding starts at the initial state in the base copy, traverses a whole number of petals, and ends at a final state in the base copy. A run of Anodding on a word w = σ0 . . .… view at source ↗

**Figure 3.** Figure 3: Catchup product automaton Definition of Acatchup. First consider k = 2. We define the catch-up product automaton Acatchup = (Q, Σ, ∆, s, F). Here Q = Q0 × Q1 × ({ε} ∪ Σ ∪ Σ 2 ) and s = (s0, s1, ε). The set ∆ includes transitions: • (p0, q, ε) σ0 −→ (p2, q, σ0σ1) whenever p0 σ0 −→ p1 σ1 −→ p2 is a path in A0, • (p, q0, σ0σ1) σ1 −→ (p, q2, ε) whenever q0 σ0 −→ q1 σ1 −→ q2 is a path in A1 (we note that pre-co… view at source ↗

**Figure 4.** Figure 4: Leapfrog product automaton Aleapfrog Proof (Sketch). Suppose Acatchup reads a word w, where k divides |w|. The run, call it π, starts at the initial state in the base copy, traverses a whole number of petals, and returns to the base copy. Consider the restriction π↾0 mod k : in it, only the first volley in each petal is taken. Let t = |w|/k. In the sequence of transitions π↾0 mod k , the Q0 component of Ac… view at source ↗

**Figure 5.** Figure 5: A run of Aleapfrog This is the main idea behind the leapfrog product, which saves a factor of ℓ in the number of states compared to the catch-up product. Given k NFA, the leapfrog product automaton processes k|w| updates while only storing Σ k−1 in memory; see [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗

**Figure 6.** Figure 6: Graph G = (V, E) and DFA A0, A1, A2 such that G contains a 4-clique iff these 3 DFA accept a word in common. Every edge labelled V represents five transitions. The notion of a ‘combinatorial’ algorithm is not rigorous. It refers to avoiding fast matrix multiplication. Many such algorithms have only a small constant in the Big O bound on the worst-case running time and use natural combinatorial structures … view at source ↗

**Figure 7.** Figure 7: Leapfrog automaton with state-update labels [PITH_FULL_IMAGE:figures/full_fig_p019_7.png] view at source ↗

read the original abstract

We observe that the classical Cartesian product construction for the intersection of (languages of) nondeterministic finite automata (NFA) is non-optimal in the worst case, if the automata have many transitions. For a fixed alphabet, the product of two NFA may have $\Theta(m^2)$ transitions if these NFA have at most $n$ states and $m$ transitions each. We describe alternative constructions with $O(m n)$ transitions: or $O(m n^{k-1})$ for the intersection of $k$ NFA (for fixed $k \ge 2$ and alphabet $\Sigma$). This gives a faster algorithm for deciding NFA intersection emptiness. The new algorithm is optimal, unless there exists a breakthrough combinatorial algorithm for detecting $(k+1)$-cliques in undirected graphs. This also leads to a more efficient certification scheme for NFA intersection emptiness.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper replaces the dense Cartesian product for NFA intersection with an O(mn) transition construction when inputs are dense, plus a conditional optimality claim via clique hardness.

read the letter

The main point is a construction that builds the intersection of two dense NFAs with only O(m n) transitions rather than the quadratic size you get from the usual product. For a fixed number k of automata the bound is O(m n^{k-1}). This directly speeds up emptiness testing and also gives a certification scheme for the same problem. The authors correctly note that the classical product can reach Theta(m^2) transitions when each automaton already has many edges, so the improvement targets exactly the dense regime that matters in practice. The conditional lower bound, resting on the absence of faster (k+1)-clique algorithms, is stated plainly and matches the style of current fine-grained results in automata theory. That keeps the claim honest. The constructions appear to avoid materializing every state pair by using a sparser auxiliary representation, which is the concrete algorithmic contribution. The full paper supplies the details that the abstract only sketches, and the stress-test found no internal contradictions or hidden parameter fitting. One minor soft spot is that the practical overhead of building the new representation is not quantified; if the construction requires non-trivial preprocessing or auxiliary graphs, the asymptotic gain might shrink for moderate n. The alphabet is treated as fixed, which is standard but limits direct comparison to variable-alphabet settings. This paper is aimed at automata theorists and verification researchers who care about the complexity of language operations. Anyone working on emptiness checks or intersection-based algorithms will see immediate value. It deserves a serious referee because the improvement is focused, the lower-bound connection is explicit, and the claims rest on reproducible algorithmic constructions rather than fitted parameters.

Referee Report

2 major / 2 minor

Summary. The paper observes that the standard Cartesian product construction for the intersection of NFAs can produce Θ(m²) transitions in the worst case when the input automata each have n states and m transitions. It presents alternative constructions that realize the intersection with only O(mn) transitions for two NFAs and O(m n^{k-1}) transitions for the intersection of a fixed number k ≥ 2 of NFAs. These constructions yield a faster emptiness test for the intersection language; the test is claimed to be conditionally optimal under the assumption that no combinatorial algorithm for (k+1)-clique detection improves on the current best bounds. The work also sketches a more efficient certification procedure for emptiness.

Significance. If the constructions are correct, the result improves the worst-case transition complexity of NFA intersection from quadratic to essentially linear in m (for fixed n or fixed k), which is a meaningful advance for dense automata. The explicit reduction to (k+1)-clique hardness supplies a natural conditional lower bound that situates the upper bound tightly within known combinatorial limits. The certification scheme is a useful byproduct for verification contexts.

major comments (2)

[§3 (Construction for two automata)] The central claim that the new emptiness algorithm runs in O(mn) time (or O(m n^{k-1}) time) rests on the correctness of the sparse intersection automaton; a self-contained argument that the accepted language equals the intersection of the input languages must appear in the main body (e.g., §3 or §4) and must be independent of the standard product.
[§5 (Lower-bound argument)] The conditional optimality statement invokes the absence of faster combinatorial (k+1)-clique algorithms; the reduction from clique detection to NFA-intersection emptiness should be stated explicitly, including the precise parameter mapping between graph size and automaton size.

minor comments (2)

[Abstract] The abstract states the transition bounds but does not mention the time complexity of the subsequent emptiness test; this should be clarified in the introduction.
[§2 (Preliminaries)] Notation for the alphabet size |Σ| and whether it is treated as constant should be made uniform throughout the constructions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We are grateful to the referee for the thorough review and the recommendation for minor revision. The comments highlight important points for improving the clarity and completeness of the presentation. We address each major comment below and plan to incorporate the necessary revisions.

read point-by-point responses

Referee: [§3 (Construction for two automata)] The central claim that the new emptiness algorithm runs in O(mn) time (or O(m n^{k-1}) time) rests on the correctness of the sparse intersection automaton; a self-contained argument that the accepted language equals the intersection of the input languages must appear in the main body (e.g., §3 or §4) and must be independent of the standard product.

Authors: We agree that providing a self-contained correctness argument is essential for the paper's rigor. In the revised manuscript, we will add a detailed, independent proof in Section 3 demonstrating that the language accepted by our sparse intersection automaton is precisely the intersection of the languages of the input NFAs. This argument will not rely on the standard Cartesian product construction, ensuring it stands alone. revision: yes
Referee: [§5 (Lower-bound argument)] The conditional optimality statement invokes the absence of faster combinatorial (k+1)-clique algorithms; the reduction from clique detection to NFA-intersection emptiness should be stated explicitly, including the precise parameter mapping between graph size and automaton size.

Authors: We acknowledge the need for an explicit reduction. In the updated version of Section 5, we will present the reduction from (k+1)-clique detection to the emptiness problem for the intersection of k NFAs in full detail. This will include the exact parameter mapping, specifying how the number of vertices and edges in the graph translate to the states and transitions in the constructed automata. revision: yes

Circularity Check

0 steps flagged

No significant circularity; constructions are independent algorithmic results

full rationale

The paper's core contribution consists of explicit alternative constructions for the intersection automaton (O(m n) transitions for two NFAs, O(m n^{k-1}) for fixed k) that are presented as direct improvements over the Cartesian product. These are algorithmic descriptions, not derived from fitted parameters or self-referential definitions. The conditional optimality claim rests on an external assumption about the absence of faster (k+1)-clique algorithms in graph theory, which is an independent hardness hypothesis rather than an internal reduction or self-citation chain. No load-bearing step reduces to the paper's own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard automata definitions and the fixed-alphabet assumption for the stated complexity; the optimality rests on an external hardness assumption from graph theory. No free parameters or invented entities are introduced.

axioms (2)

domain assumption NFAs are defined over a fixed finite alphabet Σ.
The O(m n) and O(m n^{k-1}) bounds are stated to hold for fixed alphabet.
domain assumption No combinatorial breakthrough exists for (k+1)-clique detection.
Invoked to establish optimality of the new emptiness algorithm.

pith-pipeline@v0.9.0 · 5672 in / 1436 out tokens · 53224 ms · 2026-05-21T06:25:38.624261+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We describe alternative constructions with O(m n) transitions: or O(m n^{k-1}) for the intersection of k NFA ... The new algorithm is optimal, unless there exists a breakthrough combinatorial algorithm for detecting (k+1)-cliques
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

nodding product automaton ... interleaving of k runs ... k-partite ... ε-transitions

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

51 extracted references · 51 canonical work pages

[1]

If the current clique algorithms are optimal, so is Valiant’s parser

Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is Valiant’s parser. SIAM J. Comput. , 47(6):2527–2555, 2018. URL: https://doi. org/10.1137/16M1061771

work page doi:10.1137/16m1061771 2018
[2]

Faster combinatorial k-clique algorithms

Amir Abboud, Nick Fischer, and Yarin Shechter. Faster combinatorial k-clique algorithms. In LATIN 2024: Theoretical Informatics - 16th Latin American Symposium , Lecture Notes in Computer Science, pages 193–206. Springer, 2024. URL: https://doi.org/10.1007/978-3-031-55598-5_13

work page doi:10.1007/978-3-031-55598-5_13 2024
[3]

Principles of model checking

Christel Baier and Joost-Pieter Katoen. Principles of model checking . MIT Press, 2008

work page 2008
[4]

Graph logics with rational relations

Pablo Barceló, Diego Figueira, and Leonid Libkin. Graph logics with rational relations. Log. Methods Comput. Sci. , 9(3), 2013. URL: https://doi.org/10.2168/LMCS-9(3:1)2013

work page doi:10.2168/lmcs-9(3:1)2013 2013
[5]

Formal properties of literal shuffle

Béatrice Bérard. Formal properties of literal shuffle. Acta Cybern., 8(1):27–39, 1987. URL: https: //cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3317

work page 1987
[6]

Literal shuffle

Béatrice Bérard. Literal shuffle. Theor. Comput. Sci. , 51:281–299, 1987. URL: https://doi.org/ 10.1016/0304-3975(87)90037-5

work page doi:10.1016/0304-3975(87)90037-5 1987
[7]

Representing arithmetic constraints with finite automata: An overview

Bernard Boigelot and Pierre Wolper. Representing arithmetic constraints with finite automata: An overview. In Logic Programming, 18th International Conference, ICLP 2002 Proceedings , volume 2401 of Lecture Notes in Computer Science , pages 1–19. Springer, 2002. URL: https://doi.org/ 10.1007/3-540-45619-8_1

work page doi:10.1007/3-540-45619-8_1 2002
[8]

Efficiently Testing Simon’s Congruence

Karl Bringmann. Fine-grained complexity theory (tutorial). In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019 , volume 126 of LIPIcs, pages 4:1–4:7. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS. 2019.4. 16

work page doi:10.4230/lipics.stacs 2019
[9]

The NF A ac- ceptance hypothesis: Non-combinatorial and dynamic lower bounds

Karl Bringmann, Allan Grønlund, Marvin Künnemann, and Kasper Green Larsen. The NF A ac- ceptance hypothesis: Non-combinatorial and dynamic lower bounds. TheoretiCS, 3, 2024. URL: https://doi.org/10.46298/theoretics.24.22

work page doi:10.46298/theoretics.24.22 2024
[10]

Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider

Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Com- puter Science , pages 261–270. ACM, 2016. URL: https://doi.org/...

work page doi:10.1145/2840728.2840746 2016
[11]

Katrin Casel and Markus L. Schmid. Fine-grained complexity of regular path queries. Log. Methods Comput. Sci. , 19(4), 2023. URL: https://doi.org/10.46298/lmcs-19(4:15)2023

work page doi:10.46298/lmcs-19(4:15)2023 2023
[12]

Relations over words and logic: A chronology

Christian Choffrut. Relations over words and logic: A chronology. Bull. EATCS , 89:159–163, 2006. URL: https://www.irif.fr/~cc/PUBLICATIONS/logics-for-relations.pdf

work page 2006
[13]

Intersection non-emptiness and hardness within polynomial time

Mateus de Oliveira Oliveira and Michael Wehar. Intersection non-emptiness and hardness within polynomial time. In Developments in Language Theory - 22nd International Conference, DLT 2018, volume 11088 of Lecture Notes in Computer Science , pages 282–290. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-98654-8_23

work page doi:10.1007/978-3-319-98654-8_23 2018
[14]

Transition complexity of language operations

Michael Domaratzki and Kai Salomaa. Transition complexity of language operations. Theor. Comput. Sci., 387(2):147–154, 2007. URL: https://doi.org/10.1016/j.tcs.2007.07.034

work page doi:10.1016/j.tcs.2007.07.034 2007
[15]

Lower bounds for the transition complexity of NF As

Michael Domaratzki and Kai Salomaa. Lower bounds for the transition complexity of NF As. J. Comput. Syst. Sci. , 74(7):1116–1130, 2008. URL: https://doi.org/10.1016/j.jcss.2008.02. 007

work page doi:10.1016/j.jcss.2008.02 2008
[16]

Fine-grained complexity analysis of queries: From decision to counting and enu- meration

Arnaud Durand. Fine-grained complexity analysis of queries: From decision to counting and enu- meration. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020 , pages 331–346. URL: https://doi.org/10.1145/3375395. 3389130

work page doi:10.1145/3375395 2020
[17]

Automata Theory

Javier Esparza and Michael Blondin. Automata Theory . MIT Press, 2023. URL: https: //michaelblondin.com/automata/

work page 2023
[18]

Fan, Paraschos Koutris, and Hangdong Zhao

Austen Z. Fan, Paraschos Koutris, and Hangdong Zhao. The fine-grained complexity of boolean conjunctive queries and sum-product problems. In 50th International Colloquium on Automata, Lan- guages, and Programming, ICALP 2023 , volume 261 of LIPIcs, pages 127:1–127:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.I...

work page doi:10.4230/lipics.icalp.2023.127 2023
[19]

Problems on finite automata and the exponential time hypoth- esis

Henning Fernau and Andreas Krebs. Problems on finite automata and the exponential time hypoth- esis. Algorithms, 10(1)(24):1–25, 2017. URL: https://doi.org/10.3390/a10010024

work page doi:10.3390/a10010024 2017
[20]

Golovach, Marcin Kamiński, Daniël Paulusma, and Dimitrios M

Hermann Gruber and Markus Holzer. On the average state and transition complexity of finite languages. Theor. Comput. Sci. , 387(2):155–166, 2007. URL: https://doi.org/10.1016/j.tcs. 2007.07.035

work page doi:10.1016/j.tcs 2007
[21]

Descriptional complexity of regular lan- guages

Hermann Gruber, Markus Holzer, and Martin Kutrib. Descriptional complexity of regular lan- guages. In Handbook of Automata Theory , pages 411–457. 2021. URL: https://doi.org/10.4171/ Automata-1/12

work page 2021
[22]

Dane Henshall, Narad Rampersad, and Jeffrey O. Shallit. Shuffling and unshuffling. Bull. EATCS , 107:131–142, 2012. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/71

work page 2012
[23]

The n-ary initial literal and literal shuffle

Stefan Hoffmann. The n-ary initial literal and literal shuffle. Discret. Appl. Math. , 376:112–132,

work page
[24]

URL: https://doi.org/10.1016/j.dam.2025.04.023

work page doi:10.1016/j.dam.2025.04.023 2025
[25]

Hopcroft, Rajeev Motwani, and Jeffrey D

John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition) . Addison-Wesley Longman Publishing Co., Inc., 2006

work page 2006
[26]

Comparing the size of NF As with and without ε-transitions

Juraj Hromkovic and Georg Schnitger. Comparing the size of NF As with and without ε-transitions. Theor. Comput. Sci. , 380(1-2):100–114, 2007. URL: https://doi.org/10.1016/j.tcs.2007.02. 063. 17

work page doi:10.1016/j.tcs.2007.02 2007
[27]

On the compl exity of k-sat

Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci. , 62(2):367–375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727

work page doi:10.1006/jcss.2000.1727 2001
[28]

Lipton, and Anastasios Viglas

George Karakostas, Richard J. Lipton, and Anastasios Viglas. On the complexity of intersecting finite state automata and NL versus NP. Theor. Comput. Sci. , 302(1–3):257–274, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00830-7

work page doi:10.1016/s0304-3975(02)00830-7 2003
[29]

Gradually intractable problems and nondeterministic log-space lower bounds

Takumi Kasai and Shigeki Iwata. Gradually intractable problems and nondeterministic log-space lower bounds. Mathematical systems theory , 18(1):153–170, 1985. URL: https://doi.org/10. 1007/BF01699467

work page 1985
[30]

Lower bounds for natural proof systems

Dexter Kozen. Lower bounds for natural proof systems. In 18th Annual Symposium on Foundations of Computer Science , pages 254–266. IEEE Computer Society, 1977. URL: https://doi.org/10. 1109/SFCS.1977.16

work page 1977
[31]

Orna Kupferman and Moshe Y. Vardi. Model checking of safety properties. Formal Methods Syst. Des., 19(3):291–314, 2001. URL: https://doi.org/10.1023/A:1011254632723

work page doi:10.1023/a:1011254632723 2001
[32]

McConnell, Kurt Mehlhorn, Stefan Näher, and Pascal Schweitzer

Ross M. McConnell, Kurt Mehlhorn, Stefan Näher, and Pascal Schweitzer. Certifying algorithms. Comput. Sci. Rev. , 5(2):119–161, 2011. URL: https://doi.org/10.1016/j.cosrev.2010.09.009

work page doi:10.1016/j.cosrev.2010.09.009 2011
[33]

Aaron Potechin and Jeffrey O. Shallit. Lengths of words accepted by nondeterministic finite au- tomata. Inf. Process. Lett. , 162, 2020. URL: https://doi.org/10.1016/j.ipl.2020.105993

work page doi:10.1016/j.ipl.2020.105993 2020
[34]

M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development , 3(2):114–125, 1959. doi:10.1147/rd.32.0114

work page doi:10.1147/rd.32.0114 1959
[35]

Elements of Automata Theory

Jacques Sakarovitch. Elements of Automata Theory . Cambridge University Press, 2009

work page 2009
[36]

Vardi and Pierre Wolper

Moshe Y. Vardi and Pierre Wolper. An automata-theoretic approach to automatic program verifi- cation (preliminary report). In Proceedings of the Symposium on Logic in Computer Science (LICS ’86), pages 332–344. IEEE Computer Society, 1986. URL: https://hdl.handle.net/2268/116609

work page 1986
[37]

The parameterized complexity of intersection and composition operations on sets of finite-state automata

Todd Wareham. The parameterized complexity of intersection and composition operations on sets of finite-state automata. In Implementation and Application of Automata, 5th International Conference, CIAA 2000 , volume 2088 of Lecture Notes in Computer Science , pages 302–310. Springer. URL: https://doi.org/10.1007/3-540-44674-5_26

work page doi:10.1007/3-540-44674-5_26 2000
[38]

Hardness results for intersection non-emptiness

Michael Wehar. Hardness results for intersection non-emptiness. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014 Proceedings, Part II , volume 8573 of Lecture Notes in Computer Science , pages 354–362. Springer, 2014. URL: https://doi.org/10. 1007/978-3-662-43951-7_30

work page 2014
[39]

On the complexity of intersection non-emptiness problems

Michael Wehar. On the complexity of intersection non-emptiness problems . PhD thesis, State Uni- versity of New York at Buffalo, 2017. URL: http://www.michaelwehar.com/documents/mwehar_ dissertation.pdf

work page 2017
[40]

On some fine-grained questions in algorithms and complexity , pages 3447–3487

Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity , pages 3447–3487. URL: https://www.worldscientific.com/doi/abs/10.1142/9789813272880_0188. A The standard Cartesian product automaton Definition 7 (Direct product automaton) . Given k NF A A0, . . . ,Ak−1 such that for all i ∈ [k − 1] Ai = (Qi, Σ, ∆i, si, Fi), the ...

work page doi:10.1142/9789813272880_0188
[41]

Q = Q0 × Q1 × · · · × Qk−1, where × denotes the Cartesian product of sets

work page
[42]

s = (s0, s1, . . . , sk−1)

work page
[43]

F = F0 × F1 × · · · × Fk−1

work page
[44]

, qk−1), σ, (q′ 0,

∆ = {((q0, . . . , qk−1), σ, (q′ 0, . . . , q′ k−1)) | (qi, σ, q′ i) ∈ ∆i for all i ∈ [k − 1]}. For a fixed k, given k NF AA0, . . . ,Ak−1 with at most n states and m transitions each, over an ℓ-letter alphabet, the direct product automaton AC contains O(nk) states and O(mk) transitions. 18 Q0× Q1×{( 1, a)} Q0× Q1×{ ε} Q0× Q1×{( 1, b)} Q0× Q1×{( 0, a)} ∆0...

work page
[45]

Given k NF A with at most n states and m transitions each and a k-tape automaton with nC states and mC transitions, NF A k-RS has an O(k · nk−1(nCm + nmC))-time algorithm

work page
[46]

For all ε > 0, if there exists a O((k · nknc)1−ε) time algorithm for NF A k-RS, then SETH is false

work page
[47]

NF Ak-RS belongs to NTIME(kℓ · nk+ω−2nC) ∩ coNTIME(k · nknC)

work page
[48]

If there is a fine-grained reduction such that, given SETH, NF A k-RS cannot be solved faster than kℓ · nk+ω−2+γnC for some γ > 0, then NSETH is false. D.2 Proof of Theorem 9 and Theorem 10: from NF A (k + 1)-IE to NF A k-RS and back Reducing NF A (k + 1)-IE to NF A k-RS As previously mentioned, the NF A k-IE problem can be seen as a special case of the N...

work page
[49]

(q, (σ, 0), (q, σ, 1)) for all q ∈ Qk and σ ∈ Σ

work page
[50]

, k− 2} and σ ∈ Σ

((q, σ, i), (σ, i), (q, σ, i + 1)) for all q ∈ Qk, i ∈ {1, . . . , k− 2} and σ ∈ Σ

work page
[51]

Suppose A0, A1,

((q, σ, k − 1), (σ, k − 1), q′) for all (q, σ, q′) ∈ ∆k. Suppose A0, A1, . . . ,Ak have a word w in their intersection. Then, by definition, w ∈ L(Ai) for each i ∈ [k], but moreover since w ∈ L(Ak), there is an accepting run ρ from sk to f ∈ Fk in Ak labelled by w. There is a corresponding run in C, where each transition q σ − →q′ in ρ is replaced by the ...

work page

[1] [1]

If the current clique algorithms are optimal, so is Valiant’s parser

Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is Valiant’s parser. SIAM J. Comput. , 47(6):2527–2555, 2018. URL: https://doi. org/10.1137/16M1061771

work page doi:10.1137/16m1061771 2018

[2] [2]

Faster combinatorial k-clique algorithms

Amir Abboud, Nick Fischer, and Yarin Shechter. Faster combinatorial k-clique algorithms. In LATIN 2024: Theoretical Informatics - 16th Latin American Symposium , Lecture Notes in Computer Science, pages 193–206. Springer, 2024. URL: https://doi.org/10.1007/978-3-031-55598-5_13

work page doi:10.1007/978-3-031-55598-5_13 2024

[3] [3]

Principles of model checking

Christel Baier and Joost-Pieter Katoen. Principles of model checking . MIT Press, 2008

work page 2008

[4] [4]

Graph logics with rational relations

Pablo Barceló, Diego Figueira, and Leonid Libkin. Graph logics with rational relations. Log. Methods Comput. Sci. , 9(3), 2013. URL: https://doi.org/10.2168/LMCS-9(3:1)2013

work page doi:10.2168/lmcs-9(3:1)2013 2013

[5] [5]

Formal properties of literal shuffle

Béatrice Bérard. Formal properties of literal shuffle. Acta Cybern., 8(1):27–39, 1987. URL: https: //cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3317

work page 1987

[6] [6]

Literal shuffle

Béatrice Bérard. Literal shuffle. Theor. Comput. Sci. , 51:281–299, 1987. URL: https://doi.org/ 10.1016/0304-3975(87)90037-5

work page doi:10.1016/0304-3975(87)90037-5 1987

[7] [7]

Representing arithmetic constraints with finite automata: An overview

Bernard Boigelot and Pierre Wolper. Representing arithmetic constraints with finite automata: An overview. In Logic Programming, 18th International Conference, ICLP 2002 Proceedings , volume 2401 of Lecture Notes in Computer Science , pages 1–19. Springer, 2002. URL: https://doi.org/ 10.1007/3-540-45619-8_1

work page doi:10.1007/3-540-45619-8_1 2002

[8] [8]

Efficiently Testing Simon’s Congruence

Karl Bringmann. Fine-grained complexity theory (tutorial). In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019 , volume 126 of LIPIcs, pages 4:1–4:7. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS. 2019.4. 16

work page doi:10.4230/lipics.stacs 2019

[9] [9]

The NF A ac- ceptance hypothesis: Non-combinatorial and dynamic lower bounds

Karl Bringmann, Allan Grønlund, Marvin Künnemann, and Kasper Green Larsen. The NF A ac- ceptance hypothesis: Non-combinatorial and dynamic lower bounds. TheoretiCS, 3, 2024. URL: https://doi.org/10.46298/theoretics.24.22

work page doi:10.46298/theoretics.24.22 2024

[10] [10]

Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider

Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Com- puter Science , pages 261–270. ACM, 2016. URL: https://doi.org/...

work page doi:10.1145/2840728.2840746 2016

[11] [11]

Katrin Casel and Markus L. Schmid. Fine-grained complexity of regular path queries. Log. Methods Comput. Sci. , 19(4), 2023. URL: https://doi.org/10.46298/lmcs-19(4:15)2023

work page doi:10.46298/lmcs-19(4:15)2023 2023

[12] [12]

Relations over words and logic: A chronology

Christian Choffrut. Relations over words and logic: A chronology. Bull. EATCS , 89:159–163, 2006. URL: https://www.irif.fr/~cc/PUBLICATIONS/logics-for-relations.pdf

work page 2006

[13] [13]

Intersection non-emptiness and hardness within polynomial time

Mateus de Oliveira Oliveira and Michael Wehar. Intersection non-emptiness and hardness within polynomial time. In Developments in Language Theory - 22nd International Conference, DLT 2018, volume 11088 of Lecture Notes in Computer Science , pages 282–290. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-98654-8_23

work page doi:10.1007/978-3-319-98654-8_23 2018

[14] [14]

Transition complexity of language operations

Michael Domaratzki and Kai Salomaa. Transition complexity of language operations. Theor. Comput. Sci., 387(2):147–154, 2007. URL: https://doi.org/10.1016/j.tcs.2007.07.034

work page doi:10.1016/j.tcs.2007.07.034 2007

[15] [15]

Lower bounds for the transition complexity of NF As

Michael Domaratzki and Kai Salomaa. Lower bounds for the transition complexity of NF As. J. Comput. Syst. Sci. , 74(7):1116–1130, 2008. URL: https://doi.org/10.1016/j.jcss.2008.02. 007

work page doi:10.1016/j.jcss.2008.02 2008

[16] [16]

Fine-grained complexity analysis of queries: From decision to counting and enu- meration

Arnaud Durand. Fine-grained complexity analysis of queries: From decision to counting and enu- meration. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020 , pages 331–346. URL: https://doi.org/10.1145/3375395. 3389130

work page doi:10.1145/3375395 2020

[17] [17]

Automata Theory

Javier Esparza and Michael Blondin. Automata Theory . MIT Press, 2023. URL: https: //michaelblondin.com/automata/

work page 2023

[18] [18]

Fan, Paraschos Koutris, and Hangdong Zhao

Austen Z. Fan, Paraschos Koutris, and Hangdong Zhao. The fine-grained complexity of boolean conjunctive queries and sum-product problems. In 50th International Colloquium on Automata, Lan- guages, and Programming, ICALP 2023 , volume 261 of LIPIcs, pages 127:1–127:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.I...

work page doi:10.4230/lipics.icalp.2023.127 2023

[19] [19]

Problems on finite automata and the exponential time hypoth- esis

Henning Fernau and Andreas Krebs. Problems on finite automata and the exponential time hypoth- esis. Algorithms, 10(1)(24):1–25, 2017. URL: https://doi.org/10.3390/a10010024

work page doi:10.3390/a10010024 2017

[20] [20]

Golovach, Marcin Kamiński, Daniël Paulusma, and Dimitrios M

Hermann Gruber and Markus Holzer. On the average state and transition complexity of finite languages. Theor. Comput. Sci. , 387(2):155–166, 2007. URL: https://doi.org/10.1016/j.tcs. 2007.07.035

work page doi:10.1016/j.tcs 2007

[21] [21]

Descriptional complexity of regular lan- guages

Hermann Gruber, Markus Holzer, and Martin Kutrib. Descriptional complexity of regular lan- guages. In Handbook of Automata Theory , pages 411–457. 2021. URL: https://doi.org/10.4171/ Automata-1/12

work page 2021

[22] [22]

Dane Henshall, Narad Rampersad, and Jeffrey O. Shallit. Shuffling and unshuffling. Bull. EATCS , 107:131–142, 2012. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/71

work page 2012

[23] [23]

The n-ary initial literal and literal shuffle

Stefan Hoffmann. The n-ary initial literal and literal shuffle. Discret. Appl. Math. , 376:112–132,

work page

[24] [24]

URL: https://doi.org/10.1016/j.dam.2025.04.023

work page doi:10.1016/j.dam.2025.04.023 2025

[25] [25]

Hopcroft, Rajeev Motwani, and Jeffrey D

John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition) . Addison-Wesley Longman Publishing Co., Inc., 2006

work page 2006

[26] [26]

Comparing the size of NF As with and without ε-transitions

Juraj Hromkovic and Georg Schnitger. Comparing the size of NF As with and without ε-transitions. Theor. Comput. Sci. , 380(1-2):100–114, 2007. URL: https://doi.org/10.1016/j.tcs.2007.02. 063. 17

work page doi:10.1016/j.tcs.2007.02 2007

[27] [27]

On the compl exity of k-sat

Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci. , 62(2):367–375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727

work page doi:10.1006/jcss.2000.1727 2001

[28] [28]

Lipton, and Anastasios Viglas

George Karakostas, Richard J. Lipton, and Anastasios Viglas. On the complexity of intersecting finite state automata and NL versus NP. Theor. Comput. Sci. , 302(1–3):257–274, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00830-7

work page doi:10.1016/s0304-3975(02)00830-7 2003

[29] [29]

Gradually intractable problems and nondeterministic log-space lower bounds

Takumi Kasai and Shigeki Iwata. Gradually intractable problems and nondeterministic log-space lower bounds. Mathematical systems theory , 18(1):153–170, 1985. URL: https://doi.org/10. 1007/BF01699467

work page 1985

[30] [30]

Lower bounds for natural proof systems

Dexter Kozen. Lower bounds for natural proof systems. In 18th Annual Symposium on Foundations of Computer Science , pages 254–266. IEEE Computer Society, 1977. URL: https://doi.org/10. 1109/SFCS.1977.16

work page 1977

[31] [31]

Orna Kupferman and Moshe Y. Vardi. Model checking of safety properties. Formal Methods Syst. Des., 19(3):291–314, 2001. URL: https://doi.org/10.1023/A:1011254632723

work page doi:10.1023/a:1011254632723 2001

[32] [32]

McConnell, Kurt Mehlhorn, Stefan Näher, and Pascal Schweitzer

Ross M. McConnell, Kurt Mehlhorn, Stefan Näher, and Pascal Schweitzer. Certifying algorithms. Comput. Sci. Rev. , 5(2):119–161, 2011. URL: https://doi.org/10.1016/j.cosrev.2010.09.009

work page doi:10.1016/j.cosrev.2010.09.009 2011

[33] [33]

Aaron Potechin and Jeffrey O. Shallit. Lengths of words accepted by nondeterministic finite au- tomata. Inf. Process. Lett. , 162, 2020. URL: https://doi.org/10.1016/j.ipl.2020.105993

work page doi:10.1016/j.ipl.2020.105993 2020

[34] [34]

M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development , 3(2):114–125, 1959. doi:10.1147/rd.32.0114

work page doi:10.1147/rd.32.0114 1959

[35] [35]

Elements of Automata Theory

Jacques Sakarovitch. Elements of Automata Theory . Cambridge University Press, 2009

work page 2009

[36] [36]

Vardi and Pierre Wolper

Moshe Y. Vardi and Pierre Wolper. An automata-theoretic approach to automatic program verifi- cation (preliminary report). In Proceedings of the Symposium on Logic in Computer Science (LICS ’86), pages 332–344. IEEE Computer Society, 1986. URL: https://hdl.handle.net/2268/116609

work page 1986

[37] [37]

The parameterized complexity of intersection and composition operations on sets of finite-state automata

Todd Wareham. The parameterized complexity of intersection and composition operations on sets of finite-state automata. In Implementation and Application of Automata, 5th International Conference, CIAA 2000 , volume 2088 of Lecture Notes in Computer Science , pages 302–310. Springer. URL: https://doi.org/10.1007/3-540-44674-5_26

work page doi:10.1007/3-540-44674-5_26 2000

[38] [38]

Hardness results for intersection non-emptiness

Michael Wehar. Hardness results for intersection non-emptiness. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014 Proceedings, Part II , volume 8573 of Lecture Notes in Computer Science , pages 354–362. Springer, 2014. URL: https://doi.org/10. 1007/978-3-662-43951-7_30

work page 2014

[39] [39]

On the complexity of intersection non-emptiness problems

Michael Wehar. On the complexity of intersection non-emptiness problems . PhD thesis, State Uni- versity of New York at Buffalo, 2017. URL: http://www.michaelwehar.com/documents/mwehar_ dissertation.pdf

work page 2017

[40] [40]

On some fine-grained questions in algorithms and complexity , pages 3447–3487

Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity , pages 3447–3487. URL: https://www.worldscientific.com/doi/abs/10.1142/9789813272880_0188. A The standard Cartesian product automaton Definition 7 (Direct product automaton) . Given k NF A A0, . . . ,Ak−1 such that for all i ∈ [k − 1] Ai = (Qi, Σ, ∆i, si, Fi), the ...

work page doi:10.1142/9789813272880_0188

[41] [41]

Q = Q0 × Q1 × · · · × Qk−1, where × denotes the Cartesian product of sets

work page

[42] [42]

s = (s0, s1, . . . , sk−1)

work page

[43] [43]

F = F0 × F1 × · · · × Fk−1

work page

[44] [44]

, qk−1), σ, (q′ 0,

∆ = {((q0, . . . , qk−1), σ, (q′ 0, . . . , q′ k−1)) | (qi, σ, q′ i) ∈ ∆i for all i ∈ [k − 1]}. For a fixed k, given k NF AA0, . . . ,Ak−1 with at most n states and m transitions each, over an ℓ-letter alphabet, the direct product automaton AC contains O(nk) states and O(mk) transitions. 18 Q0× Q1×{( 1, a)} Q0× Q1×{ ε} Q0× Q1×{( 1, b)} Q0× Q1×{( 0, a)} ∆0...

work page

[45] [45]

Given k NF A with at most n states and m transitions each and a k-tape automaton with nC states and mC transitions, NF A k-RS has an O(k · nk−1(nCm + nmC))-time algorithm

work page

[46] [46]

For all ε > 0, if there exists a O((k · nknc)1−ε) time algorithm for NF A k-RS, then SETH is false

work page

[47] [47]

NF Ak-RS belongs to NTIME(kℓ · nk+ω−2nC) ∩ coNTIME(k · nknC)

work page

[48] [48]

If there is a fine-grained reduction such that, given SETH, NF A k-RS cannot be solved faster than kℓ · nk+ω−2+γnC for some γ > 0, then NSETH is false. D.2 Proof of Theorem 9 and Theorem 10: from NF A (k + 1)-IE to NF A k-RS and back Reducing NF A (k + 1)-IE to NF A k-RS As previously mentioned, the NF A k-IE problem can be seen as a special case of the N...

work page

[49] [49]

(q, (σ, 0), (q, σ, 1)) for all q ∈ Qk and σ ∈ Σ

work page

[50] [50]

, k− 2} and σ ∈ Σ

((q, σ, i), (σ, i), (q, σ, i + 1)) for all q ∈ Qk, i ∈ {1, . . . , k− 2} and σ ∈ Σ

work page

[51] [51]

Suppose A0, A1,

((q, σ, k − 1), (σ, k − 1), q′) for all (q, σ, q′) ∈ ∆k. Suppose A0, A1, . . . ,Ak have a word w in their intersection. Then, by definition, w ∈ L(Ai) for each i ∈ [k], but moreover since w ∈ L(Ak), there is an accepting run ρ from sk to f ∈ Fk in Ak labelled by w. There is a corresponding run in C, where each transition q σ − →q′ in ρ is replaced by the ...

work page