Stem nondeterminist$ (all stems)

111 papers:

CIAA-2015-Giaquinta #automaton #nondeterminism

Run-Length Encoded Nondeterministic KMP and Suffix Automata (EG), pp. 102–113.

CIAA-2015-GruberHJ #automaton #finite #nondeterminism

More on Deterministic and Nondeterministic Finite Cover Automata — Extended Abstract (HG, MH, SJ), pp. 114–126.

CIAA-2015-KushikY #automaton #finite #nondeterminism #sequence #state machine

Describing Homing and Distinguishing Sequences for Nondeterministic Finite State Machines via Synchronizing Automata (NK, NY), pp. 188–198.

ASE-2014-LuckowPDFV #approximate #execution #nondeterminism #probability #source code #symbolic computation

Exact and approximate probabilistic symbolic execution for nondeterministic programs (KSL, CSP, MBD, AF, WV), pp. 575–586.

AFL-2014-Campeanu #automaton #finite #nondeterminism

Simplifying Nondeterministic Finite Cover Automata (CC), pp. 162–173.

FSE-2014-Llerena #nondeterminism #verification

Dealing with uncertainty in verification of nondeterministic systems (YRSL), pp. 787–790.

CIAA-2013-KushikY #finite #nondeterminism #on the #sequence #state machine

On the Length of Homing Sequences for Nondeterministic Finite State Machines (NK, NY), pp. 220–231.

QAPL-2013-BernardoNL #behaviour #nondeterminism #probability #process

The Spectrum of Strong Behavioral Equivalences for Nondeterministic and Probabilistic Processes (MB, RDN, ML), pp. 81–96.

ICTSS-2013-KushikEY #adaptation #finite #nondeterminism #state machine

Adaptive Homing and Distinguishing Experiments for Nondeterministic Finite State Machines (NK, KEF, NY), pp. 33–48.

FoSSaCS-2012-BernardoNL #nondeterminism #probability #process #testing

Revisiting Trace and Testing Equivalences for Nondeterministic and Probabilistic Processes (MB, RDN, ML), pp. 195–209.

PLDI-2012-CarbinKMR #approximate #nondeterminism #proving #source code

Proving acceptability properties of relaxed nondeterministic approximate programs (MC, DK, SM, MCR), pp. 169–180.

CIAA-2012-ReidenbachS #automaton #bound #nondeterminism

Automata with Modulo Counters and Nondeterministic Counter Bounds (DR, MLS), pp. 361–368.

DLT-2012-KapoutsisL #automaton #finite #nondeterminism #theorem

Analogs of Fagin’s Theorem for Small Nondeterministic Finite Automata (CAK, NL), pp. 202–213.

DLT-2012-LavadoPS #automaton #context-free grammar #nondeterminism

Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata (GJL, GP, SS), pp. 284–295.

PPoPP-2012-BurnimENS #correctness #named #nondeterminism #parallel #specification

NDetermin: inferring nondeterministic sequential specifications for parallelism correctness (JB, TE, GCN, KS), pp. 329–330.

ICST-2012-PetrenkoSY #finite #generative #nondeterminism #sequence #state machine

Generating Checking Sequences for Nondeterministic Finite State Machines (AP, AdSS, NY), pp. 310–319.

PLDI-2011-BurnimENS #correctness #named #nondeterminism #parallel #runtime #specification

NDSeq: runtime checking for nondeterministic sequential specifications of parallel correctness (JB, TE, GCN, KS), pp. 401–414.

CIAA-2011-CastiglioneRS #algorithm #automaton #nondeterminism

Nondeterministic Moore Automata and Brzozowski’s Algorithm (GC, AR, MS), pp. 88–99.

CIAA-2011-HolzerKM #complexity #nondeterminism

Nondeterministic State Complexity of Star-Free Languages (MH, MK, KM), pp. 178–189.

CIAA-2011-KushikEY #adaptation #finite #nondeterminism #state machine

Preset and Adaptive Homing Experiments for Nondeterministic Finite State Machines (NK, KEF, NY), pp. 215–224.

ICALP-v2-2011-AlurD #nondeterminism #streaming #string #transducer

Nondeterministic Streaming String Transducers (RA, JVD), pp. 1–20.

