Copertina

Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Dumitru, Radu Cosmin, Yoshinaka, Ryo, Shinohara, Ayumi
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Formal Languages and Automata Theory Machine Learning
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory
di: Dhayalkar, Sahil Rajesh
Pubblicazione: (2025)

PDFA Distillation via String Probability Queries
di: Baumgartner, Robert, et al.
Pubblicazione: (2024)

Learning Reward Machines from Partially Observed Policies
di: Shehab, Mohamad Louai, et al.
Pubblicazione: (2025)

Finite-valued Streaming String Transducers
di: Filiot, Emmanuel, et al.
Pubblicazione: (2024)

Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination
di: Okudono, Takamasa, et al.
Pubblicazione: (2024)

Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing
di: Kuriyama, Takayuki
Pubblicazione: (2026)

Warm Starting State-Space Models with Automata Learning
di: Fishell, William, et al.
Pubblicazione: (2026)

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

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

Extending AALpy with Passive Learning: A Generalized State-Merging Approach
di: von Berg, Benjamin, et al.
Pubblicazione: (2025)

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

From Formal Language Theory to Statistical Learning: Finite Observability of Subregular Languages
di: Hayashi, Katsuhiko, et al.
Pubblicazione: (2025)

Learning Deterministic Multi-Clock Timed Automata
di: Teng, Yu, et al.
Pubblicazione: (2024)

Efficient Learning of Weak Deterministic Büchi Automata
di: Alluwayma, Mona, et al.
Pubblicazione: (2025)

MLRegTest: A Benchmark for the Machine Learning of Regular Languages
di: van der Poel, Sam, et al.
Pubblicazione: (2023)

SMT-Based Active Learning of Weighted Automata
di: Ferreira, Tiago, et al.
Pubblicazione: (2026)

Partial Answer of How Transformers Learn Automata
di: Zhang, Tiantian
Pubblicazione: (2025)

Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids
di: Aristote, Quentin
Pubblicazione: (2024)

Active Learning of Symbolic Automata Over Rational Numbers
di: Hagedorn, Sebastian, et al.
Pubblicazione: (2025)

On the Minimisation of Deterministic and History-Deterministic Generalised (co)Büchi Automata
di: Casares, Antonio, et al.
Pubblicazione: (2024)

A Detailed Account of Compositional Automata Learning through Alphabet Refinement
di: Henry, Leo, et al.
Pubblicazione: (2025)

Taking Complete Finite Prefixes To High Level, Symbolically
di: Würdemann, Nick, et al.
Pubblicazione: (2023)

Inference of Deterministic Finite Automata via Q-Learning
di: Hosseinkhani, Elaheh, et al.
Pubblicazione: (2025)

Congruence-based Learning of Probabilistic Deterministic Finite Automata
di: Carrasco, Matías, et al.
Pubblicazione: (2024)

Checking History-Determinism is NP-hard for Parity Automata
di: Prakash, Keya
Pubblicazione: (2023)

Passive Model Learning of Visibly Deterministic Context-free Grammars
di: Muškardin, Edi, et al.
Pubblicazione: (2025)

Prefix Parsing is Just Parsing
di: Pasti, Clemente, et al.
Pubblicazione: (2026)

When is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?
di: Maneth, Sebastian, et al.
Pubblicazione: (2025)

Fast and General Automatic Differentiation for Finite-State Methods
di: Yang, Lucas Ondel, et al.
Pubblicazione: (2026)

Efficient Constructions of Finite-State Independent Normal Pairs
di: Pulari, Subin
Pubblicazione: (2026)

PAC learning PDFA from data streams
di: Baumgartner, Robert, et al.
Pubblicazione: (2026)

Composing Copyless Streaming String Transducers
di: Alur, Rajeev, et al.
Pubblicazione: (2022)

History-Deterministic Büchi Automata are Succinct
di: Casares, Antonio, et al.
Pubblicazione: (2026)

Hyper-Minimization for Deterministic Register Automata
di: Li, Yong, et al.
Pubblicazione: (2026)

Deterministic Parikh automata on infinite words
di: Grobler, Mario, et al.
Pubblicazione: (2024)

Constructing Deterministic Parity Automata from Positive and Negative Examples
di: Bohn, León, et al.
Pubblicazione: (2023)

A Sharper Upper Bound for the Separating Words Problem
di: Dumitru, Bogdan C.
Pubblicazione: (2025)

Minimizing Streaming String Transducers: An algebraic approach
di: Benalioua, Yahia Idriss, et al.
Pubblicazione: (2026)

Token Games and History-Deterministic Quantitative-Automata
di: Boker, Udi, et al.
Pubblicazione: (2021)

Tokenisation is NP-Complete
di: Whittington, Philip, et al.
Pubblicazione: (2024)