Buchumschlag

On the Representation and State Complexity of Block Languages

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Duarte, Guilherme, Moreira, Nelma, Prigioniero, Luca, Reis, Rogério
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Formal Languages and Automata Theory
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Operational State Complexity of Block Languages
von: Duarte, Guilherme, et al.
Veröffentlicht: (2024)

Proceedings of the 15th International Workshop on Non-Classical Models of Automata and Applications
von: Moreira, Nelma, et al.
Veröffentlicht: (2025)

Nondeterminism makes unary 1-limited automata concise
von: Guillon, Bruno, et al.
Veröffentlicht: (2025)

On the Complexity of Language Membership for Probabilistic Words
von: Amarilli, Antoine, et al.
Veröffentlicht: (2025)

On the Complexity of Computing the Co-lexicographic Width of a Regular Language
von: Becker, Ruben, et al.
Veröffentlicht: (2024)

Star Complexity of Parikh Images of Languages over Infinite Alphabets
von: Danieli, Yoav
Veröffentlicht: (2026)

Languages of Boundedly-Ambiguous Vector Addition Systems with States
von: Czerwiński, Wojciech, et al.
Veröffentlicht: (2025)

Computational Complexity of Alignments
von: Schwanen, Christopher T., et al.
Veröffentlicht: (2026)

Descriptional Complexity of Finite Automata -- Selected Highlights
von: Salomaa, Arto, et al.
Veröffentlicht: (2023)

Fine-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs
von: Drabik, Karolina, et al.
Veröffentlicht: (2025)

A Complexity Bound for Determinisation of Min-Plus Weighted Automata
von: Almagor, Shaull, et al.
Veröffentlicht: (2026)

Unconditional Time and Space Complexity Lower Bounds for Intersection Non-Emptiness
von: Wehar, Michael
Veröffentlicht: (2025)

Waiting Nets: State Classes and Taxonomy
von: Hélouët, Loïc, et al.
Veröffentlicht: (2022)

Mind the Gap: A Formal Investigation of the Relationship Between Log and Model Complexity -- Extended Version
von: Schalk, Patrizia, et al.
Veröffentlicht: (2025)

Exact Accepting-State Spectrum for Reversal of Permutation Automata
von: German, Samuel
Veröffentlicht: (2026)

Fast and General Automatic Differentiation for Finite-State Methods
von: Yang, Lucas Ondel, et al.
Veröffentlicht: (2026)

Efficient Constructions of Finite-State Independent Normal Pairs
von: Pulari, Subin
Veröffentlicht: (2026)

Universally Wheeler Languages
von: Becker, Ruben, et al.
Veröffentlicht: (2025)

Quantitative Language Automata
von: Henzinger, Thomas A., et al.
Veröffentlicht: (2025)

On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning
von: Nowak, Franz, et al.
Veröffentlicht: (2024)

State estimation of timed automata under partial observation [Draft version]
von: Gao, Chao, et al.
Veröffentlicht: (2024)

Verification and Enforcement of Strong State-Based Opacity for Discrete-Event Systems
von: Han, Xiaoguang, et al.
Veröffentlicht: (2024)

Active Inference of Extended Finite State Machine Models with Registers and Guards
von: Groz, Roland, et al.
Veröffentlicht: (2026)

Positive Varieties of Lattice Languages
von: Inoue, Yusuke, et al.
Veröffentlicht: (2025)

The Quadratic State Cost of Classical Simulation of One-Way Quantum Finite Automata
von: Chen, Zeyu, et al.
Veröffentlicht: (2026)

Semiflows, Home Spaces, and Home States, Applications to the Analysis of Parameterized Petri Nets
von: Memmi, Gerard
Veröffentlicht: (2025)

Synthesis of State-Attack Strategies for Anonymity and Opacity Violation in Discrete Event Systems
von: Li, Xiaoyan, et al.
Veröffentlicht: (2025)

On the Separability Problem of VASS Reachability Languages
von: Keskin, Eren, et al.
Veröffentlicht: (2024)

Regular Languages in the Sliding Window Model
von: Ganardi, Moses, et al.
Veröffentlicht: (2024)

Stochastic Languages at Sub-stochastic Cost
von: Agarwal, Smayan, et al.
Veröffentlicht: (2025)

State Complexity of Multiple Concatenation
von: Jirásek, Jozef, et al.
Veröffentlicht: (2025)

Positive Characteristic Sets for Relational Pattern Languages
von: Mousawi, S. Mahmoud, et al.
Veröffentlicht: (2025)

Idefix-Closed Languages and Their Application in Contextual Grammars
von: Ködding, Marvin, et al.
Veröffentlicht: (2025)

A Tree Sampler for Bounded Context-Free Languages
von: Considine, Breandan
Veröffentlicht: (2024)

Greybox Learning of Languages Recognizable by Event-Recording Automata
von: Majumdar, Anirban, et al.
Veröffentlicht: (2024)

Kamp Theorem for Pomset Languages of Higher Dimensional Automata
von: Clement, Emily, et al.
Veröffentlicht: (2024)

Some Remarks on First-Order Definable Tree Languages
von: Blumensath, Achim
Veröffentlicht: (2024)

Shuffles of Context-Free Languages along Regular Trajectories
von: Barloy, Corentin, et al.
Veröffentlicht: (2026)

Atomic Gliders and CA as Language Generators (Extended Version)
von: Fisman, Dana, et al.
Veröffentlicht: (2025)

Measure-Theoretic Aspects of Star-Free and Group Languages
von: Sin'ya, Ryoma, et al.
Veröffentlicht: (2025)