Cover Image

Mind the Gap: A Formal Investigation of the Relationship Between Log and Model Complexity -- Extended Version

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Schalk, Patrizia, Polyvyanyy, Artem
Format:	Preprint
Published:	2025
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

Exploring Complexity: An Extended Study of Formal Properties for Process Model Complexity Measures
by: Schalk, Patrizia, et al.
Published: (2024)

Stochastic Directly-Follows Process Discovery Using Grammatical Inference
by: Alkhammash, Hanan, et al.
Published: (2023)

Stochastic Alignments: Matching an Observed Trace to Stochastic Process Models
by: Li, Tian, et al.
Published: (2025)

Correctness Notions for Petri Nets with Identifiers
by: van der Werf, Jan Martijn E. M., et al.
Published: (2022)

Componentwise Automata Learning for System Integration (Extended Version)
by: Fujinami, Hiroya, et al.
Published: (2025)

Atomic Gliders and CA as Language Generators (Extended Version)
by: Fisman, Dana, et al.
Published: (2025)

Collaboration Miner: Discovering Collaboration Petri Nets (Extended Version)
by: Benzin, Janik-Vasily, et al.
Published: (2024)

On-The-Fly Algorithm for Reachability in Parametric Timed Games (Extended Version)
by: Dahlsen-Jensen, Mikael Bisgaard, et al.
Published: (2024)

Chance and Mass Interpretations of Probabilities in Markov Decision Processes (Extended Version)
by: Tsai, Yun Chen, et al.
Published: (2025)

TARZAN: A Region-Based Library for Forward and Backward Reachability of Timed Automata (Extended Version)
by: Manini, Andrea, et al.
Published: (2026)

A Formal Approach for Tuning Stochastic Oscillators
by: Ballarini, Paolo, et al.
Published: (2024)

A General Information Extraction Framework Based on Formal Languages
by: Schmid, Markus L.
Published: (2025)

Active Inference of Extended Finite State Machine Models with Registers and Guards
by: Groz, Roland, et al.
Published: (2026)

WEX: Formal Specifications for Windows in Stream Processing
by: Hitarth, S, et al.
Published: (2022)

Closure Properties of General Grammars -- Formally Verified
by: Dvorak, Martin, et al.
Published: (2023)

Abstract String Domain Defined with Word Equations as a Reduced Product (Extended Version)
by: Nepeivoda, Antonina, et al.
Published: (2025)

Extended time Petri nets
by: Radom, Marcin, et al.
Published: (2024)

Certified Symbolic Finite Transducers: Formalization and Applications to String Analysis
by: Kan, Shuanglong, et al.
Published: (2025)

Bridging the Empirical-Theoretical Gap in Neural Network Formal Language Learning Using Minimum Description Length
by: Lan, Nur, et al.
Published: (2024)

The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective
by: Bergsträßer, Pascal, et al.
Published: (2024)

Formalized Run-Time Analysis of Active Learning -- Coalgebraically in Agda
by: Wißmann, Thorsten
Published: (2026)

Reachability in VASS Extended with Integer Counters
by: Bizière, Clotilde, et al.
Published: (2026)

Extended Stone Duality via Monoidal Adjunctions
by: Lenke, Fabian, et al.
Published: (2024)

Automated Formal Verification of Area-Optimized Safety Registers in Automotive SoCs
by: Zhang, Shuhang, et al.
Published: (2025)

An Automata-Based Method to Formalize Psychological Theories -- The Case Study of Lazarus and Folkman's Stress Theory
by: Finkel, Alain, et al.
Published: (2025)

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

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

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)

Dual Adjunction Between $Ω$-Automata and Wilke Algebra Quotients
by: Chernev, Anton, et al.
Published: (2024)

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

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

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

On the Complexity of Computing the Co-lexicographic Width of a Regular Language
by: Becker, Ruben, et al.
Published: (2024)

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

Formally Verified Linear-Time Invertible Lexing
by: Chassot, Samuel, et al.
Published: (2025)

Automata-less Monitoring via Trace-Checking (Extended Version)
by: Brunello, Andrea, et al.
Published: (2025)

It Takes a Village: Bridging the Gaps between Current and Formal Specifications for Protocols
by: Basin, David, et al.
Published: (2025)

Continuous Diffusion Models Can Obey Formal Syntax
by: Kim, Jinwoo, et al.
Published: (2026)