CSL-2011-Schwencke #nondeterminism #recursion

A Category Theoretic View of Nondeterministic Recursive Program Schemes (DS), pp. 496–511.

ICTSS-2011-PetrenkoY #adaptation #implementation #nondeterminism #testing

Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs (AP, NY), pp. 162–178.

ICALP-v1-2010-BojanczykP #automaton #evaluation #nondeterminism #performance #using

Efficient Evaluation of Nondeterministic Automata Using Factorization Forests (MB, PP), pp. 515–526.

IFM-2010-Dimovski #composition #equivalence #nondeterminism #source code #termination

A Compositional Method for Deciding Equivalence and Termination of Nondeterministic Programs (AD), pp. 121–135.

ICST-2010-PorresR #contract #nondeterminism #protocol #uml

From Nondeterministic UML Protocol Statemachines to Class Contracts (IP, IR), pp. 107–116.

CASE-2009-XuK #nondeterminism

Discrete event control under nondeterministic partial observation (SX, RK), pp. 127–132.

SIGMOD-2009-BexGMN #nondeterminism #regular expression #xml

Simplifying XML schema: effortless handling of nondeterministic regular expressions (GJB, WG, WM, FN), pp. 731–744.

CIAA-J-2008-HolzerK09 #automaton #complexity #finite #nondeterminism

Nondeterministic Finite Automata — Recent Results on the Descriptional and Computational Complexity (MH, MK), pp. 563–580.

LATA-2009-BeyersdorffKM #complexity #nondeterminism #proving

Nondeterministic Instance Complexity and Proof Systems with Advice (OB, JK, SM), pp. 164–175.

QAPL-2009-Bernardo #logic #markov #nondeterminism #probability #process #testing

Uniform Logical Characterizations of Testing Equivalences for Nondeterministic, Probabilistic and Markovian Processes (MB), pp. 3–23.

TACAS-2008-AndresR #nondeterminism #probability

Conditional Probabilities over Probabilistic and Nondeterministic Systems (MEA, PvR), pp. 157–172.

DLT-J-2007-JirasekJS08 #automaton #finite #nondeterminism

Deterministic blow-UPS of Minimal Nondeterministic Finite Automata over a Fixed Alphabet (JJ, GJ, AS), pp. 617–631.

CIAA-2008-BouajjaniHHTV #automaton #finite #nondeterminism #testing

Antichain-Based Universality and Inclusion Testing over Nondeterministic Finite Tree Automata (AB, PH, LH, TT, TV), pp. 57–67.

CIAA-2008-GarciaPAR #automaton #finite #learning #nondeterminism #regular expression #using

Learning Regular Languages Using Nondeterministic Finite Automata (PG, MVdP, GIA, JR), pp. 92–101.

CIAA-2008-HolzerK #complexity #finite #nondeterminism

Nondeterministic Finite Automata-Recent Results on the Descriptional and Computational Complexity (MH, MK), pp. 1–16.

ICALP-A-2008-Yin #complexity #nondeterminism #proving

Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity (YY), pp. 72–83.

LICS-2008-Murawski #game studies #nondeterminism #reachability #semantics #source code

Reachability Games and Game Semantics: Comparing Nondeterministic Programs (ASM), pp. 353–363.

ASE-2007-VainRKE #nondeterminism #synthesis

Synthesis of test purpose directed reactive planning tester for nondeterministic systems (JV, KR, AK, JPE), pp. 363–372.

DLT-2007-GruberH #complexity #exclamation #nondeterminism

Inapproximability of Nondeterministic State and Transition Complexity Assuming P=!NP (HG, MH), pp. 205–216.

DLT-2007-JirasekJS #automaton #finite #nondeterminism

Deterministic Blow-Ups of Minimal Nondeterministic Finite Automata over a Fixed Alphabet (JJ, GJ, AS), pp. 254–265.

DLT-2007-Salomaa #automaton #complexity #finite #nondeterminism

Descriptional Complexity of Nondeterministic Finite Automata (KS), pp. 31–35.

ICALP-2007-BeameDPW #communication #complexity #multi #nondeterminism

Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity (PB, MD, TP, PW), pp. 134–145.

