Search results for "nondeterministic"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
78	Beate Bollig	Complexity Theoretical Results on Nondeterministic Graph-Driven Read-Once Branching Programs.	STACS	2003	DBLP DOI BibTeX RDF
72	Benjamin Aminof, Orna Kupferman	On the Succinctness of Nondeterminism.	ATVA	2006	DBLP DOI BibTeX RDF
71	Beate Bollig, Philipp Woelfel	A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
71	Beate Bollig, Philipp Woelfel	A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications.	MFCS	2002	DBLP DOI BibTeX RDF
64	Dieter Spreen	On Functions Computable in Nondeterministic Polynomial Time: Some Characterizations.	CSL	1987	DBLP DOI BibTeX RDF
60	Natalia Shabaldina, Khaled El-Fakih, Nina Yevtushenko 0001	Testing Nondeterministic Finite State Machines with Respect to the Separability Relation.	TestCom/FATES	2007	DBLP DOI BibTeX RDF	separability relation, testing nondeterministic FSMs
57	Martin Sauerhoff	Computing with Restricted Nondeterminism: The Dependence of the OBDD Size on the Number of Nondeterministic Variables.	FSTTCS	1999	DBLP DOI BibTeX RDF
57	Gerhard Buntrock, Lane A. Hemachandra, Dirk Siefkes	Using Inductive Counting to Simulate Nondeterministic Computation.	MFCS	1990	DBLP DOI BibTeX RDF
53	Michal Armoni, Noa Lewenstein, Mordechai Ben-Ari	Teaching students to think nondeterministically.	SIGCSE	2008	DBLP DOI BibTeX RDF	nondeterministic automata, nondeterminism
53	P. A. Subrahmanyam	Nondeterminism in Abstract Data Types.	ICALP	1981	DBLP DOI BibTeX RDF	nondeterministic operations, extraction equivalence, observable behavior, implementations, correctness, abstract data types, nondeterminism
53	Joseph M. Morris, Malcolm Tyrrell	Dually nondeterministic functions.	ACM Trans. Program. Lang. Syst.	2008	DBLP DOI BibTeX RDF	Angelic nondeterminacy, demonic nondeterminacy, free completely distributive lattice, modeling nondeterminacy, nondeterministic functions, nondeterminism
53	Xianan Zhang, Flavio Junqueira, Matti A. Hiltunen, Keith Marzullo, Richard D. Schlichting	Replicating Nondeterministic Services on Grid Environments.	HPDC	2006	DBLP DOI BibTeX RDF	nondeterministic service, primary-backup approach, replicated grid service, Web service, distributed systems, synchronous system
53	Lev Nachmanson, Margus Veanes, Wolfram Schulte, Nikolai Tillmann, Wolfgang Grieskamp	Optimal strategies for testing nondeterministic systems.	ISSTA	2004	DBLP DOI BibTeX RDF	optimal game strategies, probabilistic nondeterministic finite state machines, abstract state machines
53	Gang Luo, Gregor von Bochmann, Alexandre Petrenko	Test Selection Based on Communicating Nondeterministic Finite-State Machines Using a Generalized WP-Method.	IEEE Trans. Software Eng.	1994	DBLP DOI BibTeX RDF	communicating nondeterministic finite-state machines, generalized Wp-method, conformance relation, trace-equivalence, deterministic finite-state machines, software engineering, software engineering, protocols, software testing, finite state machines, specification languages, program testing, concurrent programs, communication protocols, fault coverage, conformance testing, programming theory, SDL, reachability analysis, test suites, multiprocessing programs, test selection, protocol engineering, test sequence generation, protocol conformance testing
53	John G. Geske, Diane Kakihara	Almost-Everywhere Complexity, Bi-Immunity and Nondeterministic Space.	ICCI	1990	DBLP DOI BibTeX RDF	Nondeterministic space complexity, immune sets, almost-everywhere complexity, hierarchy theorems
50	Yitong Yin	Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity.	ICALP (1)	2008	DBLP DOI BibTeX RDF
50	Andreas Glausch, Wolfgang Reisig	A Semantic Characterization of Unbounded-Nondeterministic Abstract State Machines.	CALCO	2007	DBLP DOI BibTeX RDF
50	Chandra M. R. Kintala, Detlef Wotschke	Concurrent Conciseness of Degree, Probabilistic, Nondeterministic and Deterministic Finite Automata (Extended Abstract).	STACS	1986	DBLP DOI BibTeX RDF
49	Clifford Bergman, Giora Slutzki	Computational Complexity of Some Problems Involving Congruences on Algebras.	LICS	2000	DBLP DOI BibTeX RDF	fully invariant, subdirectly irreducible, nondeterministic log-space, nondeterministic polynomial time, congruence, simple
49	Ville Laurikari	NFAs with Tagged Transitions, Their Conversion to Deterministic Automata and Application to Regular Expressions.	SPIRE	2000	DBLP DOI BibTeX RDF	tagged transitions, automata conversion, input string position tracking, last-use tracking, nondeterministic Mealy machines, string processing, substring addressing, lookahead operator, regular expressions, finite automata, formal semantics, deterministic automata, nondeterministic finite automata
43	Orna Kupferman, Nir Piterman	Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata.	FoSSaCS	2009	DBLP DOI BibTeX RDF
43	Orna Kupferman, Gila Morgenstern, Aniello Murano	Typeness for omega-Regular Automata.	ATVA	2004	DBLP DOI BibTeX RDF
43	Michal Walicki, Sigurd Meldal	A Complete Calculus for the Multialgebraic and Functional Semantics of Nondeterminism.	ACM Trans. Program. Lang. Syst.	1995	DBLP DOI BibTeX RDF	reasoning with nondeterminism, algebraic specifications
43	John E. Hopcroft, Jeffrey D. Ullman	Relations Between Time and Tape Complexities.	J. ACM	1968	DBLP DOI BibTeX RDF
42	Gordon Fraser 0001, Franz Wotawa	Test-Case Generation and Coverage Analysis for Nondeterministic Systems Using Model-Checkers.	ICSEA	2007	DBLP DOI BibTeX RDF
42	Toshiharu Fujita, Takayuki Ueno, Seiichi Iwamoto	A Nondeterministic Dynamic Programming Model.	KES	2004	DBLP DOI BibTeX RDF
42	Lance Fortnow, Dieter van Melkebeek	Time-Space Tradeoffs for Nondeterministic Computation.	CCC	2000	DBLP DOI BibTeX RDF	Satisfiability, Time-space tradeoffs
42	Lance Fortnow	Nondeterministic Polynomial Time versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability.	CCC	1997	DBLP DOI BibTeX RDF
39	Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers	Inverting Onto Functions.	CCC	1996	DBLP DOI BibTeX RDF	function classes, total functions, nondeterministic Turing machines, unambiguous computation, Computational complexity, invertibility
38	Jüri Vain, Kullo Raiend, Andres Kull, Juhan P. Ernits	Synthesis of test purpose directed reactive planning tester for nondeterministic systems.	ASE	2007	DBLP DOI BibTeX RDF	nondeterministic extended finite state machine, reactive planning, model-based testing, online testing
38	Fan Zhang, To-Yat Cheung	Optimal Transfer Trees and Distinguishing Trees for Testing Observable Nondeterministic Finite-State Machines.	IEEE Trans. Software Eng.	2003	DBLP DOI BibTeX RDF	Average weight, distinguishing tree, nondeterministic finite-state machine, transfer tree, weighted height, testing
38	Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer	Nondeterministic NC1 Computation.	CCC	1996	DBLP DOI BibTeX RDF	nondeterministic Turing machine, leaf language, Computational complexity, circuit
36	Yifeng Chen, Jeff W. Sanders	Unifying Probability with Nondeterminism.	FM	2009	DBLP DOI BibTeX RDF
36	Thomas A. Henzinger, Nir Piterman	Solving Games Without Determinization.	CSL	2006	DBLP DOI BibTeX RDF
36	Juraj Hromkovic, Martin Sauerhoff	The Power of Nondeterminism and Randomness for Oblivious Branching Programs.	Theory Comput. Syst.	2003	DBLP DOI BibTeX RDF
35	Andrzej S. Murawski	Reachability Games and Game Semantics: Comparing Nondeterministic Programs.	LICS	2008	DBLP DOI BibTeX RDF	Idealized Algol, pushdown graphs, reachability games, nondeterminism, game semantics
35	Chuzo Iwamoto, Harumasa Yoneda, Kenichi Morita, Katsunobu Imai	A Time Hierarchy Theorem for Nondeterministic Cellular Automata.	TAMC	2007	DBLP DOI BibTeX RDF
35	Agnieszka Makarec	Interpretation of Probabilistic Algorithmic Logic in Nondeterministic Algorithmic Logic.	CISIM	2007	DBLP DOI BibTeX RDF
35	Kim Solin	On Two Dually Nondeterministic Refinement Algebras.	RelMiCS	2006	DBLP DOI BibTeX RDF
35	François Le Gall	Quantum Weakly Nondeterministic Communication Complexity.	MFCS	2006	DBLP DOI BibTeX RDF
35	Richard Edwin Stearns	Deterministic versus nondeterministic time and lower bound problems.	J. ACM	2003	DBLP DOI BibTeX RDF	generic problems, power index, Computational complexity, NP-completeness, time complexity, SAT, nondeterminism, generic algorithms
35	Alexandru Mateescu, Arto Salomaa	Nondeterministic Trajectories.	Formal and Natural Computing	2002	DBLP DOI BibTeX RDF
35	B. F. Melnikov	Heuristics in Programming of Nondeterministic Games.	Program. Comput. Softw.	2001	DBLP DOI BibTeX RDF
35	Beate Bollig	Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication.	MFCS	2000	DBLP DOI BibTeX RDF
35	Jacques Chassin de Kergommeaux, Michiel Ronsse, Koenraad De Bosschere	MPL*: Efficient Record/Play of Nondeterministic Features of Message Passing Libraries.	PVM/MPI	1999	DBLP DOI BibTeX RDF
35	Hiroshi Sakai	Some Issues on Nondeterministic Knowledge Bases with Incomplete and Selective Information.	Rough Sets and Current Trends in Computing	1998	DBLP DOI BibTeX RDF
35	Jirí Wiedermann	Speeding-up Single-Tape Nondeterministic Computations by Single Alternation, with Separation Results.	ICALP	1996	DBLP DOI BibTeX RDF
35	Hong Liu 0004, Raymond E. Miller	Generalized fair reachability analysis for cyclic protocols with nondeterministic and internal transitions.	ICNP	1995	DBLP DOI BibTeX RDF
35	Dietrich Kuske	Nondeterministic Automata with Concurrency Relations and Domains.	CAAP	1994	DBLP DOI BibTeX RDF
35	Viliam Geffert	Nondeterministic Computations in Sublogarithmic Space and Space Constructibility. (journal version: SIAM J. Comput. 20(3): 484-498(1991))	ICALP	1990	DBLP DOI BibTeX RDF
35	Manfred Broy	On the Herbrand Kleene Universe for Nondeterministic Computations.	MFCS	1984	DBLP DOI BibTeX RDF
35	Peter H. Starke	On the Representability of Relations by Deterministic and Nondeterministic Multi-Tape Automata.	MFCS	1975	DBLP DOI BibTeX RDF
35	Chung Keung Poon	Space Bounds for Graph Connectivity Problems on Node-named JAGs and Node-ordered JAGs	FOCS	1993	DBLP DOI BibTeX RDF	nondeterministic NO-JAG, graph connectivity problems, node-named JAGs, node-ordered JAGs, nondeterministic Turing machine, space bounds
32	Frank Ciesinski, Marcus Größer	On Probabilistic Computation Tree Logic.	Validation of Stochastic Systems	2004	DBLP DOI BibTeX RDF	PCTL, PCTL*, probabilistic deterministic systems, probabilistic nondeterministic systems, quantitative model checking, scheduler, fairness, Markov decision processes, discrete time Markov chains
32	Wendy MacCaull, Ewa Orlowska	A Calculus of Typed Relations.	RelMiCS	2003	DBLP DOI BibTeX RDF	Relational proof system, typed relations, nondeterministic databases, information relations, relational database
32	Lucian Ilie, Sheng Yu 0001	Constructing NFA s by Optimal Use of Positions in Regular Expressions.	CPM	2002	DBLP DOI BibTeX RDF	right-invariant equivalence, $varepsilon$-elimination, algorithms, regular expressions, positions, partial derivatives, quotients, regular expression matching, nondeterministic finite automata
32	Lucian Ilie, Sheng Yu 0001	Algorithms for Computing Small NFAs.	MFCS	2002	DBLP DOI BibTeX RDF	follow relations, invariant equivalences, algorithms, regular expressions, positions, partial derivatives, quotients, nondeterministic finite automata
32	Tetsuro Katayama, Zengo Furukawa, Kazuo Ushijima	A Method for Structural Testing of Ada Concurrent Programs Using the Event Interactions Graph.	APSEC	1996	DBLP DOI BibTeX RDF	Ada programming language, Event InterActions Graph(EIAG), nondeterministic execution, software testing, concurrent programs, test-cases, structural testing, testing criteria
31	Shaobo Liu, Meikang Qiu, Wenzhong Gao, Xiao-jun Tang, Bin Guo	Hybrid of Job Sequencing and DVFS for Peak Temperature Reduction with Nondeterministic Applications.	CIT	2010	DBLP DOI BibTeX RDF	peak temperature, nondeterministic, embedded systems, Thermal management
31	Kumar V. Vadaparty, Shamim A. Naqvi	Using Constraints for Efficient Query Processing in Nondeterministic Databases.	IEEE Trans. Knowl. Data Eng.	1995	DBLP DOI BibTeX RDF	Nondeterministic data, efficiency of query processing, constraints
31	James R. Russell	Full Abstraction for Nondeterministic Dataflow Networks	FOCS	1989	DBLP DOI BibTeX RDF	input-output relation, nondeterministic dataflow networks, bounded choice, semantic models, full abstraction
29	Christian Dax, Felix Klaedtke	Alternation Elimination by Complementation (Extended Abstract).	LPAR	2008	DBLP DOI BibTeX RDF
29	Galina Jirásková	On the State Complexity of Complements, Stars, and Reversals of Regular Languages.	Developments in Language Theory	2008	DBLP DOI BibTeX RDF
29	Orna Kupferman, Moshe Y. Vardi	Safraless Decision Procedures.	FOCS	2005	DBLP DOI BibTeX RDF
29	Lynette van Zijl	Magic Numbers for Symmetric Difference NFAs.	CIAA	2004	DBLP DOI BibTeX RDF
29	Atsuyuki Inoue, Akira Ito, Katsushi Inoue, Tokio Okazaki	Some Properties of One-Pebble Turing Machines with Sublogarithmic Space.	ISAAC	2003	DBLP DOI BibTeX RDF
29	Philipp Woelfel	A Lower Bound Technique for Restricted Branching Programs and Applications.	STACS	2002	DBLP DOI BibTeX RDF
29	Alessandro Aldini	Probabilistic Information Flow in a Process Algebra.	CONCUR	2001	DBLP DOI BibTeX RDF
29	Orna Kupferman, Nir Piterman, Moshe Y. Vardi	Extended Temporal Logic Revisited.	CONCUR	2001	DBLP DOI BibTeX RDF
29	Rahul Santhanam	On Separators, Segregators and Time versus Space.	CCC	2001	DBLP DOI BibTeX RDF
29	Peter Bro Miltersen, N. V. Vinodchandran	Derandomizing Arthur-Merlin Games Using Hitting Sets.	FOCS	1999	DBLP DOI BibTeX RDF	derandomization, hitting sets, Arthur-Merlin games
29	Hing Leung	On Finite Automata with Limited Nondeterminism.	Acta Informatica	1998	DBLP DOI BibTeX RDF
29	Carlo Mereghetti, Giovanni Pighizzini	Optimal Simulations Between Unary Automata.	STACS	1998	DBLP DOI BibTeX RDF
29	Vikraman Arvind, Johannes Köbler, Martin Mundhenk	On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets.	FSTTCS	1992	DBLP DOI BibTeX RDF
29	Lane A. Hemachandra, Albrecht Hoene	Collapsing Degrees via Strong Computation (Extended Abstract).	ICALP	1991	DBLP DOI BibTeX RDF
29	Maria Zamfir	Initial Algebra Semantics and Concurrency.	MFPS	1987	DBLP DOI BibTeX RDF
29	Oscar H. Ibarra, Sam M. Kim, Louis E. Rosier	Space and Time Efficient Simulations and Characterizations of Some Restricted Classes of PDAs.	ICALP	1984	DBLP DOI BibTeX RDF
28	Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse	Nondeterministic Graph Searching: From Pathwidth to Treewidth.	Algorithmica	2009	DBLP DOI BibTeX RDF	Treewidth, Graph searching, Pathwidth
28	Benjamin Aminof, Orna Kupferman, Omer Lev	On the Relative Succinctness of Nondeterministic Büchi and co-Büchi Word Automata.	LPAR	2008	DBLP DOI BibTeX RDF
28	Oana Agrigoroaiei, Gabriel Ciobanu	Non-interleaving Semantics with Causality for Nondeterministic Dataflow.	ICTAC	2008	DBLP DOI BibTeX RDF
28	Markus Holzer 0001, Martin Kutrib	Nondeterministic Finite Automata-Recent Results on the Descriptional and Computational Complexity.	CIAA	2008	DBLP DOI BibTeX RDF
28	Hermann Gruber, Markus Holzer 0001	Inapproximability of Nondeterministic State and Transition Complexity Assuming P=!NP.	Developments in Language Theory	2007	DBLP DOI BibTeX RDF
28	Junfeng Wu, Huaikou Miao	A Rewriting Based Model for Nondeterministic Composite Web Service System.	ICEBE	2007	DBLP DOI BibTeX RDF
28	Gordon Fraser 0001, Franz Wotawa	Nondeterministic Testing with Linear Model-Checker Counterexamples.	QSIC	2007	DBLP DOI BibTeX RDF
28	Pascal Van Hentenryck, Laurent Michel	Nondeterministic Control for Hybrid Search.	Constraints An Int. J.	2006	DBLP DOI BibTeX RDF	hybrid search, search procedure, local search, checkpoint, continuation, closure, non determinism, solution, constraint language
28	Hermann Gruber, Markus Holzer 0001	Finding Lower Bounds for Nondeterministic State Complexity Is Hard.	Developments in Language Theory	2006	DBLP DOI BibTeX RDF
28	Alexander Brodsky 0001, Hadon Nash	CoJava: Optimization Modeling by Nondeterministic Simulation.	CP	2006	DBLP DOI BibTeX RDF
28	Laurent Michel, Andrew See, Pascal Van Hentenryck	High-Level Nondeterministic Abstractions in.	CP	2006	DBLP DOI BibTeX RDF
28	Felipe W. Trevizan, Fábio Gagliardi Cozman, Leliane Nunes de Barros	Unifying Nondeterministic and Probabilistic Planning Through Imprecise Markov Decision Processes.	IBERAMIA-SBIA	2006	DBLP DOI BibTeX RDF
28	Alessandro Giua, Daniele Corona, Carla Seatzu	State Estimation of lambda-free Labeled Petri Nets with Contact-Free Nondeterministic Transitions*.	Discret. Event Dyn. Syst.	2005	DBLP DOI BibTeX RDF	labeled nets, marking estimation, Petri nets, observer
28	Pascal Van Hentenryck, Laurent Michel	Nondeterministic Control for Hybrid Search.	CPAIOR	2005	DBLP DOI BibTeX RDF
28	Christos A. Kapoutsis	Removing Bidirectionality from Nondeterministic Finite Automata.	MFCS	2005	DBLP DOI BibTeX RDF
28	Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse	Nondeterministic Graph Searching: From Pathwidth to Treewidth.	MFCS	2005	DBLP DOI BibTeX RDF	treewidth, graph searching, pathwidth
28	Jörg Flum, Martin Grohe, Mark Weyer	Bounded Fixed-Parameter Tractability and log2n Nondeterministic Bits.	ICALP	2004	DBLP DOI BibTeX RDF
28	Manfred Broy	A Functional Calculus for Specification and Verification of Nondeterministic Interactive Systems.	Verification: Theory and Practice	2003	DBLP DOI BibTeX RDF
28	Sankar Gurumurthy, Orna Kupferman, Fabio Somenzi, Moshe Y. Vardi	On Complementing Nondeterministic Büchi Automata.	CHARME	2003	DBLP DOI BibTeX RDF
28	Peter A. Dinda, Dong Lu	Nondeterministic Queries in a Relational Grid Information Service.	SC	2003	DBLP DOI BibTeX RDF
28	Bernd Finkbeiner	Language Containment Checking with Nondeterministic BDDs.	TACAS	2001	DBLP DOI BibTeX RDF
28	Anne Brüggemann-Klein, Derick Wood	Regularly Extended Two-Way Nondeterministic Tree Automata.	CIAA	2000	DBLP DOI BibTeX RDF
28	Jirí Wiedermann	Speeding-Up Nondeterministic Single-Tape Off-Line Computations by One Alternation.	MFCS	1998	DBLP DOI BibTeX RDF