Search results for "decidable"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
68	Qing Zhou, Weihao Hu	Decidability in Analysis.	Computing	2005	DBLP DOI BibTeX RDF	almost decidable, Decidable
53	Dietrich Kuske, Markus Lohrey	Decidable Theories of Cayley-Graphs.	STACS	2003	DBLP DOI BibTeX RDF
49	Amir Pnueli, Roni Rosner	Distributed Reactive Systems Are Hard to Synthesize	FOCS	1990	DBLP DOI BibTeX RDF	elementarily decidable, distributed reactive system, propositional specification, nonelementarily decidable, distributed architecture, undecidable, finite-state
47	Mikolaj Bojanczyk, Piotr Hoffman	Reachability in Unions of Commutative Rewriting Systems Is Decidable.	STACS	2007	DBLP DOI BibTeX RDF	Topic classification Logic in computer science, rewriting
40	Friedrich Otto, Masashi Katsura, Yuji Kobayashi	Cross-Sections for Finitely Presented Monoids with Decidable Word Problems.	RTA	1997	DBLP DOI BibTeX RDF
40	Christian Prehofer	Decidable Higher-Order Unification Problems.	CADE	1994	DBLP DOI BibTeX RDF
39	Limin Jia 0001, Jianzhou Zhao, Vilhelm Sjöberg, Stephanie Weirich	Dependent types and program equivalence.	POPL	2010	DBLP DOI BibTeX RDF	dependent types, program equivalence
39	Thomas A. Henzinger, Jean-François Raskin, Pierre-Yves Schobbens	The Regular Real-Time Languages.	ICALP	1998	DBLP DOI BibTeX RDF
39	Neil D. Jones, Steven S. Muchnick	Even Simple Programs are Hard to Analyze.	POPL	1975	DBLP DOI BibTeX RDF
34	Tony Tan	On Pebble Automata for Data Languages with Decidable Emptiness Problem.	MFCS	2009	DBLP DOI BibTeX RDF
34	Barbara F. Csima, Bakhadyr Khoussainov	When Is Reachability Intrinsically Decidable?.	Developments in Language Theory	2008	DBLP DOI BibTeX RDF
34	Aharon Abadi, Alexander Moshe Rabinovich, Mooly Sagiv	Decidable Fragments of Many-Sorted Logic.	LPAR	2007	DBLP DOI BibTeX RDF
34	Thomas Ågotnes, Natasha Alechina	Full and relative awareness: a decidable logic for reasoning about knowledge of unawareness.	TARK	2007	DBLP DOI BibTeX RDF
34	Patricia Bouyer, Thomas Brihaye, Fabrice Chevalier	Weighted O-Minimal Hybrid Systems Are More Decidable Than Weighted Timed Automata!	LFCS	2007	DBLP DOI BibTeX RDF
34	Joël Ouaknine, James Worrell 0001	Safety Metric Temporal Logic Is Fully Decidable.	TACAS	2006	DBLP DOI BibTeX RDF
34	Nicolas Peltier	Representing and Building Models for Decidable Subclasses of Equational Clausal Logic.	J. Autom. Reason.	2004	DBLP DOI BibTeX RDF	resolution, decision procedure, model building, model representation
34	Pavel Krcál, Wang Yi 0001	Decidable and Undecidable Problems in Schedulability Analysis Using Timed Automata.	TACAS	2004	DBLP DOI BibTeX RDF
34	Diego Calvanese, Giuseppe De Giacomo, Moshe Y. Vardi	Decidable Containment of Recursive Queries.	ICDT	2003	DBLP BibTeX RDF
34	Krysia Broda	A Decidable CLDS for Some Propositional Resource Logics.	Computational Logic: Logic Programming and Beyond	2002	DBLP DOI BibTeX RDF
34	Regimantas Pliuskevicius	On an omega-Decidable Deductive Procedure for Non-Horn Sequents of a Restricted FTL.	Computational Logic	2000	DBLP DOI BibTeX RDF
34	Manfred Schmidt-Schauß, Klaus U. Schulz	Solvability of Context Equations with Two Context Variables is Decidable.	CADE	1999	DBLP DOI BibTeX RDF
34	Jordi Levy	Decidable and Undecidable Second-Order Unification Problems.	RTA	1998	DBLP DOI BibTeX RDF
34	Florent Jacquemard	Decidable Approximations of Term Rewriting Systems.	RTA	1996	DBLP DOI BibTeX RDF
34	Helmut Seidl	Equivalence of Finite-Valued Bottom-up Finite State Tree Transducers Is Decidable.	CAAP	1990	DBLP DOI BibTeX RDF
32	Laurent Bienvenu, Wolfgang Merkle	Reconciling Data Compression and Kolmogorov Complexity.	ICALP	2007	DBLP DOI BibTeX RDF
32	Markus Lohrey, Géraud Sénizergues	Theories of HNN-Extensions and Amalgamated Products.	ICALP (2)	2006	DBLP DOI BibTeX RDF
32	Bakhadyr Khoussainov, Sasha Rubin	Decidability of Term Algebras Extending Partial Algebras.	CSL	2005	DBLP DOI BibTeX RDF
31	Ralf H. Reussner	Counter-Constrained Finite State Machines: A New Model for Component Protocols with Resource-Dependencies.	SOFSEM	2002	DBLP DOI BibTeX RDF	software component protocols, finite state machine extension, decidable inclusion check, interoperability, substitutability
31	Mihhail Matskin, Enn Tyugu	Strategies of Structural Synthesis of Programs.	ASE	1997	DBLP DOI BibTeX RDF	structural program synthesis strategies, deductive program synthesis method, compositional programming, decidable logical calculus, PSPACE complexity, independent subtasks, iteration synthesis, regular data structures, heuristics, programming environments, structured programming, proof search, search efficiency
29	Domenico Cantone, Pietro Maugeri, Eugenio G. Omodeo	Complexity assessments for decidable fragments of Set Theory. III: Testers for crucial, polynomial-maximal decidable Boolean languages.	Theor. Comput. Sci.	2023	DBLP DOI BibTeX RDF
29	Bruno Bernardo	Un Calcul des Constructions implicite avec sommes dépendantes et à inférence de type décidable. (An implicit Calculus of Constructions with dependent sums and decidable type inference).		2015	RDF
29	Fabio Mogavero, Aniello Murano, Giuseppe Perelli, Moshe Y. Vardi	What Makes Atl* Decidable? A Decidable Fragment of Strategy Logic.	CONCUR	2012	DBLP DOI BibTeX RDF
29	René Vidal, Shawn Schaffert, Omid Shakernia, John Lygeros, Shankar Sastry 0001	Decidable and semi-decidable controller synthesis for classes of discrete time hybrid systems.	CDC	2001	DBLP DOI BibTeX RDF
29	Natasha Alechina	On a Decidable Generalized Quantifier Logic Corresponding to a Decidable Fragment of First-Order Logic.	J. Log. Lang. Inf.	1995	DBLP DOI BibTeX RDF
29	Terrence Millar	A Complete, Decidable Theory with Two Decidable Models.	J. Symb. Log.	1979	DBLP DOI BibTeX RDF
28	Kenneth L. Knowles, Cormac Flanagan	Compositional reasoning and decidable checking for dependent contract types.	PLPV	2009	DBLP DOI BibTeX RDF	refinement types, abstraction, dependent types, compositional reasoning
28	Jacques Duparc, Alessandro Facchini, Filip Murlak	Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata.	CSL	2009	DBLP DOI BibTeX RDF
28	Albert Atserias, Mark Weyer	Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems.	CSL	2009	DBLP DOI BibTeX RDF
28	Pascal Fontaine	Combinations of Theories for Decidable Fragments of First-Order Logic.	FroCoS	2009	DBLP DOI BibTeX RDF
28	Alberto Casagrande, Pietro Corvaja, Carla Piazza, Bud Mishra	Decidable Compositions of O-Minimal Automata.	ATVA	2008	DBLP DOI BibTeX RDF
28	Peter Habermehl, Radu Iosif, Tomás Vojnar	What Else Is Decidable about Integer Arrays?.	FoSSaCS	2008	DBLP DOI BibTeX RDF
28	Matthew J. Patitz, Scott M. Summers	Self-assembly of Decidable Sets.	UC	2008	DBLP DOI BibTeX RDF
28	Norihiro Kamide	Linear Exponentials as Resource Operators: A Decidable First-order Linear Logic with Bounded Exponentials.	JELIA	2008	DBLP DOI BibTeX RDF
28	Yoshiharu Kojima, Masahiko Sakai	Innermost Reachability and Context Sensitive Reachability Properties Are Decidable for Linear Right-Shallow Term Rewriting Systems.	RTA	2008	DBLP DOI BibTeX RDF
28	Brad Lushman, Gordon V. Cormack	A larger decidable semiunification problem.	PPDP	2007	DBLP DOI BibTeX RDF	acyclic semiunification, semiunification, decidability
28	Francesco Calimeri, Susanna Cozza, Giovambattista Ianni	Decidable Fragments of Logic Programming with Value Invention.	JELIA	2006	DBLP DOI BibTeX RDF
28	Pietro di Lena	Decidable Properties for Regular Cellular Automata.	IFIP TCS	2006	DBLP DOI BibTeX RDF
28	Dietrich Kuske, Markus Lohrey	Decidable First-Order Theories of One-Step Rewriting in Trace Monoids.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
28	Manfred Schmidt-Schauß	Decidable Variants of Higher-Order Unification.	Mechanizing Mathematical Reasoning	2005	DBLP DOI BibTeX RDF
28	Jon A. Solworth, Robert H. Sloan	A Layered Design of Discretionary Access Controls with Decidable Safety Properties.	S&P	2004	DBLP DOI BibTeX RDF
28	Viktor Kuncak, Martin C. Rinard	Structural Subtyping of Non-Recursive Types is Decidable.	LICS	2003	DBLP DOI BibTeX RDF
28	Jesse D. Bingham, Anne Condon, Alan J. Hu	Toward a decidable notion of sequential consistency.	SPAA	2003	DBLP DOI BibTeX RDF	shared memory systems, memory model, sequential consistency
28	Michaël Adélaïde, Olivier F. Roux	A Class of Decidable Parametric Hybrid Systems.	AMAST	2002	DBLP DOI BibTeX RDF
28	Thomas Colcombet	On Families of Graphs Having a Decidable First Order Theory with Reachability.	ICALP	2002	DBLP DOI BibTeX RDF
28	Volker Diekert, Anca Muscholl	Solvability of Equations in Free Partially Commutative Groups Is Decidable.	ICALP	2001	DBLP DOI BibTeX RDF
28	Oscar H. Ibarra, Jianwen Su, Zhe Dang, Tevfik Bultan, Richard A. Kemmerer	Conter Machines: Decidable Properties and Applications to Verification Problems.	MFCS	2000	DBLP DOI BibTeX RDF
28	Paliath Narendran, Michaël Rusinowitch	The Theory of Total Unary RPO Is Decidable.	Computational Logic	2000	DBLP DOI BibTeX RDF	recursive path ordering, ground reducibility, ordered rewriting, tree automata, first-order theory
28	Yoram Hirshfeld, Alexander Moshe Rabinovich	A Framework for Decidable Metrical Logics.	ICALP	1999	DBLP DOI BibTeX RDF
28	Adriana Popovici, Dan Popovici	delta-Uniformly Decidable Sets and Turing Machines.	FCT	1999	DBLP DOI BibTeX RDF
28	Franz Baader, Ralf Molitor, Stephan Tobies	Tractable and Decidable Fragments of Conceptual Graphs.	ICCS	1999	DBLP DOI BibTeX RDF
28	Reinhard Pichler	Extending Decidable Clause Classes via Constraints.	FTP (LNCS Selection)	1998	DBLP DOI BibTeX RDF
28	Sergei G. Vorobyov	The "Hardest" Natural Decidable Theory.	LICS	1997	DBLP DOI BibTeX RDF
28	Erich Grädel, Martin Otto 0001, Eric Rosen	Two-Variable Logic with Counting is Decidable.	LICS	1997	DBLP DOI BibTeX RDF
28	Petr Jancar	Bisimulation Equivalence is Decidable for One-Counter Processes.	ICALP	1997	DBLP DOI BibTeX RDF
28	D. J. B. Bosscher, W. O. David Griffioen	Regularity for a Large Class of Context-Free Processes is Decidable.	ICALP	1996	DBLP DOI BibTeX RDF
28	Christoph Weidenbach	Unification in Pseudo-Linear Sort Theories is Decidable.	CADE	1996	DBLP DOI BibTeX RDF
28	Søren Christensen	Distributed Bisimularity is Decidable for a Class of Infinite State-Space Systems.	CONCUR	1992	DBLP DOI BibTeX RDF
28	Sophie Tison	Fair Termination is Decidable for Ground Systems.	RTA	1989	DBLP DOI BibTeX RDF
28	Paavo Turakainen	The Equivalence of DGSM Replications on Q-Rational Languages is Decidable.	ICALP	1988	DBLP DOI BibTeX RDF
28	Jeffrey F. Naughton, Yehoshua Sagiv	A Decidable Class of Bounded Recursions.	PODS	1987	DBLP DOI BibTeX RDF
28	Karel Culík II, Juhani Karhumäki	The Equivalence of Finite Valued Transducers (on HDTOL Languages) is Decidable.	MFCS	1986	DBLP DOI BibTeX RDF
28	Jacob Gonczaroski	Decidable Properties of Monadic Recursive Schemas with a Depth Parameter.	CAAP	1983	DBLP DOI BibTeX RDF
28	Edward A. Ashcroft, Zohar Manna, Amir Pnueli	Decidable Properties of Monadic Functional Schemas.	J. ACM	1973	DBLP DOI BibTeX RDF
26	Laurent Doyen 0001, Gilles Geeraerts, Jean-François Raskin, Julien Reichert	Realizability of Real-Time Logics.	FORMATS	2009	DBLP DOI BibTeX RDF
26	Salvatore La Torre, P. Madhusudan, Gennaro Parlato	Context-Bounded Analysis of Concurrent Queue Systems.	TACAS	2008	DBLP DOI BibTeX RDF
26	Piotr Hoffman	Unions of Equational Monadic Theories.	RTA	2006	DBLP DOI BibTeX RDF
26	Efrat Jaeger, Nissim Francez, Shuly Wintner	Unification Grammars and Off-Line Parsability.	J. Log. Lang. Inf.	2005	DBLP DOI BibTeX RDF	off-line parsability, parsing termination, unification grammars
26	Yoshihito Toyama	Reduction Strategies for Left-Linear Term Rewriting Systems.	Processes, Terms and Cycles	2005	DBLP DOI BibTeX RDF
26	Venkatesh Mysore, Amir Pnueli	Refining the Undecidability Frontier of Hybrid Automata.	FSTTCS	2005	DBLP DOI BibTeX RDF
26	Boris Motik, Ulrike Sattler, Rudi Studer	Query Answering for OWL-DL with Rules.	ISWC	2004	DBLP DOI BibTeX RDF
26	Olivier Serre	Games with Winning Conditions of High Borel Complexity.	ICALP	2004	DBLP DOI BibTeX RDF	Borel Complexity, Pushdown Automata, Two-player Games
26	Lila Kari, Stavros Konstantinidis, Petr Sosík	Bond-Free Languages: Formalizations, Maximality and Construction Methods.	DNA	2004	DBLP DOI BibTeX RDF
26	Takashi Nagaya, Yoshihito Toyama	Decidability for Left-Linaer Growing Term Rewriting Systems.	RTA	1999	DBLP DOI BibTeX RDF
26	Andrea Sattler-Klein	New Undecidablility Results for Finitely Presented Monoids.	RTA	1997	DBLP DOI BibTeX RDF
26	Isabelle Fagnot	On the Subword Equivalence Problem for Infinite Words.	STACS	1995	DBLP DOI BibTeX RDF
26	Ke Wang	Some Positive Results for Boundedness of Multiple Recursive Rules.	ICDT	1995	DBLP DOI BibTeX RDF
26	Mahesh Girkar, Robert Moll	New Results on the Analysis of Concurrent Systems with an Infinite Number of Processes.	CONCUR	1994	DBLP DOI BibTeX RDF
26	Oscar H. Ibarra, Tao Jiang 0001, Nicholas Q. Trân, Hui Wang 0008	New Decidability Results Concerning Two-way Counter Machines and Applications.	ICALP	1993	DBLP DOI BibTeX RDF
26	Ravindran Kannan, Richard J. Lipton	Polynomial-time algorithm for the orbit problem.	J. ACM	1986	DBLP DOI BibTeX RDF
26	Mohamed G. Gouda, Louis E. Rosier	Communicating Finite State Machines with Priority Channnels.	ICALP	1984	DBLP DOI BibTeX RDF
24	I. D. Zaslavsky	Some Criteria of Decidability for Axiomatic Systems in Three-Valued Logic.	TbiLLC	2005	DBLP DOI BibTeX RDF	three-valued predicate, Luk-theory, Luk-consistent theory, Lukcomplete theory, Luk-decidable theory
24	Ian Pratt-Hartmann	Fragments of Language.	J. Log. Lang. Inf.	2004	DBLP DOI BibTeX RDF	decidable fragments, computational complexity, semantics, logic
24	Susan Landau 0001	Simplification of Nested Radicals	FOCS	1989	DBLP DOI BibTeX RDF	radical simplification, nested radicals, equivalent expression, minimum nesting depth, decidable, minimal polynomial
24	Martín Abadi, Joseph Y. Halpern	Decidability and Expressiveness for First-Order Logics of Probability (Extended Abstract)	FOCS	1989	DBLP DOI BibTeX RDF	unary predicates, validity problem, binary predicate, elementary analysis, function symbols, probability, language, reasoning, first-order logics, decidable, expressiveness, domain, possible worlds
24	Leszek Pacholski, Wieslaw Szwast	The 0-1 Law Fails for the Class of Existential Second Order Gödel Sentences with Equality	FOCS	1989	DBLP DOI BibTeX RDF	prenex first-order sentences, second order Godel sentences, 0-1 law, Bernays-Schonfinkel, Ackermann prefix classes, decidable cases
24	Russell Impagliazzo, Gábor Tardos	Decision Versus Search Problems in Super-Polynomial Time	FOCS	1989	DBLP DOI BibTeX RDF	X-search problem, super-polynomial time, decidable, search problems, decision problems, parallel complexity
21	Ken Kaneiwa, Philip H. P. Nguyen	Decidable Order-Sorted Logic Programming for Ontologies and Rules with Argument Restructuring.	ISWC	2009	DBLP DOI BibTeX RDF
21	Thomas Place, Luc Segoufin	A Decidable Characterization of Locally Testable Tree Languages.	ICALP (2)	2009	DBLP DOI BibTeX RDF
21	Raphaël Bailly, François Denis	Absolute Convergence of Rational Series Is Semi-decidable.	LATA	2009	DBLP DOI BibTeX RDF
21	Yuliya Lierler, Vladimir Lifschitz	One More Decidable Class of Finitely Ground Programs.	ICLP	2009	DBLP DOI BibTeX RDF