LATA-2007-ChoudharySB #nondeterminism

Universality for Nondeterministic Logspace (VC, AKS, SB), pp. 103–114.

LATA-2007-Kresz #automaton #nondeterminism

Nondeterministic soliton automata with a single external vertex (MK), pp. 319–330.

TestCom-FATES-2007-ShabaldinaEY #finite #nondeterminism #state machine #testing

Testing Nondeterministic Finite State Machines with Respect to the Separability Relation (NS, KEF, NY), pp. 305–318.

DLT-2006-GruberH #bound #complexity #nondeterminism

Finding Lower Bounds for Nondeterministic State Complexity Is Hard (HG, MH), pp. 363–374.

HPDC-2006-ZhangJHMS #grid #nondeterminism

Replicating Nondeterministic Services on Grid Environments (XZ, FJ, MAH, KM, RDS), pp. 105–116.

LICS-2006-Piterman #automaton #nondeterminism

From Nondeterministic Buchi and Streett Automata to Deterministic Parity Automata (NP), pp. 255–264.

TACAS-2005-KupfermanV #automaton #infinity #nondeterminism #word

Complementation Constructions for Nondeterministic Automata on Infinite Words (OK, MYV), pp. 206–221.

FATES-2005-PetrenkoY #automaton #consistency #nondeterminism #testing

Conformance Tests as Checking Experiments for Partial Nondeterministic FSM (AP, NY), pp. 118–133.

ICALP-2004-FlumGW #bound #nondeterminism #parametricity

Bounded Fixed-Parameter Tractability and log2n Nondeterministic Bits (JF, MG, MW), pp. 555–567.

FATES-2003-KhoumsiJM #generative #nondeterminism #realtime #testing

Test Cases Generation for Nondeterministic Real-Time Systems (AK, TJ, HM), pp. 131–146.

TLCA-2003-Maurel #logic #nondeterminism

Nondeterministic Light Logics and NP-Time (FM), pp. 241–255.

CIAA-J-2000-Bruggemann-KleinW02 #automaton #nondeterminism

The Regularity of Two-Way Nondeterministic Tree Automata Languages (ABK, DW), pp. 67–81.

CIAA-J-2000-Champarnaud02 #automaton #evaluation #nondeterminism #regular expression

Evaluation of Three Implicit Structures to Implement Nondeterministic Automata From Regular Expressions (JMC), pp. 99–113.

CIAA-2002-HolzerK #automaton #complexity #finite #nondeterminism

State Complexity of Basic Operations on Nondeterministic Finite Automata (MH, MK), pp. 148–157.

DLT-2002-Adorna #nondeterminism #on the

On the Separation between k-Party and (k-1)-Party Nondeterministic Message Complexities (HNA), pp. 152–161.

DLT-2002-HolzerK #complexity #nondeterminism

Unary Language Operations and Their Nondeterministic State Complexity (MH, MK), pp. 162–172.

ICALP-2002-HearnD #constraints #logic #nondeterminism #reduction

The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications (RAH, EDD), pp. 401–413.

TACAS-2001-Finkbeiner #nondeterminism

Language Containment Checking with Nondeterministic BDDs (BF), pp. 24–38.

CIAA-2000-Bruggemann-KleinW #automaton #nondeterminism

Regularly Extended Two-Way Nondeterministic Tree Automata (ABK, DW), pp. 57–66.

WLC-2000-BuchholzKK #array #communication #nondeterminism

Iterative Arrays With Limited Nondeterministic Communication Cell (TB, AK, MK), pp. 73–87.

FoSSaCS-1999-DantsinV #algorithm #nondeterminism #polynomial #set #unification

A Nondeterministic Polynomial-Time Unification Algorithm for Bags, Sets and Trees (ED, AV), pp. 180–196.

DLT-1999-CaludeC #automaton #behaviour #bisimulation #nondeterminism

Bisimulations and behaviour of nondeterministic automata (CC, EC), pp. 60–70.

IWTCS-1999-YevtushenkoCA #embedded #finite #nondeterminism #state machine #testing

Test Suite Minimization for Embedded Nondeterministic Finite State Machines (NY, ARC, RA), pp. 237–250.

