Cover Image

On the Complexity of Computing the Co-lexicographic Width of a Regular Language

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Becker, Ruben, Cenzato, Davide, Kim, Sung-Hwan, Kociumaka, Tomasz, Kodric, Bojana, Policriti, Alberto, Prezza, Nicola
Format:	Preprint
Published:	2024
Subjects:	Formal Languages and Automata Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Universally Wheeler Languages
by: Becker, Ruben, et al.
Published: (2025)

Indexing Finite-State Automata Using Forward-Stable Partitions
by: Becker, Ruben, et al.
Published: (2024)

Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems
by: Kociumaka, Tomasz, et al.
Published: (2014)

Regular Grammars for Sets of Graphs of Tree-Width 2
by: Bozga, Marius, et al.
Published: (2024)

Computational Complexity of Alignments
by: Schwanen, Christopher T., et al.
Published: (2026)

Well-Behaved (Co)algebraic Semantics of Regular Expressions in Dafny
by: Zetzsche, Stefan, et al.
Published: (2024)

Regular Languages in the Sliding Window Model
by: Ganardi, Moses, et al.
Published: (2024)

Shuffles of Context-Free Languages along Regular Trajectories
by: Barloy, Corentin, et al.
Published: (2026)

Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages
by: Angluin, Dana, et al.
Published: (2022)

On The Space Complexity of Partial Derivatives of Regular Expressions with Shuffle
by: Ancona, Davide, et al.
Published: (2025)

Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries
by: Figueira, Diego, et al.
Published: (2022)

The Complexity of Aggregates over Extractions by Regular Expressions
by: Doleschal, Johannes, et al.
Published: (2020)

Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
by: Giuliani, Sara, et al.
Published: (2020)

On the Complexity of Language Membership for Probabilistic Words
by: Amarilli, Antoine, et al.
Published: (2025)

Operational State Complexity of Block Languages
by: Duarte, Guilherme, et al.
Published: (2024)

On the Representation and State Complexity of Block Languages
by: Duarte, Guilherme, et al.
Published: (2024)

Regular Expressions with Backreferences on Multiple Context-Free Languages, and the Closed-Star Condition
by: Nogami, Taisei, et al.
Published: (2024)

Star Complexity of Parikh Images of Languages over Infinite Alphabets
by: Danieli, Yoav
Published: (2026)

Classifying Words with 3-sort Automata
by: Jastrząb, Tomasz, et al.
Published: (2024)

On the Expressive Power of Regular Expressions with Backreferences
by: Nogami, Taisei, et al.
Published: (2023)

Directed Regular and Context-Free Languages
by: Ganardi, Moses, et al.
Published: (2024)

Weighted Automata and Regular Expressions for Financial Systems
by: Droste, Manfred, et al.
Published: (2026)

A Regular and Complete Notion of Delay for Streaming String Transducers
by: Filiot, Emmanuel, et al.
Published: (2022)

GrappaRE -- A Tool for Efficient Graph Recognition Based on Finite Automata and Regular Expressions
by: De Rosa, Mattia, et al.
Published: (2025)

Descriptional Complexity of Finite Automata -- Selected Highlights
by: Salomaa, Arto, et al.
Published: (2023)

Computational Model for Parsing Expression Grammars
by: Rubtsov, Alexander, et al.
Published: (2024)

Compiling Quantum Regular Language States
by: Bellante, Armando, et al.
Published: (2026)

Fine-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs
by: Drabik, Karolina, et al.
Published: (2025)

A Complexity Bound for Determinisation of Min-Plus Weighted Automata
by: Almagor, Shaull, et al.
Published: (2026)

Temporal Causal Models as a Model of Computation
by: Gladyshev, Maksim, et al.
Published: (2026)

Unconditional Time and Space Complexity Lower Bounds for Intersection Non-Emptiness
by: Wehar, Michael
Published: (2025)

Undecidability of the Emptiness Problem for Weak Models of Distributed Computing
by: Principato, Flavio T., et al.
Published: (2025)

Computing measures of weak-MSO definable sets of trees
by: Niwiński, Damian, et al.
Published: (2024)

A Characterization of Turing Machines that Compute Primitive Recursive Functions
by: Schwartz, Daniel G.
Published: (2025)

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

Quantitative Language Automata
by: Henzinger, Thomas A., et al.
Published: (2025)

Positive Varieties of Lattice Languages
by: Inoue, Yusuke, et al.
Published: (2025)

Linear Matching of JavaScript Regular Expressions
by: Barrière, Aurèle, et al.
Published: (2023)

Stochastic Languages at Sub-stochastic Cost
by: Agarwal, Smayan, et al.
Published: (2025)

On the Separability Problem of VASS Reachability Languages
by: Keskin, Eren, et al.
Published: (2024)