Imagen de Portada

Quantum finite automata and linear context-free languages: a decidable problem

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bertoni, A., Choffrut, Ch., D'Alessandro, F.
Formato:	Preprint
Publicado:	2013
Materias:	Formal Languages and Automata Theory
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

The complexity of reachability problems in strongly connected finite automata
por: Kiefer, Stefan, et al.
Publicado: (2025)

Message complexity for unary multiautomata systems
por: Choffrut, Christian
Publicado: (2024)

[Draft] High-order estimation-based properties and high-order observers for labeled finite-state automata
por: Zhang, Kuize, et al.
Publicado: (2024)

A short survey around the pumping lemma for context-free languages
por: Gullà, Gabriele
Publicado: (2024)

Two-way affine automata can verify every language
por: Chen, Zeyu, et al.
Publicado: (2025)

Execution-time opacity problems in one-clock parametric timed automata
por: André, Étienne, et al.
Publicado: (2024)

Is decidability of the Submonoid Membership Problem closed under finite extensions?
por: Shafrir, Doron
Publicado: (2024)

Topological transitivity of group cellular automata is decidable
por: Castronuovo, Niccolò, et al.
Publicado: (2026)

State estimation of timed automata under partial observation [Draft version]
por: Gao, Chao, et al.
Publicado: (2024)

Database-assisted automata learning
por: Walinga, Hielke, et al.
Publicado: (2024)

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

Cerny type automata and rank conjecture
por: Rystsov, Igor
Publicado: (2025)

Conway's cosmological theorem and automata theory
por: Lairez, Pierre, et al.
Publicado: (2024)

The complexity of separability for semilinear sets and Parikh automata
por: Collins, Elias Rojas, et al.
Publicado: (2024)

Non-deterministic asynchronous automata games and their undecidability
por: Adsul, Bharat, et al.
Publicado: (2024)

Diagnosability of labeled $\mathfrak{D_p}$ automata
por: Zhang, Kuize, et al.
Publicado: (2021)

Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fields
por: Bell, Jason P., et al.
Publicado: (2022)

Bounded treewidth, multiple context-free grammars, and downward closures
por: Aiswarya, C., et al.
Publicado: (2025)

Characterizing normality via automata and random matrix products
por: Bienvenu, Laurent, et al.
Publicado: (2026)

Nondeterminism makes unary 1-limited automata concise
por: Guillon, Bruno, et al.
Publicado: (2025)

Exact descriptional complexity of determinization of input-driven pushdown automata
por: Martynova, Olga
Publicado: (2024)

Soft state reduction of fuzzy automata over residuated lattices
por: Nguyen, Linh Anh, et al.
Publicado: (2025)

Deterministic pushdown automata can compress some normal sequences
por: Carton, Olivier, et al.
Publicado: (2022)

Cluster automata
por: Kornai, András
Publicado: (2025)

The Tribonacci constant and finite automata
por: Shallit, Jeffrey
Publicado: (2025)

Completely reachable automata: a quadratic decision algorithm and a quadratic upper bound on the reaching threshold
por: Ferens, Robert, et al.
Publicado: (2022)

Cellular automata can really solve the parity problem
por: Wolnik, Barbara, et al.
Publicado: (2025)

Time for Quiescence: Modelling quiescent behaviour in testing via time-outs in timed automata
por: Briones, Laura Brandán, et al.
Publicado: (2025)

A hierarchy of reversible finite automata
por: Radionova, Maria, et al.
Publicado: (2024)

A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata
por: Petrov, Semyon, et al.
Publicado: (2024)

Characterization of deterministically recognizable weighted tree languages over commutative semifields by finitely generated and cancellative scalar algebras
por: Fülöp, Zoltán, et al.
Publicado: (2025)

Saturating automata for game semantics
por: Dixon, Alex, et al.
Publicado: (2023)

Completeness for categories of generalized automata
por: Boccali, Guido, et al.
Publicado: (2023)

A study on the composition of elementary cellular automata
por: Castillo-Ramirez, Alonso, et al.
Publicado: (2023)

The Agafonov and Schnorr-Stimm theorems for probabilistic automata
por: Bienvenu, Laurent, et al.
Publicado: (2025)

On the transversals of Latin squares generated by nonlinear bipermutive cellular automata
por: Dennunzio, Alberto, et al.
Publicado: (2026)

Navigational hierarchies of regular languages
por: Place, Thomas, et al.
Publicado: (2024)

Geodesic languages for rational subsets and conjugates in virtually free groups
por: Carvalho, André, et al.
Publicado: (2024)

Idempotent cellular automata and their natural order
por: Castillo-Ramirez, Alonso, et al.
Publicado: (2024)

Note on dissecting power of regular languages
por: Rukavicka, Josef
Publicado: (2023)