Top 10 Arxiv Papers Today in Formal Languages And Automata Theory


0.0 Mikeys
#1. On random primitive sets, directable NDFAs and the generation of slowly synchronizing DFAs
Costanza Catalano, Raphaël M. Jungers
We tackle the problem of the randomized generation of slowly synchronizing deterministic automata (DFAs) by generating random primitive sets of matrices. We show that when the randomized procedure is too simple the exponent of the generated sets is O(n log n) with high probability, thus the procedure fails to return DFAs with large reset threshold. We extend this result to random nondeterministic automata (NDFAs) by showing, in particular, that a uniformly sampled NDFA has both a 2-directing word and a 3-directing word of length O(n log n) with high probability. We then present a more involved randomized algorithm that manages to generate DFAs with large reset threshold and we finally leverage this finding for exhibiting new families of DFAs with reset threshold of order $ \Omega(n^2/4) $.
more | pdf | html
Figures
Tweets
MathPaper: On random primitive sets, directable NDFAs and the generation of slowly synchronizing DFAs. https://t.co/nkuseGK8A7
MUKULBHALLA7: https://t.co/csZzdjGs4Y
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 15622
Unqiue Words: 2703

0.0 Mikeys
#2. A Faster-Than Relation for Semi-Markov Decision Processes
Mathias R. Pedersen, Giorgio Bacci, Kim G. Larsen
When modeling concurrent or cyber-physical systems, non-functional requirements such as time are important to consider. In order to improve the timing aspects of a model, it is necessary to have some notion of what it means for a process to be faster than another, which can guide the stepwise refinement of the model. To this end we study a faster-than relation for semi-Markov decision processes and compare it to standard notions for relating systems. We show that checking whether a system is faster than another one is undecidable, but as a positive result we give a decision procedure for approximating it. Furthermore, we consider the compositional aspects of this relation, and show that the faster-than relation is not a precongruence with respect to parallel composition, hence giving rise to so-called parallel timing anomalies. We take the first steps toward understanding this problem by identifying decidable conditions sufficient to avoid parallel timing anomalies in the absence of non-determinism.
more | pdf | html
Figures
None.
Tweets
ComputerPapers: A Faster-Than Relation for Semi-Markov Decision Processes. https://t.co/YtuiqDO3X3
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 11079
Unqiue Words: 2250

0.0 Mikeys
#3. The problem with probabilistic DAG automata for semantic graphs
Ieva Vasiljeva, Sorcha Gilroy, Adam Lopez
Semantic representations in the form of directed acyclic graphs (DAGs) have been introduced in recent years, and to model them, we need probabilistic models of DAGs. One model that has attracted some attention is the DAG automaton, but it has not been studied as a probabilistic model. We show that some DAG automata cannot be made into useful probabilistic models by the nearly universal strategy of assigning weights to transitions. The problem affects single-rooted, multi-rooted, and unbounded-degree variants of DAG automata, and appears to be pervasive. It does not affect planar variants, but these are problematic for other reasons.
more | pdf | html
Figures
None.
Tweets
there_are_two_: In time for tonight’s Great @BritishBakeOff final, here is a mathematical / computational linguistics research paper with #GBBO-themed examples, by Ieva Vasiljeva and @SorchaGilroy. https://t.co/ngWI1EP3aq https://t.co/FiRmSpZFd1
there_are_two_: In this paper, Ieva Vasiljeva and @SorchaGilroy give you a simple and elegant proof that it is *impossible* to define a probabilistic model by weighting the transitions of a DAG automaton. https://t.co/ngWI1EP3aq https://t.co/DFI2oaQWGl
there_are_two_: In time for tonight’s Great @BritishBakeOff final, here is a mathematical / computational linguistics research paper with #GBBO-themed examples, by Ieva Vasiljeva and @SorchaGilroy. https://t.co/ngWI1EP3aq https://t.co/Ci4AtqaMuQ
arxiv_cscl: The problem with probabilistic DAG automata for semantic graphs https://t.co/zwFtuieTsl
arxiv_cscl: The problem with probabilistic DAG automata for semantic graphs https://t.co/zwFtuieTsl
Github
None.
Youtube
None.
Other stats
Sample Sizes : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Authors: 3
Total Words: 6659
Unqiue Words: 1738

0.0 Mikeys
#4. Circular critical exponents for Thue-Morse factors
Jeffrey Shallit, Ramin Zarifi
We prove various results about the largest exponent of a repetition in a factor of the Thue-Morse word, when that factor is considered as a circular word. Our results confirm and generalize previous results of Fitzpatrick and Aberkane & Currie.
more | pdf | html
Figures
None.
Tweets
MathPaper: Circular critical exponents for Thue-Morse factors. https://t.co/5d3yypLIK5
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 5589
Unqiue Words: 1647

