Formal Languages and Automata Theory

Authors and titles for recent submissions

[ total of 15 entries: 1-12 | 13-15 ]
[ showing 12 entries per page: fewer | more | all ]

[1] arXiv:2405.20026 [pdf, ps, other]: Title: The CFG Complexity of Singleton Sets

Authors: Lance Fortnow, William Gasarch

Subjects: Formal Languages and Automata Theory (cs.FL)
[2] arXiv:2405.19622 (cross-list from cs.DM) [pdf, ps, other]: Title: On shortest products for nonnegative matrix mortality

Authors: Andrew Ryzhikov

Subjects: Discrete Mathematics (cs.DM); Formal Languages and Automata Theory (cs.FL); Combinatorics (math.CO)

[3] arXiv:2405.18871 [pdf, other]: Title: DFAMiner: Mining minimal separating DFAs from labelled samples

Authors: Daniele Dell'Erba, Yong Li, Sven Schewe

Comments: 24 pages including appendices and references; version for LearnAut workshop

Subjects: Formal Languages and Automata Theory (cs.FL); Machine Learning (cs.LG)
[4] arXiv:2405.18439 (cross-list from cs.CC) [pdf, ps, other]: Title: The Polynomial Hierarchy does not collapse

Authors: Reiner Czerwinski

Comments: 11 pages

Subjects: Computational Complexity (cs.CC); Formal Languages and Automata Theory (cs.FL)

[5] arXiv:2405.17629 [pdf, ps, other]: Title: Lindenmayer graph languages, first-order theories and expanders

Authors: Teodor Knapik

Subjects: Formal Languages and Automata Theory (cs.FL); Logic (math.LO)
[6] arXiv:2405.18409 (cross-list from math.GR) [pdf, ps, other]: Title: Sections of Submonoids of Nilpotent Groups

Authors: Doron Shafrir

Subjects: Group Theory (math.GR); Formal Languages and Automata Theory (cs.FL)
[7] arXiv:2405.18032 (cross-list from cs.DM) [pdf, other]: Title: Automatic Abelian Complexities of Parikh-Collinear Fixed Points

Authors: Michel Rigo, Manon Stipulanti, Markus A. Whiteland

Comments: 18 pages, 2 figures, long version of [M. Rigo, M. Stipulanti, M. A. Whiteland, Automaticity and Parikh-collinear morphisms. In: Combinatorics on Words. Lecture Notes in Comput. Sci., vol. 13899, pp. 247-260. Springer, 2023]

Subjects: Discrete Mathematics (cs.DM); Formal Languages and Automata Theory (cs.FL); Combinatorics (math.CO)

[8] arXiv:2405.16166 [pdf, other]: Title: The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective

Authors: Pascal Bergsträßer, Chris Köcher, Anthony Widjaja Lin, Georg Zetzsche

Subjects: Formal Languages and Automata Theory (cs.FL)
[9] arXiv:2405.17394 (cross-list from cs.CL) [pdf, other]: Title: The Expressive Capacity of State Space Models: A Formal Language Perspective

Authors: Yash Sarrof, Yana Veitsman, Michael Hahn

Subjects: Computation and Language (cs.CL); Formal Languages and Automata Theory (cs.FL); Machine Learning (cs.LG)
[10] arXiv:2405.16767 (cross-list from cs.CR) [pdf, other]: Title: Oblivious Monitoring for Discrete-Time STL via Fully Homomorphic Encryption

Authors: Masaki Waga, Kotaro Matsuoka, Takashi Suwa, Naoki Matsumoto, Ryotaro Banno, Song Bian, Kohei Suenaga

Subjects: Cryptography and Security (cs.CR); Formal Languages and Automata Theory (cs.FL)
[11] arXiv:2405.16176 (cross-list from cs.CL) [pdf, other]: Title: Bi-reachability in Petri nets with data

Authors: Łukasz Kamiński, Sławomir Lasota

Subjects: Computation and Language (cs.CL); Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO)

[12] arXiv:2405.14272 [pdf, other]: Title: Nominal Tree Automata With Name Allocation

Authors: Simon Prucker, Lutz Schröder

Subjects: Formal Languages and Automata Theory (cs.FL)

[ total of 15 entries: 1-12 | 13-15 ]
[ showing 12 entries per page: fewer | more | all ]