Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages (English)
- New search for: Golovkins, Marats
- New search for: Kravtsev, Maksim
- New search for: Kravcevs, Vasilijs
- New search for: Golovkins, Marats
- New search for: Kravtsev, Maksim
- New search for: Kravcevs, Vasilijs
In:
Mathematical Foundations of Computer Science 2011
2
;
351-363
;
2011
- Article/Chapter (Book) / Electronic Resource
-
Title:Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
-
Contributors:
-
Published in:Mathematical Foundations of Computer Science 2011 , 2 ; 351-363Lecture Notes in Computer Science ; 6907, 2 ; 351-363
-
Publisher:
- New search for: Springer Berlin Heidelberg
-
Place of publication:Berlin, Heidelberg
-
Publication date:2011-01-01
-
Size:13 pages
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Article/Chapter (Book)
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:
-
Source:
Table of contents eBook
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
Nearest Neighbor Search in High-Dimensional SpacesAndoni, Alexandr et al. | 2011
- 2
-
Invariantization of ListingsFlum, Jörg et al. | 2011
- 3
-
Duality and RecognitionGehrke, Mai et al. | 2011
- 19
-
Some Variants of the Star Height ProblemKirsten, Daniel et al. | 2011
- 34
-
Generic Techniques to Round SDP RelaxationsRaghavendra, Prasad et al. | 2011
- 35
-
New Proofs in Graph MinorsWollan, Paul et al. | 2011
- 36
-
The Least-Core of Threshold Network Flow GamesBachrach, Yoram et al. | 2011
- 48
-
Adhesivity Is Not Enough: Local Church-Rosser RevisitedBaldan, Paolo / Gadducci, Fabio / Sobociński, Pawel et al. | 2011
- 60
-
Quantitative Refinement for Weighted Modal Transition SystemsBauer, Sebastian S. / Fahrenberg, Uli / Juhl, Line / Larsen, Kim G. / Legay, Axel / Thrane, Claus et al. | 2011
- 72
-
Faster Coupon Collecting via Replication with Applications in GossipingBerenbrink, Petra / Elsässer, Robert / Friedetzky, Tom / Nagel, Lars / Sauerwald, Thomas et al. | 2011
- 84
-
Verifying Proofs in Constant DepthBeyersdorff, Olaf / Datta, Samir / Mahajan, Meena / Scharfenberger-Fabian, Gido / Sreenivasaiah, Karteek / Thomas, Michael / Vollmer, Heribert et al. | 2011
- 96
-
The Complexity of the Cover Polynomials for Planar Graphs of Bounded DegreeBläser, Markus / Curticapean, Radu et al. | 2011
- 108
-
Model Checking Coverability Graphs of Vector Addition SystemsBlockelet, Michel / Schmitz, Sylvain et al. | 2011
- 120
-
Hard Functions for Low-Degree Polynomials over Prime FieldsBogdanov, Andrej / Kawachi, Akinori / Tanaka, Hidetoki et al. | 2011
- 132
-
Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model CheckingBollig, Benedikt / Cyriac, Aiswarya / Gastin, Paul / Zeitoun, Marc et al. | 2011
- 145
-
The Reachability Problem for Vector Addition System with One Zero-TestBonnet, Rémi et al. | 2011
- 158
-
The Bounded Search Tree Algorithm for the Closest String Problem Has Quadratic Smoothed ComplexityBoucher, Christina et al. | 2011
- 170
-
Solving Analytic Differential Equations in Polynomial Time over Unbounded DomainsBournez, Olivier / Graça, Daniel S. / Pouly, Amaury et al. | 2011
- 182
-
Pattern-Guided Data Anonymization and ClusteringBredereck, Robert / Nichterlein, André / Niedermeier, Rolf / Philip, Geevarghese et al. | 2011
- 194
-
Language Equivalence of Deterministic Real-Time One-Counter Automata Is NL-CompleteBöhm, Stanislav / Göller, Stefan et al. | 2011
- 206
-
Energy and Mean-Payoff Parity Markov Decision ProcessesChatterjee, Krishnendu / Doyen, Laurent et al. | 2011
- 219
-
The Role of Polymorphism in the Characterisation of Complexity by Soft TypesChrząszcz, Jacek / Schubert, Aleksy et al. | 2011
- 231
-
An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois ConnectionCohen, David A. / Creed, Páidí / Jeavons, Peter G. / Živný, Stanislav et al. | 2011
- 243
-
On the Use of Guards for Logics with DataColcombet, Thomas / Ley, Clemens / Puppis, Gabriele et al. | 2011
- 256
-
An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine DispersersDemenkov, Evgeny / Kulikov, Alexander S. et al. | 2011
- 266
-
On the Complexity of the l-diversity ProblemDondi, Riccardo / Mauri, Giancarlo / Zoppis, Italo et al. | 2011
- 278
-
Infinite Synchronizing Words for Probabilistic AutomataDoyen, Laurent / Massart, Thierry / Shirmohammadi, Mahsa et al. | 2011
- 290
-
Characterizing EF over Infinite Trees and Modal Logic on Transitive GraphsCate, Balder / Facchini, Alessandro et al. | 2011
- 303
-
Parity Games on Graphs with Medium Tree-WidthFearnley, John / Lachish, Oded et al. | 2011
- 315
-
Satisfiability of Systems of Equations of Real Analytic Functions Is Quasi-decidableFranek, Peter / Ratschan, Stefan / Zgliczynski, Piotr et al. | 2011
- 327
-
On Minimising Automata with ErrorsGawrychowski, Paweł / Jeż, Artur / Maletti, Andreas et al. | 2011
- 339
-
Contracting a Chordal Graph to a Split Graph or a TreeGolovach, Petr A. / Kamiński, Marcin / Paulusma, Daniël et al. | 2011
- 351
-
Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent LanguagesGolovkins, Marats / Kravtsev, Maksim / Kravcevs, Vasilijs et al. | 2011
- 364
-
A Universally Defined Undecidable Unimodal LogicHemaspaandra, Edith / Schnoor, Henning et al. | 2011
- 376
-
On the Approximability of Minimum Topic Connected Overlay and Its Special InstancesHosoda, Jun / Hromkovič, Juraj / Izumi, Taisuke / Ono, Hirotaka / Steinová, Monika / Wada, Koichi et al. | 2011
- 36
-
Can Everybody Sit Closer to Their Friends Than Their Enemies?Kermarrec, Anne-Marie / Thraves, Christopher et al. | 2011
- 400
-
Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular FunctionsKolmogorov, Vladimir et al. | 2011
- 412
-
Streaming Algorithms for Recognizing Nearly Well-Parenthesized ExpressionsKrebs, Andreas / Limaye, Nutan / Srinivasan, Srikanth et al. | 2011
- 424
-
Size and Computation of Injective Tree Automatic PresentationsKuske, Dietrich / Weidner, Thomas et al. | 2011
- 436
-
Symmetric Functions Capture General FunctionsLipton, Richard J. / Regan, Kenneth W. / Rudra, Atri et al. | 2011
- 448
-
Compressed Word Problems for Inverse MonoidsLohrey, Markus et al. | 2011
- 460
-
Pushing for Weighted Tree AutomataMaletti, Andreas / Quernheim, Daniel et al. | 2011
- 472
-
Periodicity Algorithms for Partial WordsManea, Florin / Mercaş, Robert / Tiseanu, Cătălin et al. | 2011
- 485
-
State Complexity of Operations on Input-Driven Pushdown AutomataOkhotin, Alexander / Salomaa, Kai et al. | 2011
- 497
-
Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related ProblemPaul, Christophe / Perez, Anthony / Thomassé, Stéphan et al. | 2011
- 508
-
Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern EmergencePerrot, Kevin / Rémila, Eric et al. | 2011
- 520
-
Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical ApproachPilipczuk, Michał et al. | 2011
- 532
-
Distributed Synthesis for Regular and Contextfree SpecificationsFridman, Wladimir / Puchala, Bernd et al. | 2011
- 544
-
Geometric Graphs with Randomly Deleted Edges - Connectivity and Routing ProtocolsKrzywdziński, K. / Rybarczyk, K. et al. | 2011
- 556
-
Untimed Language Preservation in Timed SystemsSankur, Ocan et al. | 2011
- 568
-
Lower Bounds for Linear Decision Trees via an Energy Complexity ArgumentUchizawa, Kei / Takimoto, Eiji et al. | 2011
- 580
-
Weak Cost Monadic Logic over Infinite TreesBoom, Michael et al. | 2011
- 592
-
Linear Problem Kernels for Planar Graph Problems with Small Distance PropertyWang, Jianxin / Yang, Yongjie / Guo, Jiong / Chen, Jianer et al. | 2011
- 604
-
New Parameterized Algorithms for the Edge Dominating Set ProblemXiao, Mingyu / Kloks, Ton / Poon, Sheung-Hung et al. | 2011