WIA-1998-HolubM #approximate #automaton #finite #implementation #nondeterminism #pattern matching

Implementation of Nondeterministic Finite Automata for Approximate Pattern Matching (JH, BM), pp. 92–99.

CSL-1998-GiannottiMNP #database #effectiveness #logic #nondeterminism #on the #semantics

On the Effective Semantics of Nondeterministic, Nonmonotonic, Temporal Logic Databases (FG, GM, MN, DP), pp. 58–72.

IWTCS-1998-Boroday #finite #nondeterminism #state machine #testing

Distinguishing Tests for Nondeterministic Finite State Machines (SB), pp. 101–108.

DLT-1997-Moshkov #complexity #nondeterminism #recognition #regular expression #word

Complexity of Deterministic and Nondeterministic Decision Trees for Regular Language Word Recognition (MM), pp. 343–349.

CSL-1997-Olive #linear #logic #nondeterminism

A Conjunctive Logical Characterization of Nondeterministic Linear Time (FO), pp. 360–372.

STOC-1996-HromkovicS #communication #nondeterminism

Nondeterministic Communication with a Limited Number of Advice Bits (JH, GS), pp. 551–560.

ICALP-1996-Wiedermann #nondeterminism

Speeding-up Single-Tape Nondeterministic Computations by Single Alternation, with Separation Results (JW), pp. 381–392.

WIA-1996-GarzonE #automaton #concurrent #implementation #nondeterminism

Dynamical Implementation of Nondeterministic Automata and Concurrent Systems (MHG, EE), pp. 35–49.

RTA-1996-Vittek #compilation #nondeterminism #term rewriting

A Compiler for Nondeterministic Term Rewriting Systems (MV), pp. 154–167.

STOC-1995-AlurCY #nondeterminism #probability #testing

Distinguishing tests for nondeterministic and probabilistic machines (RA, CC, MY), pp. 363–372.

EDAC-1994-Damiani #finite #nondeterminism #state machine

Nondeterministic finite-state machines and sequential don’t cares (MD), pp. 192–198.

STOC-1994-CondonHPW #automaton #finite #nondeterminism #on the #power of #probability

On the power of finite automata with both nondeterministic and probabilistic states (preliminary version) (AC, LH, SP, AW), pp. 676–685.

DLT-1993-HromkovicRS #nondeterminism

Deterministic Versus Nondeterministic Space in Terms of Synchronized Alternating Machines (JH, BR, AS), pp. 314–325.

DLT-1993-KrithivasanM #array #modelling #nondeterminism #probability

Nondeterministic, Probabilistic and Alternating Computations on Cellular Array Models (KK, MM), pp. 342–354.

ICALP-1993-Yamamoto #bound #nondeterminism #trade-off #turing machine

Reversal-Space Trade-offs For Simultaneous Resource-Bounded Nondeterministic Turing Machines (HY), pp. 203–214.

IWPTS-1993-PetrenkoYLD #consistency #nondeterminism #protocol #state machine #testing

Nondeterministic State Machines in Protocol Conformance Testing (AP, NY, AL, AD), pp. 363–378.

STOC-1992-BeameL #communication #complexity #nondeterminism #random

Randomized versus Nondeterministic Communication Complexity (PB, JL), pp. 188–199.

IWPTS-1992-TripathyN #adaptation #finite #generative #modelling #nondeterminism #testing

Generation of Adaptive Test Cases from Nondeterministic Finite State Models (PT, KN), pp. 309–320.

LICS-1992-GraedelM #logic #nondeterminism #transitive

Deterministic vs. Nondeterministic Transitive Closure Logic (EG, GLM), pp. 58–63.

ICALP-1990-Geffert #nondeterminism

Nondeterministic Computations in Sublogarithmic Space and Space Constructibility (VG), pp. 111–124.

STOC-1988-GurevichS #linear #nondeterminism #sublinear

Nondeterministic Linear-Time Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space (YG, SS), pp. 281–289.

ICALP-1988-Watanabe #complexity #nondeterminism #on the

On ≤ᴾ₁₋tt-Sparseness and Nondeterministic Complexity Classes (Extended Abstract) (OW0), pp. 697–709.

ALP-1988-Hussmann #algebra #nondeterminism #specification #term rewriting

