java -Xss4m -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC_wBE.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/hopv/lia/termination/McCarthy9103.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-24 21:29:00,598 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-24 21:29:00,600 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-24 21:29:00,611 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-24 21:29:00,612 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-24 21:29:00,613 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-24 21:29:00,614 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-24 21:29:00,617 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-24 21:29:00,619 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-24 21:29:00,619 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-24 21:29:00,622 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-24 21:29:00,622 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-24 21:29:00,623 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-24 21:29:00,626 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-24 21:29:00,636 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-24 21:29:00,637 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-24 21:29:00,639 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-24 21:29:00,641 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-24 21:29:00,645 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-24 21:29:00,646 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-24 21:29:00,647 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-24 21:29:00,650 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-24 21:29:00,653 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-24 21:29:00,653 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-24 21:29:00,654 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-24 21:29:00,655 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-24 21:29:00,655 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-24 21:29:00,657 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-24 21:29:00,658 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-24 21:29:00,658 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-24 21:29:00,659 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-24 21:29:00,659 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-24 21:29:00,664 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-24 21:29:00,665 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-24 21:29:00,666 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-24 21:29:00,666 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-24 21:29:00,692 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-24 21:29:00,693 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-24 21:29:00,693 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-24 21:29:00,693 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-24 21:29:00,694 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-24 21:29:00,694 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-24 21:29:00,694 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-24 21:29:00,695 INFO L133 SettingsManager]: * Use SBE=true [2018-06-24 21:29:00,696 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-24 21:29:00,696 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-24 21:29:00,696 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-24 21:29:00,696 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-24 21:29:00,696 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-24 21:29:00,697 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-24 21:29:00,697 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-24 21:29:00,697 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-24 21:29:00,697 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-24 21:29:00,697 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-24 21:29:00,697 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-24 21:29:00,698 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-24 21:29:00,698 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-24 21:29:00,701 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-24 21:29:00,701 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-24 21:29:00,748 INFO ]: Repository-Root is: /tmp [2018-06-24 21:29:00,764 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-24 21:29:00,769 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-24 21:29:00,770 INFO ]: Initializing SmtParser... [2018-06-24 21:29:00,770 INFO ]: SmtParser initialized [2018-06-24 21:29:00,770 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/hopv/lia/termination/McCarthy9103.smt2 [2018-06-24 21:29:00,772 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-24 21:29:00,858 INFO ]: Executing SMT file /storage/chc-comp/hopv/lia/termination/McCarthy9103.smt2 unknown [2018-06-24 21:29:01,156 INFO ]: Succesfully executed SMT file /storage/chc-comp/hopv/lia/termination/McCarthy9103.smt2 [2018-06-24 21:29:01,160 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-24 21:29:01,165 INFO ]: Walking toolchain with 5 elements. [2018-06-24 21:29:01,166 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-24 21:29:01,166 INFO ]: Initializing ChcToBoogie... [2018-06-24 21:29:01,166 INFO ]: ChcToBoogie initialized [2018-06-24 21:29:01,170 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 24.06 09:29:01" (1/1) ... [2018-06-24 21:29:01,248 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:29:01 Unit [2018-06-24 21:29:01,249 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-24 21:29:01,249 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-24 21:29:01,249 INFO ]: Initializing Boogie Preprocessor... [2018-06-24 21:29:01,249 INFO ]: Boogie Preprocessor initialized [2018-06-24 21:29:01,273 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:29:01" (1/1) ... [2018-06-24 21:29:01,273 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:29:01" (1/1) ... [2018-06-24 21:29:01,282 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:29:01" (1/1) ... [2018-06-24 21:29:01,282 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:29:01" (1/1) ... [2018-06-24 21:29:01,293 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:29:01" (1/1) ... [2018-06-24 21:29:01,295 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:29:01" (1/1) ... [2018-06-24 21:29:01,297 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:29:01" (1/1) ... [2018-06-24 21:29:01,300 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-24 21:29:01,301 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-24 21:29:01,301 INFO ]: Initializing RCFGBuilder... [2018-06-24 21:29:01,301 INFO ]: RCFGBuilder initialized [2018-06-24 21:29:01,302 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:29:01" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-24 21:29:01,319 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-24 21:29:01,319 INFO ]: Found specification of procedure gotoProc [2018-06-24 21:29:01,319 INFO ]: Found implementation of procedure gotoProc [2018-06-24 21:29:01,320 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-24 21:29:01,320 INFO ]: Found specification of procedure Ultimate.START [2018-06-24 21:29:01,320 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-24 21:29:01,848 INFO ]: Using library mode [2018-06-24 21:29:01,849 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:29:01 BoogieIcfgContainer [2018-06-24 21:29:01,849 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-24 21:29:01,849 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-24 21:29:01,849 INFO ]: Initializing BlockEncodingV2... [2018-06-24 21:29:01,850 INFO ]: BlockEncodingV2 initialized [2018-06-24 21:29:01,851 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:29:01" (1/1) ... [2018-06-24 21:29:01,871 INFO ]: Initial Icfg 47 locations, 75 edges [2018-06-24 21:29:01,873 INFO ]: Using Remove infeasible edges [2018-06-24 21:29:01,873 INFO ]: Using Maximize final states [2018-06-24 21:29:01,875 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-24 21:29:01,875 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-24 21:29:01,877 INFO ]: Using Remove sink states [2018-06-24 21:29:01,877 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-24 21:29:01,877 INFO ]: Using Use SBE [2018-06-24 21:29:01,938 INFO ]: SBE split 3 edges [2018-06-24 21:29:01,946 INFO ]: Removed 4 edges and 2 locations because of local infeasibility [2018-06-24 21:29:01,947 INFO ]: 0 new accepting states [2018-06-24 21:29:02,406 INFO ]: Removed 46 edges and 12 locations by large block encoding [2018-06-24 21:29:02,408 INFO ]: Removed 1 edges and 1 locations by removing sink states [2018-06-24 21:29:02,409 INFO ]: Removed 2 edges and 0 locations because of local infeasibility [2018-06-24 21:29:02,409 INFO ]: 0 new accepting states [2018-06-24 21:29:02,410 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-24 21:29:02,410 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-24 21:29:02,411 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-24 21:29:02,411 INFO ]: 0 new accepting states [2018-06-24 21:29:02,412 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-24 21:29:02,412 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-24 21:29:02,412 INFO ]: Encoded RCFG 32 locations, 62 edges [2018-06-24 21:29:02,413 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 24.06 09:29:02 BasicIcfg [2018-06-24 21:29:02,413 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-24 21:29:02,414 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-24 21:29:02,414 INFO ]: Initializing TraceAbstraction... [2018-06-24 21:29:02,418 INFO ]: TraceAbstraction initialized [2018-06-24 21:29:02,418 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 24.06 09:29:01" (1/4) ... [2018-06-24 21:29:02,418 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2f0b66ec and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 24.06 09:29:02, skipping insertion in model container [2018-06-24 21:29:02,418 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:29:01" (2/4) ... [2018-06-24 21:29:02,419 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2f0b66ec and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.06 09:29:02, skipping insertion in model container [2018-06-24 21:29:02,419 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:29:01" (3/4) ... [2018-06-24 21:29:02,419 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2f0b66ec and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.06 09:29:02, skipping insertion in model container [2018-06-24 21:29:02,419 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 24.06 09:29:02" (4/4) ... [2018-06-24 21:29:02,420 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-24 21:29:02,426 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-24 21:29:02,434 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-24 21:29:02,476 INFO ]: Using default assertion order modulation [2018-06-24 21:29:02,476 INFO ]: Interprodecural is true [2018-06-24 21:29:02,476 INFO ]: Hoare is false [2018-06-24 21:29:02,476 INFO ]: Compute interpolants for FPandBP [2018-06-24 21:29:02,476 INFO ]: Backedges is TWOTRACK [2018-06-24 21:29:02,476 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-24 21:29:02,476 INFO ]: Difference is false [2018-06-24 21:29:02,476 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-24 21:29:02,476 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-24 21:29:02,487 INFO ]: Start isEmpty. Operand 32 states. [2018-06-24 21:29:02,502 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-24 21:29:02,502 INFO ]: Found error trace [2018-06-24 21:29:02,504 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-24 21:29:02,504 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:02,509 INFO ]: Analyzing trace with hash 46947817, now seen corresponding path program 1 times [2018-06-24 21:29:02,511 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:02,512 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:02,559 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:02,559 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:02,559 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:02,598 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:02,660 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:29:02,661 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:29:02,661 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:29:02,663 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:29:02,676 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:29:02,676 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:29:02,679 INFO ]: Start difference. First operand 32 states. Second operand 3 states. [2018-06-24 21:29:03,419 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:03,419 INFO ]: Finished difference Result 57 states and 110 transitions. [2018-06-24 21:29:03,420 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:29:03,421 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-24 21:29:03,422 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:03,434 INFO ]: With dead ends: 57 [2018-06-24 21:29:03,434 INFO ]: Without dead ends: 41 [2018-06-24 21:29:03,435 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:29:03,450 INFO ]: Start minimizeSevpa. Operand 41 states. [2018-06-24 21:29:03,478 INFO ]: Finished minimizeSevpa. Reduced states from 41 to 41. [2018-06-24 21:29:03,482 INFO ]: Start removeUnreachable. Operand 41 states. [2018-06-24 21:29:03,485 INFO ]: Finished removeUnreachable. Reduced from 41 states to 41 states and 72 transitions. [2018-06-24 21:29:03,490 INFO ]: Start accepts. Automaton has 41 states and 72 transitions. Word has length 5 [2018-06-24 21:29:03,491 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:03,491 INFO ]: Abstraction has 41 states and 72 transitions. [2018-06-24 21:29:03,491 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:29:03,491 INFO ]: Start isEmpty. Operand 41 states and 72 transitions. [2018-06-24 21:29:03,492 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-24 21:29:03,492 INFO ]: Found error trace [2018-06-24 21:29:03,492 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-24 21:29:03,492 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:03,493 INFO ]: Analyzing trace with hash 1479448052, now seen corresponding path program 1 times [2018-06-24 21:29:03,493 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:03,493 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:03,496 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:03,496 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:03,496 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:03,509 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:03,550 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:29:03,550 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:29:03,550 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:29:03,551 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:29:03,551 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:29:03,551 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:29:03,551 INFO ]: Start difference. First operand 41 states and 72 transitions. Second operand 3 states. [2018-06-24 21:29:03,971 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:03,971 INFO ]: Finished difference Result 58 states and 104 transitions. [2018-06-24 21:29:03,971 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:29:03,971 INFO ]: Start accepts. Automaton has 3 states. Word has length 6 [2018-06-24 21:29:03,972 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:03,975 INFO ]: With dead ends: 58 [2018-06-24 21:29:03,975 INFO ]: Without dead ends: 58 [2018-06-24 21:29:03,976 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:29:03,976 INFO ]: Start minimizeSevpa. Operand 58 states. [2018-06-24 21:29:03,986 INFO ]: Finished minimizeSevpa. Reduced states from 58 to 58. [2018-06-24 21:29:03,986 INFO ]: Start removeUnreachable. Operand 58 states. [2018-06-24 21:29:03,989 INFO ]: Finished removeUnreachable. Reduced from 58 states to 58 states and 104 transitions. [2018-06-24 21:29:03,989 INFO ]: Start accepts. Automaton has 58 states and 104 transitions. Word has length 6 [2018-06-24 21:29:03,989 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:03,989 INFO ]: Abstraction has 58 states and 104 transitions. [2018-06-24 21:29:03,989 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:29:03,989 INFO ]: Start isEmpty. Operand 58 states and 104 transitions. [2018-06-24 21:29:03,992 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-24 21:29:03,992 INFO ]: Found error trace [2018-06-24 21:29:03,992 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:03,992 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:03,992 INFO ]: Analyzing trace with hash 1786071277, now seen corresponding path program 1 times [2018-06-24 21:29:03,992 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:03,992 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:03,993 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:03,993 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:03,993 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:04,003 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:04,028 INFO ]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 21:29:04,028 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:29:04,028 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:29:04,028 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:29:04,028 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:29:04,028 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:29:04,029 INFO ]: Start difference. First operand 58 states and 104 transitions. Second operand 3 states. [2018-06-24 21:29:04,248 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:04,249 INFO ]: Finished difference Result 74 states and 130 transitions. [2018-06-24 21:29:04,249 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:29:04,249 INFO ]: Start accepts. Automaton has 3 states. Word has length 11 [2018-06-24 21:29:04,249 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:04,252 INFO ]: With dead ends: 74 [2018-06-24 21:29:04,252 INFO ]: Without dead ends: 58 [2018-06-24 21:29:04,252 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:29:04,253 INFO ]: Start minimizeSevpa. Operand 58 states. [2018-06-24 21:29:04,261 INFO ]: Finished minimizeSevpa. Reduced states from 58 to 58. [2018-06-24 21:29:04,261 INFO ]: Start removeUnreachable. Operand 58 states. [2018-06-24 21:29:04,263 INFO ]: Finished removeUnreachable. Reduced from 58 states to 58 states and 103 transitions. [2018-06-24 21:29:04,263 INFO ]: Start accepts. Automaton has 58 states and 103 transitions. Word has length 11 [2018-06-24 21:29:04,263 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:04,263 INFO ]: Abstraction has 58 states and 103 transitions. [2018-06-24 21:29:04,263 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:29:04,263 INFO ]: Start isEmpty. Operand 58 states and 103 transitions. [2018-06-24 21:29:04,265 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-24 21:29:04,265 INFO ]: Found error trace [2018-06-24 21:29:04,265 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:04,265 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:04,265 INFO ]: Analyzing trace with hash 1589557772, now seen corresponding path program 1 times [2018-06-24 21:29:04,265 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:04,265 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:04,266 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:04,266 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:04,266 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:04,280 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:04,460 INFO ]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 21:29:04,460 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:29:04,460 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-06-24 21:29:04,460 INFO ]: Interpolant automaton has 5 states [2018-06-24 21:29:04,461 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-24 21:29:04,461 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-24 21:29:04,461 INFO ]: Start difference. First operand 58 states and 103 transitions. Second operand 5 states. [2018-06-24 21:29:05,028 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:05,028 INFO ]: Finished difference Result 129 states and 275 transitions. [2018-06-24 21:29:05,029 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-24 21:29:05,029 INFO ]: Start accepts. Automaton has 5 states. Word has length 11 [2018-06-24 21:29:05,029 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:05,040 INFO ]: With dead ends: 129 [2018-06-24 21:29:05,041 INFO ]: Without dead ends: 129 [2018-06-24 21:29:05,041 INFO ]: 0 DeclaredPredicates, 8 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-06-24 21:29:05,041 INFO ]: Start minimizeSevpa. Operand 129 states. [2018-06-24 21:29:05,065 INFO ]: Finished minimizeSevpa. Reduced states from 129 to 62. [2018-06-24 21:29:05,065 INFO ]: Start removeUnreachable. Operand 62 states. [2018-06-24 21:29:05,067 INFO ]: Finished removeUnreachable. Reduced from 62 states to 62 states and 111 transitions. [2018-06-24 21:29:05,067 INFO ]: Start accepts. Automaton has 62 states and 111 transitions. Word has length 11 [2018-06-24 21:29:05,067 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:05,067 INFO ]: Abstraction has 62 states and 111 transitions. [2018-06-24 21:29:05,067 INFO ]: Interpolant automaton has 5 states. [2018-06-24 21:29:05,067 INFO ]: Start isEmpty. Operand 62 states and 111 transitions. [2018-06-24 21:29:05,070 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-24 21:29:05,070 INFO ]: Found error trace [2018-06-24 21:29:05,070 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:05,070 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:05,070 INFO ]: Analyzing trace with hash 2030304678, now seen corresponding path program 1 times [2018-06-24 21:29:05,070 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:05,070 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:05,071 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:05,071 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:05,071 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:05,091 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:05,176 INFO ]: Checked inductivity of 5 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 21:29:05,176 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:29:05,176 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-06-24 21:29:05,176 INFO ]: Interpolant automaton has 5 states [2018-06-24 21:29:05,176 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-24 21:29:05,176 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-24 21:29:05,176 INFO ]: Start difference. First operand 62 states and 111 transitions. Second operand 5 states. [2018-06-24 21:29:05,401 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:05,401 INFO ]: Finished difference Result 149 states and 252 transitions. [2018-06-24 21:29:05,402 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-24 21:29:05,402 INFO ]: Start accepts. Automaton has 5 states. Word has length 12 [2018-06-24 21:29:05,402 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:05,408 INFO ]: With dead ends: 149 [2018-06-24 21:29:05,408 INFO ]: Without dead ends: 149 [2018-06-24 21:29:05,408 INFO ]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-06-24 21:29:05,408 INFO ]: Start minimizeSevpa. Operand 149 states. [2018-06-24 21:29:05,440 INFO ]: Finished minimizeSevpa. Reduced states from 149 to 74. [2018-06-24 21:29:05,440 INFO ]: Start removeUnreachable. Operand 74 states. [2018-06-24 21:29:05,441 INFO ]: Finished removeUnreachable. Reduced from 74 states to 74 states and 129 transitions. [2018-06-24 21:29:05,441 INFO ]: Start accepts. Automaton has 74 states and 129 transitions. Word has length 12 [2018-06-24 21:29:05,442 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:05,442 INFO ]: Abstraction has 74 states and 129 transitions. [2018-06-24 21:29:05,442 INFO ]: Interpolant automaton has 5 states. [2018-06-24 21:29:05,442 INFO ]: Start isEmpty. Operand 74 states and 129 transitions. [2018-06-24 21:29:05,448 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-24 21:29:05,448 INFO ]: Found error trace [2018-06-24 21:29:05,448 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:05,448 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:05,448 INFO ]: Analyzing trace with hash -1563598040, now seen corresponding path program 1 times [2018-06-24 21:29:05,448 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:05,448 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:05,449 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:05,449 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:05,449 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:05,466 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:05,517 INFO ]: Checked inductivity of 5 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-24 21:29:05,517 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:29:05,517 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-24 21:29:05,517 INFO ]: Interpolant automaton has 4 states [2018-06-24 21:29:05,518 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-24 21:29:05,518 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-24 21:29:05,518 INFO ]: Start difference. First operand 74 states and 129 transitions. Second operand 4 states. [2018-06-24 21:29:05,556 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:05,556 INFO ]: Finished difference Result 110 states and 186 transitions. [2018-06-24 21:29:05,557 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-24 21:29:05,557 INFO ]: Start accepts. Automaton has 4 states. Word has length 12 [2018-06-24 21:29:05,557 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:05,559 INFO ]: With dead ends: 110 [2018-06-24 21:29:05,559 INFO ]: Without dead ends: 110 [2018-06-24 21:29:05,559 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-24 21:29:05,559 INFO ]: Start minimizeSevpa. Operand 110 states. [2018-06-24 21:29:05,569 INFO ]: Finished minimizeSevpa. Reduced states from 110 to 83. [2018-06-24 21:29:05,569 INFO ]: Start removeUnreachable. Operand 83 states. [2018-06-24 21:29:05,571 INFO ]: Finished removeUnreachable. Reduced from 83 states to 83 states and 141 transitions. [2018-06-24 21:29:05,571 INFO ]: Start accepts. Automaton has 83 states and 141 transitions. Word has length 12 [2018-06-24 21:29:05,571 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:05,571 INFO ]: Abstraction has 83 states and 141 transitions. [2018-06-24 21:29:05,571 INFO ]: Interpolant automaton has 4 states. [2018-06-24 21:29:05,571 INFO ]: Start isEmpty. Operand 83 states and 141 transitions. [2018-06-24 21:29:05,576 INFO ]: Finished isEmpty. Found accepting run of length 31 [2018-06-24 21:29:05,576 INFO ]: Found error trace [2018-06-24 21:29:05,576 INFO ]: trace histogram [5, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:05,576 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:05,576 INFO ]: Analyzing trace with hash 1534233348, now seen corresponding path program 1 times [2018-06-24 21:29:05,577 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:05,577 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:05,577 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:05,577 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:05,577 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:05,598 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:05,736 INFO ]: Checked inductivity of 46 backedges. 24 proven. 2 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2018-06-24 21:29:05,737 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:29:05,737 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:29:05,760 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:05,823 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:05,838 INFO ]: Computing forward predicates... [2018-06-24 21:29:06,022 INFO ]: Checked inductivity of 46 backedges. 32 proven. 0 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2018-06-24 21:29:06,047 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-24 21:29:06,047 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2018-06-24 21:29:06,048 INFO ]: Interpolant automaton has 10 states [2018-06-24 21:29:06,048 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-24 21:29:06,048 INFO ]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2018-06-24 21:29:06,048 INFO ]: Start difference. First operand 83 states and 141 transitions. Second operand 10 states. [2018-06-24 21:29:07,822 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:07,822 INFO ]: Finished difference Result 191 states and 390 transitions. [2018-06-24 21:29:07,822 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-24 21:29:07,822 INFO ]: Start accepts. Automaton has 10 states. Word has length 30 [2018-06-24 21:29:07,822 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:07,827 INFO ]: With dead ends: 191 [2018-06-24 21:29:07,828 INFO ]: Without dead ends: 174 [2018-06-24 21:29:07,829 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=89, Invalid=217, Unknown=0, NotChecked=0, Total=306 [2018-06-24 21:29:07,829 INFO ]: Start minimizeSevpa. Operand 174 states. [2018-06-24 21:29:07,865 INFO ]: Finished minimizeSevpa. Reduced states from 174 to 118. [2018-06-24 21:29:07,865 INFO ]: Start removeUnreachable. Operand 118 states. [2018-06-24 21:29:07,870 INFO ]: Finished removeUnreachable. Reduced from 118 states to 118 states and 218 transitions. [2018-06-24 21:29:07,870 INFO ]: Start accepts. Automaton has 118 states and 218 transitions. Word has length 30 [2018-06-24 21:29:07,870 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:07,870 INFO ]: Abstraction has 118 states and 218 transitions. [2018-06-24 21:29:07,870 INFO ]: Interpolant automaton has 10 states. [2018-06-24 21:29:07,870 INFO ]: Start isEmpty. Operand 118 states and 218 transitions. [2018-06-24 21:29:07,876 INFO ]: Finished isEmpty. Found accepting run of length 32 [2018-06-24 21:29:07,876 INFO ]: Found error trace [2018-06-24 21:29:07,876 INFO ]: trace histogram [5, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:07,876 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:07,877 INFO ]: Analyzing trace with hash -2121060244, now seen corresponding path program 2 times [2018-06-24 21:29:07,877 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:07,877 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:07,877 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:07,877 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:07,877 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:07,940 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:08,048 INFO ]: Checked inductivity of 53 backedges. 18 proven. 8 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2018-06-24 21:29:08,048 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:29:08,048 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:29:08,056 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:29:08,127 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:29:08,128 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:08,131 INFO ]: Computing forward predicates... [2018-06-24 21:29:08,243 INFO ]: Checked inductivity of 53 backedges. 30 proven. 4 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2018-06-24 21:29:08,276 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:29:08,276 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6] total 12 [2018-06-24 21:29:08,277 INFO ]: Interpolant automaton has 12 states [2018-06-24 21:29:08,277 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-24 21:29:08,277 INFO ]: CoverageRelationStatistics Valid=21, Invalid=111, Unknown=0, NotChecked=0, Total=132 [2018-06-24 21:29:08,277 INFO ]: Start difference. First operand 118 states and 218 transitions. Second operand 12 states. [2018-06-24 21:29:09,052 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:09,052 INFO ]: Finished difference Result 328 states and 895 transitions. [2018-06-24 21:29:09,053 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-24 21:29:09,053 INFO ]: Start accepts. Automaton has 12 states. Word has length 31 [2018-06-24 21:29:09,053 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:09,066 INFO ]: With dead ends: 328 [2018-06-24 21:29:09,066 INFO ]: Without dead ends: 328 [2018-06-24 21:29:09,067 INFO ]: 0 DeclaredPredicates, 52 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=102, Invalid=404, Unknown=0, NotChecked=0, Total=506 [2018-06-24 21:29:09,067 INFO ]: Start minimizeSevpa. Operand 328 states. [2018-06-24 21:29:09,101 INFO ]: Finished minimizeSevpa. Reduced states from 328 to 118. [2018-06-24 21:29:09,101 INFO ]: Start removeUnreachable. Operand 118 states. [2018-06-24 21:29:09,103 INFO ]: Finished removeUnreachable. Reduced from 118 states to 118 states and 218 transitions. [2018-06-24 21:29:09,103 INFO ]: Start accepts. Automaton has 118 states and 218 transitions. Word has length 31 [2018-06-24 21:29:09,103 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:09,103 INFO ]: Abstraction has 118 states and 218 transitions. [2018-06-24 21:29:09,103 INFO ]: Interpolant automaton has 12 states. [2018-06-24 21:29:09,103 INFO ]: Start isEmpty. Operand 118 states and 218 transitions. [2018-06-24 21:29:09,108 INFO ]: Finished isEmpty. Found accepting run of length 35 [2018-06-24 21:29:09,108 INFO ]: Found error trace [2018-06-24 21:29:09,108 INFO ]: trace histogram [6, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:09,108 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:09,108 INFO ]: Analyzing trace with hash 1433649293, now seen corresponding path program 1 times [2018-06-24 21:29:09,108 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:09,108 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:09,109 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:09,109 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:29:09,109 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:09,122 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:09,310 INFO ]: Checked inductivity of 59 backedges. 22 proven. 8 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2018-06-24 21:29:09,310 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:29:09,310 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:29:09,326 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:09,385 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:09,388 INFO ]: Computing forward predicates... [2018-06-24 21:29:09,770 INFO ]: Checked inductivity of 59 backedges. 34 proven. 0 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2018-06-24 21:29:09,802 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-24 21:29:09,802 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2018-06-24 21:29:09,802 INFO ]: Interpolant automaton has 10 states [2018-06-24 21:29:09,802 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-24 21:29:09,802 INFO ]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2018-06-24 21:29:09,803 INFO ]: Start difference. First operand 118 states and 218 transitions. Second operand 10 states. [2018-06-24 21:29:10,744 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:10,744 INFO ]: Finished difference Result 301 states and 723 transitions. [2018-06-24 21:29:10,744 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-24 21:29:10,744 INFO ]: Start accepts. Automaton has 10 states. Word has length 34 [2018-06-24 21:29:10,745 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:10,750 INFO ]: With dead ends: 301 [2018-06-24 21:29:10,750 INFO ]: Without dead ends: 193 [2018-06-24 21:29:10,751 INFO ]: 0 DeclaredPredicates, 52 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=106, Invalid=236, Unknown=0, NotChecked=0, Total=342 [2018-06-24 21:29:10,751 INFO ]: Start minimizeSevpa. Operand 193 states. [2018-06-24 21:29:10,767 INFO ]: Finished minimizeSevpa. Reduced states from 193 to 122. [2018-06-24 21:29:10,767 INFO ]: Start removeUnreachable. Operand 122 states. [2018-06-24 21:29:10,769 INFO ]: Finished removeUnreachable. Reduced from 122 states to 122 states and 241 transitions. [2018-06-24 21:29:10,769 INFO ]: Start accepts. Automaton has 122 states and 241 transitions. Word has length 34 [2018-06-24 21:29:10,769 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:10,769 INFO ]: Abstraction has 122 states and 241 transitions. [2018-06-24 21:29:10,769 INFO ]: Interpolant automaton has 10 states. [2018-06-24 21:29:10,769 INFO ]: Start isEmpty. Operand 122 states and 241 transitions. [2018-06-24 21:29:10,774 INFO ]: Finished isEmpty. Found accepting run of length 36 [2018-06-24 21:29:10,774 INFO ]: Found error trace [2018-06-24 21:29:10,774 INFO ]: trace histogram [6, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:10,774 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:10,775 INFO ]: Analyzing trace with hash -847192595, now seen corresponding path program 2 times [2018-06-24 21:29:10,775 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:10,775 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:10,775 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:10,775 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:10,775 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:10,787 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:10,940 INFO ]: Checked inductivity of 66 backedges. 28 proven. 5 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2018-06-24 21:29:10,940 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:29:10,940 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:29:10,946 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:29:10,996 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:29:10,996 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:11,000 INFO ]: Computing forward predicates... [2018-06-24 21:29:11,273 INFO ]: Checked inductivity of 66 backedges. 45 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-24 21:29:11,293 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-24 21:29:11,293 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2018-06-24 21:29:11,293 INFO ]: Interpolant automaton has 10 states [2018-06-24 21:29:11,294 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-24 21:29:11,294 INFO ]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2018-06-24 21:29:11,294 INFO ]: Start difference. First operand 122 states and 241 transitions. Second operand 10 states. [2018-06-24 21:29:11,832 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:11,832 INFO ]: Finished difference Result 162 states and 336 transitions. [2018-06-24 21:29:11,832 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-24 21:29:11,832 INFO ]: Start accepts. Automaton has 10 states. Word has length 35 [2018-06-24 21:29:11,832 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:11,834 INFO ]: With dead ends: 162 [2018-06-24 21:29:11,834 INFO ]: Without dead ends: 162 [2018-06-24 21:29:11,835 INFO ]: 0 DeclaredPredicates, 54 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=90, Invalid=252, Unknown=0, NotChecked=0, Total=342 [2018-06-24 21:29:11,835 INFO ]: Start minimizeSevpa. Operand 162 states. [2018-06-24 21:29:11,845 INFO ]: Finished minimizeSevpa. Reduced states from 162 to 114. [2018-06-24 21:29:11,845 INFO ]: Start removeUnreachable. Operand 114 states. [2018-06-24 21:29:11,847 INFO ]: Finished removeUnreachable. Reduced from 114 states to 114 states and 217 transitions. [2018-06-24 21:29:11,847 INFO ]: Start accepts. Automaton has 114 states and 217 transitions. Word has length 35 [2018-06-24 21:29:11,847 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:11,847 INFO ]: Abstraction has 114 states and 217 transitions. [2018-06-24 21:29:11,847 INFO ]: Interpolant automaton has 10 states. [2018-06-24 21:29:11,847 INFO ]: Start isEmpty. Operand 114 states and 217 transitions. [2018-06-24 21:29:11,851 INFO ]: Finished isEmpty. Found accepting run of length 37 [2018-06-24 21:29:11,851 INFO ]: Found error trace [2018-06-24 21:29:11,851 INFO ]: trace histogram [6, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:11,851 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:11,851 INFO ]: Analyzing trace with hash 1348948961, now seen corresponding path program 3 times [2018-06-24 21:29:11,851 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:11,851 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:11,852 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:11,852 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:29:11,852 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:11,868 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:11,900 INFO ]: Checked inductivity of 74 backedges. 34 proven. 2 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2018-06-24 21:29:11,900 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:29:11,900 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:29:11,920 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:29:11,953 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-24 21:29:11,953 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:11,955 INFO ]: Computing forward predicates... [2018-06-24 21:29:11,960 INFO ]: Checked inductivity of 74 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-24 21:29:11,980 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-24 21:29:11,980 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [3] total 3 [2018-06-24 21:29:11,980 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:29:11,980 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:29:11,980 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:29:11,980 INFO ]: Start difference. First operand 114 states and 217 transitions. Second operand 3 states. [2018-06-24 21:29:12,012 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:12,013 INFO ]: Finished difference Result 161 states and 296 transitions. [2018-06-24 21:29:12,013 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:29:12,013 INFO ]: Start accepts. Automaton has 3 states. Word has length 36 [2018-06-24 21:29:12,013 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:12,015 INFO ]: With dead ends: 161 [2018-06-24 21:29:12,015 INFO ]: Without dead ends: 136 [2018-06-24 21:29:12,015 INFO ]: 0 DeclaredPredicates, 38 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:29:12,015 INFO ]: Start minimizeSevpa. Operand 136 states. [2018-06-24 21:29:12,026 INFO ]: Finished minimizeSevpa. Reduced states from 136 to 136. [2018-06-24 21:29:12,026 INFO ]: Start removeUnreachable. Operand 136 states. [2018-06-24 21:29:12,030 INFO ]: Finished removeUnreachable. Reduced from 136 states to 136 states and 250 transitions. [2018-06-24 21:29:12,030 INFO ]: Start accepts. Automaton has 136 states and 250 transitions. Word has length 36 [2018-06-24 21:29:12,030 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:12,030 INFO ]: Abstraction has 136 states and 250 transitions. [2018-06-24 21:29:12,030 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:29:12,030 INFO ]: Start isEmpty. Operand 136 states and 250 transitions. [2018-06-24 21:29:12,035 INFO ]: Finished isEmpty. Found accepting run of length 44 [2018-06-24 21:29:12,035 INFO ]: Found error trace [2018-06-24 21:29:12,035 INFO ]: trace histogram [7, 4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:12,035 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:12,035 INFO ]: Analyzing trace with hash -158276233, now seen corresponding path program 1 times [2018-06-24 21:29:12,035 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:12,035 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:12,036 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:12,036 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:29:12,036 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:12,053 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:12,247 INFO ]: Checked inductivity of 109 backedges. 51 proven. 3 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-24 21:29:12,247 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:29:12,247 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-24 21:29:12,261 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:29:12,336 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:12,340 INFO ]: Computing forward predicates... [2018-06-24 21:29:12,353 INFO ]: Checked inductivity of 109 backedges. 67 proven. 0 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2018-06-24 21:29:12,382 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-24 21:29:12,382 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [3] total 3 [2018-06-24 21:29:12,382 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:29:12,383 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:29:12,383 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:29:12,383 INFO ]: Start difference. First operand 136 states and 250 transitions. Second operand 3 states. [2018-06-24 21:29:12,414 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:12,414 INFO ]: Finished difference Result 152 states and 273 transitions. [2018-06-24 21:29:12,414 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:29:12,414 INFO ]: Start accepts. Automaton has 3 states. Word has length 43 [2018-06-24 21:29:12,415 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:12,416 INFO ]: With dead ends: 152 [2018-06-24 21:29:12,416 INFO ]: Without dead ends: 130 [2018-06-24 21:29:12,416 INFO ]: 0 DeclaredPredicates, 45 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:29:12,416 INFO ]: Start minimizeSevpa. Operand 130 states. [2018-06-24 21:29:12,423 INFO ]: Finished minimizeSevpa. Reduced states from 130 to 130. [2018-06-24 21:29:12,423 INFO ]: Start removeUnreachable. Operand 130 states. [2018-06-24 21:29:12,425 INFO ]: Finished removeUnreachable. Reduced from 130 states to 130 states and 234 transitions. [2018-06-24 21:29:12,425 INFO ]: Start accepts. Automaton has 130 states and 234 transitions. Word has length 43 [2018-06-24 21:29:12,426 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:12,426 INFO ]: Abstraction has 130 states and 234 transitions. [2018-06-24 21:29:12,426 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:29:12,426 INFO ]: Start isEmpty. Operand 130 states and 234 transitions. [2018-06-24 21:29:12,430 INFO ]: Finished isEmpty. Found accepting run of length 59 [2018-06-24 21:29:12,430 INFO ]: Found error trace [2018-06-24 21:29:12,430 INFO ]: trace histogram [10, 5, 5, 4, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:12,430 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:12,430 INFO ]: Analyzing trace with hash 734463602, now seen corresponding path program 1 times [2018-06-24 21:29:12,430 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:12,430 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:12,431 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:12,431 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:12,431 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:12,449 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:12,520 INFO ]: Checked inductivity of 202 backedges. 77 proven. 4 refuted. 0 times theorem prover too weak. 121 trivial. 0 not checked. [2018-06-24 21:29:12,520 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:29:12,520 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:29:12,527 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:12,589 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:12,593 INFO ]: Computing forward predicates... [2018-06-24 21:29:12,627 INFO ]: Checked inductivity of 202 backedges. 100 proven. 0 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2018-06-24 21:29:12,647 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-24 21:29:12,647 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2018-06-24 21:29:12,647 INFO ]: Interpolant automaton has 10 states [2018-06-24 21:29:12,648 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-24 21:29:12,648 INFO ]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2018-06-24 21:29:12,648 INFO ]: Start difference. First operand 130 states and 234 transitions. Second operand 10 states. [2018-06-24 21:29:12,921 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:12,921 INFO ]: Finished difference Result 156 states and 298 transitions. [2018-06-24 21:29:12,922 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-24 21:29:12,922 INFO ]: Start accepts. Automaton has 10 states. Word has length 58 [2018-06-24 21:29:12,922 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:12,924 INFO ]: With dead ends: 156 [2018-06-24 21:29:12,924 INFO ]: Without dead ends: 155 [2018-06-24 21:29:12,925 INFO ]: 0 DeclaredPredicates, 69 GetRequests, 58 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=43, Invalid=113, Unknown=0, NotChecked=0, Total=156 [2018-06-24 21:29:12,925 INFO ]: Start minimizeSevpa. Operand 155 states. [2018-06-24 21:29:12,932 INFO ]: Finished minimizeSevpa. Reduced states from 155 to 129. [2018-06-24 21:29:12,932 INFO ]: Start removeUnreachable. Operand 129 states. [2018-06-24 21:29:12,934 INFO ]: Finished removeUnreachable. Reduced from 129 states to 129 states and 232 transitions. [2018-06-24 21:29:12,934 INFO ]: Start accepts. Automaton has 129 states and 232 transitions. Word has length 58 [2018-06-24 21:29:12,934 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:12,934 INFO ]: Abstraction has 129 states and 232 transitions. [2018-06-24 21:29:12,934 INFO ]: Interpolant automaton has 10 states. [2018-06-24 21:29:12,934 INFO ]: Start isEmpty. Operand 129 states and 232 transitions. [2018-06-24 21:29:12,938 INFO ]: Finished isEmpty. Found accepting run of length 60 [2018-06-24 21:29:12,938 INFO ]: Found error trace [2018-06-24 21:29:12,938 INFO ]: trace histogram [10, 5, 5, 5, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:12,938 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:12,938 INFO ]: Analyzing trace with hash 442051266, now seen corresponding path program 2 times [2018-06-24 21:29:12,938 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:12,938 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:12,939 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:12,939 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:12,939 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:12,967 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:13,117 INFO ]: Checked inductivity of 216 backedges. 66 proven. 2 refuted. 0 times theorem prover too weak. 148 trivial. 0 not checked. [2018-06-24 21:29:13,117 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:29:13,117 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:29:13,123 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:29:13,184 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:29:13,184 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:13,188 INFO ]: Computing forward predicates... [2018-06-24 21:29:13,276 INFO ]: Checked inductivity of 216 backedges. 92 proven. 0 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2018-06-24 21:29:13,299 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-24 21:29:13,299 INFO ]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 14 [2018-06-24 21:29:13,299 INFO ]: Interpolant automaton has 14 states [2018-06-24 21:29:13,300 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-24 21:29:13,300 INFO ]: CoverageRelationStatistics Valid=31, Invalid=151, Unknown=0, NotChecked=0, Total=182 [2018-06-24 21:29:13,300 INFO ]: Start difference. First operand 129 states and 232 transitions. Second operand 14 states. [2018-06-24 21:29:14,981 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:14,981 INFO ]: Finished difference Result 309 states and 735 transitions. [2018-06-24 21:29:14,981 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-06-24 21:29:14,981 INFO ]: Start accepts. Automaton has 14 states. Word has length 59 [2018-06-24 21:29:14,981 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:14,990 INFO ]: With dead ends: 309 [2018-06-24 21:29:14,990 INFO ]: Without dead ends: 308 [2018-06-24 21:29:14,990 INFO ]: 0 DeclaredPredicates, 100 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 282 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=243, Invalid=1163, Unknown=0, NotChecked=0, Total=1406 [2018-06-24 21:29:14,991 INFO ]: Start minimizeSevpa. Operand 308 states. [2018-06-24 21:29:15,014 INFO ]: Finished minimizeSevpa. Reduced states from 308 to 130. [2018-06-24 21:29:15,014 INFO ]: Start removeUnreachable. Operand 130 states. [2018-06-24 21:29:15,016 INFO ]: Finished removeUnreachable. Reduced from 130 states to 130 states and 234 transitions. [2018-06-24 21:29:15,016 INFO ]: Start accepts. Automaton has 130 states and 234 transitions. Word has length 59 [2018-06-24 21:29:15,017 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:15,017 INFO ]: Abstraction has 130 states and 234 transitions. [2018-06-24 21:29:15,017 INFO ]: Interpolant automaton has 14 states. [2018-06-24 21:29:15,017 INFO ]: Start isEmpty. Operand 130 states and 234 transitions. [2018-06-24 21:29:15,021 INFO ]: Finished isEmpty. Found accepting run of length 61 [2018-06-24 21:29:15,021 INFO ]: Found error trace [2018-06-24 21:29:15,021 INFO ]: trace histogram [10, 6, 5, 5, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:15,021 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:15,021 INFO ]: Analyzing trace with hash 817054102, now seen corresponding path program 3 times [2018-06-24 21:29:15,021 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:15,021 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:15,022 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:15,022 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:29:15,022 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:15,054 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:15,239 INFO ]: Checked inductivity of 231 backedges. 82 proven. 31 refuted. 0 times theorem prover too weak. 118 trivial. 0 not checked. [2018-06-24 21:29:15,239 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:29:15,239 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:29:15,245 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:29:15,319 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2018-06-24 21:29:15,319 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:15,323 INFO ]: Computing forward predicates... [2018-06-24 21:29:15,588 INFO ]: Checked inductivity of 231 backedges. 122 proven. 10 refuted. 0 times theorem prover too weak. 99 trivial. 0 not checked. [2018-06-24 21:29:15,621 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:29:15,621 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 19 [2018-06-24 21:29:15,621 INFO ]: Interpolant automaton has 19 states [2018-06-24 21:29:15,621 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-24 21:29:15,622 INFO ]: CoverageRelationStatistics Valid=36, Invalid=306, Unknown=0, NotChecked=0, Total=342 [2018-06-24 21:29:15,622 INFO ]: Start difference. First operand 130 states and 234 transitions. Second operand 19 states. [2018-06-24 21:29:24,779 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:24,779 INFO ]: Finished difference Result 821 states and 2509 transitions. [2018-06-24 21:29:24,779 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 112 states. [2018-06-24 21:29:24,779 INFO ]: Start accepts. Automaton has 19 states. Word has length 60 [2018-06-24 21:29:24,780 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:24,807 INFO ]: With dead ends: 821 [2018-06-24 21:29:24,807 INFO ]: Without dead ends: 821 [2018-06-24 21:29:24,813 INFO ]: 0 DeclaredPredicates, 214 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 121 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5125 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=1109, Invalid=13897, Unknown=0, NotChecked=0, Total=15006 [2018-06-24 21:29:24,813 INFO ]: Start minimizeSevpa. Operand 821 states. [2018-06-24 21:29:24,971 INFO ]: Finished minimizeSevpa. Reduced states from 821 to 248. [2018-06-24 21:29:24,971 INFO ]: Start removeUnreachable. Operand 248 states. [2018-06-24 21:29:24,975 INFO ]: Finished removeUnreachable. Reduced from 248 states to 248 states and 474 transitions. [2018-06-24 21:29:24,975 INFO ]: Start accepts. Automaton has 248 states and 474 transitions. Word has length 60 [2018-06-24 21:29:24,975 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:24,975 INFO ]: Abstraction has 248 states and 474 transitions. [2018-06-24 21:29:24,975 INFO ]: Interpolant automaton has 19 states. [2018-06-24 21:29:24,975 INFO ]: Start isEmpty. Operand 248 states and 474 transitions. [2018-06-24 21:29:24,981 INFO ]: Finished isEmpty. Found accepting run of length 80 [2018-06-24 21:29:24,981 INFO ]: Found error trace [2018-06-24 21:29:24,981 INFO ]: trace histogram [13, 7, 7, 7, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:24,981 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:24,981 INFO ]: Analyzing trace with hash -211861086, now seen corresponding path program 1 times [2018-06-24 21:29:24,982 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:24,982 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:24,982 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:24,982 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:29:24,982 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:25,015 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:25,692 INFO ]: Checked inductivity of 407 backedges. 123 proven. 55 refuted. 0 times theorem prover too weak. 229 trivial. 0 not checked. [2018-06-24 21:29:25,692 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:29:25,692 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:29:25,703 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:25,779 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:25,783 INFO ]: Computing forward predicates... [2018-06-24 21:29:25,911 INFO ]: Checked inductivity of 407 backedges. 161 proven. 47 refuted. 0 times theorem prover too weak. 199 trivial. 0 not checked. [2018-06-24 21:29:25,931 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:29:25,931 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 16 [2018-06-24 21:29:25,931 INFO ]: Interpolant automaton has 16 states [2018-06-24 21:29:25,931 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-24 21:29:25,931 INFO ]: CoverageRelationStatistics Valid=35, Invalid=205, Unknown=0, NotChecked=0, Total=240 [2018-06-24 21:29:25,931 INFO ]: Start difference. First operand 248 states and 474 transitions. Second operand 16 states. [2018-06-24 21:29:26,527 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:26,527 INFO ]: Finished difference Result 412 states and 909 transitions. [2018-06-24 21:29:26,527 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-24 21:29:26,527 INFO ]: Start accepts. Automaton has 16 states. Word has length 79 [2018-06-24 21:29:26,527 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:26,534 INFO ]: With dead ends: 412 [2018-06-24 21:29:26,534 INFO ]: Without dead ends: 412 [2018-06-24 21:29:26,534 INFO ]: 0 DeclaredPredicates, 105 GetRequests, 82 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=95, Invalid=505, Unknown=0, NotChecked=0, Total=600 [2018-06-24 21:29:26,535 INFO ]: Start minimizeSevpa. Operand 412 states. [2018-06-24 21:29:26,574 INFO ]: Finished minimizeSevpa. Reduced states from 412 to 314. [2018-06-24 21:29:26,574 INFO ]: Start removeUnreachable. Operand 314 states. [2018-06-24 21:29:26,580 INFO ]: Finished removeUnreachable. Reduced from 314 states to 314 states and 617 transitions. [2018-06-24 21:29:26,580 INFO ]: Start accepts. Automaton has 314 states and 617 transitions. Word has length 79 [2018-06-24 21:29:26,580 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:26,580 INFO ]: Abstraction has 314 states and 617 transitions. [2018-06-24 21:29:26,580 INFO ]: Interpolant automaton has 16 states. [2018-06-24 21:29:26,580 INFO ]: Start isEmpty. Operand 314 states and 617 transitions. [2018-06-24 21:29:26,590 INFO ]: Finished isEmpty. Found accepting run of length 80 [2018-06-24 21:29:26,590 INFO ]: Found error trace [2018-06-24 21:29:26,591 INFO ]: trace histogram [13, 7, 7, 7, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:26,591 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:26,591 INFO ]: Analyzing trace with hash 627172576, now seen corresponding path program 1 times [2018-06-24 21:29:26,591 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:26,591 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:26,591 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:26,591 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:26,591 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:26,621 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:27,268 INFO ]: Checked inductivity of 407 backedges. 123 proven. 55 refuted. 0 times theorem prover too weak. 229 trivial. 0 not checked. [2018-06-24 21:29:27,268 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:29:27,268 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:29:27,273 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:27,350 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:27,354 INFO ]: Computing forward predicates... [2018-06-24 21:29:27,421 INFO ]: Checked inductivity of 407 backedges. 161 proven. 47 refuted. 0 times theorem prover too weak. 199 trivial. 0 not checked. [2018-06-24 21:29:27,441 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:29:27,441 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 13 [2018-06-24 21:29:27,441 INFO ]: Interpolant automaton has 13 states [2018-06-24 21:29:27,441 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-24 21:29:27,441 INFO ]: CoverageRelationStatistics Valid=26, Invalid=130, Unknown=0, NotChecked=0, Total=156 [2018-06-24 21:29:27,441 INFO ]: Start difference. First operand 314 states and 617 transitions. Second operand 13 states. [2018-06-24 21:29:28,788 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:28,788 INFO ]: Finished difference Result 454 states and 999 transitions. [2018-06-24 21:29:28,788 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-24 21:29:28,788 INFO ]: Start accepts. Automaton has 13 states. Word has length 79 [2018-06-24 21:29:28,788 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:28,796 INFO ]: With dead ends: 454 [2018-06-24 21:29:28,796 INFO ]: Without dead ends: 454 [2018-06-24 21:29:28,797 INFO ]: 0 DeclaredPredicates, 110 GetRequests, 86 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 72 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=104, Invalid=546, Unknown=0, NotChecked=0, Total=650 [2018-06-24 21:29:28,799 INFO ]: Start minimizeSevpa. Operand 454 states. [2018-06-24 21:29:28,837 INFO ]: Finished minimizeSevpa. Reduced states from 454 to 314. [2018-06-24 21:29:28,837 INFO ]: Start removeUnreachable. Operand 314 states. [2018-06-24 21:29:28,843 INFO ]: Finished removeUnreachable. Reduced from 314 states to 314 states and 617 transitions. [2018-06-24 21:29:28,843 INFO ]: Start accepts. Automaton has 314 states and 617 transitions. Word has length 79 [2018-06-24 21:29:28,843 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:28,843 INFO ]: Abstraction has 314 states and 617 transitions. [2018-06-24 21:29:28,843 INFO ]: Interpolant automaton has 13 states. [2018-06-24 21:29:28,843 INFO ]: Start isEmpty. Operand 314 states and 617 transitions. [2018-06-24 21:29:28,858 INFO ]: Finished isEmpty. Found accepting run of length 127 [2018-06-24 21:29:28,858 INFO ]: Found error trace [2018-06-24 21:29:28,859 INFO ]: trace histogram [21, 11, 11, 11, 6, 6, 6, 5, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:29:28,859 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:28,859 INFO ]: Analyzing trace with hash 1915350514, now seen corresponding path program 2 times [2018-06-24 21:29:28,859 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:28,859 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:28,859 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:28,859 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:29:28,859 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:28,891 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:29,181 INFO ]: Checked inductivity of 1068 backedges. 216 proven. 49 refuted. 0 times theorem prover too weak. 803 trivial. 0 not checked. [2018-06-24 21:29:29,182 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:29:29,182 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:29:29,187 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:29:29,362 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:29:29,362 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:29,370 INFO ]: Computing forward predicates... [2018-06-24 21:29:29,625 INFO ]: Checked inductivity of 1068 backedges. 281 proven. 120 refuted. 0 times theorem prover too weak. 667 trivial. 0 not checked. [2018-06-24 21:29:29,645 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:29:29,645 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 12] total 19 [2018-06-24 21:29:29,645 INFO ]: Interpolant automaton has 19 states [2018-06-24 21:29:29,645 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-24 21:29:29,645 INFO ]: CoverageRelationStatistics Valid=36, Invalid=306, Unknown=0, NotChecked=0, Total=342 [2018-06-24 21:29:29,645 INFO ]: Start difference. First operand 314 states and 617 transitions. Second operand 19 states. [2018-06-24 21:29:31,524 WARN ]: Spent 186.00 ms on a formula simplification that was a NOOP. DAG size: 20 [2018-06-24 21:29:35,171 WARN ]: Spent 167.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-06-24 21:29:38,355 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:29:38,355 INFO ]: Finished difference Result 973 states and 3423 transitions. [2018-06-24 21:29:38,356 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 110 states. [2018-06-24 21:29:38,356 INFO ]: Start accepts. Automaton has 19 states. Word has length 126 [2018-06-24 21:29:38,356 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:29:38,382 INFO ]: With dead ends: 973 [2018-06-24 21:29:38,382 INFO ]: Without dead ends: 913 [2018-06-24 21:29:38,385 INFO ]: 0 DeclaredPredicates, 264 GetRequests, 142 SyntacticMatches, 0 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5109 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=1652, Invalid=13600, Unknown=0, NotChecked=0, Total=15252 [2018-06-24 21:29:38,386 INFO ]: Start minimizeSevpa. Operand 913 states. [2018-06-24 21:29:38,544 INFO ]: Finished minimizeSevpa. Reduced states from 913 to 337. [2018-06-24 21:29:38,544 INFO ]: Start removeUnreachable. Operand 337 states. [2018-06-24 21:29:38,553 INFO ]: Finished removeUnreachable. Reduced from 337 states to 337 states and 684 transitions. [2018-06-24 21:29:38,553 INFO ]: Start accepts. Automaton has 337 states and 684 transitions. Word has length 126 [2018-06-24 21:29:38,553 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:29:38,553 INFO ]: Abstraction has 337 states and 684 transitions. [2018-06-24 21:29:38,553 INFO ]: Interpolant automaton has 19 states. [2018-06-24 21:29:38,553 INFO ]: Start isEmpty. Operand 337 states and 684 transitions. [2018-06-24 21:29:38,570 INFO ]: Finished isEmpty. Found accepting run of length 195 [2018-06-24 21:29:38,570 INFO ]: Found error trace [2018-06-24 21:29:38,570 INFO ]: trace histogram [32, 18, 17, 17, 9, 9, 9, 8, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2018-06-24 21:29:38,570 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:29:38,570 INFO ]: Analyzing trace with hash -2042530270, now seen corresponding path program 3 times [2018-06-24 21:29:38,570 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:29:38,570 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:29:38,571 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:38,571 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:29:38,571 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:29:38,645 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:39,080 INFO ]: Checked inductivity of 2620 backedges. 423 proven. 400 refuted. 0 times theorem prover too weak. 1797 trivial. 0 not checked. [2018-06-24 21:29:39,080 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:29:39,080 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:29:39,090 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:29:39,293 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-24 21:29:39,293 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:29:39,300 INFO ]: Computing forward predicates... [2018-06-24 21:29:39,507 INFO ]: Checked inductivity of 2620 backedges. 639 proven. 81 refuted. 0 times theorem prover too weak. 1900 trivial. 0 not checked. [2018-06-24 21:29:39,526 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:29:39,526 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 12] total 26 [2018-06-24 21:29:39,527 INFO ]: Interpolant automaton has 26 states [2018-06-24 21:29:39,527 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-24 21:29:39,527 INFO ]: CoverageRelationStatistics Valid=55, Invalid=595, Unknown=0, NotChecked=0, Total=650 [2018-06-24 21:29:39,527 INFO ]: Start difference. First operand 337 states and 684 transitions. Second operand 26 states. Received shutdown request... [2018-06-24 21:30:01,897 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 190 states. [2018-06-24 21:30:01,898 WARN ]: Verification canceled [2018-06-24 21:30:01,900 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-24 21:30:01,901 WARN ]: Timeout [2018-06-24 21:30:01,901 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.06 09:30:01 BasicIcfg [2018-06-24 21:30:01,901 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-24 21:30:01,902 INFO ]: Toolchain (without parser) took 60741.68 ms. Allocated memory was 307.2 MB in the beginning and 1.2 GB in the end (delta: 893.9 MB). Free memory was 256.6 MB in the beginning and 1.0 GB in the end (delta: -780.7 MB). Peak memory consumption was 113.2 MB. Max. memory is 3.6 GB. [2018-06-24 21:30:01,902 INFO ]: SmtParser took 0.05 ms. Allocated memory is still 307.2 MB. Free memory is still 272.7 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-24 21:30:01,903 INFO ]: ChcToBoogie took 83.16 ms. Allocated memory is still 307.2 MB. Free memory was 255.6 MB in the beginning and 253.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-24 21:30:01,903 INFO ]: Boogie Preprocessor took 51.08 ms. Allocated memory is still 307.2 MB. Free memory was 253.7 MB in the beginning and 251.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-24 21:30:01,904 INFO ]: RCFGBuilder took 548.07 ms. Allocated memory is still 307.2 MB. Free memory was 251.7 MB in the beginning and 230.6 MB in the end (delta: 21.0 MB). Peak memory consumption was 21.0 MB. Max. memory is 3.6 GB. [2018-06-24 21:30:01,905 INFO ]: BlockEncodingV2 took 563.48 ms. Allocated memory is still 307.2 MB. Free memory was 230.6 MB in the beginning and 212.6 MB in the end (delta: 18.0 MB). Peak memory consumption was 18.0 MB. Max. memory is 3.6 GB. [2018-06-24 21:30:01,906 INFO ]: TraceAbstraction took 59487.61 ms. Allocated memory was 307.2 MB in the beginning and 1.2 GB in the end (delta: 893.9 MB). Free memory was 212.6 MB in the beginning and 1.0 GB in the end (delta: -824.8 MB). Peak memory consumption was 69.1 MB. Max. memory is 3.6 GB. [2018-06-24 21:30:01,908 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.plugins.blockencoding: - StatisticsResult: Initial Icfg 47 locations, 75 edges - StatisticsResult: Encoded RCFG 32 locations, 62 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.05 ms. Allocated memory is still 307.2 MB. Free memory is still 272.7 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 83.16 ms. Allocated memory is still 307.2 MB. Free memory was 255.6 MB in the beginning and 253.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 51.08 ms. Allocated memory is still 307.2 MB. Free memory was 253.7 MB in the beginning and 251.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 548.07 ms. Allocated memory is still 307.2 MB. Free memory was 251.7 MB in the beginning and 230.6 MB in the end (delta: 21.0 MB). Peak memory consumption was 21.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 563.48 ms. Allocated memory is still 307.2 MB. Free memory was 230.6 MB in the beginning and 212.6 MB in the end (delta: 18.0 MB). Peak memory consumption was 18.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 59487.61 ms. Allocated memory was 307.2 MB in the beginning and 1.2 GB in the end (delta: 893.9 MB). Free memory was 212.6 MB in the beginning and 1.0 GB in the end (delta: -824.8 MB). Peak memory consumption was 69.1 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds Cancelled while BasicCegarLoop was constructing difference of abstraction (337states) and interpolant automaton (currently 190 states, 26 states before enhancement), while ReachableStatesComputation was computing reachable states (1887 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 32 locations, 1 error locations. TIMEOUT Result, 59.4s OverallTime, 19 OverallIterations, 32 TraceHistogramMax, 50.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 2684 SDtfs, 1543 SDslu, 12534 SDs, 0 SdLazy, 59917 SolverSat, 6301 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 35.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1568 GetRequests, 941 SyntacticMatches, 0 SemanticMatches, 627 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26488 ImplicationChecksByTransitivity, 12.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=337occurred in iteration=18, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.7s AutomataMinimizationTime, 18 MinimizatonAttempts, 2145 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 1.2s SatisfiabilityAnalysisTime, 5.7s InterpolantComputationTime, 1785 NumberOfCodeBlocks, 1653 NumberOfCodeBlocksAsserted, 55 NumberOfCheckSat, 1753 ConstructedInterpolants, 0 QuantifiedInterpolants, 273819 SizeOfPredicates, 77 NumberOfNonLiveVariables, 7277 ConjunctsInSsa, 150 ConjunctsInUnsatCore, 32 InterpolantComputations, 13 PerfectInterpolantSequences, 10199/11132 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/McCarthy9103.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-24_21-30-01-924.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/McCarthy9103.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-24_21-30-01-924.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/McCarthy9103.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-24_21-30-01-924.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/McCarthy9103.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-24_21-30-01-924.csv Completed graceful shutdown