0.0 Mikeys
#5. Visibly Pushdown Languages and Free Profinite Algebras
Silke Czarnetzki, Andreas Krebs, Klaus-Jörn Lange
We build a notion of algebraic recognition for visibly pushdown languages by finite algebraic objects. These come with a typical Eilenberg relationship, now between classes of visibly pushdown languages and classes of finite algebras. Building on that algebraic foundation, we further construct a topological object with one purpose being the possibility to derive a notion of equations, through which it is possible to prove that some given visibly pushdown language is not part of a certain class (or to even show decidability of the membership-problem of the class in some cases). In particular, we obtain a special instance of Reiterman's theorem for pseudo-varieties. These findings are then employed on two subclasses of the visibly pushdown languages, for which we derive concrete sets of equations. For some showcase languages, these equations are utilised to prove non-membership to the previously described classes.
more | pdf | html
Figures
None.
Tweets
ComputerPapers: Visibly Pushdown Languages and Free Profinite Algebras. https://t.co/0XZDa7SQSh
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 14014
Unqiue Words: 2489

0.0 Mikeys
#6. Bounded Synthesis of Register Transducers
Ayrat Khalimov, Benedikt Maderbacher, Roderick Bloem
Reactive synthesis aims at automatic construction of systems from their behavioural specifications. The research mostly focuses on synthesis of systems dealing with Boolean signals. But real-life systems are often described using bit-vectors, integers, etc. Bit-blasting would make such systems unreadable, hit synthesis scalability, and is not possible for infinite data-domains. One step closer to real-life systems are register transducers: they can store data-input into registers and later output the content of a register, but they do not directly depend on the data-input, only on its comparison with the registers. Previously it was proven that synthesis of register transducers from register automata is undecidable, but there the authors considered transducers equipped with the unbounded queue of registers. First, we prove the problem becomes decidable if bound the number of registers in transducers, by reducing the problem to standard synthesis of Boolean systems. Second, we show how to use quantified temporal logic, instead of...
more | pdf | html
Figures
None.
Tweets
ComputerPapers: Bounded Synthesis of Register Transducers. https://t.co/ZpM78V7wBu
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 10116
Unqiue Words: 2179

0.0 Mikeys
#7. Transfinite Lyndon words
Olivier Carton, Luc Boasson
In this paper, we extend the notion of Lyndon word to transfinite words. We prove two main results. We first show that, given a transfinite word, there exists a unique factorization in Lyndon words that are locally decreasing, a relaxation of the condition used in the case of finite words. In the part, we prove that the factorization of a rational word has a special form and that it can be computed in polynomial time from a rational expression describing the word.
more | pdf | html
Figures
None.
Tweets
ComputerPapers: Transfinite Lyndon words. https://t.co/z7cuRsxWqf
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 24929
Unqiue Words: 2328

0.0 Mikeys
#8. Branch-Continuous Tree Algebras
Achim Blumensath
We study a class of algebras that can be used as recognisers for regular languages of infinite trees.
more | pdf | html
Figures
None.
Tweets
ComputerPapers: Branch-Continuous Tree Algebras. https://t.co/EJUk8hnxyr
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 23711
Unqiue Words: 3019

0.0 Mikeys
#9. Streamable Regular Transductions
Rajeev Alur, Dana Fisman, Konstantinos Mamouras, Mukund Raghothaman, Caleb Stanford
Motivated by real-time monitoring and data processing applications, we develop a formal theory of quantitative queries for streaming data that can be evaluated efficiently. We consider the model of unambiguous Cost Register Automata (CRAs), which are machines that combine finite-state control (for identifying regular patterns) with a finite set of data registers (for computing numerical aggregates). The definition of CRAs is parameterized by the collection of numerical operations that can be applied to the registers. These machines give rise to the class of streamable regular transductions (SR), and to the class of streamable linear regular transductions (SLR) when the register updates are copyless, i.e. every register appears at most once the right-hand-side expressions of the updates. We give a logical characterization of the class SR (resp., SLR) using MSO-definable transformations from strings to DAGs (resp., trees) without backward edges. Additionally, we establish that the two classes SR and SLR are closed under operations...
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 5
Total Words: 19437
Unqiue Words: 3378

0.0 Mikeys
#10. Enumerating Cryptarithms Using Deterministic Finite Automata
Yuki Nozaki, Diptarama Hendrian, Ryo Yoshinaka, Takashi Horiyama, Ayumi Shinohara
A cryptarithm is a mathematical puzzle where given an arithmetic equation written with letters rather than numerals, a player must discover an assignment of numerals on letters that makes the equation hold true. In this paper, we propose a method to construct a DFA that accepts cryptarithms that admit (unique) solutions for each base. We implemented the method and constructed a DFA for bases $k \le 7$. Those DFAs can be used as complete catalogues of cryptarithms,whose applications include enumeration of and counting the exact numbers $G_k(n)$ of cryptarithm instances with $n$ digits that admit base-$k$ solutions. Moreover, explicit formulas for $G_2(n)$ and $G_3(n)$ are given.
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 5
Total Words: 5564
Unqiue Words: 1531

About

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 72,893 papers.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 72,893 papers.