{"results":[{"id":"arxiv_2512.23403","title":"A pumping-like lemma for languages over infinite alphabets","authors":[{"name":"Yoav Danieli"}],"abstract":"We prove a kind of a pumping lemma for languages accepted by one-register alternating finite-memory automata. As a corollary, we obtain that the set of lengths of words in such languages is semi-linear.","source":"arXiv","year":2025,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/2512.23403","pdf_url":"https://arxiv.org/pdf/2512.23403","is_open_access":true,"published_at":"2025-12-29T11:49:48Z","score":69},{"id":"arxiv_2504.20395","title":"Partial Answer of How Transformers Learn Automata","authors":[{"name":"Tiantian Zhang"}],"abstract":"We introduce a novel framework for simulating finite automata using representation-theoretic semidirect products and Fourier modules, achieving more efficient Transformer-based implementations.","source":"arXiv","year":2025,"language":"en","subjects":["cs.FL","cs.LG"],"url":"https://arxiv.org/abs/2504.20395","pdf_url":"https://arxiv.org/pdf/2504.20395","is_open_access":true,"published_at":"2025-04-29T03:35:40Z","score":69},{"id":"arxiv_2211.00758","title":"Counterfactual Causality in Networks","authors":[{"name":"Georgiana Caltais"},{"name":"Can Olmezoglu"}],"abstract":"In this abstract we propose a framework for explaining violations of safety properties in Software Defined Networks, using counterfactual causal reasoning.","source":"arXiv","year":2022,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/2211.00758","pdf_url":"https://arxiv.org/pdf/2211.00758","is_open_access":true,"published_at":"2022-11-01T21:29:10Z","score":66},{"id":"doaj_10.23638/DMTCS-22-4-2","title":"A Type System Describing Unboundedness","authors":[{"name":"Paweł Parys"}],"abstract":"We consider nondeterministic higher-order recursion schemes as recognizers of languages of finite words or finite trees. We propose a type system that allows to solve the simultaneous-unboundedness problem (SUP) for schemes, which asks, given a set of letters A and a scheme G, whether it is the case that for every number n the scheme accepts a word (a tree) in which every letter from A appears at least n times. Using this type system we prove that SUP is (m-1)-EXPTIME-complete for word-recognizing schemes of order m, and m-EXPTIME-complete for tree-recognizing schemes of order m. Moreover, we establish the reflection property for SUP: out of an input scheme G one can create its enhanced version that recognizes the same language but is aware of the answer to SUP.","source":"DOAJ","year":2020,"language":"","subjects":["Mathematics"],"doi":"10.23638/DMTCS-22-4-2","url":"https://dmtcs.episciences.org/4748/pdf","pdf_url":"https://dmtcs.episciences.org/4748/pdf","is_open_access":true,"published_at":"","score":64},{"id":"arxiv_1901.03913","title":"The range of non-linear natural polynomials cannot be context-free","authors":[{"name":"Dömötör Pálvölgyi"}],"abstract":"Suppose that some polynomial $f$ with rational coefficients takes only natural values at natural numbers, i.e., $L=\\{f(n)\\mid n\\in \\mathbb N\\}\\subset\\mathbb N$. We show that the base-$q$ representation of $L$ is a context-free language if and only if $f$ is linear, answering a question of Shallit. The proof is based on a new criterion for context-freeness, which is a combination of the Interchange lemma and a generalization of the Pumping lemma.","source":"arXiv","year":2019,"language":"en","subjects":["cs.DM","cs.FL"],"url":"https://arxiv.org/abs/1901.03913","pdf_url":"https://arxiv.org/pdf/1901.03913","is_open_access":true,"published_at":"2019-01-12T23:05:33Z","score":63},{"id":"arxiv_1907.05369","title":"Abelian-square factors and binary words","authors":[{"name":"Salah Triki"}],"abstract":"In this work, we affirm the conjecture proposed by Gabriele Fici and Filippo Mignosi at the 10th Conference on Combinatorics on Words.","source":"arXiv","year":2019,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/1907.05369","pdf_url":"https://arxiv.org/pdf/1907.05369","is_open_access":true,"published_at":"2019-07-04T21:14:28Z","score":63},{"id":"arxiv_1907.05368","title":"On The Structure of Dyck Languages","authors":[{"name":"Rita Gitik"},{"name":"Eliyahy Rips"}],"abstract":"We prove that the closure of the one-sided Dyck language in a free monoid is a two-sided Dyck language.","source":"arXiv","year":2019,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/1907.05368","pdf_url":"https://arxiv.org/pdf/1907.05368","is_open_access":true,"published_at":"2019-07-04T19:06:50Z","score":63},{"id":"arxiv_1807.05555","title":"Briefly on Bottom-up","authors":[{"name":"Paola Quaglia"}],"abstract":"These short notes are meant as a quick reference for the construction of SLR(1), of LR(1), and of LALR(1) parsing tables.","source":"arXiv","year":2018,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/1807.05555","pdf_url":"https://arxiv.org/pdf/1807.05555","is_open_access":true,"published_at":"2018-07-15T14:29:35Z","score":62},{"id":"arxiv_1807.04568","title":"Branch-Continuous Tree Algebras","authors":[{"name":"Achim Blumensath"}],"abstract":"We study a class of algebras that can be used as recognisers for regular languages of infinite trees.","source":"arXiv","year":2018,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/1807.04568","pdf_url":"https://arxiv.org/pdf/1807.04568","is_open_access":true,"published_at":"2018-07-12T12:24:41Z","score":62},{"id":"arxiv_1706.08429","title":"Cellular Automata on Group Sets","authors":[{"name":"Simon Wacker"}],"abstract":"We introduce and study cellular automata whose cell spaces are left-homogeneous spaces. Examples of left-homogeneous spaces are spheres, Euclidean spaces, as well as hyperbolic spaces acted on by isometries; uniform tilings acted on by symmetries; vertex-transitive graphs, in particular, Cayley graphs, acted on by automorphisms; groups acting on themselves by multiplication; and integer lattices acted on by translations. For such automata and spaces, we prove, in particular, generalisations of topological and uniform variants of the Curtis-Hedlund-Lyndon theorem, of the Tarski-Følner theorem, and of the Garden-of-Eden theorem on the full shift and certain subshifts. Moreover, we introduce signal machines that can handle accumulations of events and using such machines we present a time-optimal quasi-solution of the firing mob synchronisation problem on finite and connected graphs.","source":"arXiv","year":2017,"language":"en","subjects":["math.GR","cs.FL"],"doi":"10.5445/IR/1000070923","url":"https://arxiv.org/abs/1706.08429","pdf_url":"https://arxiv.org/pdf/1706.08429","is_open_access":true,"published_at":"2017-06-26T15:11:51Z","score":61},{"id":"arxiv_1607.01828","title":"A Note on Nested String Replacements","authors":[{"name":"Holger Petersen"}],"abstract":"We investigate the number of nested string replacements required to reduce a string of identical characters to one character.","source":"arXiv","year":2016,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/1607.01828","pdf_url":"https://arxiv.org/pdf/1607.01828","is_open_access":true,"published_at":"2016-07-06T22:19:27Z","score":60},{"id":"arxiv_1502.03573","title":"Automata and rational expressions","authors":[{"name":"Jacques Sakarovitch"}],"abstract":"This text is an extended version of the chapter 'Automata and rational expressions' in the AutoMathA Handbook that will appear soon, published by the European Science Foundation and edited by JeanEricPin.","source":"arXiv","year":2015,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/1502.03573","pdf_url":"https://arxiv.org/pdf/1502.03573","is_open_access":true,"published_at":"2015-02-12T09:26:05Z","score":59},{"id":"arxiv_1501.00507","title":"Defining and composing big state machines","authors":[{"name":"Victor Yodaiken"}],"abstract":"A sequence function alternative representation of state machines.","source":"arXiv","year":2015,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/1501.00507","pdf_url":"https://arxiv.org/pdf/1501.00507","is_open_access":true,"published_at":"2015-01-02T22:12:13Z","score":59},{"id":"arxiv_1507.05164","title":"A theory of probabilistic automata, part 1","authors":[{"name":"Andrew M. Mironov"}],"abstract":"In the book we present main concepts of probabilistic automata theory.","source":"arXiv","year":2015,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/1507.05164","pdf_url":"https://arxiv.org/pdf/1507.05164","is_open_access":true,"published_at":"2015-07-18T09:49:30Z","score":59},{"id":"arxiv_1502.02328","title":"Context-free Algorithms","authors":[{"name":"Jonathan Graehl"}],"abstract":"Algorithms on grammars/transducers with context-free derivations: hypergraph reachability, shortest path, and inside-outside pruning of 'relatively useless' arcs that are unused by any near-shortest paths.","source":"arXiv","year":2015,"language":"en","subjects":["cs.FL","cs.DS"],"url":"https://arxiv.org/abs/1502.02328","pdf_url":"https://arxiv.org/pdf/1502.02328","is_open_access":true,"published_at":"2015-02-09T01:45:17Z","score":59},{"id":"arxiv_1210.2343","title":"Ostrowski Numeration and the Local Period of Sturmian Words","authors":[{"name":"Luke Schaeffer"}],"abstract":"We show that the local period at position n in a characteristic Sturmian word can be given in terms of the Ostrowski representation for n + 1.","source":"arXiv","year":2012,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/1210.2343","pdf_url":"https://arxiv.org/pdf/1210.2343","is_open_access":true,"published_at":"2012-10-08T17:11:42Z","score":56},{"id":"arxiv_1202.6275","title":"The FC-rank of a context-free language","authors":[{"name":"Arnaud Carayol"},{"name":"Zoltan Esik"}],"abstract":"We prove that the finite condensation rank (FC-rank) of the lexicographic ordering of a context-free language is strictly less than $ω^ω$.","source":"arXiv","year":2012,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/1202.6275","pdf_url":"https://arxiv.org/pdf/1202.6275","is_open_access":true,"published_at":"2012-02-28T16:41:44Z","score":56},{"id":"arxiv_1110.4136","title":"The non-abelian squares are not context-free","authors":[{"name":"Shuo Tan"}],"abstract":"Answering a recent question of Crochemore, we prove that the language of words that are not abelian squares is not context-free.","source":"arXiv","year":2011,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/1110.4136","pdf_url":"https://arxiv.org/pdf/1110.4136","is_open_access":true,"published_at":"2011-10-18T22:18:45Z","score":55},{"id":"arxiv_1102.0850","title":"Scattered context-free linear orderings","authors":[{"name":"Zoltan Esik"}],"abstract":"We show that it is decidable in exponential time whether the lexicographic ordering of a context-free language is scattered, or a well-ordering.","source":"arXiv","year":2011,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/1102.0850","pdf_url":"https://arxiv.org/pdf/1102.0850","is_open_access":true,"published_at":"2011-02-04T08:13:59Z","score":55},{"id":"arxiv_1105.2849","title":"Pattern avoidance with involution","authors":[{"name":"James D. Currie"}],"abstract":"We give the avoidance indices (morphic and antimorphic) for all unary patterns with involution.","source":"arXiv","year":2011,"language":"en","subjects":["cs.FL"],"url":"https://arxiv.org/abs/1105.2849","pdf_url":"https://arxiv.org/pdf/1105.2849","is_open_access":true,"published_at":"2011-05-13T22:59:27Z","score":55}],"total":2,"page":1,"page_size":20,"sources":["DOAJ","arXiv"],"query":"cs.FL"}