Nondeterministic Algebraic Specifications and Nonconfluent Term Rewriting (HH), pp. 31–40.

CSL-1988-Dahlhaus #nondeterminism #polynomial

Completeness with Respect to Interpretations in Deterministic and Nondeterministic Polynomial Time (ED), pp. 52–62.

CSL-1988-Gradel #complexity #modelling #nondeterminism

Size of Models versus Length of Computations: On Inseparability by Nondeterministic Time Complexity Classes (EG), pp. 118–137.

ICALP-1987-ShyamasundarNP #network #nondeterminism #semantics

Semantics for Nondeterministic Asynchronous Broadcast Networks (RKS, KTN, TP), pp. 72–83.

CSL-1987-Spreen #nondeterminism #on the #polynomial

On Functions Computable in Nondeterministic Polynomial Time: Some Characterizations (DS), pp. 289–303.

ESOP-1986-Kaplan #algebra #nondeterminism #proving

Rewriting with a Nondeterministic Choice Operator: From Algebra to Proofs (SK), pp. 351–374.

STOC-1986-GalilKS #graph #nondeterminism #on the #simulation #turing machine

On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines (ZG, RK, ES), pp. 39–49.

ICALP-1986-Lange #nondeterminism #reduction

Decompositions of Nondeterministic Reductions (Extended Abstract) (KJL), pp. 206–214.

LICS-1986-Plaisted #nondeterminism #recursion #semantics #source code #using

The Denotional Semantics of Nondeterministic Recursive Programs using Coherent Relations (DAP), pp. 163–174.

ICALP-1985-Hortala-GonzalezR #hoare #logic #nondeterminism #source code #standard #theorem

Hoare’s Logic for Nondeterministic Regular Programs: A Nonstandard Completeness Theorem (MTHG, MRA), pp. 270–280.

STOC-1984-Maass #bound #nondeterminism #polynomial #turing machine

Quadratic Lower Bounds for Deterministic and Nondeterministic One-Tape Turing Machines (Extended Abstract) (WM), pp. 401–408.

STOC-1982-DurisG #nondeterminism

Two Tapes are Better than One for Nondeterministic Machines (PD, ZG), pp. 1–7.

STOC-1982-ManberT #nondeterminism #probability

Probabilistic, Nondeterministic, and Alternating Decision Trees (UM, MT), pp. 234–244.

LFP-1982-Clinger #call-by #lazy evaluation #nondeterminism

Nondeterministic Call by Need is Neither Lazy Nor by Name (WDC), pp. 226–234.

LFP-1982-CohenM #algebra #nondeterminism #source code #towards

Toward an Algebra of Nondeterministic Programs (ATC, TJM), pp. 235–242.

DAC-1980-LeinwandL #algebra #analysis #behaviour #nondeterminism

Algebraic analysis of nondeterministic behavior (SML, TL), pp. 483–493.

STOC-1980-Mirkowska #algorithm #axiom #bound #nondeterminism

Complete Axiomatization of Algorithmic Properties of Program Schemes with Bounded Nondeterministic Interpretations (GM), pp. 14–21.

ICALP-1978-Gallier #correctness #nondeterminism #recursion #semantics #source code

Semantics and Correctness of Nondeterministic Flowchart Programs with Recursive Procedures (JHG), pp. 251–267.

ICALP-1978-Savitch #complexity #nondeterminism #parallel

Parallel and Nondeterministic Time Complexity Classes (Preliminary Report) (WJS), pp. 411–424.

STOC-1977-KintalaF #nondeterminism #strict

Computations with a Restricted Number of Nondeterministic Steps (Extended Abstract) (CMRK, PCF), pp. 178–185.

ICALP-1976-Bakker #nondeterminism #recursion #semantics #source code #termination

Semantics and Termination of Nondeterministic Recursive Programs (JWdB), pp. 435–477.

STOC-1974-Seiferas #array #multi #nondeterminism

Observations on Nondeterministic Multidimensional Iterative Arrays (JIS), pp. 276–289.

STOC-1972-Cook #complexity #nondeterminism

A Hierarchy for Nondeterministic Time Complexity (SAC), pp. 187–192.