# Automaton

An automaton is an abstract machine model that performs computations on input through states or configurations.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## OmegaHyper: Explicit-State HyperLTL Model Checking on an omega-Automaton Diet

DevFeed: [OmegaHyper: Explicit-State HyperLTL Model Checking on an omega-Automaton Diet](<https://devfeed.tech/articles/omegahyper-explicit-state-hyperltl-model-checking-on-an-omega-automaton-diet-142207.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.24210>)

Author: Hugo Pacheco

Published: 2026-11-19T05:00:00Z

Content type: release

Language: en

Sources: [arXiv: Software Engineering](<https://devfeed.tech/sources/arxiv-software-engineering.md>)

Topics: [Automaton](<https://devfeed.tech/topics/automaton.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [announce](<https://devfeed.tech/tags/announce.md>), [benchmarks](<https://devfeed.tech/tags/benchmarks.md>), [bounded](<https://devfeed.tech/tags/bounded.md>), [compare](<https://devfeed.tech/tags/compare.md>), [complete](<https://devfeed.tech/tags/complete.md>), [cs-fl](<https://devfeed.tech/tags/cs-fl.md>), [cs-se](<https://devfeed.tech/tags/cs-se.md>), [existing](<https://devfeed.tech/tags/existing.md>), [input](<https://devfeed.tech/tags/input.md>), [intermediate](<https://devfeed.tech/tags/intermediate.md>), [magnitude](<https://devfeed.tech/tags/magnitude.md>), [model](<https://devfeed.tech/tags/model.md>), [orders](<https://devfeed.tech/tags/orders.md>), [performance](<https://devfeed.tech/tags/performance.md>), [published](<https://devfeed.tech/tags/published.md>), [size](<https://devfeed.tech/tags/size.md>), [state](<https://devfeed.tech/tags/state.md>), [systems](<https://devfeed.tech/tags/systems.md>), [tool](<https://devfeed.tech/tags/tool.md>), [tools](<https://devfeed.tech/tags/tools.md>), [traces](<https://devfeed.tech/tags/traces.md>)

### AI overview

OmegaHyper reduces state explosion in explicit-state HyperLTL model checking by decomposing and reducing processed automata, while retaining AUtoHyper's quantifier-elimination algorithm and integrating Kofola for omega-automaton complementation. On 120 benchmarks from published suites, it improved explicit-state performance by up to orders of magnitude. Bounded symbolic tools still reached further on violated instances with short counterexamples. These findings are reported for the tested benchmarks.

### Source excerpt

arXiv:2611.24210v1 Announce Type: new Abstract: HyperLTL extends LTL with quantification over traces. AUtoHyper is the de facto explicit-state model checker for HyperLTL, complete for an arbitrary quantifier prefix: it eliminates quantifiers through products of the formula's omega-automaton with the systems, complementing on quantifier alternations. However, it suffers from state explosion, as it fully materializes input systems and intermediate automata. We present OmegaHyper, an overhaul of AutoHyper that keeps its algorithm but decomposes and reduces the size of the processed automata, and integrates the Kofola omega-automaton complementation tool. We compare OmegaHyper with existing explicit-state and symbolic HyperLTL model checkers, on 120 benchmarks from their published suites. OmegaHyper improves the performance of explicit-state HyperLTL model checking by up to orders of magnitude; bounded symbolic tools still reach further on violated instances with short counterexamples, as expected.

## Symbolic Abstraction Refinement

DevFeed: [Symbolic Abstraction Refinement](<https://devfeed.tech/articles/symbolic-abstraction-refinement-140024.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.22404>)

Author: Daniel Bryce (Smart Information Flow Technologies, LLC), Robert P. Goldman (Smart Information Flow Technologies, LLC), David J. Musliner (Smart Information Flow Technologies, LLC), Jeremy Gottlieb (Sm

Published: 2026-11-18T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [Artificial Intelligence](<https://devfeed.tech/topics/ai.md>), [Automaton](<https://devfeed.tech/topics/automaton.md>)

Tags: [abstraction](<https://devfeed.tech/tags/abstraction.md>), [artificial-intelligence](<https://devfeed.tech/tags/artificial-intelligence.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [autonomous-systems](<https://devfeed.tech/tags/autonomous-systems.md>), [benchmarks](<https://devfeed.tech/tags/benchmarks.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [function](<https://devfeed.tech/tags/function.md>), [game](<https://devfeed.tech/tags/game.md>), [graph](<https://devfeed.tech/tags/graph.md>), [leader-election](<https://devfeed.tech/tags/leader-election.md>), [nondeterminism](<https://devfeed.tech/tags/nondeterminism.md>), [probabilistic](<https://devfeed.tech/tags/probabilistic.md>), [probability](<https://devfeed.tech/tags/probability.md>), [property](<https://devfeed.tech/tags/property.md>), [region](<https://devfeed.tech/tags/region.md>), [search](<https://devfeed.tech/tags/search.md>), [timing](<https://devfeed.tech/tags/timing.md>), [verification](<https://devfeed.tech/tags/verification.md>)

### AI overview

SYMAR verifies probabilistic timed automata by storing probability bounds as functions over clock sub-regions, avoiding splits to previously generated states and reconstruction of incoming transitions. Preimage computation accounts for timing and action-choice nondeterminism; heuristic forward search focuses refinement on promising, property-relevant behaviors, while partial-refinement backups limit sub-region growth. The abstract reports up to 108x speedup on PRISM PTA benchmarks, one solved instance where the existing method times out, and a deadline-sensitive case solved with a 37-node search graph even as the deadline triples; the existing method uses 86,380 abstract states and 73 refinement rounds there.

### Source excerpt

arXiv:2611.22404v1 Announce Type: new Abstract: Autonomous systems choose actions whose outcomes are uncertain and are subject to time constraints. Probabilistic timed automata (PTAs) model exactly this, and verifying one answers a question about the system's decision-making: the maximum probability of reaching a goal, or the minimum probability of reaching a hazard, that a controller can guarantee. Verification normally works over symbolic states, each pairing a discrete location with a region of clock values, and its difficulty is that the best behavior generally varies within such a region. The PRISM verifier's most capable PTA method responds by splitting regions until each is uniform, rebuilding the transitions that reach them and propagating the split backward through the state graph of a stochastic game, a cascade of graph reconstruction that partitions regions the property never depends on. We present SYMAR, which instead makes the value function symbolic: each symbolic state carries a function from sub-regions of its clock region to probability bounds, so refinement is the appearance of new sub-regions in that function, and previously generated states are never split nor their incoming transitions reconstructed. Both sources of PTA nondeterminism, the timing and the choice of actions, are captured implicitly by the preimage computation that produces those sub-regions. Heuristic forward search then bounds how much refinement is done at all, expanding an And-Or graph from the initial state along the most promising behaviors so that effort is confined to the property-relevant fragment, guided by bounds and preferred actions from a single unrefined run of the existing method; a partial-refinement backup keeps the otherwise combinatorial sub-region count lean, and every stored interval provably contains the true probability. On the PRISM PTA benchmarks, whose subproblems recur in autonomous systems (distributed agreement under contention, leader election, and se

## Writing as a thinking tool

DevFeed: [Writing as a thinking tool](<https://devfeed.tech/articles/writing-as-a-thinking-tool-122219.md>)

Original publisher: [Read original article](<https://muratbuffalo.blogspot.com/2026/11/writing-as-thinking-tool.html>)

Author: Murat (noreply@blogger.com)

Published: 2026-11-07T08:22:10Z

Content type: opinion

Language: en

Sources: [Metadata](<https://devfeed.tech/sources/metadata.md>)

Topics: [CVE-2026-58058](<https://devfeed.tech/topics/cve-2026-58058.md>), [Automaton](<https://devfeed.tech/topics/automaton.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [Large Language Model](<https://devfeed.tech/topics/llm.md>)

Tags: [advice](<https://devfeed.tech/tags/advice.md>), [ai](<https://devfeed.tech/tags/ai.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [graduate-students](<https://devfeed.tech/tags/graduate-students.md>), [information](<https://devfeed.tech/tags/information.md>), [intelligence](<https://devfeed.tech/tags/intelligence.md>), [language](<https://devfeed.tech/tags/language.md>), [llms](<https://devfeed.tech/tags/llms.md>), [model](<https://devfeed.tech/tags/model.md>), [my-advice](<https://devfeed.tech/tags/my-advice.md>), [notes](<https://devfeed.tech/tags/notes.md>), [paper](<https://devfeed.tech/tags/paper.md>), [pencil](<https://devfeed.tech/tags/pencil.md>), [reading](<https://devfeed.tech/tags/reading.md>), [research-advice](<https://devfeed.tech/tags/research-advice.md>), [thinking](<https://devfeed.tech/tags/thinking.md>), [tool](<https://devfeed.tech/tags/tool.md>), [turing-machine](<https://devfeed.tech/tags/turing-machine.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>), [turkey](<https://devfeed.tech/tags/turkey.md>), [writing](<https://devfeed.tech/tags/writing.md>)

### AI overview

The author argues that writing extends thought by giving the mind external memory and workspace: notes help process reading, while drafting a paper review can expose gaps and reveal connections that were not apparent beforehand. They worry that relying on an LLM before forming one's own ideas can crowd out that work; models may know established literature and framing but, in the author's view, cannot be trusted to make the creative leap from a person's half-formed intuition. Their practical method is to draft freely without judging, then edit hard across several passes, favor plain and concise prose, write for intrinsic reasons, and schedule regular writing rather than waiting for inspiration. The author presents these as personal experience and advice, not as a tested universal method.

### Source excerpt

In middle school I could not get through long passages no matter how hard I tried. I would read an entire page and find that nothing had registered, so I started taking notes out of desperation. This was the late 80s, and Tony Buzan's mind maps had just reached Turkey. This led me to produce pages and pages of notes that looked like spiderwebs. Creating those notes have helped me tremendously. I made sense of what I was reading by figuring out which branch they would hang off in my mind maps. I realized my pages were not for storing the information as much as they were for processing it. It took me another ten years to understand why this works so well. During a stretch of PhD procrastination, I read Manuel Blum's advice to graduate students: You are all computer scientists. You know what FINITE AUTOMATA can do. You know what TURING MACHINES can do. For example, Finite Automata can add but not multiply. Turing Machines can compute any computable function. Turing machines are incredibly more powerful than Finite Automata. Yet the only difference between a FA and a TM is that the TM, unlike the FA, has paper and pencil. Think about it. It tells you something about the power of writing. Without writing, you are reduced to a finite automaton. With writing you have the extraordinary power of a Turing machine. This is a crisp technical claim about which problems you can solve with writing. If you take the paper away, you downgrade yourself by an entire complexity class! I think this explains a lot about human history as well. Language let us externalize some of our thinking, and our species got smarter. Writing let us externalize even more of it, and we got smarter again. I suspect this is also why LLMs are as capable as they are: so much of our intelligence is already deposited in language that a model trained on it inherits a good deal of intelligence for free. Out-of-core execution When we write, we are externalizing our thinking onto paper, and that is what raises our

## Efficient Stable Word-RAM Simulation by Population Protocols

DevFeed: [Efficient Stable Word-RAM Simulation by Population Protocols](<https://devfeed.tech/articles/efficient-stable-word-ram-simulation-by-population-protocols-119108.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.06178>)

Author: Leszek G\\k{a}sieniec, Tytus Grodzicki, Grzegorz Stachowiak

Published: 2026-11-05T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Distributed Computing](<https://devfeed.tech/sources/arxiv-distributed-computing.md>)

Topics: [Distributed Systems & Parallel Computing](<https://devfeed.tech/topics/distributed-systems-parallel-computing.md>), [Automaton](<https://devfeed.tech/topics/automaton.md>)

Tags: [cs-dc](<https://devfeed.tech/tags/cs-dc.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [protocols](<https://devfeed.tech/tags/protocols.md>), [ram](<https://devfeed.tech/tags/ram.md>), [simulation](<https://devfeed.tech/tags/simulation.md>), [stable](<https://devfeed.tech/tags/stable.md>), [word-ram](<https://devfeed.tech/tags/word-ram.md>)

### AI overview

The paper gives an efficient, stable, silent population-protocol simulation of every P-program: a word-RAM program whose running time and register count are polynomial in w = Θ(log n). Stabilisation takes polylogarithmic time in expectation and with high probability. The construction converts unary inputs to binary registers using MC+ majority comparisons against a system of weights, assigns one agent per bit, and uses MC+ bit operations to emulate RAM instructions; outputs are then converted back to unary. If MC+ detects an anomaly, a universal rank-based backup ensures correct, silent stabilisation. The framework supports multiple outputs and extends efficient stable computation beyond semilinear predicates, which characterize constant-state stable computation.

### Source excerpt

arXiv:2611.06178v1 Announce Type: new Abstract: Population protocols model computation by indistinguishable agents interacting in uniformly random pairs, with unary inputs and outputs encoded by state counts. Efficiency requires polylogarithmically many states and polylogarithmic stabilisation time, measured as interactions divided by population size $n$. Stability requires eventual stabilisation to the correct output with probability $1$; silence requires that no agent changes state after stabilisation. Fast stable leader election and majority in leaderless populations require growing state spaces. Despite progress on individual problems, the general computational power of efficient stable protocols remains largely unexplored. We show that it extends beyond semilinear predicates, which characterise constant-state stable computation. We give an efficient, stable, and silent simulation of every $\mathcal{P}$-program: a word-RAM program with running time and number of registers polynomial in $w=\Theta(\log n)$. Stabilisation takes polylogarithmic time both in expectation and with high probability. The framework supports general word-oriented computations, including multiple outputs. The construction extends MC$+$ protocols, fast Monte Carlo protocols whose failures are eventually detected as anomalies, and the system of weights. MC$+$ majority comparisons against the weights convert unary inputs into binary registers, with one agent per bit. MC$+$ operations on individual bits emulate RAM instructions, after which outputs are converted back to unary. A detected anomaly triggers a new universal rank-based backup that stabilises correctly and silently. These results open a systematic study of computational power and resource trade-offs, including extensions to external or spatial data.

## Distributed LTL Synthesis under Arbitrary Message Adversaries

DevFeed: [Distributed LTL Synthesis under Arbitrary Message Adversaries](<https://devfeed.tech/articles/distributed-ltl-synthesis-under-arbitrary-message-adversaries-116491.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.04561>)

Author: Benedikt Bollig, Patricia Bouyer-Decitre, Matthias F\\"ugger, Dhrubajyoti Ghosh, Thomas Nowak, Nathalie Sznajder

Published: 2026-11-04T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Distributed Computing](<https://devfeed.tech/sources/arxiv-distributed-computing.md>)

Topics: [distributed algorithm](<https://devfeed.tech/topics/distributed-algorithm.md>), [consensus algorithm](<https://devfeed.tech/topics/consensus-algorithm.md>), [Formal verification](<https://devfeed.tech/topics/formal-verification.md>), [Automaton](<https://devfeed.tech/topics/automaton.md>)

Tags: [adversary](<https://devfeed.tech/tags/adversary.md>), [consensus](<https://devfeed.tech/tags/consensus.md>), [cs-dc](<https://devfeed.tech/tags/cs-dc.md>), [cs-fl](<https://devfeed.tech/tags/cs-fl.md>), [cs-lo](<https://devfeed.tech/tags/cs-lo.md>), [cs-sy](<https://devfeed.tech/tags/cs-sy.md>), [distributed](<https://devfeed.tech/tags/distributed.md>), [eess-sy](<https://devfeed.tech/tags/eess-sy.md>), [formal-verification](<https://devfeed.tech/tags/formal-verification.md>), [graph](<https://devfeed.tech/tags/graph.md>), [linear](<https://devfeed.tech/tags/linear.md>), [logic](<https://devfeed.tech/tags/logic.md>), [message](<https://devfeed.tech/tags/message.md>), [processes](<https://devfeed.tech/tags/processes.md>), [reactive](<https://devfeed.tech/tags/reactive.md>), [regular](<https://devfeed.tech/tags/regular.md>), [synthesis](<https://devfeed.tech/tags/synthesis.md>), [verification](<https://devfeed.tech/tags/verification.md>)

### AI overview

For two processes communicating over unreliable links with at least one message delivered each round, LTL synthesis can still be undecidable--even when messages contain complete causal histories. For every ω-regular message adversary A, the abstract gives a decidability criterion: synthesis is decidable exactly when the image π(A), derived through iterated chromatic subdivision, is nowhere dense in [0,1]. In decidable cases, a procedure takes a deterministic parity automaton for A and a specification, decides realizability, and constructs an algorithm when one exists. The abstract also states that this decidability condition is equivalent to consensus being repeatedly solvable in bounded time.

### Source excerpt

arXiv:2611.04561v1 Announce Type: new Abstract: Reactive synthesis is the problem of generating a program that produces outputs satisfying a logical specification for every input stream. We study distributed synthesis for two processes communicating in rounds over unreliable links, with at least one message delivered in every round. Despite this delivery guarantee, we show that synthesis from linear temporal logic specifications is undecidable, even when messages carry the processes' complete causal histories. More generally, we give a complete characterization of the communication restrictions that make synthesis decidable. Restrictions are described by a message adversary $A$, a set of allowed infinite graph histories: sequences of communication graphs, each specifying which messages are delivered in a round. Iterated chromatic subdivision associates these histories with points in the unit interval, yielding an image $\pi(A) \subseteq [0,1]$. For every $\omega$-regular message adversary $A$, synthesis is decidable if and only if $\pi(A)$ is nowhere dense. In the decidable cases, our procedure takes a deterministic parity automaton for $A$ and a specification, decides realizability, and constructs a realizing distributed algorithm whenever one exists. Further, our topological arguments shed new light on the fundamental requirements of synthesis. They show that, for $\omega$-regular message adversaries, synthesis is decidable if and only if consensus is repeatedly solvable in bounded time. This links two previously unrelated problems from formal verification and distributed computing through the processes' uncertainty about communication.

## FACET: Feasibility-Automaton Complete Enumeration and Truncation-Free Scoring of Molecular Formulas from MS/MS

DevFeed: [FACET: Feasibility-Automaton Complete Enumeration and Truncation-Free Scoring of Molecular Formulas from MS/MS](<https://devfeed.tech/articles/facet-feasibility-automaton-complete-enumeration-and-truncation-free-scoring-of-molecular-formulas-from-ms-ms-114533.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.01352>)

Author: Xujun Che, Depeng Xu, Xiuxia Du

Published: 2026-11-03T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [Neural Network](<https://devfeed.tech/topics/neural-network.md>), [Automaton](<https://devfeed.tech/topics/automaton.md>)

Tags: [2022](<https://devfeed.tech/tags/2022.md>), [benchmark](<https://devfeed.tech/tags/benchmark.md>), [complete](<https://devfeed.tech/tags/complete.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [element](<https://devfeed.tech/tags/element.md>), [enumeration](<https://devfeed.tech/tags/enumeration.md>), [exhaustive](<https://devfeed.tech/tags/exhaustive.md>), [fixed](<https://devfeed.tech/tags/fixed.md>), [model](<https://devfeed.tech/tags/model.md>), [neural](<https://devfeed.tech/tags/neural.md>), [pass](<https://devfeed.tech/tags/pass.md>), [q-bio-qm](<https://devfeed.tech/tags/q-bio-qm.md>), [recall](<https://devfeed.tech/tags/recall.md>), [spectrum](<https://devfeed.tech/tags/spectrum.md>)

### AI overview

FACET separates candidate generation from ranking for molecular formula identification from MS/MS spectra. Its feasibility automaton exhaustively generates formulas matching precursor mass and ring-and-double-bond and valence constraints; a neural head ranks every candidate using one pass of a pretrained spectrum encoder. This avoids model-based candidate truncation, while exhaustive enumeration fixes recall to the chemically feasible set. On NPLIB1, reported top-1 accuracy is 0.859 with known adducts and 0.729 with unknown adducts, versus 0.766 and 0.660 for the strongest established method; FACET also reports the highest recall. On CASMI 2022, recall is 1.000, and with unknown adducts it is the most accurate method compared.

### Source excerpt

arXiv:2611.01352v1 Announce Type: new Abstract: Determining the neutral molecular formula of a precursor ion from its tandem mass (MS/MS) spectrum is the first step in identifying an unknown small molecule. Existing methods trade recall, whether the correct formula is among the candidates, against the cost of examining each candidate. Methods that examine each candidate in depth must first shorten the list, by limiting element counts or truncating it, and that is where the correct formula is lost. End-to-end regressors are fast but guarantee neither validity nor recall. We present FACET, which separates deciding which formulas to consider from deciding which one to choose. A feasibility automaton builds a formula one element count at a time and admits exactly the formulas that fit the precursor mass and satisfy the ring-and-double-bond and valence constraints. Run as an exhaustive search, it enumerates the complete feasible set, so every candidate is valid and recall is fixed by the chemical constraints rather than by a trained model. A small neural scoring head then ranks every feasible formula from one pass of a pretrained spectrum encoder, so no candidate is discarded. On the NPLIB1 benchmark FACET reaches top-1 accuracies of $0.859$ with the adduct known and $0.729$ with it unknown, compared with $0.766$ and $0.660$ for the strongest established method, and its recall is the highest. On the external CASMI 2022 set its recall is $1.000$, and with the adduct unknown it is the most accurate of the methods compared.

## Certified Split Windows for Parallel Lexing: Recovering Boundaries Where No Byte Certifies

DevFeed: [Certified Split Windows for Parallel Lexing: Recovering Boundaries Where No Byte Certifies](<https://devfeed.tech/articles/certified-split-windows-for-parallel-lexing-recovering-boundaries-where-no-byte-certifies-101586.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2608.09761>)

Author: Nicklas Nidh\\"ogg

Published: 2026-10-27T04:00:00Z

Content type: article

Language: en

Sources: [arXiv: Distributed Computing](<https://devfeed.tech/sources/arxiv-distributed-computing.md>)

Topics: [Automaton](<https://devfeed.tech/topics/automaton.md>), [Finite-state machine](<https://devfeed.tech/topics/finite-state-machine.md>)

Tags: [certificate](<https://devfeed.tech/tags/certificate.md>), [cs-dc](<https://devfeed.tech/tags/cs-dc.md>), [cs-fl](<https://devfeed.tech/tags/cs-fl.md>), [cs-pl](<https://devfeed.tech/tags/cs-pl.md>), [lexer](<https://devfeed.tech/tags/lexer.md>), [local](<https://devfeed.tech/tags/local.md>), [model](<https://devfeed.tech/tags/model.md>), [parallel](<https://devfeed.tech/tags/parallel.md>), [profile](<https://devfeed.tech/tags/profile.md>), [pspace](<https://devfeed.tech/tags/pspace.md>), [scanner](<https://devfeed.tech/tags/scanner.md>), [semantic](<https://devfeed.tech/tags/semantic.md>), [serial](<https://devfeed.tech/tags/serial.md>), [split](<https://devfeed.tech/tags/split.md>), [stream](<https://devfeed.tech/tags/stream.md>), [string](<https://devfeed.tech/tags/string.md>), [tables](<https://devfeed.tech/tags/tables.md>), [token](<https://devfeed.tech/tags/token.md>), [using](<https://devfeed.tech/tags/using.md>), [window](<https://devfeed.tech/tags/window.md>), [windows](<https://devfeed.tech/tags/windows.md>)

### AI overview

The paper extends certified parallel-lexing boundaries from single bytes to bounded windows that reveal where the token covering the window's final byte began. It models possible maximal-munch scanner histories and decides reachability exactly within a finite quotient: positive results are sound semantic certificates for flat, completely tokenizable input, while negative results are limited by the conservative model. Certificates depend on an asserted occurrence witness and may otherwise be vacuous. In 400 random token sets, 322 of 337 sets with no byte certificate gained a witnessed window; every exact-empty case in the predecessor study gained one of two to four bytes. Analysis uses compiled tables once after automaton construction, without input. The existence problem is PSPACE-complete, and shortest windows can be exponentially long in the square root of the number of live states.

### Source excerpt

arXiv:2608.09761v3 Announce Type: replace-cross Abstract: A certified split point lets a parallel lexer cut unlexed input at a single byte with the serial token stream provably preserved, but several conventional token sets in the predecessor's controlled study certify no byte once string, comment, or whitespace-run forms are included (arXiv:2608.03473v2). We generalize from a byte to a bounded window, a byte string after which the position where the current token began is known, regardless of surrounding context. We certify the directly usable form of that recovery, namely that the token covering the window's final byte begins at the reported origin. The certificate is conditional on occurrence and may be vacuous; every applicability figure counts only windows carrying an asserted completely tokenizable occurrence witness. We give a conservative model of a maximal-munch scanner's possible histories across a window, prove it sound, and decide reachability in that model exactly by exhausting a finite quotient of its reachable configurations. Within the flat, completely tokenizable scope, model-positive answers are semantic certificates; negatives are relative to the model, which deliberately refuses some windows a greedy scanner would allow. Whether the model certifies any window, plain or witnessed, is PSPACE-complete, and a shortest window can need $2^{\Omega(\sqrt{n})}$ bytes over n live states. Two smaller searches decide plain model existence, the second shipped in release 2.2.0 of munch. In a sample of 400 random token sets, 322 of the 337 sets certifying no byte gain a witnessed window, with zero inconclusive searches, and every exact-empty row of the predecessor's study gains a witnessed window of two to four bytes. The analysis runs once after automaton construction, using only the compiled tables and no input. A boundary profile marks each gap of a window forced, crossed or open, and a window-local cut is sound exactly at forced gaps.

## Introducing pg\_re2, fast, RE2-powered regular expressions in Postgres

DevFeed: [Introducing pg\_re2, fast, RE2-powered regular expressions in Postgres](<https://devfeed.tech/articles/introducing-pg-re2-fast-re2-powered-regular-expressions-in-postgres-5337.md>)

Original publisher: [Read original article](<https://clickhouse.com/blog/introducing-pg_re2-regex-in-postgres>)

Author: David Wheeler; Philip Dubé

Published: 2026-07-08T18:12:04Z

Content type: article

Language: en

Sources: [ClickHouse Blog](<https://devfeed.tech/sources/clickhouse-blog.md>)

Topics: [PostgreSQL](<https://devfeed.tech/topics/postgresql.md>), [Regular expression](<https://devfeed.tech/topics/regular-expression.md>), [Extension](<https://devfeed.tech/topics/extension.md>), [Benchmark](<https://devfeed.tech/topics/benchmark.md>), [Finite-state machine](<https://devfeed.tech/topics/finite-state-machine.md>), [Automaton](<https://devfeed.tech/topics/automaton.md>), [clickhouse](<https://devfeed.tech/topics/clickhouse.md>), [Open Source](<https://devfeed.tech/topics/open-source.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [article](<https://devfeed.tech/tags/article.md>), [aws](<https://devfeed.tech/tags/aws.md>), [benchmark](<https://devfeed.tech/tags/benchmark.md>), [benchmarks](<https://devfeed.tech/tags/benchmarks.md>), [clickhouse](<https://devfeed.tech/tags/clickhouse.md>), [development](<https://devfeed.tech/tags/development.md>), [engineering](<https://devfeed.tech/tags/engineering.md>), [extension](<https://devfeed.tech/tags/extension.md>), [open](<https://devfeed.tech/tags/open.md>), [open-source](<https://devfeed.tech/tags/open-source.md>), [performance](<https://devfeed.tech/tags/performance.md>), [postgres](<https://devfeed.tech/tags/postgres.md>), [postgresql](<https://devfeed.tech/tags/postgresql.md>), [sql](<https://devfeed.tech/tags/sql.md>)

### AI overview

This article introduces pg_re2, a PostgreSQL extension that adds fast RE2-powered regular expression functions. It explains the performance and compatibility rationale, compares RE2 with PostgreSQL's native engine, and reports benchmark results showing RE2 outperforming the native functions in the tested cases.

### Source excerpt

Introducing pg_re2, a Postgres extension that brings ClickHouse's fast RE2-powered regular expressions to Postgres, with benchmarks and pg_clickhouse pushdown integration.

## Solving regex crosswords with Z3

DevFeed: [Solving regex crosswords with Z3](<https://devfeed.tech/articles/solving-regex-crosswords-with-z3-21962.md>)

Original publisher: [Read original article](<https://blog.nelhage.com/post/regex-crosswords-z3/>)

Author: Nelson Elhage

Published: 2025-10-21T14:00:00Z

Content type: tutorial

Language: en

Sources: [Nelson Elhage](<https://devfeed.tech/sources/nelson-elhage.md>)

Topics: [Regular expression](<https://devfeed.tech/topics/regular-expression.md>), [Automaton](<https://devfeed.tech/topics/automaton.md>), [Finite-state machine](<https://devfeed.tech/topics/finite-state-machine.md>), [Python](<https://devfeed.tech/topics/python.md>)

Tags: [code](<https://devfeed.tech/tags/code.md>), [dfa](<https://devfeed.tech/tags/dfa.md>), [experimentation](<https://devfeed.tech/tags/experimentation.md>), [performance](<https://devfeed.tech/tags/performance.md>), [python](<https://devfeed.tech/tags/python.md>), [regex](<https://devfeed.tech/tags/regex.md>)

### AI overview

This technical post explains how to solve regular-expression crossword puzzles with a Z3-backed solver. It describes encoding regular expressions as deterministic finite automata, using a Python library to convert regex syntax to finite-state machines, and exploring solver performance and implementation improvements.

### Source excerpt

For a while now, I've been fascinated by Z3 and by SMT solving more broadly. While on pat leave recently, I was reminded of the existence of regular-expression crossword puzzles, and allowed myself to get nerdsniped by writing a Z3-backed solver. I expected to spend perhaps an afternoon cranking out a quick solver; I ended up getting sucked into understanding and debugging Z3 performance, and learning far more about Z3 and about SMT than I expected.

## Make Impossible States Impossible

DevFeed: [Make Impossible States Impossible](<https://devfeed.tech/articles/make-impossible-states-impossible-51826.md>)

Original publisher: [Read original article](<https://kentcdodds.com/blog/make-impossible-states-impossible>)

Author: Yaron Minsky

Published: 2018-09-10T00:00:00Z

Content type: article

Language: en

Sources: [Kent C. Dodds Blog](<https://devfeed.tech/sources/kent-c-dodds-blog.md>)

Topics: [enum](<https://devfeed.tech/topics/enum.md>), [App](<https://devfeed.tech/topics/app.md>), [React](<https://devfeed.tech/topics/react.md>), [Automaton](<https://devfeed.tech/topics/automaton.md>)

Tags: [application](<https://devfeed.tech/tags/application.md>), [boolean](<https://devfeed.tech/tags/boolean.md>), [component](<https://devfeed.tech/tags/component.md>), [react](<https://devfeed.tech/tags/react.md>), [simplify](<https://devfeed.tech/tags/simplify.md>), [state](<https://devfeed.tech/tags/state.md>)

### AI overview

The article explains how designing component APIs around explicit valid states can prevent impossible combinations and simplify application state. It presents replacing boolean props with enum-like values as one practical technique.

### Source excerpt

A simple trick to simplify your application and component state

## Myhill-Nerode Theorem in Practice

DevFeed: [Myhill-Nerode Theorem in Practice](<https://devfeed.tech/articles/myhill-nerode-theorem-in-practice-40721.md>)

Original publisher: [Read original article](<https://radek.io/posts/myhill-nerode-theorem-in-practice/>)

Published: 2011-10-24T00:00:00Z

Content type: article

Language: en

Sources: [Radek Pazdera](<https://devfeed.tech/sources/radek-pazdera.md>)

Topics: [Computer science](<https://devfeed.tech/topics/computer-science.md>), [Automaton](<https://devfeed.tech/topics/automaton.md>), [syntax](<https://devfeed.tech/topics/syntax.md>), [Compiler](<https://devfeed.tech/topics/compiler.md>)

Tags: [compilers](<https://devfeed.tech/tags/compilers.md>), [computer-science](<https://devfeed.tech/tags/computer-science.md>), [context-free-languages](<https://devfeed.tech/tags/context-free-languages.md>), [language](<https://devfeed.tech/tags/language.md>), [machine](<https://devfeed.tech/tags/machine.md>), [regular-languages](<https://devfeed.tech/tags/regular-languages.md>), [syntax](<https://devfeed.tech/tags/syntax.md>), [turing-machine](<https://devfeed.tech/tags/turing-machine.md>)

### AI overview

This article explains the Myhill-Nerode theorem as a way to prove that a formal language is regular. It connects regular languages and finite automata with practical syntax checking, regular expressions, and compiler-related language processing.

### Source excerpt

A way of proving that a language is regular

## Turing Machines--A Primer

DevFeed: [Turing Machines--A Primer](<https://devfeed.tech/articles/turing-machines-a-primer-40218.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2011/07/04/turing-machines-a-primer/>)

Published: 2011-07-04T16:35:44Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Automaton](<https://devfeed.tech/topics/automaton.md>), [function](<https://devfeed.tech/topics/function.md>)

Tags: [acceptance](<https://devfeed.tech/tags/acceptance.md>), [computability-theory](<https://devfeed.tech/tags/computability-theory.md>), [computers](<https://devfeed.tech/tags/computers.md>), [concepts](<https://devfeed.tech/tags/concepts.md>), [decidability](<https://devfeed.tech/tags/decidability.md>), [halting-problem](<https://devfeed.tech/tags/halting-problem.md>), [input](<https://devfeed.tech/tags/input.md>), [machine](<https://devfeed.tech/tags/machine.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [primer](<https://devfeed.tech/tags/primer.md>), [process](<https://devfeed.tech/tags/process.md>), [pushdown-automata](<https://devfeed.tech/tags/pushdown-automata.md>), [state](<https://devfeed.tech/tags/state.md>), [symbols](<https://devfeed.tech/tags/symbols.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>)

### AI overview

This tutorial introduces Turing machines as a model of computation. It defines their states, tape symbols, input symbols, initial state, accepting and rejecting states, and transition function, then explains how the tape, read-write head, state transitions, and halting behavior work.

### Source excerpt

We assume the reader is familiar with the concepts of determinism and finite automata, or has read the corresponding primer on this blog. The Mother of All Computers Last time we saw some models for computation, and saw in turn how limited they were. Now, we open Pandrora's hard drive: Definition: A Turing machine is a tuple $ (S, \Gamma, \Sigma, s_0, F, \tau)$, where $ S$ is a set of states, $ \Gamma$ is a set of tape symbols, including a special blank symbol $ b$, $ \Sigma \subset \Gamma$ is a set of input symbols, not including $ b$, $ s_0$ is the initial state, $ A \subset S$ is a set of accepting states, $ R \subset S$ is a set of rejecting states, $ \tau: S - (A \cup R) \times \Gamma \to S \times \Gamma \times \left \{ L, R \right \}$ is a partial function called the transition function, where $ L, R$ correspond to "left shift" and "right shift," respectively.

## Determinism and Finite Automata--A Primer

DevFeed: [Determinism and Finite Automata--A Primer](<https://devfeed.tech/articles/determinism-and-finite-automata-a-primer-40217.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2011/07/02/determinism-and-finite-automata-a-primer/>)

Published: 2011-07-02T23:41:30Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Automaton](<https://devfeed.tech/topics/automaton.md>), [function](<https://devfeed.tech/topics/function.md>)

Tags: [computability-theory](<https://devfeed.tech/tags/computability-theory.md>), [computing](<https://devfeed.tech/tags/computing.md>), [context-free-languages](<https://devfeed.tech/tags/context-free-languages.md>), [deterministic-finite-automata](<https://devfeed.tech/tags/deterministic-finite-automata.md>), [finite-state-machines](<https://devfeed.tech/tags/finite-state-machines.md>), [function](<https://devfeed.tech/tags/function.md>), [input](<https://devfeed.tech/tags/input.md>), [language](<https://devfeed.tech/tags/language.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [nondeterministic-finite-automata](<https://devfeed.tech/tags/nondeterministic-finite-automata.md>), [primer](<https://devfeed.tech/tags/primer.md>), [pushdown-automata](<https://devfeed.tech/tags/pushdown-automata.md>), [regular-languages](<https://devfeed.tech/tags/regular-languages.md>), [string](<https://devfeed.tech/tags/string.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>)

### AI overview

This primer introduces computation as a function that maps input to output, then develops a more rigorous model based on finite alphabets and strings. It explains how a computational model recognizes a language by accepting or rejecting strings.

### Source excerpt

The first step in studying the sorts of possible computations (and more interestingly, those things which cannot be computed) is to define exactly what we mean by a "computation." At a high level, this is easy: a computation is simply a function. Given some input, produce the appropriate output. Unfortunately this is much too general. For instance, we could define almost anything we want in terms of functions. Let $ f$ be the function which accepts as input the date of California Super Lotto drawings, and returns the set of winning numbers for that date.

## Turing Machines and Conway's Dreams

DevFeed: [Turing Machines and Conway's Dreams](<https://devfeed.tech/articles/turing-machines-and-conway-s-dreams-40215.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2011/06/30/turing-machines-and-conways-dreams/>)

Published: 2011-06-30T20:50:04Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Automaton](<https://devfeed.tech/topics/automaton.md>)

Tags: [cellular](<https://devfeed.tech/tags/cellular.md>), [cellular-automata](<https://devfeed.tech/tags/cellular-automata.md>), [computability-theory](<https://devfeed.tech/tags/computability-theory.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [conway](<https://devfeed.tech/tags/conway.md>), [infinite](<https://devfeed.tech/tags/infinite.md>), [life](<https://devfeed.tech/tags/life.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [patterns](<https://devfeed.tech/tags/patterns.md>), [period](<https://devfeed.tech/tags/period.md>), [programming](<https://devfeed.tech/tags/programming.md>), [recursion](<https://devfeed.tech/tags/recursion.md>), [theory](<https://devfeed.tech/tags/theory.md>), [turing-machine](<https://devfeed.tech/tags/turing-machine.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>)

### AI overview

The article examines Conway's Game of Life patterns that do not stabilize, including Gosper's glider gun and puffers that produce continuing activity. It connects these patterns to computability, explaining that infinite looping is necessary for Turing-complete computation.

### Source excerpt

Additional Patterns Last time we left the reader with the assertion that Conway's game of life does not always stabilize. Specifically, there exist patterns which result in unbounded cell population growth. Although John Conway's original conjecture was that all patterns eventually stabilize (and offered $50 to anyone who could provide a proof or counterexample), he was proven wrong. Here we have the appropriately named glider gun, whose main body oscillates, expelling a glider once per period.

## Introduction to Cellular Automata

DevFeed: [Introduction to Cellular Automata](<https://devfeed.tech/articles/the-wild-world-of-cellular-automata-40214.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2011/06/29/conways-game-of-life/>)

Published: 2011-06-29T21:08:45Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Cellular automaton](<https://devfeed.tech/topics/cellular-automaton.md>), [Automaton](<https://devfeed.tech/topics/automaton.md>), [Finite-state machine](<https://devfeed.tech/topics/finite-state-machine.md>)

Tags: [cellular-automata](<https://devfeed.tech/tags/cellular-automata.md>), [computability-theory](<https://devfeed.tech/tags/computability-theory.md>), [conus](<https://devfeed.tech/tags/conus.md>), [conway](<https://devfeed.tech/tags/conway.md>), [life](<https://devfeed.tech/tags/life.md>), [mathematica](<https://devfeed.tech/tags/mathematica.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [patterns](<https://devfeed.tech/tags/patterns.md>), [programming](<https://devfeed.tech/tags/programming.md>), [rules](<https://devfeed.tech/tags/rules.md>), [simulation](<https://devfeed.tech/tags/simulation.md>), [turing-machine](<https://devfeed.tech/tags/turing-machine.md>)

### AI overview

An introductory tutorial on cellular automata, explaining cells, states, transition rules, simultaneous updates, and a one-dimensional binary example.

### Source excerpt

Cellular Automata There is a long history of mathematical models for computation. One very important one is the Turing Machine, which is the foundation of our implementations of actual computers today. On the other end of the spectrum, one of the simpler models of computation (often simply called a system) is a cellular automaton. Surprisingly enough, there are deep connections between the two. But before we get ahead of ourselves, let's see what these automata can do.

## Regexp performances and Finite Automata

DevFeed: [Regexp performances and Finite Automata](<https://devfeed.tech/articles/regexp-performances-and-finite-automata-34389.md>)

Original publisher: [Read original article](<https://tapoueh.org/blog/2010/09/regexp-performances-and-finite-automata/>)

Author: Dimitri Fontaine PostgreSQL Major Contributor; Author

Published: 2010-09-26T19:00:00Z

Content type: article

Language: en

Sources: [Dimitri Fontaine](<https://devfeed.tech/sources/dimitri-fontaine.md>)

Topics: [Automaton](<https://devfeed.tech/topics/automaton.md>), [Regular expression](<https://devfeed.tech/topics/regular-expression.md>), [Parser](<https://devfeed.tech/topics/parser.md>), [PostgreSQL](<https://devfeed.tech/topics/postgresql.md>), [Perl](<https://devfeed.tech/topics/perl.md>), [Ruby](<https://devfeed.tech/topics/ruby.md>), [Emacs](<https://devfeed.tech/topics/emacs.md>)

Tags: [dfa](<https://devfeed.tech/tags/dfa.md>), [emacs-lisp](<https://devfeed.tech/tags/emacs-lisp.md>), [perl](<https://devfeed.tech/tags/perl.md>), [postgresql](<https://devfeed.tech/tags/postgresql.md>), [regexp](<https://devfeed.tech/tags/regexp.md>), [regular-expressions](<https://devfeed.tech/tags/regular-expressions.md>), [ruby](<https://devfeed.tech/tags/ruby.md>)

### AI overview

This article examines regular-expression performance through the lens of finite automata, contrasting NFA and DFA-based implementation techniques. It also discusses PostgreSQL's regular-expression implementation and the author's preference for using awk in some file-searching situations.

### Source excerpt

The major reason why I dislike perl so much, and ruby too, and the thing I'd want different in the Emacs Lisp API so far is how they set developers mind into using regexp. You know the quote, don't you? Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems. That said, some situations require the use of regexp -- or are so much simpler to solve using them than the maintenance hell you're building here ain't that big a drag. The given expressiveness is hard to match with any other solution, to the point I sometime use them in my code (well I use rx to lower the burden sometime, just see this example).